18

私の質問:冗長な括弧を使用せずに式をきれいに出力する最もクリーンな方法は何ですか?

ラムダ式の次の表現があります。

Term ::= Fun(String x, Term t)
      |  App(Term t1, Term t2)
      |  Var(String x)

慣例によりApp、 は左結合です。つまり、a b cと解釈され(a b) c、関数本体は可能な限り右に伸びます。つまり、λ x. x yと解釈されλ x. (x y)ます。

私は良い仕事をするパーサーを持っていますが、今はきれいなプリンターが欲しいです。これが私が現在持っているものです（疑似scala）：

term match {
    case Fun(v, t) => "(λ %s.%s)".format(v, prettyPrint(t))
    case App(s, t) => "(%s %s)".format(prettyPrint(s), prettyPrint(t))
    case Var(v)    => v
}

上記のプリンターは、常に( )式を配置します (アトミック変数を除く)。したがって、Fun(x, App(Fun(y, x), y))それは生成します

(λ x.((λ y.x) y))

私はを頂きたい

λ x.(λ y.x) y
4

2 に答える 2

5

ここでは、演算子が優先順位の昇順でリストされている次の文法によって定義される結合性と優先順位を持つ中置式に単純な文法を使用します。

E -> E + T | E - T | T     left associative
T -> T * F | T / F | F     left associative
F -> G ^ F | G             right associative
G -> - G | ( E ) | NUM

抽象構文木(AST)が与えられた場合、以下の疑似コードで説明するように、必要な括弧のみを使用して AST を文字列に変換します。ツリーを再帰的に下って、いつ括弧が必要かを判断しながら、相対的な優先順位と結合性を調べます。式を括弧で囲む決定はすべて、親ノードで行う必要があることに注意してください。

toParenString(AST) {
    if (AST.type == NUM)   // simple atomic type (no operator)
        return toString(AST)
    else if (AST.TYPE == UNARY_MINUS)  // prefix unary operator
        if (AST.arg.type != NUM AND 
           precedence(AST.op) > precedence(AST.arg.op))
              return "-(" + toParenString(AST.arg) + ")"
        else 
              return "-" + toParenString(AST.arg)
    else {  // binary operation
        var useLeftParen = 
             AST.leftarg.type != NUM AND
             (precedence(AST.op) > precedence(AST.leftarg.op) OR
              (precedence(AST.op) == precedence(AST.leftarg.op) AND
               isRightAssociative(AST.op)))

        var useRightParen = 
             AST.rightarg.type != NUM AND
             (precedence(AST.op) > precedence(AST.rightarg.op) OR
              (precedence(AST.op) == precedence(AST.rightarg.op) AND
               isLeftAssociative(AST.op)))

        var leftString;
        if (useLeftParen) {
           leftString = "(" + toParenString(AST.leftarg) + ")"
        else
           leftString = toParenString(AST.leftarg)

        var rightString;
        if (useRightParen) {
           rightString = "(" + toParenString(AST.rightarg) + ")"
        else
           rightString = toParenString(AST.rightarg)

        return leftString + AST.op + rightString;
    }
  }
于 2016-03-31T21:00:57.247 に答える
3

App の引数の型を確認するだけでいいのではないですか?

これをscalaで書く方法がわかりません..

term match {
    case Fun(v: String, t: Term) => "λ %s.%s".format(v, prettyPrint(t))
    case App(s: Fun,    t: App)  => "(%s) (%s)".format(prettyPrint(s), prettyPrint(t))
    case App(s: Term,   t: App)  => "%s (%s)".format(prettyPrint(s), prettyPrint(t))
    case App(s: Fun,    t: Term) => "(%s) %s".format(prettyPrint(s), prettyPrint(t))
    case App(s: Term,   t: Term) => "%s %s".format(prettyPrint(s), prettyPrint(t))
    case Var(v: String)          => v
}
于 2012-08-19T15:50:26.513 に答える