广工编译原理课程设计及实验报告.docx

编译原理课程设计课程名称 编 译 原 理 题目名称 课 程 设 计 学生学院 计 算 机 学 院 专业班级 学 号 学生姓名 指导教师 蒋 艳 荣 2015 年 12 月 27 日一、 实验要求课内实验对PL/0作以下修改扩充：（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN运算符 *=，/=，+，-，&，|，！（2）修改单词：不等号# 改为 （3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。将原本 条件语句 - if条件 then 语句 改为 条件语句 - if条件 then 语句 else 语句1 课程设计基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：*= 和 /=语句 - ident *= 表达式语句 - ident /= 表达式扩充语句（Pascal的FOR语句）:FOR := TO DO FOR := DOWNTO DO 其中，语句的循环变量的步长为2，语句的循环变量的步长为-2。（3）增加运算：+ 和 -。 选做内容（成绩评定范围扩大到：“优”和“良”）（1）增加类型： 字符类型； 实数类型。（2）扩充函数： 有返回值和返回语句； 有参数函数。（3）增加一维数组类型（可增加指令）。（4）其他典型语言设施。二、 实验环境及工具源语言 ：PL0目标语言：假想栈式计算机的汇编语言（C语言实现）实现工具：codeblock运行平台：Windows 10三、 结构设计说明（1）PL/0 语言编译程序结构 PL/0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0源程序词法分析程序语法语义分析程序代码生成程序表格管理程序出错处理程序目标程序PL/0编译程序的结构图（2）PL/0 语言编译程序总体流程以下是编译程序的总体流程图，其中，PL/0编译程序的语法分析过程BLOCK是整个编译过程的核心，我们通过该流程图来弄清BLOCK过程在整个编译程序中的作用。PL/0 的编译程序采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量，常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。（3）各功能模块描述过程或函数名简要功能说明pl0主程序error出错处理，打印出错位置和错误编码getsym词法分析，读取一个单词getch漏掉空格，读取一个字符gen生成目标代码，并送入目标程序区test测试当前单词符号是否合法block分程序分析处理过程enter登录名字表position(函数)查找标识符在名字表中的位置constdeclaration常量定义处理vardeclaration变量说明处理listode列出目标代码清单statement语句处理expression表达式处理term项处理factor因子处理condition条件处理interpret对目标代码的解释执行程序base(函数)通过静态链求出数据区的基地址四、 主要成分描述 符号表在PL0中，使用以下数据结构存储符号表：struct tablestruct char nameal; /*名字*/ enum object kind; /*类型：const，var，array or procedure*/ int val; /*数值，仅const使用*/ int level; /*所处层，仅const不使用*/ int adr; /*地址，仅const不使用*/ int size; /*需要分配的数据区空间，仅procedure使用*/;struct tablestruct tabletxmax; /*名字表*/他是一个全程量一维数组TABLE。表中每个元素为记录型数据。如果标识符被说明为常数，其属性值为常数值；如果标识符被说明成变量，其属性就是由层次和修正量（偏移量）组成的地址；如果标识符被说明为过程，其属性就是过程的入口地址及层次。常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0 机中，每个变量占一个存贮单元）。开始编译一个过程时，要对数据单元的下标dx 赋初值，表示新开辟一个数据区。dx 的初值为3，因为每个数据区包含三个内部变量RA，DL 和SL。 运行时存储组织和管理当源程序经过语法分析，如果没有发现错误，由编译程序调用解释程序，对存放在CODE中的目标代码从CODE0开始解释执行。存放目标代码的数据结构：struct instructionenum fct f;/*虚拟机代码指令*/ int l;/*引用层与声明层层次差*/ int a;/*根据f的不同而不同*/;struct instruction codecxmax;/*存放虚拟机代码的数组*/当编译结束之后，记录源程序中标识符的TABLE表已经没用了，因此存储区只需要以数组CODE存放的只读目标程序和运行时的数据区S。S是由解释程序定义的一维整型数组。代码如下:int p, b, t; /*指令指针，指令基址，栈顶指针*/struct instruction i; /*存放当前指令*/int sstacksize; /*栈*/其中，有四个寄存器。分别为I指令寄存器，P程序地址寄存器，T栈顶寄存器，B基址寄存器。对于源程序的每一个过程（包括主程序），在被调用时，首先在数据段中开辟三个空间，存放静态链SL、动态链DL和返回地址RA。1. 静态链记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。2. 动态链记录调用该过程前正在运行的过程的数据段基址。3. 返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL、DL和RA的值均置为0。静态链的功能是在一个子过程要引用它的直接或间接父过程（这里的父过程是按定义过程时的嵌套情况来定的，而不是按执行时的调用顺序定的）的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它。 语法分析方法PL/0编译程序的语法分析采用了自顶向下的递归子程序法。语法分析从读入第一个单词开始由开始符程序出发，沿语法描述图箭头所指方向进行分析。当遇到非终结符时，则调用相对应的处理过程，从语法描述图也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行对应的语义程序（翻译程序）。再读入下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个比较，若都不匹配时可能是进入下一非终结符语法单位或是出错。如果一个PL0语言程序的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符，这时说明所输入的程序是正确的。对于正确的语法分析进行对应的语义翻译，生成目标代码。语法分析主要由分程序分析过程（BLOCK）常量定义分析过程（ConstDeclaration）、变量定义分析过程（Vardeclaration）、字符变量定义分析过程（Chardeclaration）、语句分析过程（Statement）、表达式处理过程（Expression）、项处理过程（Term）、因子处理过程（Factor）和条件处理过程（Condition）构成。这些过程在结构上构成一个嵌套的层次结构。 中间代码表示中间代码是是源程序的一种内部表示，复杂性介于源语言和目标机语言之间。中间代码的表示方法有逆波兰式、三元式、树形、四元式等。(1) 逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式。后缀表示法表示表达式，其最大的优点是易于栈式计算机处理表达式。(2) 每个三元式由三个部分组成：算符op第一运算对象ARG1第二运算对象ARG2运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。(3) 树形表示是三元式表示的翻版。(4) 四元式是一种比较普遍采用的中间代码形式：算符op运算对象ARG1运算对象ARG2运算结果RESULT五、 开发过程和完成情况（1）增加单词：保留字 ELSE，FOR，TO，DOWNTO，RETURN运算符 *=，/=，+，-，&，|，！1.1修改symbol枚举enum symbol nul, ident, number, plus, minus, times, slash, oddsym, eql, neq,lss, leq, gtr, geq, lparen,rparen, comma, semicolon,period, becomes,beginsym, endsym, ifsym, thensym, whilesym,writesym, readsym, dosym, callsym, constsym,varsym, procsym,elsesym,forsym,tosym,downtosym,returnsym,muleqsym,deviesym,pplus,mminus,andsym,logical_or,logical_not,charsym,charvalue,writecharsym,readcharsym;1.2 修改getSym(),增加以下语句int getsym()/乘等识别else if(ch=*)getchdo;if (ch=)sym= muleqsym;getchdo;elsesym = nul;./除等识别else if(ch=/)getchdo;if (ch=)sym= deviesym;getchdo;elsesym = nul;/+、-识别if (ch=+)getchdo;if (ch=+) / 自增检测sym=pplus;getchdo;elsesym = plus;else if (ch=-)getchdo;if (ch=-) / 自减检测sym=mminus;getchdo;elsesym = minus;1.3 修改init()，增加以下语句void init().ssym&=andsym;ssym!=neq;.1.4 修改init()增加保留字识别strcpy(&(wordi+0),do);strcpy(&(wordi+0),downto);strcpy(&(wordi+0),else);strcpy(&(wordi+0),for);strcpy(&(wordi+0),return);strcpy(&(wordi+0),then);strcpy(&(wordi+0),to); i = 0;/*设置保留字符号*/wsymi+=dosym;wsymi+=downtosym;wsymi+ =elsesym;wsymi+=forsym;wsymi+=returnsym;wsymi+=thensym;wsymi+=tosym;1.5 修改单词总数symnum，加2#define NumOfKeywork 21 /21是完成时的状态（2）修改单词：不等号# 改为 2.1 修改getsym(),识别getsym().else if(ch=) /不等于sym=neq;getchdo;elsesym = lss;.(3)增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。3.1 文法将原本 条件语句 - if条件 then 语句 改为 条件语句 - if条件 then 语句 else 语句 := if then else 3.2修改statementelse if(sym=ifsym) /*准备按照if语句处理*/getsymdo;memcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevthensym=true;nxtlevdosym=true; /*后跟符号为then或do*/conditiondo(nxtlev,ptx,lev); /*调用条件处理（逻辑运算）函数*/if(sym=thensym)getsymdo;elseerror(16); /*缺少then*/cx1=codePointer; /*保存当前指令地址*/gendo(jpc,0,0); /*生成条件跳转指令，暂写0*/statementdo(fsys,ptx,lev); /*处理then后的语句*/*经statement处理后，cx为then后语句执行 完的位置，它正是前面未定的跳转地址*/ getsymdo;if (sym=elsesym)codecx1.a=codePointer+1;int jmpdx = codePointer;/记下jmp指令位置gendo(jmp,0,0);getsymdo;statementdo(fsys,ptx,lev);codejmpdx.a = codePointer;elsecodecx1.a=codePointer;（4）扩充赋值运算：*= 和 /=4.1 文法语句 - ident *= 表达式语句 - ident /= 表达式4.2 符号识别（上面已经完成）4.3 修改statement函数 if(sym=ident) i=position(id,*ptx); if(i=0) error(11); else if(tablei.kind!=variable&tablei.kind!=character) error(12); i=0; else if (tablei.kind=variable) getsymdo; /如果是 := *= /= if(sym=becomes|sym=muleqsym|sym=deviesym) tempsym = sym; /如果是 /= if (sym=deviesym) /将变量放到顶 gendo(lod,lev-tablei.level,tablei.adr); getsymdo; memcpy(nxtlev,fsys,sizeof(bool)* symnum); expressiondo(nxtlev,ptx,lev); if (tempsym=becomes)/如果是赋值 gendo(sto,lev-tablei.level,tablei.adr); else if (tempsym=muleqsym)/如果是 *= /将变量放到顶 gendo(lod,lev-tablei.level,tablei.adr); /乘法运算 gendo(opr,0,4); /将结果送到变量 gendo(sto,lev-tablei.level,tablei.adr); else if (tempsym=deviesym)/如果是 /= /除法法运算 gendo(opr,0,5); /将结果送到变量 gendo(sto,lev-tablei.level,tablei.adr); . （5）扩充语句（Pascal的FOR语句）:FOR := TO DO FOR := DOWNTO DO 其中，语句的循环变量的步长为2，语句的循环变量的步长为-2。5.1 文法for语句 := FOR := TO DO | FOR := DOWNTO DO 5.2关键字识别修改init()void init() .strcpy(&(wordi+0),for);strcpy(&(wordi+0),to);strcpy(&(wordi+0),do);strcpy(&(wordi+0),downto);.wsymi+=forsym;wsymi+=dosym;wsymi+=downtosym;wsymi+=tosym;.5.3 语法语义解析修改statement 增加for分支int statement() .else if (sym=forsym)getsymdo;if (sym=ident)i=position(id,*ptx); if(i=0) error(11);/找不到标识符 else if(tablei.kind!=variable) /如果不是变量 error(12); i=0; else getsymdo; if(sym=becomes)/如果是赋值 getsymdo; expressiondo(nxtlev,ptx,lev); /将栈顶表达式内容送到变量中 gendo(sto,lev-tablei.level,tablei.adr); if (sym=tosym|sym=downtosym) int jmp1,jmp2,jpc1; tempsym = sym; jmp1 = codePointer; gendo(jmp,0,0);/jmp1,跳到判断处 /开始自增 jmp2 = codePointer; gendo(lod,lev-tablei.level,tablei.adr); if (tempsym=tosym) gendo(lit,0,tostep); else gendo(lit,0,downtostep); gendo(opr,0,2); gendo(sto,lev-tablei.level,tablei.adr); codejmp1.a = codePointer;getsymdo; expressiondo(nxtlev,ptx,lev); /开始判断 gendo(lod,lev-tablei.level,tablei.adr); if (tempsym=tosym) gendo(opr,0,11); else gendo(opr,0,13); jpc1 = codePointer; gendo(jpc,0,0);/如果为假，跳到循环后面,否则执行后面语句 if (sym=dosym) getsymdo; statementdo(fsys,ptx,lev); gendo(jmp,0,jmp2);/跳到自增指令 codejpc1.a = codePointer; else error(27); else error(26);/to expected .（6）增加运算：+ 和 -。 6.1 文法 := +|- ident := ident +|- := +|- ident:= ident +|- 6.2 增加自增自减处理函数int selfopr(int lev,int addr,int opration)gendo(lod,lev,addr);gendo(lit,0,1);if (opration=pplus)gendo(opr,0,2);elsegendo(opr,0,3);gendo(sto,lev,addr); return 0;6.3 修改statement语句，增加i+ i-句式识别int statement().if(sym=ident).else if (sym=pplus) / ident 后面跟 + 处理 selfopr(lev-tablei.level,tablei.adr,pplus); getsymdo; else if (sym=mminus) / - 处理 selfopr(lev-tablei.level,tablei.adr,mminus); getsymdo; .6.4 修改statement语句，增加、+ - 前缀句式识别int statement().else if (sym=mminus|sym=pplus) /如果是 + 或 -tempsym= sym;getsymdo;if(sym=ident) i=position(id,*ptx); if(i=0) error(11); else if(tablei.kind!=variable) error(12); i=0; else selfopr(lev-tablei.level,tablei.adr,tempsym); getsymdo; else error(12); 6.4 修改因子 + - 前缀识别int factor(bool*fsys,int *ptx,int lev) int sopr = -1; int i; bool nxtlevsymnum; testdo(facbegsys,fsys,24); /*检测因子的开始符好号*/ while(inset(sym,facbegsys) /*循环直到不是因子开始符号*/ if (sym=mminus|sym=pplus) sopr = sym; getsymdo; if(sym=ident) /*因子为常量或者变量*/ i=position(id,*ptx); /*查找名字*/ if(i=0) error(11); /*标识符未声明*/ else switch(tablei.kind)case constant:/*名字为常量*/ error(28);break;case variable: selfopr(lev-tablei.level,tablei.adr,sopr);/+ -处理gendo(lod,lev-tablei.level,tablei.adr); /*找到变量地址并将其值入栈*/break;case procedur:error(21);break;case character:error(31);break; getsymdo;elseerror(29);6.5 增加因子 + - 后缀识别6.5.1 增加新的数据结构，记录要自增或自减的变量struct backpathint o; /+ 或 - int lev; / 层次 int addr; /地址Info50;6.5.2 增加语句完成后的自增处理函数/在statemtent之后调用int backpath() int i = 0; for(;iinfoindex;i+) selfopr(Infoi.lev,Infoi.addr,Infoi.o); infoindex = 0; return 0;6.5.3 修改statement函数else if(sym=beginsym) /*准备按照复合语句处理*/getsymdo;memcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevsemicolon=true;nxtlevendsym=true;/*后跟符号为分号或end*/*循环调用语句处理函数，直到下一个符号不是语句开始符号或收到end*/statementdo(nxtlev,ptx,lev);backpath();while(inset(sym,statbegsys)|sym=semicolon)if(sym=semicolon)getsymdo;elseerror(10);/*缺少分号*/statementdo(nxtlev,ptx,lev);backpath();6.5.4 因子处理修改factor函数int factor()if(sym=ident) .getsymdo;if (sym=mminus|sym=pplus)Infoinfoindex.o = sym;Infoinfoindex.lev = lev-tablei.level;Infoinfoindex.addr =tablei.adr;infoindex+;getsymdo;.增加因子前缀集facbegsyspplus=true;facbegsysmminus=true;(7) 增加字符类型7.1 增加枚举变量enum symbol . charsym、charvalue .enum object constant, variable, procedur, character;7.2增加 关键字识别strcpy(&(wordi+0),char);wsymi+=charsym;7.3增加到声明符集declbegsyscharsym=true;7.4增加字符识别修改getsym() .else if (ch=)getchdo;Tchar = ch;getchdo;if (ch!=)error(30);elsesym = charvalue;getchdo;7.5 增加字符声明函数int chardeclaration(int * ptx,int lev,int * pdx)if(sym=ident) enter(character,ptx,lev,pdx);/填写名字表