《编译原理》设计方案报告

编译原理课程设计报告设计题目：pio编译器设计一、PL0程序的文法及，指令及属性翻译简化c语言文法定义（LL （1）文法）C 程序：=void main （） 函数体函数体：=变量定义部分 语句列变量定义部分：=变量定义 变量定义部分| ?变量定义：=int变量表变量表：=标识符|标识符，变量表语句列：=语句语句列| ?语句：=条件语句|循环语句|读语句|写语句|复合语句|表达式语句|空语句 条件语句：=if （表达式）语句循环语句：=while （表达式）语句读语句：=read （变量表）；写语句：=write （表达式表）；复合语句：=语句列；表达式语句：=表达式；空语句：=;表达式定义（算符优先文法）表达式：=变量=表达式|变量+=表达式|变量-=表达式|变量*=表达式|变量/=表达式|变量%=表达式|表达式1表达式1 :=表达式1 |表达式2 |表达式2表达式2:=表达式2&表达式3 |表达式3表达式3:=表达式3=表达式4 |表达式3！=表达式4 |表达式3=表达式4 |表达式3表达式4 |表达式3=表达式4 |表达式3表达式4 |表达式4表达式4:=表达式4+表达式5 |表达式4-表达式5 |表达式5表达式5:=表达式5*表达式6 |表达式5/表达式6 |表达式5/表达式6 |表达式6表达式6: =!表达式7表达式7:=（表达式）|变量|常量PL0文法定义程序：=分程序.分程序：=常量定义；常后分程序|常后分程序常后分程序：=变量定义；变后分程序|变后分程序变后分程序：=过程定义；变后分程序|语句常量定义：=const常量定义表常量定义表：=id = number | id = number,常量定义表变量定义:=var变量表变量表：=id | id,变量表过程定义：=procedure id ;分程序语句：=赋值语句I条件语句I循环语句I读语句I写语名I复合语句 |过程调用语句I 赋值语句：=id :=表达式读语句：=read（变量表）写语句：=write（表达式表）表达式表：:=表达式 I表达式，表达式表条件语句：=if条件表达式then语句循环语句：=while条件表达式do语句复合语句：=begin 语句列 end过程调用语句:=call id参量表：=有参表I 有参表：=表达式，有参表I表达式表达式：=+表达式1卜表达式1I表达式1表达式1：=表达式1+表达式 2I表达式1-表达式 2I表达式 2表达式 2：=表达式2*表达式3I表达式 2/表达式 3I表达式2mod表达式 3|表达式 3表达式 3：=id | number | （表达式）条件表达式=条件表达式or条件表达式1|条件表达式1条件表达式1：=条件表达式1and条件表达式 2|条件表达式2条件表达式2：=not 条件表达式3|条件表达式3关系表达式 关系表达式 关系表达式 关系表达式 关系表达式 关系表达式条件表达式3：=（条件表达式）|关系表达式=表达式表达式=表达式=表达式=表达式表达式=表达式=表达式=表达式=表达式=表达式#表达式PL0栈式机指令指令格式：指令码（f）所在层数差（I），操作数（a）PL0栈式机指令：LIT :将常数a取到栈顶LOD :将位于（当前层-l）层处的变量a取到栈顶STO:将栈顶处值存储到指定位置，l,a同上CALL调用当前-l层处的过程aINT :为调用过程在栈中开辟数据区，a为单元个数JMP:无条件转移指令，a目标地址JPC:条件转移指令，栈顶值的布尔值为非真时转移到a处，否则执行下面语句OPR:关系运算或算术运算义开始），CALL （call:过程调用语句）BEGIN （ begon：复合语句开始）PL0属性翻译MCONST （ con st:常量定义开始）VAR（var:变量定义开始）,PROCEDURE （procedure：过程定END （end:复合语句结束）， IF （if :条件语句开始）,THEN（then :条件结束）,WHILE （while :循环语句开始） DO （do：循环条件结束），READ （read :读语句）， WRITE （write :输出语句）， ODD （ odd :判奇运算），分隔符、运算符号DOT （点：.），COMMA （逗号：，）， SEMICOLON （分号：;）,LPAREN （左括号：（）， RPAREN （右括号：），ASSIGNOP （赋值：:=）, PLUSOP （加法运算符号：+） MINUSOP （减法运算符：-）,MULTOP （乘法运算符：*） DIVOP （除法运算符：/）, GT （大于：）,GE （大于等于：=）,LT （小于：）,LE （小于等于：=）,EQ （等于：=）,NE （不等：#）,ENDF （输入结束符），分析过程中需要的非终结符号SERVERKEY （保留字），FACTOR （因子），ROP （关系运算），CONSTANT （常量部份定义） VARIABLE （变量部份定义） IDENT （自定义标识符），NUMBER （常数）二、符号表的结构，组织，填写及查找1、符号表结构const char*pName;符号名称intki nd;符号类别，由上面单词分类确定intval;/符号表中的位置值intlevel;符号的层数intpare nt;符号的作用域intsize;/过程长度char strBuffMAXLENSTR;/符号堆2、符号表的组织符号表的组织方式有： 线性表、散列表、树结构等，其必须维持源程序中的作用域信息。 栈符号表：函数或分程序的嵌套结构， 使得程序中出现的符号的处理（内层可引用外层符号、同名变量内层优先） 与栈的操作相一致。一个过程结束时将释放相应的子符号表-解决作用域检查问题。3、符号表的填写及查找词法分析子程序名为getsym，功能是从源程序中读取一个单词符号（taken），把他的信息放入全局变量sym id和num中，词法分析器需要单词时，直接从这三个变量中获得。Getsym过程通过反复调用 getch子过程从源程序获取字符，并把它们拼成单词。Getch过程使用了缓冲技术提高了运行效率。三、扫描器（词法分析器）1、词法分析子程序分析词法分析子程序名为getsym，功能是从源程序中读出一个单词符号（ token）,把它的信息放入全局变量 sym、id和num中，语法分析器需要单词时，直接从这三个变量中获得注意：语法分析器每次用完这三个变量的值就立即调用getsym子程序获取新的单词供下一次使用。而不是在需要新单词时才调用getsym过程。getsym过程通过反复调用 getch子过程从源程序过获取字符，并把它们拼成单词。getch过程中使用了行缓冲区技术以提高程序运行效率。2、词法分析器的分析过程调用getsym时，它通过getch过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表， 如果查到为保留字，则把sym变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把sym置为ide nt，把这个单词存入id变量。查保留字表时使用了二分法查找以提高效率。如果getch获得的字符是数字，则继续用getch获取数字，并把它们拼成一个整数，然后把sym置为number，并把拼成的数值放入 num变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等），则把sym则成相应的类型。如果遇到不合法的字符，把 sym 置成 nul。3、词法分析函数getsym（所识别的单词：保留字或关键字：如：BEGIN、 END、 IF、 THEN等运算符：女口： +、-、*、人：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数： 女口： 10、25、100等整数界符： 女口： ， 、 ;、 （ 等在编译程序中，单词的表示方式：（sym, id/num）四、语法分析的设计1、语法分析子程序分析语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语意生成相应的代码，并提供了出错处理的机制。语法分析主要由分程序分析过程（block）、常量定义分析过 程（constdeclaration ）、变量定义分 析过 程（vardeclaration ）、语句分析过程（statement）、表达式处理过程（expression）、项处理过程（term）、因子处理过程（factor） 和条件处理过程（condition ）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出错报告过程（error）、代码生成过程（gen）、测试单词合法性及出错恢复过程（test）、 登录名字表过程（enter）、查询名字表函数（position）以及列出类PCODE代码过程（listcode） 作过语法分析的辅助过程。2、语法分析的设计与实现递归子程序法（递归下降分析器recursive-descent parser）:对应每个非终结符（语法成分），编一个独立的处理子程序。由 程序开始，按规则右部（语法描述图箭头方向）进行分析：遇到非终结符，则调用相 应的处理过程；遇到终结符，则判断当前读入的单词是否与该终结符相匹配，若匹配，再读取下一个单词继续分析。图1 语法调用关系图五、代码生成和分配变量PL/O编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和目标”代码。PL/0处理机有两类存贮，目标代码放在一个固定的存贮数组code中，而所需数据组织成一个栈形式存放。PL/0处理机的指令集根据 PL/0语言的要求而设计，它包括以下的指令：（1）LIT /*将常数置于栈顶 */（2） LOD /*将变量值置于栈顶*/（3） STO /*将栈顶的值赋与某变量*/（4） CAL /*用于过程调用的指令*/（5） INT /*在数据栈中分配存贮空间*/（6） JMP, JPC /*用于if, while语句的条件或无条件控制转移指令*/（7） OPR /* 一组算术或逻辑运算指令*/FLaINT常最LIT常aLOD层次差数据地址STO层次差数据地址CAL层次羞程序地址JMP程序地址JPC程序地址OPR运算类别上述指令的格式由三部分组成:F L A，含义见下表:表1 PL/O处理机指令上表中，层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址。PL/0的编译程序为每一条 PL/0源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译比较简单。而对if和while语句稍繁琐一点，因为此时要生成一些跳转指令，而跳转的目标地址大都是未知的。顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0机中，每个变量占一个存贮单元）。开始编译一个过程时， 要对数据单元的下标 dx赋初值， 表示新开辟一个数据区。dx的初值为3，因为每个数据区包含三个内部变量 RA , DL和SL。六、执行伪代码和访问变量1、伪代码指令行栈S中开辟数据区;INT :为被调用的过程（包括主程序）在运L : 0A :所需数据单元（包括 SL、DL、RA ）个 数;CAL :调用过程；L :层差;A :被调用过程的过程体（过程体之前一条指令）在目标程序区的入口地址;LIT :将常量送到 S栈的栈顶;L : 0;A :常量值；LOD :将变量送到S栈的栈顶;L :层差;A :变量所在说明层的相对地址；STO:将运行栈S的栈顶内容送入某变量单元中;L :层差;A :变量所在说明层的相对地址;JMP :无条件转移；L : 0;A :转向地址；JPC:条件转移，当运行栈S的栈顶的布尔值为 0时，则转向A所指目标程序地址；否则顺 序执行；L : 0 ；A :转向地址；OPR :关系或算数运算；L : 0 ；A :具体运算（06, 813）,运算对象取自S栈栈顶和次栈顶；2、伪代码的生成PROCEDURE Stateme nt（）中： 赋值语句：STO ,层差，ADR读语句：OPR , 0, 16STO ,层差，ADR写语句：OPR , 0, 14OPR , 0, 15过程调用语句：CAL ,层差，ADR（入口地址） 当型语句：JPC , 0 , 0（A = 0，需要返填）JMP , 0 ,CX1条件语句：JPC , 0 , 0（A = 0,需要返填 常量：LIT, 0, VAL变量：LOD ,层差，ADR3、伪代码的生成顺序（1）为主程序产生第一个无条件转移语句：JMP 0 L(2)为过程P1产生第二个无条件转移语句：JMP0L1(3)为过程P2产生第三个无条件转移语句：JMP0L2(4)为过程P3产生第四个无条件转移语句：JMP0L3(5)为过程体P3产生目标代码程序块，其入口地址为L3:L3:INT 0 A3（过程P3所需单元个数）OPR 00（返回到调用P3语句的下一条语句）（6）为过程P2产生目标代码程序块，其入口地址为L2 :L2:INT 0A2（过程P2所需单元个数）OPR 00（返回到调用P2语句的下一条语句）七、补充PI/0工作的基本流程如下:符号农首理F词法分析诱法分析1r语文分析1F代码生贱1F代码执行源稈序执斤结累帖没诊芍豐理First 和 follow集合:非终结符First ( s)Follow ( s)程序体Const var procedure ide nt call if begi n while5 5语句Ide nt call begi n if while,;end条件Odd+-(ide nt nu mberThe n do表达式+-(ide nt nu mber,;)R end the n do项Ide nt nu mber(,;)R +-e nd the n do例子Ide nt nu mber(,;)R +-*/ end then doP10词法分析程序流程图:PL/0的语言的词法分析器将要完成以下工作：（1）跳过分隔符（如空格，回车，制表符）；（2） 识别诸如begin, end, if, while等保留字；（3） 识别非保留字的一般标识符，此标识符值（字符序列）赋给全局量id， 而全局量sym 赋值为SYM_IDENTIFIER。（4） 识别数字序列，当前值赋给全局量NUM，sym则置为SYM_NUMBER ；（5）识别:=，=，=之类的特殊符号，全局量 sym则分别被赋值为 SYM_BECOMES，SYM_LEQ，SYM_GTR 等。解释执行pcode代码时，数据段存储分配方式如下：对于源程序的每一个过程，在被调用时，首先在数据段开辟第三个空间，存放静态链SL，动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程运行时的最 新数据段的基地址。 动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL DL RA的值均为0静态链的功能是在一个子过程要引用他的直接或间接父过程的变量时可以通过静态连，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址，通过当前段基址恢复数据段的分配指针，通过动态链接恢复局部段基址指针。实现子过程的返回。 对于主程序来说，解释程序会遇到返回地址为0的情况，这时就认为程序运行结束解释程序过程中的base函数的功能，就是用于沿着静态连，向前查找相差制定层数的局部数据段基址，这在是使用sto, lod等访问局部变量的指令中会经常用到。总结编译器的编写涉及到程序设计语言，计算机体系结构，语言理论，算法和编译原理等学科。一个编译程序从逻辑上分为词法分析，语法分析，语义分析，代码级代码优化等 5部分,为编好编译程序还需要有出错处理及符号表管理两个辅助模块。一个编译程序是将某一个高 级语言编写的源程序翻译成机器语言目标程序或者翻译成汇编语言目标程序。 然而翻译成汇 编语言目标程序或机器语言目标程序需要十分熟悉目标机的指令系统， 为编译器的编写带来 很多麻烦。为了简化编译器的编写，我们仅仅完成编译器的前端设计， 即实现解释执行简化 后的c语言源程序。通过这次的课程设计， 我了解高级语言的编译过程， 理解了词法分析， 语法分析及语义 分析，理解符号表及符号表的作用以及出错在编译过程中的作用。同时通过 c语言的编写， 进一步提升了自己的编程水平，锻炼了独立编程的能力。