在定义语法时,说一个语法来评估算术表达式:我们将表达式划分为项和因子,如下所示:
E ::= E + T
T ::= T * F
F ::= num
| (E)
然后我们需要解决左递归问题。
那么为什么不这样定义语法:
E ::= T + E
T ::= F * T
F := num
| (E)
并且只有正确的递归。
最佳答案
问题是它弄错了结合性——左递归文法是左结合的,而右递归文法是右结合的。由于关联性对于 +
或 *
无关紧要,因此您看不到问题,但是如果您添加运算符(例如 -
)对于哪个关联性很重要,您就会看到问题所在。
请注意,在 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
关于grammar - LL(1) 预测解析——避免左递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16694823/