自上而下的解析器希望在"代码"中有正确的案例示例左递归

Question

你好伙伴堆栈流量成员.

我正在学习编译器类.我确实理解Top-Down Parser应该避免左递归,并转换为右递归方式.

问题是,

a)我理解正确的自上而下的解析器等于LL而自下而上的解析器等于LR？

b)我发现左递归是规则,自称为ex)Expr:== Expr'+'Term | 可能导致无限循环查找Expr的术语.但无论如何,在C或Java中考虑输入的任何示例代码？(我不想要解析器或扫描器代码)我需要的是具有句子形式的案例代码示例,它通过左递归发生无限循环.

c)在自上而下的解析器中使用右递归的方式实际上有什么不同？

ANS c)无需回溯.还有别的吗？

ANS b)x - 2 * y还有其他什么？因为这个用回溯方式解析.

我已经找到了非左递归和左递归的案例.

左递归语法

A -> Ax

非左递归语法

A -> Bx
B -> Ay

两者都进入无限循环.

谢谢你,感谢所有专家.

Answer 1

a)我理解正确的自上而下的解析器等于LL而自下而上的解析器等于LR？是

自上而下的解析器进入带有左递归的无限循环,因为代码中的产生如下所示:

A() {
  A(); match(x);
}

A永远调用自身,永远不会从输入流中删除任何内容.

左递归不一定是立即的,所以你的"非左递归语法"仍然是递归的:

A -> Bx | z
B -> Ay

如果用生产代替B,你可以看到它是递归的:

A -> Ayx | z

下面是将左递归语法正确转换为右递归语法的示例:左递归:

E -> E + T | T

正确的递归:

E -> T B
B -> + T B | Lambda

E - > TB以来,在规则E - > E + T | 完成规则的应用后,T,T将始终出现在最左侧.由于最左侧由E - > TB处理,我们可以自由地构造我们用B - > + T B做的弦的右侧.我们需要一个lambda生产给我们一个停止点递归.

A - > Ax和A - > xA将是等效的语法,只剩下一个,另一个是右递归.