LR解析如何选择符合条件的语法产品(从叶子构建解析树)？

Question

我正在阅读LR解析教程。本教程在这里使用了一个示例语法：

S -> aABe
A -> Abc | b
B -> d

然后，为了说明解析算法是如何工作的，本教程展示了下面解析单词"abbcde“的过程。

​

​

我了解到，在算法的每一步，都会搜索一个限定结果(即表第2列所示的语法规则)，以匹配字符串的一个片段。但是LR解析如何在一组符合条件的产品中进行选择(如表中的第3列所示)？

Answer 1

字符串的LR解析反向跟踪最右边的派生。从这个意义上说，如果您总是通过展开最右边的非终端，然后向后运行该过程来派生字符串，那么所应用的缩减的顺序就是您所得到的。(在你的例子中试试这个--这不是很好吗？)

LR解析器实际使用的具体机制包括使用一个解析自动机来跟踪语法生成中解析的位置，以及一些前瞻性信息。LR解析器有几种不同的样式(LR(0)、SLR(1)、LALR(1)、LR(1)等)，它们在自动机是如何构造和如何使用前瞻性信息方面有所不同。您可能会发现搜索关于这些自动机如何工作的教程很有帮助，因为这是LR解析器实际工作的核心。