使用最小括号的漂亮打印AST

Question

我正在为一个JavaScript AST实现一个漂亮的打印机,我想问一下是否有人知道一个"正确的"算法,根据运算符优先级和关联性自动用最小括号括起表达式.我没有在谷歌上找到任何有用的材料.

显而易见的是,父级具有更高优先级的运算符应该用括号括起来,例如:

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

但是,也有一些运算符不是关联的,在这种情况下仍需要括号,例如:

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

我想知道后一种情况的最佳规则是什么.对于除法和减法,是否足以说明,如果rhs子表达式的优先级小于或等于,则应将其括起来.

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 ++是不明确的.但我怀疑即使其中一个不需要括号,为了便于阅读,你可能还想添加括号.

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 的左子树括起来。