基于C++设计的WHILE循环语句的翻译程序（编译原理课设）【100013043】

# 课程设计报告 | 课程名称 | 编译原理课程设计 | | -------- | ----------------------------------------------------- | | 题 目 | WHILE 循环语句的翻译程序设计（LL（1）法、输出四元式） | | 学 院 | 计算机科学与技术 | | 班 级 | 计算机 1701 班 | | 姓 名 | 张超杰 | | 指导教师 | 林老师 | # 课程设计任务书 **题目: WHILE 循环语句的翻译程序设计（LL（1）法、输出四元式）** 初始条件： - 理论：学完编译课程，掌握一种计算机高级语言的使用。 - 实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） - 写出符合给定的语法分析方法的文法及属性文法。 - 完成题目要求的中间代码四元式的描述。 - 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。 - 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 - 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括： - 系统描述（问题域描述）； - 文法及属性文法的描述； - 语法分析方法描述及语法分析表设计； - 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计； - 详细的算法描述（流程图或伪代码）； - 软件的测试方法和测试结果； - 实践总结（本设计的评价、特点、不足、收获与体会等）； # 一、系统描述（问题域描述） ## 1.1 题目描述 WHILE 循环语句的翻译程序设计（LL（1）法、输出四元式） ## 1.2 题目要求 - 写出符合给定的语法分析方法的文法及属性文法 - 完成题目要求的中间代码四元式的描述 - 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计 - 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序 # 二、问题分析及编译系统的概要设计 ​ 编译过程一般分为六个阶段的过程，可以由六个模块完成，它们称为词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序，此外，一个完整编译程序还必须包括“表格管理程序”和“出错处理程序”。 ​ 这次实验采用的方法对文法有一定的要求，要求文法必须是 LL(1)型文法，由于所用的 while 语句文法并不符合这一要求，所以要首先对文法进行修改，消除左递归，时文法符合 LL(1)型文法的要求。同时，这次实验涉及到词法分析、语法分析、语义分析及表格管理和出错管理。其中，词法分析至少要能识别关键字“while”，标识符（即自定义变量），数字，运算符和界符等等；语法分析要分析程序结构的合法性，即是否为文法的句子；语义分析要能够语法制导翻译出中间代码四元式并将其输出；表格管理是指符号表；出错处理是指在语法分析时，所有非文法句子的错误类型处理。 # 三、文法及属性文法的描述 ## 3.1 文法描述 ### 3.1.1 while 语句的初始文法描述 - while 语句： A→w(P){B:} - 赋值语句： B→g=C - 表达式： C→CHD - 项： D→DIE - 因子： E→f | g | (C) - 加法运算符：H→+|- - 乘法运算符：I→*|/ - 比较运算符：J→< | > | >= | <= - 关系表达式：P→CJC - 无符号整数：f - 标识符： g ### 3.1.2 改进为 LL(1)文法之后的文法描述 - while 语句： A→w(P){B:} - 赋值语句： B→g=C - 表达式： C→DM - M→HDM | - 项： D→EN - N→IEN | - 因子： E→f | g | (C) - 加法运算符：H→+|- - 乘法运算符：I→*|/ - 比较运算符：J→< | > | >= | <= - 关系表达式：P→CJC - 无符号整数：f - 标识符： g ### 3.1.3 名词说明 以上文法中使用 w 代替 while 关键字，M 和 N 分别是为了消除左递归引入的符号，无具体对应含义 ## 3.2 属性文法 ### 3.2.1 属性文法定义形式 ​ 属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或者非终结符）配备若干相关的“值”（与文法符号相关的属性）。 ​ 在一个属性文法中，对应于每个产生式 A→a 都有一套与之相关联的语义规则，每规则的形式为：b:=f(c1,c2,…，ck)其中 f 是一个函数，而且或者 b 是 A 的一个综合属性并且 c1,c2,…，ck 是产生式右边文法符号的属性；或者非终结符既可有综合属性也可有继属性，文法开始符号的所有继承属性作为属性计算前的初始值。 ### 3.2.2 while 语句的属性文法 ```c++ while语句： A→w {X1 = gotostm} (P) { X2 = gotostm }{ B; } { backpatch(Ptruelist, M2gotostm); backpatch(Pfalselist, tacIndex-1); gen(‘J’,,, X1); gen(,,,tacIndex); } 赋值语句： B→g=C{B.val=C.val; gen(‘=’,C.val, ,g.val);} 表达式： C→D{M.i=D.val}M{C.val=M.s} M→HD{ M1.i=newtemp; gen(H.val,M.i,D.val, M1.i);} M1{M.s= M1.s} M→ℇ{ M.s= M.i} 项： D→E{N.i=E.val}N{D.val=N.s} N→IE{ N1.i=newtemp; gen(I.val,N.i,D.val, N1.i);} N1{N.s= N1.s} N→ℇ{N.s= N.i} 因子： E→f{ E.val= f.val} E→g{ E.val= g.val} E→(C) { E.val= C.val} 加法运算符：H→+|-{H.val=+ | H.val=-;} 乘法运算符：I→*|/{I.val=+ | I.val=-;} 比较运算符：J→< | > | >= | <={J.val = > | J.val =< |J.val = <= | J.val = >=;} 关系表达式：P→C1JC2{P.val=newtemp; gen(J.val, C1.val,C2.val,P.val);} 无符号整数：f 标识符： g ``` ### 3.2.3 名词说明 ​ 上述属性文法中 gen(op,par1, par2,result)生成四元式，newtemp 产生一个未使用过的名字，val 表示符号的值，f 和 g 的值由输入时直接确定，tacIndex 为生成四元式的标号。X1 和 X2 是为了后续拉链回填添加的符号，无具体对应含义，backpatch(p,i)为拉链回填，将链表 P 中的每个元素指向 i。 # 四、语法分析方法描述及语法分析表设计 ## 4.1 语法分析方法描述 预测分析法是一种表驱动的方法，它由下推栈，预测分析表和控制程序组成。实际上是一种下推自动机的实现模型。预测分析法的关键为预测分析表的构建，即根据文法中各非终结符 FIRST 集和 FOLLOW 集求得 SELECT 集。预测分析法从开始符号开始，根据当前句型的最左边的非终结符和分析串中的当前符号，查预测分析表确定下一步推导所要选择的产生式，最终得到输入串的最左推导，完成输入串的语法检查。 ## 4.2 语法分析表设计 利用上文中提到的方法根据消除左递归后的文法求解 FIRST 集、FOLLOW 集和 SELECT 集，根据 SELECT 集填写预测分析表，结果如表 1-1 所示，其中未填写部分表示分析错误。 表 1-1 | | w | f | g | ( | ) | { | } | ; | + | - | * | / | > | < | >= | <= | # | | - | -------- | --- | --- | --- | - | - | - | - | --- | --- | --- | --- | - | - | -- | -- | - | | A | w(P){B;} | | | | | | | | | | | | | | | | | | B | | | g=C | | | | | | | | | | | | | | | | C | | DM | DM | DM | | | | | | | | | | | | | | | M | | | | | | | | | HDM | HDM | | | | | | | | | D | | EN | EN | EN | | | | | | | |