漂亮打印AST与最小括号 [英] Pretty Printing AST with Minimal Parentheses

问题描述

我正在为一个JavaScript AST实现一个漂亮的打印机，我想问一个人是否知道一个正确的算法自动括号括号表达式，最小括号基于运算符优先级和关联性。我没有在google上找到任何有用的材料。

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 ，不带括号， c $ 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 /

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屋！