删除此语法中的间接左递归

Question

我正在尝试弄清楚如何从Ruby解析器(https://github.com/kenaniah/ruby-parser/blob/master/ruby-parser/src/parsers/expression/logical.rs)的Rust端口中的逻辑关键字表达式中删除间接的左递归。语法看起来像这样：

E --> N | A | O | t
N --> n E
A --> E a E
O --> E o E

E = expression
A = keyword_and_expression
O = keyword_or_expression
N = keyword_not_expression

如何进行转换以删除A和O中的递归

Answer 1

我认为这里的问题不是间接递归，而是歧义。

如果只是间接递归，您可以简单地替换N、A和O的右侧，从而消除间接递归：

E → n E
  | E a E
  | E o E
  | t

为了摆脱直接的左递归，你可以使用左因子：

E → n E
  | E A'
  | t
A'→ a E
  | o E

然后删除剩余的左递归：

E → n E E'
  | t E'
E'→ ε
  | A' E'
A'→ a E
  | o E

它没有直接或间接的左递归，并且每个规则都以唯一的终结点开头。但是，它不是LL(1)，因为存在first/follow冲突。

这并不奇怪，因为原始语法是高度歧义的，而且左递归消除不了歧义。只有在伴随operator precedence table的情况下，原始语法才有意义。

该表表明，AND和OR是具有相同优先级的左结合运算符(这是一个稍微不寻常的决定)，而NOT是具有更高优先级的一元运算符。反过来，这意味着BNF应该是这样编写的：

N → n N
  | t
E → A
  | O
  | N
A → E a N
O → E o N
N → n N
  | t

与OP中的语法的唯一区别是消除了歧义，如优先表所示。

同样，第一步是替换非终结符A和O，以使左递归更直接：

E → E a N
  | E o N
  | N
N → n N
  | t

这基本上与算术表达式的语法相同(忽略乘法，因为只有一个优先级)，并且可以直接消除左递归：

E  → N E'
E' → a E
   | o E
   | ε
N  → n N
   | t

Answer 2

根据此factorization tool，生成的语法将为：

E  -> N
    | A
    | O
    | t
N  -> n E
A  -> n E a E A'
    | O a E A'
    | t a E A'
O  -> n E o E O'
    | n E a E A' o E O'
    | t a E A' o E O'
    | t o E O'
A' -> a E A'
    | ϵ
O' -> a E A' o E O'
    | o E O'
    | ϵ

由于E的多个产品，看起来A和O的分解最终变得相当复杂。