编译原理—pl0实验报告

PL/0实验报告

课程名称 编译原理 题目名称 PL/0编译程序 学生学院 计算机科学与技术学院 专业班级

学 号 学生姓名 班内序号

山东理工大学实验报告纸 第 1 页

姓名：蔡鹏飞 计算机 院_11_级02班同组者 成 绩_________

室温： 气压： 课程名称： 编译原理 教师签字 实验项目 PL/0编译程序的分析 编号( 1 ) 指导教师 鞠传香 1.熟悉pl/0语言并能编写小程序 实 验 目 的 2.掌握pl/0编译程序的编译过程(词法分析、语法分析、语义分析等) 实验仪器（编号）PC机、VC++ 材料、工具 （原理概述） pl/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类pcode解释程序解释执行生成的类pcode代码。 PL/0语言文法的EBNF表示 EBNF表示的符号说明。 〈 〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。 ∷= ：该符号的左部由右部定义，可读作'定义为'。 | ：表示'或'，为左部可由多个右部定义。 { } ：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。 如：{*}表示*重复任意次，{*}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表示 PL/0语言文法的EBNF表示为： 〈程序〉∷=〈分程序〉． 〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉 〈常量说明部分〉∷=CONST〈常量定义〉 {，〈常量定义〉}； 〈常量定义〉∷=〈标识符〉=〈无符号整数〉 〈无符号整数〉∷=〈数字〉{〈数字〉} 〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； 〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉} 〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}； 〈过程首部〉∷=PROCEDURE〈标识符〉； 〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉| 〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉 〈赋值语句〉∷=〈标识符〉∶=〈表达式〉 〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END 〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉 〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')' 〈加法运算符〉∷=+|- 〈乘法运算符〉∷=*|/ 〈关系运算符〉∷=#|=|＜|＜=|＞|＞= 〈条件语句〉∷=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) const var procedure ident call . ; if begin while 语句 条件 表达式 项 因子 ident call begin if while odd + - ( ident number + - ( ident number ident number ( ident number ( . ; end then do . ; ) R end then do . ; ) R + - end then do . ; ) R + - * / end then do 注：表中R代表六个关系运算符。 不难证明，PL/0语言属于LL（1）文法。（证明从略。） 以下是我们给出如何结合语法图编写（递归下降）语法分析程序的一般方法。假定图S所对应的程序段为T（S），则： （1） 用合适的替换将语法约化成尽可能少的单个图； （2） 将每一个图按下面的规则（3）-（7）翻译成一个过程说明； （3） 顺序图对应复合语句： 对应：begin T(S1); T(S2); ...; T(Sn) end （4） 选择： 对应：case语句或者条件语句： case ch of if ch in L1 then T(S1) else L1: T(S1); if ch in L2 then T(S2) else L2: T(S2); 或 ... ... if ch in Ln then T(Sn) else Ln: T(Sn); error 其中Li∈FIRST（Si），ch为当前输入符号。（下同） （5） 循环 对应：while ch in L do T(S) （6） 表示另一个图A的图： 对应：过程调用A。 （7） 表示终结符的单元图： 对应：if ch == x then read(ch) else error 相关过程有： block(), constdeclaration(), vardeclaration(), statement(), condition(), expression_r(), term(), factor()等。 语义分析 PL/0的语义分析主要进行以下检查： （1） 是否存在标识符先引用未声明的情况； （2） 是否存在己声明的标识符的错误引用； （3） 是否存在一般标识符的多重声明 代码生成 PL/0编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。最终我们要“运行”该目标码。为了使我们的编译程序保持适当简单的水平，不致陷入与本课程无关的实际机器的特有性质的考虑中去，我们假想有台适合PL/0程序运行的计算机，我们称之为PL/0处理机。PL/0处理机顺序解释生成的目标代码，我们称之为解释程序。注意：这里的假设与我们的编译概念并不矛盾，在本课程中我们写的只是一个示范性的编译程序，它的后端无法完整地实现，因而只能在一个解释性的环境下予以模拟。从另一个角度上讲，把解释程序就看成是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 上述指令的格式由三部分组成： F 其中，f, l, a的含义见下表： F INT LIT LOD STO CAL L ——— ——— 层次差 层次差 层次差 a 常 量 常 量 数据地址 数据地址 程序地址 L A JMP JPC OPR ——— ——— ——— 表2-1 PL/0 处理机指令 程序地址 程序地址 运算类别 上表中，层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址。 PL/0的编译程序为每一条PL/0源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译较简单。 如赋值语句X := Y op Z（op为某个运算符），将被翻译成下面的目标代码序列：（设指令计数从第100号开始） No. 100 101 102 103 f LOD LOD OPR STO L Level_diff_Y Level_diff_Z —————— Level_diff_X a Addr_Y Addr_Z op Addr_X 而对if和while语句稍繁琐一点，因为此时要生成一些跳转指令，而跳转的目标地址大都是未知的。为解决这一问题，我们在PL/0编译程序中采用了回填技术，即产生跳转目标地址不明确的指令时，先保留这些指令的地址（code数组的下标），等到目标地址明确后再回过来将该跳转指令的目标地址补上，使其成为完整的指令。下表是if、while语句目标代码生成的模式。（L1，L2是代码地址） if C then S 条件C的目标代码 JPC -- L1 语句S的目标代码 L1: ... While C do S L1: 条件C的目标代码 JPC – L2 语句S的目标代码 JMP L1 L2: ... 表2-2 if-while语句目标代码生成模式 相关过程（函数）有：gen()，其任务是把三个参数f、l、a组装成一条目标指令并存放于code数组中，增加CX的值，CX表示下一条即将生成的目标指令的地址。 代码执行 为了简单起见，我们假设有一个PL/0处理机，它能够解释执行PL/0编译程序所生成的目标代码。这个PL/0处理机有两类存贮、一个指令寄存器和三个地址寄存器组成。程序（目标代码）存贮称为code，由编译程序装入，在目标代码执行过程中保持不变，因此它可被看成是“只读”存贮器。数据存贮S组织成为一个栈，所有的算术运算均对栈顶元和次栈顶元进行（一元运算仅作用于栈顶元），并用结果值代替原来的运算对象。栈顶元的地址（下标）记在栈顶寄存器T中，指令寄存器I包含着当前正在解释执行的指令，程序地址寄存器P指向下一条将取出的指令。 PL/0的每一个过程可能包含着局部变量，因为这些过程可以被递归地调用，故在实际调用前，无法为这些局部变量分配存贮地址。各个过程的数据区在存贮栈S内顺序叠起来，每个过程，除用户定义的变量外，还应当有它自己的内部信息，即调用它的程序段地址（返回地址）和它的调用者的数据区地址。在过程终止后，为了恢复原来程序的执行，这两个地址都是必须的。我们可将这两个内部值作为位于该过程数据区的内部式隐式局部变量。我们把它们分别称为返回地址（return address）RA和动态链（dynamic link）DL。动态链的头，即最新分配的数据区的地址，保存在某地址寄存器B内。 因为实际的存贮分配是运行（解释）时进行的，编译程序不能为其生成的代码提供绝对地址，它只能确定变量在数据区内的位置，因此它只能提供相对地址。为了正确地存取数据，解释程序需将某个修正量加到相应的数据区的基地址上去。若变量是局部于当前正在解释的过程，则此基地址由寄存器B给出，否则，就需要顺着数据区的链逐层上去找。然而遗憾的是，编译程序只能知道存取路线的表的长度，同时动态链保存的则是过程活动的动态历史，而这两条存取路线并不总是一样。 例如，假定有过程A，B，C，其中过程C的说明局部于过程B，而过程B的说明局部于过程A，程序运行时，过程A调用过程B，过程B则调用过程C，过程C又调用过程B，如下图所示： A A B BB C A C B 图2-1 过程说明嵌套图 过程调用图 表示A调用B 从静态的角度我们可以说A是在第一层说明的，B是在第二层说明的，C则是在第三层说明的。若在B中存取A中说明的变量a，由于编译程序只知道A，B间的静态层差为1，如果这时沿着动态链下降一步，将导致对C的局部变量的操作。为防止这种情况发生，有必要设置第二条链，它以编译程序能明了的方式将各个数据区连接起来。我们称之为静态链（static link）SL。这样，编译程序所生成的代码地址是一对数，指示着静态层差和数据区的相对修正量。下面我们给出的是过程A、B和C运行时刻的数据区图示： DL RA SL A的变量 B的变量 C的变量 B的变量 有了以上认识，我们就不难明白PL/0源程序的目标代码是如何被解释执行的。以语句X ：= Y op Z为例，（该语句的目标代码序列我们己在节给出），PL/0处理机解释该指令的“步骤”如下： step 1, S[++T] ← S[base(level_diff_Y) + addr_Y]; } } 相关过程：test(), inset(), createset, uniteset(), error(). 符号表管理 为了组成一条指令，编译程序必须知道其操作码及其参数（数或地址）。这些值是由编译程序本身联系到相应标识符上去的。这种联系是在处理常数、变量和过程说明完成的。为此，标识符表应包含每一标识符所联系的属性；如果标识符被说明为常数，其属性值为常数值；如果标识符被说明成变量，其属性就是由层次和修正量（偏移量）组成的地址；如果标识符被说明为过程，其属性就是过程的入口地址及层次。 常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0机中，每个变量占一个存贮单元）。开始编译一个过程时，要对数据单元的下标dx赋初值，表示新开辟一个数据区。dx的初值为3，因为每个数据区包含三个内部变量RA，DL和SL。 相关过程：enter()，该函数用于向符号表添加新的符号，并确定标识符的有关属性。 说明 （1） 每一个分程序（过程）被编译结束后，将列出该部分PL/0程序代码。这个工作由过程listcode()完成。注意，每个分程序（过程）的第一条指令未被列出。该指令是跳转指令。其作用是绕过该分程序的说明部分所产生的代码（含过程说明所产生的代码）。 （2） 解释程序作为PL/0编译程序的一个过程，若被编译的源代码没有错误，则编译结束时调用这个过程。 （3） PL/0语言没有输出语句。解释程序按执行次序，每遇到对变量的赋值就输出其值。 PL/0语言源程序 下面我们给出一个PL/0语言写的二数相乘、除并求最大公约数的算法： const m = 7, n = 85; var x, y, z, q, r; procedure multiply; var a, b; begin a := x; b := y; z := 0; while b > 0 do begin if odd b then z := z + a; a := 2 * a; b := b / 2; end end; procedure divide; var w; begin r := x; q := 0; w := y; while w > y do begin q := 2 * q; w := w / 2; if w <= r then begin r := r - w; q := q + 1; end; end end; procedure gcd; var f, g; begin f := x; g := y; while f <> g do begin if f < g then g := g – f; if g < f then f := f – g; end end; begin x := m; y := n; call multiply; x := 25; y := 3; call divide; x := 34; y := 36; call gcd; end. （数据记录表及处理） 生成的代码（片段） 前面我们给出了PL/0语言写的一段程序，其中乘法过程经过编译程序产生以下代码： 2 INT 0 5 -- allocate storage a := x 3 LOD 1 3 -- x 4 STO 0 3 -- a b := y 5 LOD 1 4 -- y 6 STO 0 4 -- b z := 0 7 LIT 0 0 -- 0 8 STO 1 5 -- z b > 0 9 LOD 0 4 -- b 10 LIT 0 0 -- 0 11 OPR 0 12 -- > 12 JPC 0 29 -- if b <= 0 then goto 29 odd(b) 13 LOD 0 4 -- b 14 OPR 0 6 -- odd 15 JPC 0 20 -- if not(odd(b)) goto 20 if 16 LOD 1 5 -- z while z := z + a 17 LOD 0 3 -- a 18 OPR 0 2 -- + 19 STO 1 5 -- z a := 2 * a 20 LIT 0 2 -- 2 21 LOD 0 3 -- a 22 OPR 0 4 -- * 23 STO 0 3 -- a 24 LOD 0 4 -- b b := b / 2 25 LIT 0 2 -- 2 26 OPR 0 2 -- / 27 STO 0 4 -- b 28 JMP 0 9 -- goto 9 29 OPR 0 0 -- return PL/0源程序的扩充 （1）扩充赋值运算:+=,-=.此功能扩充只需在语句分析里面进行增加如下程序： if(SYM==BECOMES||SYM==PLUSBECOMES||SYM==MINUSBECOMES){ if (SYM==BECOMES) { GetSym(); EXPRESSION(FSYS,LEV,TX); } else if(SYM==PLUSBECOMES||SYM==MINUSBECOMES) { GEN(LOD,LEV-TABLE[i].,TABLE[i].; if(SYM==PLUSBECOMES){ GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,2); } else if(SYM==MINUSBECOMES){ GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,3); } } if (i!=0) GEN(STO,LEV-TABLE[i].,TABLE[i].; } （2）增加条件语句的ELSE子ELSE语句的语法语义分析程序： GetSym(); CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM),FSYS),LEV,TX); if (SYM==THENSYM) GetSym(); else Error(16); CX1=CX; GEN(JPC,0,0); case IFSYM: STATEMENT(FSYS,LEV,TX); CX2=CX; GEN(JMP,0,CX+1); CODE[CX1].A=CX; if (SYM==SEMICOLON) GetSym(); if(SYM==ELSESYM) { GetSym(); STATEMENT(FSYS,LEV,TX); CODE[CX2].A=CX; } //add the statement of ELSE else STATEMENT(FSYS,LEV,TX); break; （实验结论及问题讨论） 这次实验给我们带来的收获都是受益匪浅的，它让我对编译原理的词法分析、语法语义分析等都有了更进一步的了解。一个算法的好坏决定了一段程序的好坏，它会影响它的运行时间及效率，而一种思想对一个程序来讲也起着至关重要的作用，那一行行代码不仅仅只是一些简单的字符，它还包含了设计者的理念。我觉得我们学习就是要把原理搞清楚，这样才能把思想与理念运用到更大的层面上去，通过实验我也深深体会到了这门课的重要性，也体会到了杨老师对我们的良苦用心和寄予的厚望。过程是艰辛的，但结果又是喜人的，相信这门课会对我的将来起到至关重要的作用。