12

我正在为 JavaScript AST 实现一个漂亮的打印机，我想问一下是否有人知道一种“适当的”算法，可以根据 operator priority 和associativity自动为带有最小括号的表达式加括号。我在谷歌上没有找到任何有用的材料。

显而易见的是，应将其父级具有更高优先级的运算符括起来，例如：

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

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

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

我想知道后一种情况的最佳规则是什么。对于除法和减法来说是否足够，如果 rhs 子表达式的优先级小于或等于优先级，则应该用括号括起来。

4

3 回答 3

9

我偶然发现了你的问题，我自己也在寻找答案。虽然我还没有找到一个规范的算法，但我发现，就像你说的那样，单独的运算符优先级不足以最小化括号表达式。我尝试在 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 ++)and之类的表达式(++ a) ++中，其中一个运算符必须比另一个运算符绑定得更紧密，否则++ a ++会产生歧义。但我怀疑即使其中一个不需要括号，为了便于阅读，您可能还是想添加括号。

于 2013-05-22T07:31:57.807 回答
3

这取决于特定语法的规则。我认为您对具有不同优先级的运算符以及减法和除法都正确。

然而，求幂通常被不同地处理，因为它的右手操作数首先被评估。所以你需要

 (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 的左子树。

于 2012-12-13T04:21:23.100 回答
0

有一种通用的方法可以用最少的括号来漂亮地打印表达式。首先为您的表达语言定义一个明确的语法，该语法编码优先级和关联性规则。例如，假设我的语言具有三个二元运算符（*、+、@）和一个一元运算符（~），那么我的语法可能看起来像

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

...

该算法当然可以以不那么明确的方式实现，但是该方法可以用来指导实现而不至于发疯:)。

于 2017-02-15T13:23:03.523 回答