编译原理—pl0实验报告

PL/0实验报告课程名称编译原理题目名称PL/0编译程序学生学院计算机科学与技术学院专业班级学号学生姓名班内序号2山东理工大学实验报告纸第1页姓名：蔡鹏飞计算机院_11_级02班同组者成绩_________室温：气压：课程名称：编译原理教师签字实验项目编号(1)PL/0编译程序的分析指导教师鞠传香实验目的1.熟悉pl/0语言并能编写小程序2.掌握pl/0编译程序的编译过程(词法分析、语法分析、语义分析等)实验仪器（编号）材料、工具PC机、VC++6.0（原理概述）pl/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类pcode解释程序解释执行生成的类pcode代码。34PL/0语言文法的EBNF表示EBNF表示的符号说明。〈〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。∷=：该符号的左部由右部定义，可读作'定义为'。|：表示'或'，为左部可由多个右部定义。{}：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，5有上下界时为可重复次数的限制。如：{*}表示*重复任意次，{*}38表示*重复3-8次。[]：方括号表示其内的成分为任选项。()：表示圆括号内的成分优先。例：用EBNF描述整数文法的定义：整数∷=[+|-]数字{数字}数字∷=0|1|2|3|4|5|6|7|8|9或更好的写法整数∷=[+|-]非零数字{数字}|0非零数字∷=1|2|3|4|5|6|7|8|9数字∷=0|非零数字PL/0语言文法的EBNF表示67PL/0语言文法的EBNF表示为：〈程序〉∷=〈分程序〉．〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义〉{，〈常量定义〉}；〈常量定义〉∷=〈标识符〉=〈无符号整数〉〈无符号整数〉∷=〈数字〉{〈数字〉}〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉}〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}；〈过程首部〉∷=PROCEDURE〈标识符〉；〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉〈赋值语句〉∷=〈标识符〉∶=〈表达式〉〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')'〈加法运算符〉∷=+|-〈乘法运算符〉∷=*|/8〈关系运算符〉∷=#|=|＜|＜=|＞|＞=〈条件语句〉∷=IF〈条件〉THEN〈语句〉〈过程调用语句〉∷=CALL〈标识符〉〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉〈读语句〉∷=READ'('〈标识符〉{，〈标识符〉}')'〈写语句〉∷=WRITE'('〈表达式〉{，〈表达式〉}')'〈字母〉∷=a|b|…|X|Y|Z〈数字〉∷=0|1|2|…|8|9（实验内容步骤）(1)根据PL/0语言的语法图，理解PL/0语言各级语法单位的结构，掌握PL/0语言合法程序的结构；(2)从总体上分析整个系统的体系结构、各功能模块的功能、各模块之间的调用关系、各模块之间的接口；(3)详细分析各子程序和函数的代码结构、程序流程、采用的主要算法及实现的功能；(4)撰写分析报告，主要内容包括系统结构框图、模块接口、主要算法、各模块程序流程图等1.分析PL/0源程序词法分析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_GEQ等。相关过程（函数）有getsym()，getch()，其中getch()为获取单个字符的过程，除此之外，它还完成：（1）识别且跳过行结束符；（2）将输入源文件复写到输出文件；（3）产生一份程序列表，输出相应行号或指令计数器的值。语法分析我们采用递归下降的方法来设计PL/0编译器。以下我们给出该语言的FIRST和FOLLOW集合。非终结符（S）FIRST(S)FOLLOW(S)程序体constvarprocedureidentcallifbeginwhile.;语句identcallbeginifwhile.;end条件odd+-(identnumberthendo表达式+-(identnumber.;)Rendthendo项identnumber(.;)R+-endthendo因子identnumber(.;)R+-*/endthendo9注：表中R代表六个关系运算符。不难证明，PL/0语言属于LL（1）文法。（证明从略。）以下是我们给出如何结合语法图编写（递归下降）语法分析程序的一般方法。假定图S所对应的程序段为T（S），则：（1）用合适的替换将语法约化成尽可能少的单个图；（2）将每一个图按下面的规则（3）-（7）翻译成一个过程说明；（3）顺序图对应复合语句：对应：beginT(S1);T(S2);...;T(Sn)end（4）选择：对应：case语句或者条件语句：casechofifchinL1thenT(S1)elseL1:T(S1);ifchinL2thenT(S2)elseL2:T(S2);或......ifchinLnthenT(Sn)elseLn:T(Sn);error其中Li∈FIRST（Si），ch为当前输入符号。（下同）（5）循环对应：whilechinLdoT(S)（6）表示另一个图A的图：对应：过程调用A。（7）表示终结符的单元图：对应：ifch==xthenread(ch)elseerror相关过程有：block(),constdeclaration(),vardeclaration(),statement(),condition(),expression_r(),term(),factor()等。语义分析PL/0的语义分析主要进行以下检查：（1）是否存在标识符先引用未声明的情况；（2）是否存在己声明的标识符的错误引用；（3）是否存在一般标识符的多重声明代码生成PL/0编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。最终我们要“运行”该目标码。为了使我们的编译程序保持适当简单的水平，不致陷入与本课程无关的实际机器的特有性质的考虑中去，我们假想有台适合PL/0程序运行的计算机，我们称之为PL/0处理机。PL/0处理机顺序解释生成的目标代码，我们称之为解释程序。注意：这里的假设与我们的编译概念并不矛盾，在本课程中我们写的只是一个示范性的编译程序，它的后端无法完整地实现，因而只能在一个解释性的环境下予以模拟。从另一个角度上讲，把解释程10序就看成是PL/0机硬件，把解释执行看成是PL/0的硬件执行，那么我们所做的工作：由PL/0源语言程序到PL/0机器指令的变换，就是一个完整的编译程序。PL/0处理机有两类存贮，目标代码放在一个固定的存贮数组code中，而所需数据组织成一个栈形式存放。PL/0处理机的指令集根据PL/0语言的要求而设计，它包括以下的指令：（1）LIT（2）LOD（3）STO（4）CAL（5）INT（6）JMP,JPC（7）OPR上述指令的格式由三部分组成：FLA其中，f,l,a的含义见下表：FLaINT———常量LIT———常量LOD层次差数据地址STO层次差数据地址CAL层次差程序地址JMP———程序地址JPC———程序地址OPR———运算类别表2-1PL/0处理机指令上表中，层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址。PL/0的编译程序为每一条PL/0源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译较简单。如赋值语句X:=YopZ（op为某个运算符），将被翻译成下面的目标代码序列：（设指令计数从第100号开始）No.fLa100LODLevel_diff_YAddr_Y101LODLevel_diff_ZAddr_Z102OPR——————op103STOLevel_diff_XAddr_X而对if和while语句稍繁琐一点，因为此时要生成一些跳转指令，而跳转的目标地址大都是未知的。为解决这一问题，我们在PL/0编译程序中采用了回填技术，即产生跳转目标地址不明确的指令时，先保留这些指令的地址（code数组的下标），等到目标地址明确后再回过来将该跳转指令的目标地址补上，使其成为完整的指令。下表是if、while语句目标代码生成的模式。（L1，L2是代码地址）ifCthenSWhileCdoS11条件C的目标代码JPC--L1语句S的目标代码L1:...L1:条件C的目标代码JPC–L2语句S的目标代码JMPL1L2:...表2-2if-while语句目标代码生成模式相关过程（函数）有：gen()，其任务是把三个参数f、l、a组装成一条目标指令并存放于code数组中，增加CX的值，CX表示下一条即将生成的目标指令的地址。代码执行为了简单起见，我们假设有一个PL/0处理机，它能够解释执行PL/0编译程序所生成的目标代码。这个PL/0处理机有两类存贮、一个指令寄存器和三个地址寄存器组成。程序（目标代码）存贮称为code，由编译程序装入，在目标代码执行过程中保持不变，因此它可被看成是“只读”存贮器。数据存贮S组织成为一个栈，所有的算术运算均对栈顶元和次栈顶元进行（一元运算仅作用于栈顶元），并用结果值代替原来的运算对象。栈顶元的地址（下标）记在栈顶寄存器T中，指令寄存器I包含着当前正在解释执行的指令，程序地址寄存器P指向下一条将取出的指令。PL/0的每一个过程可能包含着局部变量，因为这些过程可以被递归地调用，故在实际调用前，无法为这些局部变量分配存贮地址。各个过程的数据区在存贮栈S内顺序叠起来，每个过程，除用户定义的变量外，还应当有它自己的内部信息，即调用它的程序段地址（返回地址）和它的调用者的数据区地址。在过程终止后，为了恢复原来程序的执行，这两个地址都是必须的。我们可将这两个内部值作为位于该过程数据区的内部式隐式局部变量。我们把它们分别称为返回地址（returnaddress）RA和动态链（dynamiclink）DL。动态链的头，即最新分配的数据区的地址，保存在某地址寄存器B内。因为实际的存贮分配是运行（解释）时进行的，编译程序不能为其生成的代码提供绝对地址，它只能确定变量在数据区内的位置，因此它只能提供相对地址。为了正确地存取数据，解释程序需将某个修正量加到相应的数据区的基地址上去。若变量是局部于当前正在解释的过程，则此基地址由寄存器B给出，否则，就需要顺着数据区的链逐层上去找。然而遗憾的是，编译程序只能知道存取路线的表的长度，同时动态链保存的则是过程活动的动态历史，而这两条存取路线并不总是一样。例如，假定有过程A，B，C，其中过程C的说明局部于过程B，而过程B的说明局部于过程A，程序运行时，过程A调用过程B，过程B则调用过程C，过程C又调用过程B，如下图所示：AABBBCACB12图2-1过程说明嵌套图过程调用图表示A调用B从静态的角度我们可以说A是在第一层说明的，B是在第二层说明的，C则是在第三层