Sample语言语法、语义分析及中间代码生成


简介

由于编译原理课程需要完成两个实验,一个是词法分析,一个是语法、语义分析及中间代码生成(生成四元式),做完后在这留个记录,说不定有人会用到。
PS:可能程序的考虑并不完美,仅供参考和交流

Sample语言定义

如下图为sample语言的定义


语法分析要求

实验二:设计SAMPLE语言的语法、语义分析器,输出四元式的中间结果。
检查要求:
a) 启动程序后,先输出作者姓名、班级、学号(可用汉语、英语或拼音)。
b) 请求输入测试程序名,键入程序名后自动开始编译。
c) 输出四元式中间代码(样式见样板输出3和4)。
d) 能发现程序的语法错误并输出出错信息。

思路

自顶向下的递归下降法(LL1)

名词解释

LL1:第一个L代表从左向右扫描输入符号串,第二个L代表产生最左推导,1代表在分析过程中执行每一步推导都要向前查看一个输入符号——当前正在处理的输入符号。
Token:在我的程序中是用的自定义类Unit实现的,生成Unit的方法在前一篇文章Sample语言词法分析的代码中有提及。
State:一个状态保存类,用于每个函数的返回值,其中包含真假链信息

步骤与注意事项
  1. 首先要将原来的产生式规则消除左递归和左公因子(LL1文法必要条件,本文并未证明此过程后的语言就属于LL1文法)
  2. 程序一个Token一个Token的读入,每读入一个Token后进行判断,然后匹配不同的产生式
  3. 针对赋值表达式,需要产生中间变量保存暂时的结果
  4. 针对布尔表达式需要注意代码链回填的问题
  5. 控制语句if、while、repeat要注意有无条件跳转语句的生成

以下是对应的产生式声明

布尔表达式的例子

PS:先实现赋值表达式,再实现布尔表达式会比较容易,这里只是拿布尔表达式做例子

  1. 布尔表达式 = 布尔项 | 布尔项 or 布尔项 (后面这第二个产生式只有匹配到or才会进行,所以没有提取左公因子)
  2. 布尔项 = 布因子 | 布因子 and 布因子
  3. 布因子 = 算术表达式 二元比较符 算术表达式 | true | false | 标识符 二元比较符 标识符 | 标识符 |(布尔表达式)| not 布因子

由于布因子函数体较长,故没有截图,详情可以查看源代码。
这里需要注意的几点有:

  1. 真假链的保存,布尔表达式中,or和and以及not三种情况下对真假链的影响要想清楚
  2. or的上一项的假链跳转or的下一项入口,而or的所有真链跳转代码入口
  3. and的假链直接跳转代码出口,and的上一个真链跳转下一个布尔项的入口
  4. 遇到not的时候,需要将后面影响范围内的真假链互换(这个与赋值表达式中的负号类似)
其他语句注意事项
  1. 对于复制表达式负号的处理
  2. 对于控制语句中跳转语句的生成
  3. 各种语句中括号的影响
四元式生成

代码中采用vector< vector>的数据格式来存储四元式,即二维Unit数组,不过第二维的长度是4罢了。
实际上这是用了比较偷懒的方式来存储四元式,不过能够实现对应所需要的功能,这里的代码可以重构。
对应的四元式推入代码为pushTac(),对应四元式列表的变量为tacList。

错误的判断

当在某个产生式下,遇到了错误的Token,应该要保存相应的错误信息并停止分析(当然也可以不停止分析,不过后续处理较为复杂),然后输出相应的错误提示给用户。

自顶向下的预测分析表法

这是另一种方法,通过事先计算好表(First集合、Follow集合然后Select集合),再遇到一个符号时就使用对应产生式规则,但是我没使用这种方法,所以具体实现步骤就不太确定,如果有兴趣可以尝试实现一下。

代码

代码已经打包至GitHub仓库,请移步。
PS:代码是包含了两个实验的全部代码
GitHub地址

小结

语法、语义分析和中间代码生成比词法分析稍难一些,需要花费些时间去理解其中的一些处理和执行过程,最重要还是去编码,遇到了bug再解决,就会对其中的流程比较印象深刻了(特别是真假链回填那里,需要多测试测试复杂的例子