Zre

原本是一个正则引擎，用dot可视化状态机，后来增加了很多新东西 可用于检查编译原理作业正确性

基础说明

1. 下文中凡是涉及到图, 均为使用graphviz生成的gv或svg格式, 可以在src/tools/visualize.py中将他们转化为html文件方便查看. 其中visualize.py是从操作系统：设计与实现 (2022 春季学期) 中某个工具简化而来, 我只保留了 svg图片转html的功能.
2. 图形化界面都打包在发行版中, 解压缩即可使用.
3. 没有为正则引擎建立图形化界面, 写的太糟了, 只能实现小部分正则语法.
4. 语法处理函数有时候要自行加入栈底符号#, 需要注意. 并且尽量只使用#当作栈底. 有的地方是硬编码
5. 该项目起初在Ubuntu系统上开发, 没有中文输入法, 所有英文注释均为此时所写.
6. 所有需要自定义保存路径的代码都在main函数中.
7. ANSI Escape Code在终端上显示颜色的效果非常好, 我很喜欢.
8. 本文档所有符号都是英文符号, 是为了便于使用markdown语法.
9. 虽然下文并没有提及, 但我是实现了较好的错误处理机制的, 核心代码在src/tools/zlog.py中
10. 测试文件放在input文件夹中.
11. 整个项目测试的很少, 有待进一步测试

正则引擎

/src/core/NFA.py /src/core/DFA.py /src/core/zre.py /src/core/graph.py 三个文件包含了该项目最初写的简单的正则引擎 ，graph.py封装了抽象的图，在此基础上依次封装NFA和DFA在各自文件中，最终在zre.py中实现了汤普森算法和子集构造法，实现从正则语句到NFA到DFA的转化。并生成svg格式的图，我提供了visualize.py将svg图片放到还算好看的html界面中。该算法的实现有很大问题，只能解决很小部分的正则表达式，例如(a|b*)可以生成如下的图.

BNF读取器

/src/BNF.py 包含了将原始BNF语法识别为Token流的抽象 (又是一个小的词法分析 ! )，算是封装的很成功的模块，在后面的所有算法中都用到了，能够读取bnf文件，支持的语法如下

1. 单层的|，不支持括号嵌套
2. 每个Token之间用空格分隔，不支持尖括号指定Token，所以不需要加字符串来指定非终结符
3. 认定::=符号前面的都是非终结符，其他都是终结符，所以不限制非终结符一定要大写
4. 支持单行使用#注释，不支持行内注释
5. 将ε字符视为epsilon，其他均不可

一些符合这个语法的BNF文件示例放在input/下，对于简单的例子，学习编译原理而言是足够使用的

LL(1)分析器

该分析器拥有GUI界面

/src/core/Up_Down.py自顶向下分析算法中的LL(1)识别器，可以依次生成First首符集 Follow随符集 预测分析表，并在此基础上实现递归下降分析，识别一个句子是否符合输入的BNF语法，例如经典的表达式文法input/calc.txt (已经手动消除左递归处理的BNF)

可以成功识别a+a*a这样的句子

算符优先分析器

该分析器拥有GUI界面

/src/core/Operator_First.py 算符优先文法识别器，可以依次生成Firstvt Lastvt算符优先表并可视化，并识别句子，还是以经典的表达式文法为例

并且在识别句子时可以显示整个规约过程, 例如识别i*(i+i)'

算符优先是最小巧我最满意的, 缺点是能识别文法太少了, 这也是算法本身的问题.

SLR(1)分析器

该分析器拥有GUI界面

/src/core/SLR.py实现SLR(1)分析器，是截止当前最复杂的，并且在我的封装下更加复杂了， 首先将产生式分解成带有活前缀的项目，据此生成识别活前缀的DFA，再根据DFA生成action_goto表格，再根据该表格实现SLR(1)分析。整个过程中，生成DFA的过程相比于正则引擎需要汤普森算法需要递归，这里只需要循环迭代即可生成，然而还是在理解上遇到困难，并且现在还是存在一些小问题，例如在生成新的DFA节点时，在某些情况（我也没发现到底是什么情况）下无法合并到已经存在的DFA节点上。接下来以下述BNF语法为例, 该语法不仅是SLR(1)文法, 同时也是LR(0)文法, 事实上本分析器也是支持表达式文法的.

E ::= a A | b B
A ::= c A | d
B ::= c B | d

生成DFA如下. (还记得基础说明中的第一点吗)

生成action_goto表格如下

在分析时可以显示全部的分析过程，例如对于字符串bcd，有如下的分析过程

LR(1)

由于本人开始写LR(0)时还不懂LR(1)算法, 没有为前看符号预留位置, 导致现在要把SLR扩展为LR(1)出现了灾难性的困难 --- 几乎要全部重写. 不想写了

HW

本来这种编译底层的东西做成界面毫无意义, 但是为了学校实验结果看起来炫酷一点, 还是为每个分析器增加了GUI界面, 存放在src/HW目录下. **并且所有可执行文件我都会打包在发行版中. **

其中src/HW/core/zlex.py是为了完成作业单独写的一个词法分析器核心, 对应的界面在src/HW/gui/zlex_gui.py下. 使用方法如下:

• 输入一个lex文件, 详细可见input/HW/lex0.txt, 这个文件是我调试过的, 使用引号表示匹配相同的字符串, 使用正则表达式匹配数字, 标识符等, 使用冒号分隔Token名和正则文法. 几乎就和Antlr需要的格式一模一样.
• 读取到lex文件后, 再将源文件喂给程序, 程序就会吐出Token流了.

/HW/gui/zll1_gui.py是LL(1) 算符优先 SLR(1)三个分析器的前端界面.

大逆不道的将其称为Compiler, 实际上只实现了一些语法分析而已. 然而如果以一种广义的角度来说, 这其实也是一种Compiler, 读取lex文件BNF文件, 正则引擎解析, 这些都是一个个小小的编译器. 正是由于这些小小的编译器, 最终才有可能创造出大大的编译器.

总结

• 我找不到高效的方法回归测试
• 写着写着自己都忘记前面写的什么了
• 生成器太顺手了
• 没有使用qt的资源管理特性, 只把图标等全部存放在同一个位置, 导致项目结构管理会出现一些麻烦的问题.