数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学什么是 LR 解析器？
LR 解析器是一种自底向上解析器，用于解析上下文无关文法。LR 解析通常被称为 LR(K) 解析，其中
- L 代表从左到右扫描输入
- R 代表最右推导
- K 是用于制定解析决策的向前查看的输入符号数。
LR 解析器是一种移进-规约解析器，它利用确定性有限自动机，通过从底部到顶部读取栈来识别所有可行的前缀。
它决定哪个句柄（如果有的话）是可行的。右句型的一个可行前缀是指包含句柄但句柄右边没有符号的前缀。
因此，如果构建了一个识别右句型可行前缀的有限状态机，它可以用来指导移进规约解析器中的句柄选择。
因为 LR 解析器使用 DFA 来识别可行前缀以管理句柄的选择，所以它必须跟踪 DFA 的状态。因此，LR 解析器栈包含两种类型的符号——状态符号可以识别 DFA 的状态，而语法符号则表示文法符号。
解析器从 DFA 的初始状态 I0 开始，位于栈顶。解析器通过考虑下一个输入符号 'a' 和栈顶的状态符号 Ii 来工作。
如果在 DFA 中存在从状态 Ii 到 'a' 的转移到状态 Ij，则符号 a 后跟状态符号 Ij 推入栈中。
如果在 DFA 中不存在从 Ii 到 a 的转移，并且栈顶的状态 Ii 标识一个可行前缀，该前缀包含句柄 A → a，则解析器通过弹出 α 并将 A 推入栈来进行规约。
这类似于在 DFA 中从 Ii 到 α 进行反向转移，然后在 A 上进行正向转移。解析器的每个移进操作都对应于 DFA 中对终端符号的转移。
因此，DFA 的当前状态和下一个输入符号决定了解析器是移进下一个输入符号还是进行规约。
如果可以生成一个表，将每个状态和输入符号对映射为“移进”、“规约”、“接受”或“错误”之一，则可以得到一个用于管理解析阶段的表。这样的表被称为解析“动作”表。
更新于：2021年11月1日
2K+ 次浏览
广告