编译原理毕业课程设计

1、( 此文档为 word 格式，下载后您可任意编辑修改！)编译原理课程设计课程名称编译原理学生学院计算机学院专业班级计算机科学与技术10（ 8）学生姓名武小亮指导教师杨劲涛2012 年 1月 2日编译原理课程设计报告一、设计要求：基本内容 （成绩范围：“中”、“及格”或“不及格” ）1（ 1）扩充赋值运算：*= 和 =扩充语句（ Pascal 的 FOR 语句） : FOR < 变量 >:=<表达式 > TO < 表达式 > DO < 语句> FOR < 变量 >:=< 表达式 > DOWNTO < 表达式 >

2、DO < 语句 >其中，语句 的循环变量的步长为2，语句 的循环变量的步长为-2。（ 3）增加运算：+ 和 -。选做内容 （成绩评定范围扩大到： “优”和“良”）（ 1）增加类型：字符类型； 实数类型。（ 2）扩充函数：有返回值和返回语句；有参数函数。（ 3）增加一维数组类型（可增加指令） 。（ 4）其他典型语言设施。二、课程设计中完成的内容有：（ 1）扩充赋值运算：*= 和 =(2)扩充语句（ Pascal的 FOR 语句） : FOR < 变量 >:=<表达式 > TO < 表达式 > DO < 语句> FOR < 变量 &

3、gt;:=< 表达式 > DOWNTO < 表达式 > DO < 语句 >其中，语句 的循环变量的步长为2，语句 的循环变量的步长为-2。（ 3）增加运算：+ 和 - 。三、实验环境与工具：（1）计算机及操作系统：PC 机， WindowsXP（ 2）程序设计语言：VC+ 6.0（ 3）教学型编译程序：PL0四、设计方案：1、结构说明 :PL0 语言编译过程采用一趟扫描方式 ,以语法分析程序为核心 ,词法分析程序和代码生成程序都作为一个独立的过程 ,当语法分析需要读单词时就调用词法分析程序 ,而当语法分析正确需生成相应的目标代码时 ,则调用代码生成程序 .此

4、外 ,用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系.用出错处理程序对词法和语法分析研究遇到的错误给出在源程序中出错的位置和错误性质 .当源程序编译正确时,PL0 编译程序自动调用解释执行,并按用户程序要求输入数据和输出运行结果.2、流程图：2编译和解释执行的结构图PL0 编译程序总体流程图3、词法分析词法分析是编译的第一个阶段， 它的主要任务是从左向右逐个字符地对源程序进行扫描，产生一个个单词序列用于语法分析。 PL0 词法分析程序 GETSYM的功能是为语法分析提供单词用的，是语法分析的基础，把输入的字符串形式的源程序分割成一个个单词符号。经过词法分析程序分析出来的单词

5、，对语言固有的单词只给出类别存放在全程变量 SYM中，而对用户定义的单词（标识符或常数）既给出类别又给值，其类别放在 SYM中，值放在全程变量 ID 或全程变量NUM中，全部单词种类由编译程序定义的纯量类型 SYMBOL给出，称为语法词汇表。词法分析器的分析过程：调用 GETSYM时，它通过 GETCH过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把SYM变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字） ，把 SYM置为 IDENT，把这个单词存入I

6、D 变量。查保留字表时使用了二分法查找以提高效率。如果Getch 获得的字符是数字，则继续用Getch 获取数字，并把它们拼成一个整数或实数，然后把SYM 置为INTEGER，并把拼成的数值放入NUM变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等） ，则把 SYM则成相应的类型。如果遇到不合法的字符，把 SYM置成 NUL。词法分析程序 GETSYM将完成下列任务：（1）滤空格（2）识别保留字（3）识别标识符（4）拼数（5）拼复合词（6）输出源程序34、语法分析PL0 编译程序的语法分析采用了自顶向下的递归的子程序法。 语法分析同时也根据程序的语义生成相应三元代码，并提供了

7、出错处理的机制。语法分析主要由分程序分析过程（ BLOCK）、常量定义分析过程（ ConstDeclaration ）、变量定义分析过程（ Vardeclaration ）、语句分析过程（ Statement ）、表达式处理过程（ Expression ）、项处理过程（ Term）、因子处理过程（ Factor ）和条件处理过程（ Condition ）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出错报告过程（ Error ）、代码生成过程（ Gen）、测试单词合法性及出错恢复过程（ Test ）、登录名字表过程（ Enter ）、查询名字表函数（ Position ）以及列出

8、类 PCODE代码过程（ Listcode ）作过语法分析的辅助过程。由 PL0 的语法图可知：一个完整的 PL0 程序是由分程序和句号构成的。因此，本编译程序在运行的时候，通过主程序中调用分程序处理过程block 来分析分程序部分（分程序分析过程中还可能会递归调用 block 过程），然后，判断最后读入的符号是否为句号。如果是句号且分程序分析中未出错，则是一个合法的 PL0 程序，可以运行生成的代码，否则就说明源 PL0 程序是不合法的，输出出错提示即可。45、语义分析PL0 的语义分析主要进行以下检查：（1） 是否存在标识符先引用未声明的情况；5（2） 是否存在己声明的标识符的错误引用；（

9、3） 是否存在一般标识符的多重声明。6、语法错误处理PL0 编译程序对语法错误的处理采用两种办法：（1）对于一些易于校正的错误，如丢了逗号、分号等，指出出错的位置，加以校正，继续进行分析。（2）对于难于校正的错误，给出错误的位置与性质，跳过后面一些单词，直到下一个可以进行正常语法分析的语法单位。7、解释执行这个过程模拟了一台可以运行类 PCODE指令的栈式计算机。解释程序过程中的 base 函数的功能，就是用于沿着静态链，向前查找相差指定层数的局部数据段基址。这在使用 sto 、lod 等访问局部变量的指令中会经常用到。类 PCODE 代码解释执行的部分通过循环和简单的 case 判断不同的指

10、令，做出相应的动作。当遇到主程序中的返回指令时，指令指针会指到 0 位置，把这样一个条件作为终至循环的条件，保证程序运行可以正常的结束。生产目标代码后，程序调用Interpret程序解释执行，程序定义的一个数据区 S，三个寄存器 T 栈顶寄存器， B 基址寄存器和 P 程序地址寄存器用于运行程序。五、各功能模块描述:过程或函数名简要功能说明P10主程序error出错处理getsym词法分析 , 读取一个单词Getch漏掉空格 , 读取一个字符Gen生成目标代码 , 并送入目标程序区Test测试当前单词符号是否合法Block分程序分析处理过程Enter登录名字表Position查找标识符在名字表

11、中的位置Constdeclaration常量定义处理Vardeclaration变量说明处理Listcode列出目标代码清单6Statement语句部分处理Expression表达式处理Term项处理Factor因子处理Condition条件处理Interpret对目标代码的解释执行程序Base( 函数 )通过静态链求出数据区的基地址主要成分描述1、符号表struct ALFA NAME;OBJECTS KIND;union int VAL; *CONSTANT*struct int LEVEL,ADR,SIZE; vp; *VARIABLE,PROCEDUR:*; TABLETXMAX;所有

12、符号都放在全程量一维数组TABLE 表中。 TX 为索引表的指针，表中的每个元素为记录型数据。LEV 给出层次， DX 给出每层局部量当前已分配到的相对位置。且TABLE表的表头索引TX 和层次单元LEV 都以 BLOCK 的参数形式出现。每个过程中的变量的相对初始位置在BLOCK 内置初值DX ： =3。结构形式如下：NAMEKINDVALLEVELADRSIZE在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息, 这些信息集中反映了标识符的语义特征属性. 符号表的主要功能如下:1、收集符号属性2、上下文语义合法性检查的依据3、作为目标代码生成阶段地址分配的依据.2、运行时存储组

13、织和管理由于编译时目标程序运行的数据空间大小已经规定，所以存储组织属于静态存储。源程序的标识符存放在TABLE 表中，目标代码存放在CODE 中， S 是由解释程序定义的一维整型数组，是程序运行时的数据存储空间。解释程序还定义了4 个寄存器：1）P：程序地址寄存器：指向下一条要执行的目标程序的地址（相当目标程序CODE数组的下标）。2） I ：指令寄存器：存放着当前正在解释的下一条目标指令。3）T ：栈顶寄存器：由于每个过程当它被运行时，给它分配的数据空间（下边称数据7段）包括静态部分和动态部分，对于动态部分，要注意的是，栈顶寄存器指出了当前栈中最新分配的单元。4）B：基址寄存器： 指向每个过

14、程被调用时， 在数据区 S 中给它分配的数据段的起始地址，也称基地址。3、语法分析方法自顶向下的语法分析 :<程序 ><分程序>.<变量说明部分 ><语句 >VAR <标识符 >； < 复合语句 >ABEGIN <语句 > END<读语句 >READ（<标识符>）A4、中间代码表示PL0 编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它不依赖任何实际计算机，中间代码生成是由过程GEN 完成， GEN 有 3 个参数，分别代表目标代码的功能码，层差和位

15、移量其指令集极为简单，指令格式也很单纯，其格式如下：FLA例如： gen(opr,0,16); gen(sto,lev-level,adr)lev：当前处理的过程层次level：被引用变量或过程所在层次CX ：为目标代码code 数组的下标指针其中F 为功能号； L 为层次差，也就是变量或过程被引用的分程序与说明该变量的过程之间的层次差； A 的含义对不同指令有所区别，对存取指令表示位移，而对其它指令则分别有不同含义，解析说明如下： LIT ：将常量取到栈顶。L 为常数类型；A 为常数值。 LOD ：将变量放到栈顶。A 为变量在说明层中的相对位置，L 为调用说明层的差值。 STO ：将栈顶的内

16、容送入某变量单元中。A、 L 含义如上。 CAL ：过程调用指令。A 为被调用过程的目标程序入口地址，L 为层差。 INT ：为被调用过程在运行栈中开辟数据区，A 为开辟的单元数。8 JMP ：无条件跳转指令，A 为转向地址。 JPC ：条件跳转指令，当栈顶的值为假时，转向A ，否则顺序执行。 OPR ： opr 的 L 域为 0， A 域的内容决定操作含义，具体说明如下：A=0 过程调用结束后返回调用点，并释放被调用过程在运行栈的数据空间。 A=1 栈顶值取反，结果在栈顶。A=2 次栈顶与栈顶相加，退两个栈元素，结果值进栈。 A=3 次栈顶减去栈顶，退两个栈元素，结果值进栈。 A=4 次栈顶

17、乘以栈顶，退两个栈元素，结果值进栈。 A=5 次栈顶除以栈顶，退两个栈元素，结果值进栈。A=6 对栈顶值做奇偶判断，奇数为真，偶数为假，结果放栈顶。 A=8 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈。 A=9 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈。 A=10 次栈顶是否小于栈顶，退两个栈元素，结果值进栈。 A=11 次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈。A=12 次栈顶是否大于栈顶，退两个栈元素，结果值进栈。A=13 次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈。A= 14栈顶值输出到屏幕。A=15屏幕输出换行。A=16从命令行读入一个输入到栈顶。A 为其他值均

18、为非法指令。六、设计实现：（1）增加赋值运算符 *= 和 =以及 +,-(a)首先给这四个运算符命名， 分别命为 timeseql,slasheql ，和 pps,mms以便读单词时填写符号表。分析 *= 、 =、+、- ，当遇到 +时，根据 TABLE表中的 C 地址把 C 的值放在栈顶，再把栈顶元素和次栈顶元素相加，然后保存 C 的值。 - 的原理与 +相同。（ b）在 PL0 程序中的修改如下：词法分析GetSym 中添加， 语句分析STATEMENT中添加， expression将执行一系列指令，但最终结果将会保存在栈顶，执行sto 命令完成赋值 *1). 词法分析中修改else 下面

19、部分为较书本的版本增加的功能if(ch='+') 读到 +号，判断是否是 +getchdo;if(ch='+')sym=pps; +getchdo;else9sym=plus;单个 +elseif(ch='-')读到 -号，判断是否是 -getchdo;if(ch='-')sym=mms; -getchdo;elsesym=minus;单独 -elseif(ch='*')读到 * 号，判断是否是 *=getchdo;if(ch='=')sym=timeseql; *=getchdo;elsesym=

20、times; 单独 *elseif(ch='')读到号，判断是否是 =getchdo;if(ch='=')10sym=slasheql; =getchdo;elsesym=slash; 单独2) 语句分析STATEMENT中添加else if(sym=slasheql)检测到符号i=position(id,*ptx);把类 x*=3 的 x的地址取出来gendo(lod,lev-tablei.level,tablei.adr);* 找到变量地址并将其值入栈 *getsymdo;if(sym=semicolon)getsymdo;memcpy(nxtlev,fsy

21、s,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev);gendo(opr,0,5);if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);else if(sym=pps)检测到后置 +符号gendo(lit,0,1);gendo(lod,lev-tablei.level,tablei.adr);* 找到变量地址并将其值入栈 *gendo(opr,0,2);执行加操作，if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);getsymdo;11else if(sym

22、=mms)检测到后置 -符号gendo(lod,lev-tablei.level,tablei.adr);* 找到变量地址并将其值入栈 *gendo(lit,0,1);gendo(opr,0,3);执行减操作，if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);getsymdo;elseerror(13);if(i!=0)gendo(sto,lev-tablei.level,tablei.adr);（ 2）扩充语句（ Pascal的 FOR 语句） : FOR <变量 >:=<表达式 > TO < 表达式 > DO

23、<语句> FOR < 变量 >:=< 表达式 > DOWNTO < 表达式 > DO < 语句 >（a）增加保留字 FOR、TO、DOWNTO、DO到相应的位置，用于词法分析的识别(b) 其跳转图为12)在 statement 中添加，类似 else 的方式，主要是处理好如何出入栈的问题，代码中有详细的注释。elseif(sym=forsym)准备按照for 语句处理getsymdo;if(sym=ident)i=position(id,*ptx);if(i=0) error(11);elseif(tablei.kind!=varia

24、ble)赋值语句中，赋值号左部标识符属性应是变量error(12);i=0;elsegetsymdo;if(sym!=becomes)error(13);赋值语句左部标识符后应是赋值号:=else getsymdo;memcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevtosym=true;后跟符 to 和 downtonxtlevdowntosym=true;expressiondo(nxtlev,ptx,lev);处理赋值语句右部的表达式E1gendo(sto,lev-tablei.level,tablei.adr);保存初值switch(sym)13

25、case tosym:步长为的向上增加getsymdo;cx1=cx;保存循环开始点将循环判断变量取出放到栈顶gendo(lod,lev-tablei.level,tablei.adr);memcpy(nxtlev,fsys,sizeof(bool)*symnum);处理表达式E2nxtlevdosym=true;后跟符 doexpressiondo(nxtlev,ptx,lev);*判断循环变量条件，比如for i:=E1 to E2 do S 中，判断 i 是否小于E2 ，如小于等于，继续循环，大于的话，跳出循环*gendo(opr,0,13);生成比较指令，i 是否小于等于E2 的值cx

26、2=cx;保存循环结束点生成条件跳转指令， 跳出循环，跳出的地址未知gendo(jpc,0,0);if(sym=dosym)处理循环体Sgetsymdo;statement(fsys,ptx,lev);循环体处理增加循环变量步长为将循环变量取出放在栈顶gendo(lod,lev-tablei.level,tablei.adr);gendo(lit,0,2);将步长取到栈顶gendo(opr,0,2);循环变量加步长将栈顶的值存入循环变量14gendo(sto,lev-tablei.level,tablei.adr);gendo(jmp,0,cx1);无条件跳转到循环开始点* 回填循环结束点的地

27、址， cx 为 else后语句执行完的位置，它正是前面未定的跳转地址*codecx2.a=cx;elseerror(29);for语句中少了dobreak;casedowntosym:步长为的向下减少getsymdo;cx1=cx;保存循环开始点将循环判断变量取出放到栈顶gendo(lod,lev-tablei.level,tablei.adr);memcpy(nxtlev,fsys,sizeof(bool)*symnum);处理表达式E2nxtlevdosym=true;后跟符 doexpressiondo(nxtlev,ptx,lev);*判断循环变量条件，比如 for i:=E1 downto E2 do S 中，判断 i 是否大于等于E2 ，如大于等于，继续循环，小于的话，跳出循环*gendo(opr,0,11);生成比较指令，i 是否大于等于E2 的值cx2=cx;保存循环结束点生成条件跳转指令， 跳出循环，跳出的地址未知gendo(jpc,0,0);i