Sample语言语法、语义分析及中间代码生成
简介
由于编译原理课程需要完成两个实验，一个是词法分析，一个是语法、语义分析及中间代码生成（生成四元式），做完后在这留个记录，说不定有人会用到。
PS：可能程序的考虑并不完美，仅供参考和交流
Sample语言定义
如下图为sample语言的定义
语法分析要求
实验二：设计SAMPLE语言的语法、语义分析器，输出四元式的中间结果。
检查要求：
a) 启动程序后，先输出作者姓名、班级、学号（可用汉语、英语或拼音）。
b) 请求输入测试程序名，键入程序名后自动开始编译。
c) 输出四元式中间代码（样式见样板输出3和4）。
d) 能发现程序的语法错误并输出出错信息。
思路
自顶向下的递归下降法(LL1)
名词解释
LL1：第一个L代表从左向右扫描输入符号串，第二个L代表产生最左推导，1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。
Token：在我的程序中是用的自定义类Unit实现的，生成Unit的方法在前一篇文章Sample语言词法分析的代码中有提及。
State：一个状态保存类，用于每个函数的返回值，其中包含真假链信息
步骤与注意事项
- 首先要将原来的产生式规则消除左递归和左公因子(LL1文法必要条件，本文并未证明此过程后的语言就属于LL1文法)
- 程序一个Token一个Token的读入，每读入一个Token后进行判断，然后匹配不同的产生式
- 针对赋值表达式，需要产生中间变量保存暂时的结果
- 针对布尔表达式需要注意代码链回填的问题
- 控制语句if、while、repeat要注意有无条件跳转语句的生成
以下是对应的产生式声明
布尔表达式的例子
PS：先实现赋值表达式，再实现布尔表达式会比较容易，这里只是拿布尔表达式做例子
- 布尔表达式 = 布尔项 | 布尔项 or 布尔项 （后面这第二个产生式只有匹配到or才会进行，所以没有提取左公因子）
- 布尔项 = 布因子 | 布因子 and 布因子
- 布因子 = 算术表达式 二元比较符 算术表达式 | true | false | 标识符 二元比较符 标识符 | 标识符 |（布尔表达式）| not 布因子
由于布因子函数体较长，故没有截图，详情可以查看源代码。
这里需要注意的几点有：
- 真假链的保存，布尔表达式中，or和and以及not三种情况下对真假链的影响要想清楚
- or的上一项的假链跳转or的下一项入口，而or的所有真链跳转代码入口
- and的假链直接跳转代码出口，and的上一个真链跳转下一个布尔项的入口
- 遇到not的时候，需要将后面影响范围内的真假链互换（这个与赋值表达式中的负号类似）
其他语句注意事项
- 对于复制表达式负号的处理
- 对于控制语句中跳转语句的生成
- 各种语句中括号的影响
四元式生成
代码中采用vector< vector
实际上这是用了比较偷懒的方式来存储四元式，不过能够实现对应所需要的功能，这里的代码可以重构。
对应的四元式推入代码为pushTac()，对应四元式列表的变量为tacList。
错误的判断
当在某个产生式下，遇到了错误的Token，应该要保存相应的错误信息并停止分析（当然也可以不停止分析，不过后续处理较为复杂），然后输出相应的错误提示给用户。
自顶向下的预测分析表法
这是另一种方法，通过事先计算好表（First集合、Follow集合然后Select集合），再遇到一个符号时就使用对应产生式规则，但是我没使用这种方法，所以具体实现步骤就不太确定，如果有兴趣可以尝试实现一下。
代码
代码已经打包至GitHub仓库，请移步。
PS：代码是包含了两个实验的全部代码
GitHub地址
小结
语法、语义分析和中间代码生成比词法分析稍难一些，需要花费些时间去理解其中的一些处理和执行过程，最重要还是去编码，遇到了bug再解决，就会对其中的流程比较印象深刻了（特别是真假链回填那里，需要多测试测试复杂的例子）