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

Question

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

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

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

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

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

并且只有正确的递归。

Answer 1

问题是它弄错了结合性——左递归文法是左结合的，而右递归文法是右结合的。由于关联性对于 + 或 * 无关紧要，因此您看不到问题，但是如果您添加运算符(例如 -)对于哪个关联性很重要，您就会看到问题所在。

请注意，在 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