Golang 编译器代码浅析
  • 0. Golang 编译器代码浅析
  • 1. golang 编译器 - 前言
    • 1.1 编译器简介
    • 1.2 Golang 编译器
    • 1.3 Go 语言版本
    • 1.4 项目设置
    • 1.5 约定
    • 1.6 写作目的
  • 2. golang 编译器 - 词法分析
    • 2.1 简介
    • 2.2 代码结构
    • 2.3 处理字符
    • 2.4 扫描Token
    • 2.5 总结
  • 3.a 语法分析理论知识
    • 3A.1 语法分析简介
    • 3A.2 文法
    • 3A.3 语法解析
    • 3A.3.1 自顶向下(Top-Down)
    • 3A.3.2 自顶向下 - 递归下降
    • 3A.3.3 自顶向下 - LL(1)文法
    • 3A.3.4 自底向上(Bottom-Up)
    • 3A.3.5 自底向上 - LR(0)项集及SLR预测表
    • 3A.3.6 自底向上 - LR(1)、LALR
    • 3A.4 语法分析工具
    • 3A.5 总结
  • 3B. golang 编译器 - 语法分析
    • 3B.1 简介
    • 3B.2 代码结构
    • 3B.3 数据结构
    • 3B.4 构造语法树
    • 3B.5 Unit Test及AST可视化
  • 4. Golang 编译器 - 类型检查
    • 4.1 简介
    • 4.2 代码结构
    • 4.3 符号解析
    • 4.4.1 数据结构 - 作用域
    • 4.4.2 数据结构 - Package
    • 4.4.3 数据结构 - Object 对象
    • 4.4.4-1 类型数据结构 - 简介
    • 4.4.4-2 类型接口
    • 4.4.4-3 基础类型
    • 4.4.4-4 内置复合类型
    • 4.4.4-5 Struct 类型
    • 4.4.4-6 Interface 类型
    • 4.4.4-7 Named 类型
    • 4.4.4-8 Tuple 类型
    • 4.4.4-9 Sum 类型
    • 4.4.4-10 Function & Method 类型
    • 4.4.4-11 泛型类型
    • 4.4.4-12 类型的等价规则
    • 4.4.4-13 类型的比较规则
    • 4.4.4-14 总结
    • 4.4.5 类型检查器
    • 4.4.6 总结
    • 4.5.1 类型检查逻辑 - 包加载器
    • 4.5.2 类型检查逻辑 - 初始化
    • 4.5.2-1 全局作用域
    • 4.5.2-2 类型检查器
    • 4.5.3 类型检查逻辑 - 流程分析
    • 4.5.3-1.1 总体流程
    • 4.5.3-1.2 类型检查准备工作
    • 4.5.3-1.3 类型检查核心逻辑
    • 4.5.3-1.3a 总体介绍
    • 4.5.3-1.3b 类型表达式的类型检查
    • 4.5.3-1.3c 求值表达式的类型检查
    • 4.5.3-1.3d 类型兼容性检查
    • 4.5.3-1.3e 处理delayed队列
    • 4.5.3-1.4 构建初始化顺序
    • 4.5.3-1.5 总结
    • 4.5.3-2 特定问题分析
    • 4.5.3-2a 对象循环依赖检查
    • 4.5.3-2b 方法与属性查找
    • 4.5.3-2c Underlying Type
    • 4.6 如何测试
    • 4.7 总结
  • 5. Golang 编译器 - IR Tree
    • 5.1 简介
    • 5.2 代码结构
    • 5.3 数据结构
    • 5.4 处理逻辑
    • 5.5 编译日志
    • 5.6 Unit Test
    • 5.7 总结
  • 6. golang 编译器 - 初始化任务
    • 6.1 简介
    • 6.2 代码结构
    • 6.3 总体逻辑
    • 6.4 赋值语句
    • 6.5 编译日志
    • 6.6 Unit Test
    • 6.7 总结
  • 7. golang 编译器 - 清除无效代码
    • 7.1 简介
    • 7.2 处理逻辑
    • 7.3 Unit Test
  • 8. golang 编译器 - Inline
    • 8.1 简介
    • 8.2 Inline的问题
    • 8.3 代码结构
    • 8.4 处理逻辑
    • 8.4.1 遍历调用链
    • 8.4.2 内联判断
    • 8.4.3 内联操作
    • 8.4.4 编译日志
    • 8.4.5 Unit Test
    • 8.4.6 总结
  • 9. golang 编译器 - 逃逸分析
    • 9.1 什么是逃逸分析
    • 9.2 Go 的逃逸分析
    • 9.3 算法思路
    • 9.4 代码结构
    • 9.5 处理逻辑
    • 9.5.1总体逻辑
    • 9.5.2 数据结构
    • 9.5.3 构建数据流有向图
    • 9.5.4 逃逸分析
    • 9.6 编译日志
    • 9.7 Unit Test
    • 9.8 总结
  • 10. golang 编译器 - 函数编译及导出
    • 10.1 简介
    • 10.2 编译函数
    • 10.2.1 SSA
    • 10.2.2 ABI
    • 10.2.3 并发控制
    • 10.3 导出对象文件
    • 10.4 总结
  • 11. Golang 编译器 - 写在最后
由 GitBook 提供支持
在本页
  • 3.3.6.1 LR(1)项集定义
  • 3.3.6.2 规范LR(1)语法分析表
  • 3.3.6.3 LALR语法分析表

这有帮助吗?

  1. 3.a 语法分析理论知识

3A.3.6 自底向上 - LR(1)、LALR

3.3.6.1 LR(1)项集定义

有的文法构建出来的 LR(0) 项集可能会存在移入、规约冲突,例如:

S -> L = R | R L -> * R | id R -> L

我们为该文法的增广文法构建两个项集闭包:

I0: S’ -> ·S S -> ·L = R S -> ·R L -> ·*R L -> ·id R -> ·L

I1: S -> L· = R R -> L·

可见在 I1 中,我们既可以通过项 R -> L· 进行规约,也可以根据项 S -> L· = R 进行移入操作。想要解决这种冲突,解析器就必须读取更多的上下文信息来辅助自己做决策:即向前查看(Look ahead)符号。如果输入的下一个符号是 =, 那么就继续移入,否则就进行规约。

为了让 Look ahead 的符号能够与项集中的项进行匹配,我们必须让项保存更多信息,也就是说我们必须让项更加“精细化”,Look ahead 将要查看多少个符号,就必须向项里面引入等量的额外分量,来形成新的映射关系。我们在这里仅讨论 LR(1), 所以还需要往项里面引入一个变量,用来表示终结符号。修改之后,之前的项 A -> α·β 变成了 [A -> α·β, a], 终结符号 a 表示该项合法的后继符号,即 Look ahead 符号为 a 时,该项才可能是一个可以应用的项。该类项称为 LR(1) 项,其集合称为 LR(1) 项集。

进一步思考可以发现在项 [A -> α·β, a] 中,如果 β 不为空,则符号 a 其实没有作用,因为此时只可能进行移入操作;只有对于形如 [A -> α·, a] 的项,如果下一个输入符号是 a 时,才能进行规约。由此可见引入 Look ahead 符号其实本质上是在协助判断是否可以进行规约,例如上面例子中,我们需要通过下一个符号来判断是否可以通过 R -> L· 进行规约。

3.3.6.2 规范LR(1)语法分析表

为了正确地构建文法的 LR(1) 项集族,我们需要先对用到的两个算法稍作修改:

  • Closure(I), 使用下述三重循环为项集 I 构建闭包项集:

    for (I 中每个项 [A -> α·Bβ, a]) for (文法中的每个产生式 B -> γ) for (First(βa) 中的每个终结符号 b) 将 [B -> ·γ, b] 加入到 I 中

    重复该循环直到没有新的项加入到 I 中为止

  • Goto(I, X) 所表示的项集闭包的构建算法如下:

    1. 初始化集合 K

    2. 对于 I 中每个项 [A -> α·Xβ, a], 将 [A -> αX·β, a] 加入到集合 K

    3. Closure(K) 即为 Goto(I, X) 的项集闭包

有了 Closure 与 Goto 算法,我们就可以为文法构建 LR(1) 项集族了:

  1. 给定文法 G, 创建其增广文法 G’, 令 C 为 G’ 的项集族,初始化为空集

  2. 令 I0 = {[S’ -> ·S, $]},将 Closure(I0) 加入 C 中

  3. 对于 C 中的每个项集 I, 对于 G’ 中的每个文法符号 X, 如果 GOTO(I, X) 不在 C 中,则将其加入其中

  4. 循环第 3 步,直到没有新的项集加入到 C 中为止

对比 LR(0) 的项集族算法,其实只有 I0 不一样。现在我们可以为给定文法 G 构造其 LR(1) 的语法分析表了,其算法如下:

  1. 求出增广文法 G’ 的项集族 C = {I0, I1, I2, … ,In},i 代表 Ii 所对应的状态

  2. 对于任意项集 Ii, 执行如下操作构造 Action 部分:

    1. 如果 [A -> α·aβ, b] 在 Ii 中,并且 Goto(Ii, a) = Ij, 则将 Action[i, a] 的动作设置为移入

    2. 如果 [A -> α·, a] 在 Ii 中,则将 Action[i, a] 的动作设置为规约

    3. 如果 [S’ -> S·, $] 在 Ii 中,则将 Action[i, $] 设置为“接受”

    如果上述步骤产生了冲突,则该文法就不是 LR(1) 文法,我们无法为其构建一个 LR(1) 分析表

  3. 对于任意项集 Ii, 执行如下操作构造 Goto 部分: 对于所有的非终结符号 A, 如果 GOTO(Ii, A) = Ij, 那么将 Goto[i, A] 设置为“状态转换到 j”

  4. 将语法分析表中第 2 步与第 3 步没有设置的条目设置为报错

通过该算法得到的语法分析表成为规范 LR(1) 语法分析表。整个算法的思路与 LR(0) 语法分析表的思想是一样的,区别在于为了匹配 Look ahead 符号,在项中引入了额外的分量使项集更加精细化,从而导致产生了更多的项集,这也正是使用 Look ahead 的目的:通过更多的上下文信息将 LR(0) 中有冲突的项集划分开来。

3.3.6.3 LALR语法分析表

规范LR(1) 语法分析表已经将如何利用 Look ahead 符号来辅助解析过程的思路表达得很充分了,但额外增加的状态数量导致了对空间的需求量显著增加,为了使其具备实践价值,我们必须想办法减少状态数量。

我们在构建规范LR(1) 语法分析表时,每一个状态都是有用的,所以我们不可能直接扔掉一些状态来减少分析表的状态数量,那么剩下的策略就只能是合并:在不产生冲突的情况下,将多个状态合并为一个。

如何确定可以合并哪些状态呢?

我们知道对于同一个文法,LR(1) 项集比 LR(0) 项集多的原因是前者引入了额外的分量:Look ahead 符号。再回顾一下 LR(1) 项的形式:[A -> α·β, a], 其中第一个分量是 LR(0) 项:A -> α·β,第二个分量是 LA 符号:a. 我们将 LR(1) 项集中仅由第一个分量组成的集合叫着 LR(1) 项集的核心(Core)。容易得出:任何一个 LR(1) 项集的核心,都有一个 LR(0) 项集与之对应。根据鸽巢原理:必定存在多个 LR(1) 项集的核心,与同一个 LR(0) 项集对应。

为什么 LR(1) 项集核心必定与一个 LR(0) 对应呢?

我们知道 LR(0) 项集所代表的意义是:当前情况下,所有可能的合法产生式集合,以及每个产生式当前所处的位置!这个意义不会因为我们向前查看了输入符号而发生改变,也就是说,在自底向上解析的过程中,在任意时刻,解析器当前状态所对应的那个项集,不管 LR(k) 中的 k 是多少,其项集核心都是一样的;LR(1) 多出来的项集是 LR(0) 项集中各个项与 Look ahead 符号组合形成的新状态,所以将 Look ahead 符号剔除之后,其必定与一个 LR(0) 项集对应。

唯一合理的假设是我们将核心相同的 LR(1) 项集合并成一个状态,但要注意一个问题是:合并之后的状态不能存在冲突。由此可以得到如下合并思路:对于任意 n 个核心相同的 LR(1) 项集,只要他们的移入、规约操作没有冲突,那么就可以将他们合并为一个 LR(1) 项集。通过该方式构建的语法分析表叫着 LALR 语法分析表,由于 LALR 分析表即利用了 LA 技术,又显著减少了状态数量,所以具备很好的实践价值。

上一页3A.3.5 自底向上 - LR(0)项集及SLR预测表下一页3A.4 语法分析工具

最后更新于3年前

这有帮助吗?