compiler-construction - pretty-print 歧义语法

Question

我已经实现了解析器组合器，它可以解析可能包含歧义的语法。当语法有歧义时会给出错误，但事实证明，朝另一个方向前进会更加困难。问题是如何用最少的括号将抽象语法树漂亮地打印成可能有歧义的语法。使用运算符优先级有帮助，但不是万灵药。在相同的优先级内，问题仍然存在。

确切的运算符直到运行时才知道，并且可以在用户引入新运算符时在执行期间更改。我支持前缀、后缀和中缀(左、右和非关联)运算符。中缀左运算符和后缀运算符同时在优先级混合。这同样适用于中缀右和前缀运算符。运算符还可以嵌入完整表达式，因此 if-then-else 和 if-then 都可以实现为前缀运算符。 (尽管这可能不是明智之举。)

这是一个使用前面提到的 if-then-else 和 if-then 运算符的例子，这里假设它们处于相同的优先级。显然，表达式 if a then if b then c else d 是不明确的，因为它可以解释为 if a then (if b then c) else d 或 if a then (if b then c else d).在 pretty-print 期间，算法应该知道使用括号，即使两个运算符处于相同的优先级级别并且具有兼容的关联性(向右)。

一个警示示例:添加另一个前缀运算符 say inc，其优先级与 if-then-else 和 if-then 相同。现在假设一个任意集合 P ⊂ H x O，其中 H 是运算符空集的集合，O 是运算符的集合。该集合旨在成为一种关系，告诉您何时需要添加括号。检查表达式 if a then inc b else c 和 if a then (inc if b then c) else d。第一个要求 (if-then-else.2, inc) 不在 P 中，第二个要求相反。这与问题可以通过某种关系或顺序解决的假设相矛盾。可以尝试说让 (inc.1, if-then) 在 P 中使后一个表达式 if a then inc (if b then c) else d，但是 inc if a then b 变成了 inc (if a then b)，它有太多括号。

据我所知，语法是上下文无关的。不过，我对这个定义有点犹豫。

解析器大致基于论文 here .我正在使用 Haskell。

更新:正如 Maya 所证明的，该问题通常无法解决。我愿意接受一个可能会失败的算法。如果这还不足以使事情变得实用，那么好的启发式方法就可以了。

Answer 1

总的来说，这是不可能的。考虑运算符 A_B , _C_ , A_C_B .表达式 A_C_B 1 2 (即 A 1 C 2 B )不可能用括号括起来，因此它不能被解析为 A (1 C 2) B .