parsing - 如何实现左递归消除器？

Question

我该如何为此实施消除器？

 A := AB |
      AC |
      D  |
      E  ;

Answer 1

这是所谓的立即左递归的一个例子，并像这样被删除：

A := DA' |
     EA' ;

A' := ε   |
      BA' |
      CA' ;

基本思想是首先要注意，在解析 an 时，A您必须以 aD或 an开头E。在Dor an之后，E你要么结束（tail 是 ε）要么继续（如果我们在 a ABorAC结构中）。

实际的算法是这样工作的：

对于像这样的任何左递归产生式：A -> A a1 | ... | A ak | b1 | b2 | ... | bm将产生式替换为A -> b1 A' | b2 A' | ... | bm A'并添加产生式A' -> ε | a1 A' | ... | ak A'。

有关消除算法（包括消除间接左递归）的更多信息，请参见Wikipedia: Left Recursion。

Answer 2

另一种可用的形式是：

A := (D | E) (B | C)*

这样做的机制大致相同，但一些解析器可能会更好地处理这种形式。还要考虑将动作规则与语法本身结合起来需要什么；另一种形式需要分解工具为A'规则生成一个新类型，以返回此形式没有的地方。