使用最少的括号对AST进行漂亮打印

Question

我正在实现一个JavaScript AST的漂亮打印器，并想问一下是否有人知道一种“合适”的算法，可以根据运算符优先级和结合性自动添加最少的括号来加强表达式。我在谷歌上没有找到任何有用的资料。

显而易见的是，父级具有更高优先级的运算符应该被加上括号，例如：

(x + y) * z // x + y has lower precedence

然而，还有一些运算符是不可结合的，这种情况下仍需要使用括号，例如：

x - (y - z) // both operators have the same precedence

我想知道这种情况下最好的规则是什么。无论是除法还是减法，如果右侧子表达式具有小于或等于优先级，则应该加括号。

- Maxime C.

Answer 1

我在寻找答案时偶然发现了您的问题。虽然我没有找到一个标准的算法，但我发现像您所说的那样，仅仅使用运算符优先级是不足以使表达式最小化地加括号的。我尝试用Haskell编写了一个JavaScript漂亮打印程序，但我发现编写一个健壮的解析器很烦人，所以我改变了具体的语法：https://gist.github.com/kputnam/5625856 除了优先级外，您还必须考虑运算符的结合性。像/和-这样的二元操作被解析为左结合。然而，赋值=、指数^和相等性==是右结合的。这意味着表达式Div (Div a b) c可以写成a / b / c而不需要括号，但表达式Exp (Exp a b) c必须加括号写成(a ^ b) ^ c。

您的直觉是正确的：对于左结合的运算符，如果左操作数的表达式比其父级的表达式绑定得更松散，那么它应该加括号。如果右操作数的表达式与其父级的表达式绑定得一样紧或更松散，则应该加括号。因此，Div (Div a b) (Div c d)不需要在左子表达式周围加括号，但右子表达式需要： a / b / (c / d)。

接下来，一元运算符，特别是既可以是二元也可以是一元的运算符，如否定和减法-、强制类型转换和加法+等可能需要逐个处理。例如，Sub a (Neg b)应该打印为a - (-b)，即使一元否定比减法绑定更紧。我猜这取决于您的解析器，a - -b可能不会有歧义，只是难看。

我不确定既可以作为前缀又可以作为后缀的一元运算符应该如何工作。在像++ (a ++)和(++ a) ++这样的表达式中，一个操作符必须比另一个操作符绑定得更紧，否则++ a ++将是模棱两可的。但我怀疑即使在其中一个表达式中不需要括号，出于可读性的考虑，您可能仍然想要添加括号。

- kputnam

Answer 2

这取决于特定语法的规则。对于具有不同优先级的操作符，以及减法和除法，您的理解是正确的。

然而，幂运算通常被视为不同的情况，其右侧操作数首先进行评估。因此，您需要

 (a ** b) ** c

当c是根节点的右子节点时。

括号化的方式取决于语法规则的定义。如果您的语法形式为

exp = sub1exp ;
exp = sub1exp op exp ;
sub1exp = sub1exp ;  
sub1exp = sub1exp op1 sub2exp ;
sub2exp = sub3exp ;
sub2exp = sub3exp op2 sub2exp ;
sub3exp = ....
subNexp = '(' exp ')' ;

如果op1和op2是非结合的，那么如果子树的根也是op1，你需要为op1的右子树加括号，如果左子树的根是op2，则需要为op2的左子树加括号。

- Ira Baxter

Answer 3

有一种通用的方法可以使用最少的括号来美化表达式。首先，定义一个明确的语法，用于编码优先级和结合规则。例如，假设我有一种语言，其中包含三个二元运算符（*，+，@）和一个一元运算符（~），那么我的语法可能如下所示：

E -> E0

E0 -> E1 '+' E0       (+ right associative, lowest precedence)
E0 -> E1

E1 -> E1 '*' E2       (* left associative; @ non-associative; same precedence)
E1 -> E2 '@' E2
E1 -> E2

E2 -> '~' E2          (~ binds the tightest)
E2 -> E3

E3 -> Num             (atomic expressions are numbers and parenthesized expressions)
E3 -> '(' E0 ')'

语法分析树包含所有必要（和不必要）的括号，无法构造一个分析树，使其展开结果成为一个模棱两可的表达式。例如，对于字符串没有分析树

1 @ 2 @ 3

因为 '@' 是非结合的，总是需要括号。另一方面，字符串

1 @ (2 @ 3)

具有解析树

E(E0(E1( E2(E3(Num(1)))
         '@'
         E2(E3( '('
                E0(E1(E2(E3(Num(2)))
                      '@'
                      E2(E3(Num(3)))))
                ')')))

问题因此被简化为将抽象语法树强制转换为解析树的问题。通过尽可能避免将AST节点强制转换为原子表达式，可以获得最小数量的括号。这很容易以系统化的方式实现：

维护一对指针，其中包括AST中当前节点的指针和正在扩展的当前产生式。使用根AST节点和“E”产生式初始化该对。对于AST节点的可能形式的每种情况，尽可能扩展语法以编码AST节点。这将为每个AST子树留下一个未扩展的语法产生式。在每个（子树，产生式）对上递归地应用该方法。

例如，如果AST是（*（+ 1 2）3），则按以下方式进行：

expand[ (* (+ 1 2) 3); E ]  -->  E( E0( E1( expand[(+ 1 2) ; E1]
                                            '*'
                                            expand[3 ; E2] ) ) )

expand[ (+ 1 2) ; E1 ] --> E1(E2(E3( '('
                                     E0( expand[ 1 ; E1 ]
                                         '+'
                                         expand[ 2 ; E0 ] )
                                     ')' )))

...

当然，算法可以以更不明显的方式实现，但是该方法可用于指导实现而不会让人发疯 :)

- Ulrik Rasmussen