什么是LR解析器?
LRParser是一类用于解析上下文无关语法的自底向上解析器。LR解析被称为LR(K)解析,其中
L代表从左到右扫描输入
R代表最右推导
K是用于制定解析决策的前瞻输入符号的数量。
LR解析器是一个移位归约解析器,它创建了确定性有限自动机的使用,通过从下到上读取堆栈来识别所有适用前缀的集合。
它决定什么句柄(如果有的话)是可行的。右句形式的可实现前缀是包含句柄的前缀,但句柄右侧没有符号。
因此,如果组装了识别正确句子形式的可行前缀的有限状态机,则可以使用它来影响shiftreduce解析器中的句柄选择。
因为LR解析器创建了一个DFA的使用来识别可行的前缀来管理句柄的选择,所以它应该保持对DFA状态的跟踪。因此,LR解析器堆栈包括两种符号——状态符号可以识别DFA和语法符号的状态。
解析器以DFA的初始状态开始,即堆栈上的I0。解析器通过考虑堆栈顶部的下一个输入符号“a”和状态符号Ii进行操作。
如果存在从DFA中“a”上的状态Ii到状态Ij的转换,则符号a之后是状态符号Ij到堆栈上。
如果在DFA中没有从Ii到a的转换,并且如果堆栈顶部的状态Ii在列出时识别出一个包含句柄A→a的可行前缀,则解析器通过弹出来给出减少α并将A压入堆栈。
这类似于在DFA中开发从Ii到α的后向转换,然后在A上开发前向转换。解析器的每个转换动作都与DFA中终端符号上的转换相关。
因此,DFA和下一个输入符号的当前状态决定了解析器是移动下一个输入符号还是进行归约。
如果它可以生成一个表,将每个状态和输入符号对映射为“shift”、“reduce”、“accept”或“error”,我们将获得一个可用于管理解析阶段的表。这样的表被称为解析“动作”表。