用最少的括号漂亮地打印 AST [英] Pretty Printing AST with Minimal Parentheses

问题描述

我正在为 JavaScript AST 实现一个漂亮的打印机，我想问一下是否有人知道一种正确的"算法，可以根据运算符优先级和 关联性.我在谷歌上没有找到任何有用的材料.

I'm implementing a pretty-printer for a JavaScript AST and I wanted to ask if someone is aware of a "proper" algorithm to automatically parenthesize expressions with minimal parentheses based on operator precedence and associativity. I haven't found any useful material on the google.

似乎很明显的是，父级具有更高优先级的运算符应该用括号括起来，例如:

What seems obvious is that an operator whose parent has a higher precedence should be parenthesized, e.g.:

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

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

However, there are also some operators which are not associative, in which case parentheses are still are needed, e.g.:

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

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

I'm wondering what would be the best rule for this latter case. Whether it's sufficient to say that for division and subtraction, the rhs sub-expression should be parenthesized if it has less than or equal precedence.

推荐答案

我偶然发现了你的问题，我自己也在寻找答案.虽然我还没有找到规范的算法，但我发现，就像你说的那样，单独的运算符优先级不足以最小化括号表达式.我尝试在 Haskell 中编写一个 JavaScript 漂亮的打印机，虽然我发现编写一个强大的解析器很乏味，所以我改变了具体的语法:https://gist.github.com/kputnam/5625856

I stumbled on your question in search of the answer myself. While I haven't found a canonical algorithm, I have found that, like you say, operator precedence alone is not enough to minimally parenthesize expressions. I took a shot at writing a JavaScript pretty printer in Haskell, though I found it tedious to write a robust parser so I changed the concrete syntax: https://gist.github.com/kputnam/5625856

除了优先级之外，您还必须考虑运算符结合性.像 / 和 - 这样的二元运算被解析为左关联.但是，赋值=、求幂^ 和相等== 是右结合的.这意味着表达式Div (Div ab) c 可以不带括号写成a/b/c，但是Exp (Exp ab) c 必须括号内为(a ^ b) ^ c.

In addition to precedence, you must take operator associativity into account. Binary operations like / and - are parsed as left associative. However, assignment =, exponentiation ^, and equality == are right associative. This means the expression Div (Div a b) c can be written a / b / c without parentheses, but Exp (Exp a b) c must be parenthesized as (a ^ b) ^ c.

您的直觉是正确的:对于左结合运算符，如果左操作数的表达式与比其父级的结合不紧密，则应该将其放在括号中.如果右操作数的表达式与它的父级绑定一样紧密 或不那么紧密，那么它应该被加括号.所以Div (Div ab) (Div cd) 不需要左子表达式周围的括号，但右子表达式需要:a/b/(c/d).

Your intuition is correct: for left-associative operators, if the left operand's expression binds less tightly than its parent, it should be parenthesized. If the right operand's expression binds as tightly or less tightly than its parent, it should be parenthesized. So Div (Div a b) (Div c d) wouldn't require parentheses around the left subexpression, but the right subexpression would: a / b / (c / d).

接下来，可能需要处理一元运算符，特别是可以是二元或一元的运算符，例如否定和减法 -、强制和加法 + 等个案基础.例如 Sub a (Neg b) 应该打印为 a - (-b)，即使一元否定比减法绑定更紧密.我想这取决于你的解析器，a - -b 可能没有歧义，只是丑陋.

Next, unary operators, specifically operators which can either be binary or unary, like negation and subtraction -, coercion and addition +, etc might need to be handled on a case-by-case basis. For example Sub a (Neg b) should be printed as a - (-b), even though unary negation binds more tightly than subtraction. I guess it depends on your parser, a - -b may not be ambiguous, just ugly.

我不确定可以作为前缀和后缀的一元运算符应该如何工作.在像 ++ (a ++) 和 (++ a) ++ 这样的表达式中，运算符之一必须比另一个运算符绑定得更紧密，或者 ++ a ++ 将是模棱两可的.但我怀疑即使其中一个不需要括号，但为了可读性，您可能还是想添加括号.

I'm not sure how unary operators which can be both prefix and postfix should work. In expressions like ++ (a ++) and (++ a) ++, one of the operators must bind more tightly than the other, or ++ a ++ would be ambiguous. But I suspect even if parentheses aren't needed in one of those, for the sake of readability, you may want to add parentheses anyway.

这篇关于用最少的括号漂亮地打印 AST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！