parsing - 手动解析左递归文法的最简单方法是什么？

Question

我正在为一个宠物项目编写解析器，出于教育目的，我想手动完成而不是使用解析器生成器。不幸的是，许多在线资源(以及我在大学上的编译器类(class))都采用某种 LL(k) 语法。我不想保留语法因素，因为左递归非终结符，例如

E ::= E * E
    | E / E
    | E + E
    | E - E
    | ...

这在类似野牛的解析器生成器中是可能的，这似乎大大简化了语法。

手动解析这种语法的最简单方法是什么？到目前为止，我的研究告诉我递归下降不是一种选择，原因是 explained here ，并且使用递归上升的 LR 解析可能是一个不错的选择，尽管有几个站点停下来表示它不直观。

Answer 1

如果你想为一种玩具语言构建一个主要递归下降解析器，其唯一的左递归是或多或少的标准表达式语法，那么你应该考虑使用 Pratt 解析器( Java )( Javascript )。或者(等效地，事实证明)，您可以使用 operator precedence parser ;该算法在 Dragon 书中得到了很好的描述，并且有很多使用 shunting yard algorithm 的可用示例。 (但要注意；许多热情地发现该算法并立即将其写在博客上的人远非可靠的权威。)

松散解析的注意事项:

如果您想解析表达式语法，并且不关心运算符优先级(例如，如果您只需要对代码进行语法着色)，则可以轻松重构表达式语法以避免左递归。

起点是这个，使用 *对于 Kleene 星，?可选，和 ( )分组:

expression: term (INFIX term)*
term: PREFIX* operand postfix*
operand: ID
       | CONSTANT 
       | '(' expression ')'
       ;
postfix: POSTFIX
       | '[' expression ']'
       | '(' ( expression (',' expression)* )? ')' 
       ;

递归下降解析器可以轻松处理 *和 ?上面的运算符，并且没有左递归，所以应该足够了。

请注意，C 具有强制转换表达式的笨拙之处，除非您知道第一个带括号的表达式包含类型而不是表达式，否则在语法上无法将其与函数调用区分开来。但是，出于松散解析的目的，可以使用上述语法将它们解析为函数调用。

C++ 使用尖括号作为运算符和模板参数更难处理。我见过的许多语法着色器完全忽略了模板参数大小写；让它们正确是一个挑战，但可能是值得的。

编辑评论:

如果你愿意，可以忽略这一点，但我个人认为学习使用自下而上的 LR 解析器，尤其是 GLR 解析器，比试图将一种语言硬塞进一种受限的解析算法中更丰富的教育经验，尤其是那些细节语法的一部分被隐藏为代码路径。但话虽如此，同时做一个野牛和手工生成的解析器可能是有值(value)的，如果只是为了看看野牛解析器可以更加优雅和简单。