algorithm - 将优先表转换为适合递归下降的语法？

Question

如果我们有一种仅由原子元素和一元和二元运算符组成的语言:

atomic elements: a b c
unary operators: ! ~ + -
binary operators: + - / *

然后我们可以定义一个语法:

ATOM := a | b | c
UNOP := ! | ~ | + | -
BINOP := + | - | / | *
EXPR := ATOM | UNOP EXPR | EXPR BINOP EXPR

然而，这种语法导致了一个模糊的解析树(以及由于左递归导致递归下降解析器中的无限循环)。

所以我们添加一个优先表:

Precendence 1: unary+ unary- ~ ! (Right to Left)
Precendence 2: * / (Left to Right)
Precendence 3: binary+ binary- (Left to Right)

我的问题是我们可以通过什么算法或程序来获取优先级表并为递归下降解析器(不是左递归)生成适当的语法。

优先级表是运算符组和相关方向(L->R 或 R<-L)的有序列表。答案是将其作为输入并生成语法作为输出。

Answer 1

将运算符优先语法转换为 LR(1) 语法 [1] 很容易，但生成的语法将使用左递归来解析左关联运算符。消除左递归很容易——例如，使所有运算符右结合——但是虽然生成的语法识别相同的语言，但解析树是不同的。

事实证明，稍微修改递归下降解析器以处理优先关系并不难。该技术由 Vaughan Pratt 发明，本质上使用调用堆栈来替换经典 shunting-yard algorithm 中的显式堆栈。

普拉特解析似乎正在经历某种复兴，你可以找到很多关于它的博客文章；一个相当好的是 Eli Bendersky 。 Pratt 在 1970 年代初期设计了该程序，大约在同一时间 Frank deRemer 证明 LR(1) 解析是可行的。 Pratt 对形式解析的实用性和不灵活都持怀疑态度。我认为这场辩论从那时起就一直在酝酿之中。 Pratt 解析器确实简单且灵活，但另一方面，很难证明它们是正确的(或者它们解析了特定形式描述的语法)。另一方面，尽管 bison 最近获得了对 GLR 解析的支持，使其使用起来可能会少很多烦躁，尽管事实上 bison 生成的解析器实际上解析了他们声称要解析的语法，但仍有许多人会同意Pratt 的声明(从 1973 年开始)，即正式的解析方法“不易访问且使用起来不太愉快”。

[1] 在实践中，所有的 yacc-derivatives 和许多其他 LR 解析器生成器都将接受优先关系以消除歧义；生成的语法表更小，涉及的单位缩减更少，因此如果您打算使用解析器生成器，没有特别好的理由不使用这种技术。