LR解析算法

LR解析算法的主要步骤包括：

1. 构建LR(1)项集族：

   • 计算闭包（closure）
   • 计算转移（goto）
   • 生成所有可能的项集

2. 构建解析表：

   • ACTION表：决定移进、归约、接受或报错
   • GOTO表：记录状态转移

3. 解析过程：

   • 初始化状态栈和符号栈
   • 根据当前状态和输入符号查找ACTION表
   • 执行移进或归约操作
   • 更新状态栈和符号栈
   • 重复直到接受或报错

4. 错误处理：

   • 检测语法错误，尤其是可以定位错误
   • 提供错误恢复机制
   • 生成有意义的错误信息

句柄（Handle）的概念

在LR解析中，句柄是指一个产生式的右部，它出现在栈顶并且可以被归约。具体来说：

1. 定义：

   • 句柄是某个产生式右部的一个子串
   • 该子串与产生式右部完全匹配
   • 该子串出现在栈顶
   • 可以通过归约操作将其替换为产生式左部的非终结符

2. 句柄的特征：

   • 总是出现在栈顶
   • 是当前输入串的最左可归约子串
   • 是语法分析过程中需要归约的最小单位

3. 句柄的识别：

   • 通过解析表的状态转移和归约动作来识别
   • 当解析器处于某个状态时，如果ACTION表指示可以进行归约操作，则栈顶的相应符号序列就是句柄

4. 句柄的重要性：

   • 是LR解析算法正确性的关键
   • 决定了何时进行归约操作
   • 保证了语法分析的正确顺序

详细计算步骤

首先来几个要用的函数计算

1. 计算closure的步骤：

   • 对于每个项[A → α•Bβ, a]，其中B是非终结符
   • 对于B的每个产生式B → γ
   • 对于FIRST(βa)中的每个终结符b
   • 添加项[B → •γ, b]到closure集合
   • 重复直到没有新项可以添加

2. 计算goto的步骤：

   • 对于给定项集I和符号X
   • 创建新项集J = {}
   • 对于I中的每个项[A → α•Xβ, a]
   • 添加项[A → αX•β, a]到J
   • 返回closure(J)

3. 构建ACTION表的步骤：

   • 对于每个项集Ii
   • 对于每个项[A → α•aβ, b]，其中a是终结符
     • 如果goto(Ii, a) = Ij
     • 设置ACTION[i, a] = "移进 j"
   • 对于每个项[A → α•, a]
     • 设置ACTION[i, a] = "归约 A → α"
   • 对于包含[S' → S•, eof]的项集
     • 设置ACTION[i, eof] = "接受"

4. 构建GOTO表的步骤：

   • 对于每个项集Ii
   • 对于每个非终结符A
   • 如果goto(Ii, A) = Ij
   • 设置GOTO[i, A] = j

5. 解析过程的步骤：

   • 初始化：
     • 输入符号栈 = eof
     • 状态栈 = {0}
     • 输入符号 = 第一个输入符号
   • 循环直到接受或报错：
     • 如果ACTION[top(state stack), input symbol] = "移进 j"
       • 将input symbol压入输入符号栈

示例：构建括号列表文法的LR(1)解析表

给定文法：

1. Goal → List
2. List → List Pair
3. List → Pair
4. Pair → ( List )
5. Pair → ( )

构建过程：

1. 计算LR(1)项集族：

   • I0 = closure([S' → •Goal, eof])
   • I1 = goto(I0, Goal)
   • I2 = goto(I0, List)
   • I3 = goto(I0, Pair)
   • I4 = goto(I0, "1")
   • ...（继续计算所有项集） 所有的项集如下:

2. 构建ACTION表和GOTO表：

   构建表的详细计算步骤如上，这里不展开了。

3. 解析过程示例： 输入："( ( ) )" 解析步骤：

   1. 初始化：
      • 输入符号栈 = eof
      • 状态栈 = {0}
      • 输入符号 = 第一个输入符号
   2. 循环直到接受或报错：
      • 如果ACTION[top(state stack), input symbol] = "移进 j"
        • 将input symbol压入输入符号栈
        • 将状态j压入状态栈
        • 读取下一个输入符号
      • 如果ACTION[top(state stack), input symbol] = "归约 A → β"
        • 从栈中弹出|β|个符号
        • 将A压入输入符号栈
        • 将GOTO[top(state stack), A]压入状态栈
      • 如果ACTION[top(state stack), input symbol] = "接受"
        • 解析成功，返回
      • 如果ACTION[top(state stack), input symbol] = 空
        • 报错，返回错误信息
   3. 具体步骤：
      • 移进 '('
      • 移进 '('
      • 移进 ')', 归约 Pair → ( )
      • 移进 ')', 归约 List → Pair
      • 归约 Pair → ( List )
      • 归约 List → List Pair
      • 归约 Goal → List
      • 接受

LR(1)解析器的效率来源于嵌入在Action和Goto表中的快速句柄查找机制。规范集合CC代表了文法的句柄查找有穷状态自动机（DFA）

当LR(1)解析器执行时，它交错进行两种类型的动作：移进（shifts）和规约（reduces）。移进动作模拟了句柄查找DFA中的步骤。随着解析器将输入流中的每个单词移进解析栈，它也根据单词的语法类别改变DFA中的状态。规约动作发生在DFA到达一个终态时。此时，解析器弹出句柄及其DFA状态，以揭示开始寻找当前句柄之前DFA的状态。该状态位于栈中句柄左端之下。

更新日志

2025/1/12 02:51

查看所有更新日志

• 578c3-更新自底向上和LR(1)语法于 2025/1/12