grammar - LL(1) 预测解析——避免左递归

Question

当定义一个文法时，说一个文法来评估一个算术表达式：我们将表达式划分为术语和因子，如下所示：

E ::= E + T  
T ::= T * F  
F ::= num  
    | (E)

然后我们需要解决左递归。

那么为什么不这样定义语法：

E ::= T + E  
T ::= F * T  
F := num  
    | (E)

并且只有正确的递归。

score 6 · Accepted Answer

问题是它弄错了关联性——左递归语法是左关联的，而右递归语法是右关联的。由于关联性无关紧要，+或者*您看不到问题，但是如果您添加关联性确实重要的运算符（例如-），您就会看到问题。

请注意，在 LL 语法中处理左递归的方式本质上是转换为右递归，然后对解析树进行后处理以将其转回左递归。分解它，你转换成

E ::= T + E | T

然后你把它留在里面

E ::= T E'
E' ::= \epsilon | + E

这会将表达式解析T + T + T为

  E
 / \
T   E'
   / \
  +   E
     / \
    T   E'
       / \
      +   E
         / \
        T   E'
            |
         \epsilon

然后您通过将其视为您从上到下（从左到右）评估/执行的交替术语和运算符的链接列表来评估它：

tmp1 = eval_term(pop list head)
while (list not empty)
    op = pop list head
    tmp2 = eval_term(pop list head)
    tmp1 = tmp1 op tmp2

score 0 · Accepted Answer

在您展示的特定示例中，顺序无关紧要，因此您可以交换操作数。
但对于所有其他语法来说，情况并非如此，因为移动它们的符号可能会改变它们的含义；所以你需要找到另一种方法来消除左递归。

2 回答 2