自上而下解析器希望在“Code”中有一个像样的case示例左递归

Question

你好，flow成员上的堆栈。

我正在学习编译器课程。我确实理解自上而下解析器应该避免左递归，并转换为右递归方式。

问题是，

a)我是否理解为右自顶向下解析器等于LL，自下而上解析器等于LR？

b)我发现左递归是一种规则，它自称为ex) Expr :== '+‘Term | Term，它可以导致无限循环找到Expr。但不管怎样，有没有考虑用C或Java输入的示例代码？(我不想要解析器或扫描器代码)我需要的是带有句子形式的案例代码示例，它通过左递归进行无限循环。

c)在自顶向下解析器中使用Right Recursion的方式实际上有什么不同？

答案c)消除了回溯的需要。但还有其他的东西吗？

答案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 -> T B，因为在规则E -> E+T|T中，在完成规则的应用后，T将始终出现在最左边。由于最左侧由E -> T B负责，我们可以自由构造字符串的右侧，就像我们使用B -> +T B所做的那样。我们需要一个λ产生式来为我们的递归提供一个停止点。

-> Ax和A -> xA是等价的语法，只是一个是左的，另一个是右递归的。