《编译原理》课程设计报告

1、设计题目：pl0编译器设计一、PL0程序的文法及，指令及属性翻译简化c语言文法定义（LL（1）文法）C程序：=void main（）函数体函数体：=变量定义部分 语句列变量定义部分：=变量定义 变量定义部分| 变量定义：=int 变量表变量表：=标识符|标识符，变量表语句列：=语句 语句列| 语句：=条件语句| 循环语句 | 读语句 | 写语句 | 复合语句 | 表达式语句 | 空语句条件语句：=if（表达式）语句循环语句：=while（表达式）语句读语句：=read（变量表）；写语句：=write（表达式表）；复合语句：=语句列；表达式语句：=表达式；空语句：=；表达式定义（算符优先文法）表

2、达式：=变量=表达式 | 变量+=表达式 | 变量-=表达式 | 变量*=表达式 | 变量/=表达式 | 变量%=表达式 | 表达式1表达式1：=表达式1 | 表达式2 | 表达式2表达式2：=表达式2&表达式3 | 表达式3表达式3：=表达式3=表达式4 | 表达式3！=表达式4 | 表达式3=表达式4 | 表达式3表达式4 | 表达式3=表达式4 | 表达式3表达式关系表达式：=表达式=表达式关系表达式：=表达式表达式关系表达式：=表达式）,GE（大于等于：=）,LT（小于：）,LE（小于等于：=、=等标识符： 用户定义的变量名、常数名、过程名常数： 如：10、25、100等整数界符： 如

3、：,、. 、; 、( 、)等在编译程序中，单词的表示方式：（sym, id/num）四、语法分析的设计1、语法分析子程序分析语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语意生成相应的代码，并提供了出错处理的机制。语法分析主要由分程序分析过程（block）、常量定义分析过程（constdeclaration）、变量定义分析过程（vardeclaration）、语句分析过程（statement）、表达式处理过程（expression）、项处理过程（term）、因子处理过程（factor）和条件处理过程（condition）构成。这些过程在结构上构成一个嵌套的层次结构。除此之

4、外，还有出错报告过程（error）、代码生成过程（gen）、测试单词合法性及出错恢复过程（test）、登录名字表过程（enter）、查询名字表函数（position）以及列出类PCODE代码过程（listcode）作过语法分析的辅助过程。2、语法分析的设计与实现 递归子程序法（递归下降分析器recursive-descent parser）： 对应每个非终结符（语法成分），编一个独立的处理子程序。由开始，按规则右部(语法描述图箭头方向)进行分析：遇到非终结符，则调用相应的处理过程；遇到终结符，则判断当前读入的单词是否与该终结符相匹配，若匹配，再读取下一个单词继续分析。图1 语法调用关系图五、代

5、码生成和分配变量PL/0 编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。PL/0 处理机有两类存贮，目标代码放在一个固定的存贮数组code 中，而所需数据组织成一个栈形式存放。PL/0 处理机的指令集根据PL/0 语言的要求而设计，它包括以下的指令：（1）LIT /* 将常数置于栈顶 */（2）LOD /* 将变量值置于栈顶 */（3）STO /* 将栈顶的值赋与某变量 */（4）CAL /* 用于过程调用的指令 */（5）INT /* 在数据栈中分配存贮空间 */（6）JMP, JPC /* 用于if, while 语句的条件或无条件控制转移指令 */（7）OP

6、R /* 一组算术或逻辑运算指令 */上述指令的格式由三部分组成：F L A，含义见下表：表1 PL/0 处理机指令上表中，层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code 的下标，数据地址为变量在局部存贮中的相对地址。PL/0 的编译程序为每一条PL/0 源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译比较简单。而对if 和while 语句稍繁琐一点，因为此时要生成一些跳转指令，而跳转的目标地址大都是未知的。顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0 机中，每个变量占一个存贮单元）。

7、开始编译一个过程时，要对数据单元的下标dx 赋初值，表示新开辟一个数据区。dx 的初值为3，因为每个数据区包含三个内部变量RA，DL 和SL。六、执行伪代码和访问变量1、伪代码指令INT：为被调用的过程（包括主程序）在运 行栈S中开辟数据区；L：0A：所需数据单元（包括SL、DL、RA）个数；CAL：调用过程；L：层差；A：被调用过程的过程体（过程体之前一条指令）在目标程序区的入口地址；LIT：将常量送到S栈的栈顶；L：0；A：常量值；LOD：将变量送到S栈的栈顶；L：层差；A：变量所在说明层的相对地址；STO：将运行栈S的栈顶内容送入某变量单元中；L：层差；A：变量所在说明层的相对地址；JM

8、P：无条件转移；L：0；A：转向地址；JPC：条件转移,当运行栈S的栈顶的布尔值为0时，则转向A所指目标程序地址；否则顺序执行；L：0；A：转向地址；OPR：关系或算数运算；L：0；A：具体运算（06，813），运算对象取自S栈栈顶和次栈顶；2、伪代码的生成PROCEDURE Statement( )中：赋值语句：STO , 层差 ，ADR读语句：OPR , 0, 16 STO , 层差，ADR写语句：OPR , 0, 14 OPR , 0, 15过程调用语句：CAL ,层差，ADR(入口地址）当型语句：JPC , 0 ，0(A0，需要返填） JMP , 0 ,CX1条件语句： JPC , 0

9、 ，0(A0，需要返填常量：LIT , 0, VAL变量：LOD , 层差，ADR3、伪代码的生成顺序（1）为主程序产生第一个无条件转移语句：JMP 0 L（2）为过程P1产生第二个无条件转移语句：JMP 0 L1（3）为过程P2产生第三个无条件转移语句：JMP 0 L2（4）为过程P3产生第四个无条件转移语句：JMP 0 L3（5）为过程体P3产生目标代码程序块，其入口地址为L3:L3:INT 0 A3(过程P3所需单元个数）OPR 0 0(返回到调用P3语句的下一条语句）（6）为过程P2产生目标代码程序块，其入口地址为L2：L2:INT 0 A2(过程P2所需单元个数）OPR 0 0(返回

10、到调用P2语句的下一条语句）七、补充Pl/0工作的基本流程如下：First和follow集合：非终结符First（s）Follow（s）程序体Const var procedure ident call if begin while,;语句Ident call begin if while,;end条件Odd+-(ident numberThen do表达式+-(ident number,;) R end then do项Ident number(,;) R +-end then do例子Ident number(,;) R +-*/ end then doPl0词法分析程序流程图：PL/0

11、的语言的词法分析器将要完成以下工作：（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代码时，数据段存储分配方式如下： 对于源程序的每一个过程，在被调用时，首先在数据段开辟第三个空间，存放静态链

12、SL，动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程运行时的最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL DL RA的值均为0.静态链的功能是在一个子过程要引用他的直接或间接父过程的变量时可以通过静态连，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它 在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址，通过当前段基址恢复数据段的分配指针，通过动态链接恢复局部段基址指针。实现子过程的返回。对于主程序来说，解释程序会遇到返回地址为0的情况，这时就认为程序运行结束 解释程序过程中的base函数的功能，就是用于沿着静态连，向前查找相差制定层数的局部数据段基址，这在是使用sto，lod等访问局部变量的指令中会经常用到。总结编译器的编写涉及到程序设计语言，计算机体系结构，语言理论，算法和编译原理等学科。一个编译程序从逻辑上分为词法分析，语法分析，语义分析，代码级代码优化等5部分，为编好编译程序还需要有出错处理及符号表管理两个辅助模块。一个编译程序是将某一个高级语言编写的源程序翻译成机器语言目标程序或者翻译成汇编语言目标