什么是编译器设计中的 LR 解析器组件？

  • Z时代
  • 2024-01-10
  • 分类：综合

LR Parser 是一种自底向上的 Parser，用于解析上下文无关语法。LR Parsing 称为 LR (K) 解析。LR 解析器是一个移位归约解析器，它创建了确定性有限自动机的使用，通过从下到上读取堆栈来识别所有适用前缀的集合。

它决定了可用的句柄（如果有的话）。右序列形式的可行前缀是包含句柄但句柄右侧没有符号的前缀。因此，如果构造了一个识别右句形式的可行前缀的有限状态机，它就被用来指导移位归约解析器中的句柄选择。

LR 解析器堆栈包括两种符号——状态符号可以识别 DFA 的状态和语法符号。解析器从 DFA 的初始状态开始，即堆栈上的I 0 。解析器通过考虑堆栈顶部的下一个输入符号“a”和状态符号 I i来操作。

LR Parser 有各种组件，如下所示。

  • 输入缓冲区- 它包括要解析的字符串，后跟 $，这是一个用作右结束标记的符号，表示字符串的结尾。

  • Stack - 用于存储语法符号和状态。

         s 0 X 1 s 1 X 2 ……………………X m s m $

       其中 X 1 , X 2 ……………….X m是语法符号

       和 s 0 , s 1 , s 2 ………………..s m是状态

  • 解析表：解析表分为两部分 -

    • 行动：行动可以是转变、减少、接受和错误。

    • goto：它将状态和语法符号作为参数并生成状态示例 goto (s, X)。

  • 解析程序：它是一个执行以下功能的驱动程序：

    • 它维护初始配置 (s 0 ,w$)，其中 s 0是开始状态，w 是一个字符串。

    • 它支持以下配置

    • s 0 X 1 s 1 X 2 … … X m S m , a i , a i+1 … … a n $
           堆栈          输入字符串 (w)

    • 它确定 S m当前在堆栈顶部的状态和 ai 当前输入符号。

    • 它根据解析表中的条目动作 [S m , ai ] 采取动作。

  • 动作- 解析器采取的动作有以下类型 -

  • Shift - 如果 Action [S m , a i ] = shift s 然后将状态为 s 的 a i移到堆栈上，即配置变为。

  • Reduce - 如果 Action [S m , a i ] = reduce A → β，则 Parser 执行归约，即配置变为。

              这里

                 s = goto[s m−r , A]

                 r = β的长度

弹出的符号数 = 2r (r 状态符号 + r 语法符号)

  • Accept - 如果 Action [s m , a i ] =accept，则解析完成。

  • Error - 如果 Action [s m , a i ] = error，Parser 调用纠错函数。

以上是 什么是编译器设计中的 LR 解析器组件？ 的全部内容， 来源链接： utcz.com/z/363411.html

回到顶部