sora

前言#

词法分析器 tokenzier 的构建步骤就不赘述了，可以参照 repo 里的 tokenizer，也可以自己写一个其他类型的，保证 tokenzier 返回的 token 和 parser 里的 token（这里是Symbol类的实例）能衔接起来即可。

这个项目基于龙书 [1] 实现，Parser 中的相当一部分细节都可以在龙书中找到对应部分，可以作为例子辅助理解龙书。

这个项目使用 Python 语言。为什么？Python 语言的自由度能够使人最大限度地专注于程序逻辑的实现，而非语法的细枝末节，非常适合实践想法，而且可以借助类型注解实现静态检查。后续如果对性能有要求也可以此为蓝本构建 C++ 版本的程序。

最后感谢课程老师出了一个这么难的实验题目，不然还真不会想到去做这么一件事，更不会如痴如醉地投入一个星期左右的精力。

路线#

准备#

开发环境是 Windows 11 + Jetbrains Pycharm + Python 3.9

• 其中用到的较新版本 Python 特性有:
  • Python 3.6 以来内置类型dict的插入变为有序，用来清晰地打印项集族
  • Python 3.7 以来支持的from __future__ import annotations用法，用来类型注解，放宽了类先后定义的顺序，可以把后面定义的类在前面作为类型注解
• 编程习惯：
  • 把常量尽量放在一个统一的文件中，如 constants.py，尽量避免魔法数字和魔法字符串
  • 多使用类型注解，方便理清变量的类型，静态排错
  • 在类中定义debug_mode开关打印调试信息
  • 做单元测试
    • 参考代码中的单测在tester.py
• 如何从外部主程序 main.py 进行调试？
  • 在外部主程序实现一个create_cfg方法，在里面定义和修改上下文无关文法
  • 准备好测试的程序文本，如 test.c
    • 示例 CFG 文法可参考 test.c 中的c_generators
  • 定义好 Tokenizer 实例，读入所有 token
  • 定义好 Parser 实例，打开调试模式，初始化格局
  • 可以用 Tester 实例封装测试过程
  • 观察和分析输出，不断调整实现
    • 为了方便查看，可以重定向输出到文件

对符号、产生式、项、项集等建模#

对符号、产生式、项、项集等的建模位于 grammar.py 文件中。

• 文法符号 -> Symbol类
  • 成员变量
    • sType: token 的类型
      • 按终结符号和非终结符号两类划分
    • name: token 的类型
      • 按数值常量、标识符等划分
      • 如标识符对应的name是constants
    • content: token 的字符串表示
      • 如：int a; 中 a 是标识符类型，属性name为 "constants"，属性content为 "a"
  • 成员函数
    • __str__：转换为字符串表示，方便打印
    • __hash__和__eq__：方便使用集合类型
    • fromStr: 从str类型转换到Symbol类型，需要外部指定终结符号集
  • 空符号怎么表示？
    • 在constants.py中定义常量，用ε表示
    • 定义成Symbol类型或str均可
• 产生式 -> Generator类
  • 成员变量
    • start：产生式左部的非终结符号
    • end: 产生式右部的文法符号串
  • 成员函数
    • __str__：转换为字符串表示，方便打印调试
  • ComposedGenerator是干什么的？
    • 手动定义 CFG 文法时，写字符串比定义Symbol要方便得多，所以用ComposedGenerator做了一层转换
    • 另外，同一个产生式左部可能对应多个产生式右部，如A -> a | b，体现为ComposedGenerator中的成员end类型注解为list[list[str]]，是为 "Composed"
      • 例子：A -> a | b
        • 定义成ComposedGenerator是{start: 'A', end: [['a'], ['b']]}
        • 转换成Generator可得到两个Generator类型的实例
          • {start: 'A', end: ['a']}
          • {start: 'A', end: ['b']}
• LR (1) 项 -> Item类
  • 成员变量
    • start: 产生式左部非终结符号
    • end: 产生式右部文法符号串
    • point: 产生式体内的点，表示读入到的位置
    • lf_symbols: 向前看的符号，LR (1) 只看一个
  • 成员函数
    • __hash__和__eq__：区分实例，方便使用集合类型
    • __str__：转换为字符串表示，方便打印
      • 这里特判了产生式为空的情况
• LR (1) 项集 -> ItemSet 类
  • 成员变量
    • _items：所有的项
  • 成员函数
    • add：将项加入项集，重复的自动忽略
    • union：和其他ItemSet类型合并
    • toList: 转换成列表
      • 方便后续用数字索引 LR 自动机的状态
    • __hash__和__eq__：区分实例，方便使用集合类型
    • __iter__: 返回内部迭代器，用于for遍历
    • __len__: 返回大小
      • 需要继承Sized
  • 为什么要为项集建模？直接用set(Item)不行吗？
    • 很好，一开始我也是这样想的
    • 问题主要出在求 LR (1) 规范项集族的时候
      • 需要判断没有新增的项集时，第一反应是在set(Item)外面再套一层，set(set(Item))
      • 但是set(Item)上没有偏序和等价的默认定义，是一个复合类型
        • "复合类型" 可参考编程原本 [2] 第十二章
      • 所以需要为项集手动定义偏序和等价
    • 加上打印调试等需求，所以需要为项集建模
• 上下文无关文法 (CFG) -> GrammarCFG类
  • start_mark: 开始符号的字面量
  • end_mark: 终结符
    • 一般是栈底的 '$'
  • end_symbols: 终结符号的集合
  • generators: 产生式集合
    • 从中可得出非终结符号的集合

实现求 FIRST 集和 FOLLOW 集#

从这一步开始实现 Parser，对应的参考实现在parser.py，对应的龙书参考页码在代码有详尽的注释。

• 参考代码中相关函数
  • get_first
  • get_chain_first（对文法符号串求 first）
  • get_follow
  • _get_follow_once
  • _get_follow_all
• 参考代码中相关成员变量
  • self._map_follow
  • self._map_first
• 为什么要先从求 first 集和 follow 集开始？
  • 求 first 集和 follow 集是后续算法的基础
  • 而且你已经建模好了语法，只要按照龙书上的流程实现就可以了，只涉及文法符号和产生式
  • 从简单的操作开始不断调试迭代，可以慢慢找到编程的状态
• 应该怎么求？
  • 求 first 集没有什么坑，函数的调用过程是一个树形结构
    • 比如：对于A -> B 和 B -> b
      • 求first(A)调用求first(B)
      • 求first(B)得到{b}
  • 但是求 follow 集，函数的调用过程有环
    • 比如：对于A -> aB 和 B -> bA | b
      • 根据求 follow 集的第三条规则
      • 求 follow (A)，发现 follow (A) 都在 follow (B) 中
      • 求 follow (B)，发现 follow (B) 都在 follow (A) 中
    • 参考实现中的解决方法比较简单粗暴
      • 预先计算所有非终结符号的 follow 集，用dict保存在全局变量self._map_follow
      • 不断扫描所有非终结符号的 follow 集，直到没有新的终结符号加入为止
        • 判断方法比如 union 两个非终结符号的 follow 集，检查len是否有变化等等
    • 可以试着寻找更好的实现

实现求 CLOSURE 和 GOTO#

有了求 first 集和 follow 集的工具，下一步可以从 LR (1) 项涉及到的算法开始着手了。对应的参考实现在parser.py，对应的龙书参考页码在代码有详尽的注释。

• 参考代码中相关函数
  • get_closure
  • get_goto
• 书上没说到的部分？
  • 按照依赖顺序，先实现 closure，后实现 goto
  • closure 集
    • 需要注意去重
    • 一次遍历中另外存储新加入的项，下次只遍历新加入的项
    • 需要注意把新加入的项最后一块加进去，防止迭代器失效
    • 参考代码中我的实现很差劲，现在发现只是碰巧能跑，可能当时喝醉了，建议不要作为参考
  • goto 集是没有什么坑的
    • 后面一个符号是 X，移动点，加进去就可以
    • 最后求 closure 闭包返回

实现求 LR (1) 项集#

从增广文法的第一条产生式求闭包开始，有了 goto，就可以求 LR (1) 项集了。不断求 goto，直到没有新的项集加入为止。对应的参考实现在parser.py，对应的龙书参考页码在代码有详尽的注释。

• 可以采用和求 follow 集类似的方法判断 “没有新的项集加入”
• 参考代码中相关函数
  • get_lr1_items
• 顺利完成这一步后，通过把求 goto 的过程打印出来，把每个项集看作一个状态，你会发现实际上你已经完成了 LR (1) 项集的自动机，到这一步已经成功一半了

实现 LR (1) 的分析表#

• 参考代码中相关函数
  • get_lr
• 需要
  • 建模一个动作，作为填入分析表的内容
    • 成员必须包含
      • 执行的动作类型
      • 执行动作必需的信息
        • 比如：
          • 用哪个产生式规约
          • 下一步到哪个状态
  • 建模一个 LR (1) 分析表，往里面一个一个填
    • 对应LRSheet
    • 一维是状态的下标，一维是符号
  • 规范 LR (1) 项集族，作为所有状态
• 可以像参考代码一样按照规则一条条填动作，也可以合到一块填动作
• 如果填写过程中一个格子填了两遍？
  • 实现有错误
  • 文法不是 LR (1) 文法
• 其他
  • 参考代码中，空产生式的规约是通过出错后向栈顶试着放一个空符号实现的

实现 LR (1) 的格局#

• 建模格局
  • 假设全部输入已知
  • 这里没有严格按照 158 页 [1] 定义
  • 除了栈中的输入和余下的输入，还有栈中的状态下标，方便调试和观察自底向上的处理过程
  • 参考代码中把执行一步动作也放到了格局里，方便打印状态
• 到这一步基本就完成了

加入简单的 SDD 语法制导分析#

这里的 SDD 仅限于 S 属性的 SDD，以递归子程序的方式定义在create_cfg()体内，且仅在 action 为产生式规约操作时触发。可以试试自行修改到在产生式中间、在 action 为移入操作时触发。

• 可以参考以下步骤加入 SDD：
  • 扩展 Symbol 等建模，使其可携带各种语义属性
  • 实现简单的类型声明
  • 实现简单的表达式求值
  • 实现简单的类型检查规则
  • 实现控制流的 SDD
• 注意
  • Python 内部对于对象是浅拷贝，所以在forward执行语义动作前需要进行一层深拷贝，防止覆盖其他Symbol实例的 SDD
• 如何扩展？
  • 约定好递归子程序的格式，比如
    • 参数列表都是(input_symbols: list[grammar.Symbol], reduction_symbol: grammar.Symbol, st: parser.SymbolTable)
    • 定义好属性的名称在constants.py
      • 正好体现了统一定义常量的好处
      • 不需要多次手打字面量，容易打错字母，出意想不到的 bug
  • 每定义一个产生式，绑定一个函数作为递归子程序
  • 在Item类中也加入这个参数
  • 在 Parser 类各种方法创建新的Item实例时把绑定的函数也一块传递进去
  • 在forward执行一步规约动作时执行语义动作
  • 具体可查看参考代码中的 Git 差异

存在的问题#

• 在一开始建模时没有充分考虑Symbol等价的问题
  • 比如: a 和 b 在产生式中都是identifier ，所以对它们进行比较会得到相等的结果
  • 最终采用了只比较在产生式中的表示，不会比较字符串内容
• 为什么有sType和name两个分开？既然都是表示 token 类型，合并起来不好吗？
  • 当初设计这两个分开主要是和接口衔接的问题
  • 词法分析器 tokenizer 部分的类型没有按照终结符号与非终结符号划分，而是细分为五类
  • 最后在外部定义 CFG 文法时又按终结符号和非终结符号划分了一遍，处理的确实不好，应该在 tokenizer 就划分好
• Parser 内部的一些函数是公开的
  • 为了方便单测，但不够 neat
• if-else没有处理好，用了特判悬空 else 处理
  • 其实可以用语法定义解决，详见龙书 134 页
• 没有实现真正的恐慌模式，只是丢弃到需要的 token 出现为止
• 没有考虑实现的效率问题
  • 比如求 follow 集和求 LR (1) 规范项集族时，判断没有新的项或项集加入的操作是非常简单粗暴的
• SDD、三地址码的实现不规范
• constants.py和外部create_cfg耦合度高
• ItemSet没有充分考虑修改后求 hash 的问题
• 求闭包中用来去重的实现不好
  • 比如不用cur_items去重而是用f_list去重
  • f_list把向前看的符号和产生式右部混在一块，有潜在的 bug

参考资料#

• [1] 编译原理 第 2 版（Compilers: Principles, Techniques and Tools, Second Edition），（美）Alfred, V.A. 等著；赵建华等译，—— 北京：机械工业出版社，2009.1
• [2] 编程原本（Elements of Programming），（美）Stepanov, A.，（美）McJones, P. 著；裘宗燕译.—— 北京：机械工业出版社，2011.12