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