编译器设计中LR解析器的组成部分是什么？

LR解析器是一种自下而上的解析器，用于解析上下文无关文法。LR解析也称为LR(K)解析。LR解析器是一种移进-规约解析器，它利用确定性有限自动机，通过从下往上读取栈来识别所有适用的前缀。

它决定是否存在可用的句柄。右句型的可行前缀是指包含句柄但不包含句柄右侧任何符号的前缀。因此，如果构造了一个识别右句型可行前缀的有限状态机，则可以使用它来指导移进-规约解析器中的句柄选择。

LR解析器栈包含两种类型的符号——状态符号可以识别DFA的状态和语法符号。解析器从DFA的初始状态I₀开始，位于栈顶。解析器通过考虑下一个输入符号'a'和栈顶的状态符号I_i来运行。

LR解析器有以下几个组成部分。

• 输入缓冲区——它包含要解析的字符串，后跟$，这是一个用作字符串右端标记的符号，表示字符串的结尾。
• 栈——它用于存储语法符号和状态。

         s₀X₁s₁X₂……………………X_ms_m$

       其中X₁, X₂……………….X_m是语法符号

       而s₀, s₁, s₂………………..s_m是状态

• 分析表：分析表分为两个部分——
  • 动作：动作可以是移进、规约、接受和错误。
  • goto：它以状态和语法符号为参数，并产生一个状态示例，goto(s, X)。
• 分析程序：这是一个驱动程序，执行以下功能
  • 它维护初始配置(s₀,w$)，其中s₀是起始状态，w是字符串。
  • 它支持以下配置

  • s₀X₁s₁X₂ … … X_mS_m, a_i, a_i+1 … … a_n$
         栈           输入字符串(w)

  • 它确定S_m（当前位于栈顶的状态）和a_i（当前输入符号）。
  • 它根据分析表中的条目action[S_m,a_i]采取动作。
• 动作——解析器采取的动作有以下几种类型：
• 移进——如果Action[S_m, a_i] = shift s，则将a_i与状态s一起移入栈中，即配置变为。

• 规约——如果Action[S_m, a_i] = reduce A → β，则解析器执行规约，即配置变为。

              这里

                 s = goto[s_m−r, A]

                 r = β的长度

弹出符号的数量 = 2r（r个状态符号 + r个语法符号）

• 接受——如果Action[s_m, a_i] = accept，则解析完成。
• 错误——如果Action[s_m, a_i] = error，则解析器调用错误校正函数。

Ginni

更新于：2021年11月3日

958 次浏览

启动您的职业生涯

完成课程获得认证

开始学习