尽可能少地使用括号，漂亮打印表达式？

Question

我的问题：如何以最简洁的方式漂亮地打印表达式而不带有冗余的括号？

---

我有以下lambda表达式的表示：

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))

I would like to have

λ x.(λ y.x) y

- aioobe

---

我知道的唯一参考文献是Norman Ramsey的《使用前缀和后缀运算符反解析表达式》。如果你了解一些标准ML，应该可以适应第4节中的代码。http://www.cs.tufts.edu/~nr/pubs/unparse-abstract.html - stephen tetley

这种语言是不受特定编程语言限制的，还是你在寻找Scala的答案？无论哪种情况，你可能想要标记这个问题以获得更广泛的受众。 - neontapir

Answer 1

在这里，我将使用一个简单的语法来表示中缀表达式，其结合性和优先级由以下语法定义，其中运算符按优先级升序列出。

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;
    }
  }

- wcochran

Answer 2

你只需检查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
}

- Robert

---

这种方法不是很通用，因为它可能需要思考二次数量的情况。使用优先级水平需要更少的代码。 - Blaisorblade