《【教学课件】第二章PLO编译程序的实现.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章PLO编译程序的实现.ppt（82页珍藏版）》请在三一办公上搜索。
1、第二章 PL/O编译程序的实现,第一节 PL/O语言描述,第二节 PL/O编译程序的结构,第三节 PL/O编译程序的词法分析,第四节 PL/O编译程序的语法语义分析,第五节 PL/O编译程序的目标代码结构和代码生成,第六节 PL/O编译程序的语法错误处理,第七节 PL/O编译程序的目标代码解释执行时的存储分配,知识结构,2.1 PL/0语言描述,第二章 PL/0编译程序的实现,一.PL/0语言的语法描述图它由世界著名计算机科学家N.Wirth编写它是PASCAL语言的子集，功能简单，结构清晰，可读性强，具备了一般高级语言的必备部分它充分体现一个高级语言编译程序实现的基本方法和技术它的目标程序为
2、假想栈式计算机的汇编语言，与具体计算机无关,它的编译程序和目标程序的解释执行程序可用Pascal,C或其它语言书写，因此PL/0语言可在配备相应书写语言的任何机器上实现用语法图描述语法规则的优点是直观、易读在图2.1的语法图中用椭圆和圆圈中的英文字或字符表示终结符，用长方形内的中文字表示非终结符终结符：构成语言文法的单词，是语法成分的最小单位通常称第一个非终结符为文法的开始符号,图2.1(a)程序语法描述图,图2.1(b)分程序语法描述图,图2.1(c)语句语法描述图,图2.1(d)条件语法描述图,图2.1(e)表达式语法描述图,图2.1(f)项语法描述图,图2.1(g)因子语法描述图,画语法
3、图时要注意箭头方向和弧度，语法图中应该无直角，如图 2.1给出的PL/0语法描述图。沿语法图分析时不能走尖弧线,二.PL/O语言文法的EBNF表示1.BNF与EBNF的介绍：BNF（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它从语法上描 述程序设计语言的元语言。采用BNF就可说明哪些符号 序列是对于某给定语言在语法上有效的程序,BNF引入的符号：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符=定义为，该符号的左部由右部定义|或，为左部可由多个右部定义EBNF引入的符号：表示花括号内的语法成分可重复 表示方
4、括号内的语法成分为任选项()表示圆括号内的成分优先,一个用EBNF描述的例子：=+|-=0|1|2|3|4|5|6|7|8|9=+|-|0=1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9,2.PL/0语言文法的EBNF表示：程序=分程序.分程序=常量说明部分变量说明部分 过程说明部分语句常量说明部分=CONST常量定义部分，常 量定义；常量定义:=标识符无符号整数无符号整数=数字数字变量说明部分=VAR标识符，标识符；,常量定义:=标识符无符号整数无符号整数=数字数字变量说明部分=VAR标识符，标识符；标识符=字母字母|数字过程说明部分:=过程首部分程序；过程说明部
5、分过程首部:=PROCEDURE标识符；,语句:=赋值语句条件语句当型 循环语句过程调用语句读语句写语 句复合语句空赋值语句:=标识符:=表达式复合语句:=BEGIN语句；语句END条件:=表达式关系运算符表达式 ODD表达式,表达式:=项加法运算符 项项:=因子乘法运算符因子因子:=标识符无符号整数（表达式）,加法运算符:=乘法运算符:=*/关系运算符:=条件语句:=IF条件THEN语句过程调用语句:=CALL标识符当型循环语句:=WHILE条件DO语句读语句:=READ（标识符，标识符）,写语句:=WRITE（表达式，表达式）字母:=a|b|X|Y|Z数字:=0|1|8|9,2.2 PL/
6、O编译程序的结构,编译过程采用一趟扫描方式，以语法语义分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，就调用代码生成程序用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系,用出错处理程序对词法和语法语义分析遇到的错误给出在源程序中出错的位置和错误性质当源程序编译正确时，PL/O编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果,PL/O编译程序的结构图：,图 2.2(a)PL/0编译程序的结构图,图 2.2(b)PL/0的解释执行结构,PL
7、/O编译程序（包括主程序）是由18个嵌套及并列的过程 或函数组成:,PL/O编译程序的过程与函数定义层次结构图,图 2.3 PL/0编译程序过程与函数定义层次结构图,PL/O编译程序总体流程图,图 2.4 PL/0编译程序总体流程图,2.3 PL/O编译程序的词法分析,PL/O的词法分析过程GETSYM，如图2.5所示：,图 2.5 词法分析过程GETSYM,PL/O词法分析程序功能：为语法语义分析提供单词，把输入的字符串形式的源程序分割成一个个单词符号传递给语法语义分析,PL/O编译程序设置的三个全程变量：SYM：存放单词的类别,如beginsym,ident,numberID：存放用户所定
8、义的标识符的值NUM：存放用户定义的数,单词的种类：基本字（保留字）：BEGIN、END、IF、THEN等运算符：如+、-、*、/、：=、#、=、=等标识符：用户定义的变量名、常数名、过程名常数：如10、25、100等整数界符：如,、.、;、(、)等,词法分析程序GETSYM所要完成的任务：滤空格、识别保留字识别标识符、拼数拼复合词、输出源程序,取字符过程GETCH：,图 2.6 取字符过程GETCH,2.4 PL/O编译程序的语法语义分析,语法分析的任务：识别单词符号序列是否符合给定的语法规则PL/O编译程序的语法分析采用了自顶向下的递归子程序法：对应每个非终结符语法单元，编一个独立的处理过
9、程（或子程序）语法分析从读入第一个单词开始由非终结符程序即开始符出发，沿语法描述图箭头所指出的方向进行分析,当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序（就是翻译程序）再读取下一个单词继续分析遇到分支点时将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错,如果一个PL/O语言程序的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符“.”，这时就说所输入的程序是正确
10、的，对于正确的语法分析做相应的语义解释，生成目标代码,对PL/O语言进行语法分析时，各个非终结符语法单元所对应的分析过程之间存在的调用关系如图2.7所示（这个调用关系图也可称为PL/O语法的依赖图）：,图 2.7 PL/0语法调用关系图,流程图如图2.8所示：,程序BLOCK过程的流程图：,（1）说明部分的处理：对每个过程说明的对象（变量，常量和过程）造名字表。填写所在层次，标识符的属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成名字表是全程量一维数组TABLE。TX为索引表的指针，表中的每个元素为记录型数据。表中的LEV表示层次，DX表示给本层局部
11、变量分配的相对存贮位置，每说明完一个变量后DX加1,例如，一个PL/O语言过程说明部分的片段为：CONST A=35,B=49;VAR C,D,E;PROCEDURE P;VAR G对常量、变量和过程说明分析后，得到TABLE表中的信息如表2.2所示：,（2）过程体的处理：程序的主体是由语句构成的处理完过程的说明后就处理由语句组成的过程体，从语法上对语句逐句分析当语法正确时就生成相应语句功能的目标代码当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则调用出错处理程序,f功能码l层次差a根据不同的指令有
12、所区别,PL/O编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类PCODE指令代码，它不依赖任何实际计算机指令格式如下：,2.5 PL/O编译程序的目标代码结构和代码生成,八条目标指令：（a为其他值均为非法指令）,编译程序的目标代码是在分析程序体时生成的，在处理说明部分时一般不生成目标代码，而当分析程序体中的每个语句时，当语法正确则调用目标代码生成过程以生成与PL/O语句等价功能的目标代码，直到编译正常结束,PL/0语言的代码生成是由过程GEN完成。GEN有三个参数，分别代表目标代码的功能码，层差和位移量。生成的代码顺序放在数组CODE中。CODE为一维数组，数组元素为记录型数
13、据。每一个记录就是一条目标指令。CX为指令的指针，由0开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后,PL/O源程序和对应的目标程序的清单：,0jmp 0 88是主程序入口1jmp 0 22是P过程入口2int 0 3在运行栈中申请3个栈空间3lod 1 3将变量取至栈顶4lit 0 10将常量10取到栈顶5opr 0 2次栈顶与栈顶相加，结果放在次栈顶6sto 1 4将栈顶的内容放入变量C的单元中7opr 0 0过程调用结束后，返回调用点8int 0 5在运行栈中申请5个栈空间,Run ploInput file?TESTList object code?Yco
14、nst a=10;var b,c;procedure p;begin c:=b+a;end;,9opr 0 16从命令行读入输入置于栈顶10sto 0 3将栈顶值存入变量11lod 0 3将变量取至栈顶12lit 0 0将常值0进栈13opr 0 9 次栈顶与栈顶是否不等结果放入 次栈顶14jpc 0 24当栈顶内容为非真时，转向2415cal 0 2调用入口地址2 16lit 0 2将常量2取到栈顶17lod 0 4将变量取至栈顶18opr 0 4次栈顶与栈顶相乘放入次栈顶19opr 0 14 栈顶输出到屏幕20opr 0 15屏幕输入换行21opr 0 16从命令行读入一个输入到栈顶22s
15、to 0 3将栈顶的内容送入某变量单元中23jmp 0 11无条件转向地址1124opr 0 0过程调用结束后，返回调用点,begin read(b);while b#0 do begin call p;write(2*c);read(b);endend.start plo?2 24?4 28?0End plo,1.PL/O编译程序对语法错误两种处理方法：对于易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号对于难于校正的错误，跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。具体做法是：当语法分析进入或退出一个语法单
16、元的处理程序时，调用一个测试程序TEST，其流程图如2.9所示：它的功能是检查当前单词是否属于该语法单元的开始符号集合或后跟符号集合,2.6 PL/O编译程序的语法错误处理,表 2.3 PL/0文法非终结符的开始符号与后继符号集合表,*注：表2.3中rop表示关系运算符集合,如=，=，=。,TEST测试过程三个参数的含义：S1当语法分析进入或退出某一语法单元时当前单词符号应属于的集合，它可能是一个语法单元开始符号的集合或后继符号的集合S2在某一出错状态时，可恢复语法分析继续正常工作的补充单词符号集合n整型数，出错信息编号,2.PL/O编译程序对语义错误如标识符未加说明就引用，或虽经说明，但引用
17、与说明的属性不一致。这时只给出错误信息和出错的位置，编译工作可继续进行,3.PL/O编译程序对运行错如溢出、越界等，只能在运行时发现，由于PL/O编译程序的功能限制无法指出运行时所发生的错误在源程序的对应位置,4.PL/O语言的出错信息表：出错编号出错原因1：常数说明中的“=”写成“=”。2：常数说明中的“=”后应是数字。3：常数说明中的标识符后应是“=”。4：const,var,procedure后应为标识符。5：漏掉了，或；。6：过程说明后的符号不正确(应是语句开始符，或过程 定义符)。7：应是语句开始符。8：程序体内语句部分的后跟符不正确。,出错编号出错原因9：程序结尾丢了句号.。10：
18、语句之间漏了；。11：标识符未说明。12：赋值语句中，赋值号左部标识符属性应是变量。13：赋值语句左部标识符后应是赋值号=。14：call后应为标识符。15：call后标识符属性应为过程。16：条件语句中丢了then。17：丢了end“或；。18：while型循环语句中丢了do。,出错编号出错原因19：语句后的符号不正确。20：应为关系运算符。21：表达式内标识符属性不能是过程。22：表达式中漏掉右括号)。23：因子后的非法符号。24：表达式的开始符不能是此符号。31：数越界。32：read语句括号中的标识符不是变量。,存储区只需以数组CODE存放的只读目标程序和运行时的数据区SS是由解释程序
19、定义的一维整型数组由于PL/O语言的目标程序是一种假想的栈式计算机的汇编语言，现仍用Pascal语言解释执行,2.7 PL/O编译程序的目标代码解释执行时的存储分配,解释执行时的数据空间S为栈式计算机的存储空间遵循后进先出规则，对每个过程（包括主程序）当被调用时，才分配数据空间，退出过程时，所分配的数据空间被释放,解释程序定义了4个寄存器：I指令寄存器。存放当前正在解释的一条目标指令P程序地址寄存器。指向下一条要执行的目标程序的地址（相当目标程序CODE数组的下标）,T栈顶寄存器。指向当前栈中最新分配的单元（T也是数组S的下标）。每个过程当它被调用时，给它分配的数据空间（下边称数据段）可分成两
20、部分：静态部分：包括变量存放区和三个联系单元动态部分：作为临时工作单元和累加器用。需要时随时分配，用完后立即释放B基址寄存器。指向每个过程被调用时，在数据区S中给该过程分配的数据段起始地址，称基地址,当过程被调用时，在栈顶分配三个联系单元，这三个联系单元存放的内容分别为：SL静态链：指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址DL动态链：指向调用该过程前正在运行过程的数据段基地址RA返回地址：记录调用该过程进目标程序的断点，即当时的程序地址寄存器P的值。也就是调用过程指令的下一条指令的地址,PL/O编译程序给每个过程定义的变量在数据段内分配的相对位置是从3开始顺序增加。前面的
21、三个单元为上面指出的联系单元下面举例说明解释执行进数据区的变化过程，图2.10给出示意图：,图2.10 运行时数据栈S的变化状态,具体的过程调用和结束，对上述寄存器及3个联系单元的填写和恢复由下列目标指令完成（1）INT 0 A每个过程目标程序的入口都有这样一条指令，用以完成开辟数据段的工作A域的值指出数据段的大小，即为局部变量个数+3（联系单元个数为3）由编译程序的代码生成给出开辟数据段的结果是改变栈顶寄存器T的值，即T:=T+A,（2）OPR 0 0是每个过程出口处的一条目标指令用以完成该过程运行结束后释放数据段的工作，即退栈工作恢复调用该过程前正在运行的过程（或主程序）的数据段基地址寄存
22、器的值和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行,（3）CAL L A为调用过程的目标指令L为层次差，它是寻找静态链的依据。在解释程序中由BASE（L）函数计算求得，L为参数，实参为所给层差A为被调用过程的目标程序入口CAL指令还完成填写静态链、动态链、返回地址，并将被调用过程的基地址值送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行,【本章小结】本章是一个编译程序的实例，通过认真阅读PL/0语言编译程序文本，加深理解一般编译程序构造的整体结构和实现的步骤，对词法、语法、语义分析、代码生成及符号表管理每个过程的
23、功能和相互联系及实现技术。联系实际做好作业和实验，巩固知识。,实验要求:1.扩充条件语句条件语句:=IF条件THEN语句ELSE语句2.扩充重复语句:=REPEAT；UNTIL条件3.对PL/0语言扩充整形数组（有条件的同学尽量做此题）。读者自己设计语法并给出用语法图和EBNF描述也可用其它语言改写PL/0编译程序如用C语言或Java语言改写PL/0编译程序；,实验报告内容:对扩充部分用语法图和EBNF描述；对原PL/0语言编译程序文本中程序变动部分的说明；所用测试用例包括正确的测试用例和错误的测试用例；实验体会和建议。建议：为了引起读者对阅读PL/0编译程序文本的兴趣，建议用本节教材文本中的
24、PL/0源程序和目标程序的对应关系为例，阅读PL/0编译程序文本，并总结词法、语法、语义分析和目标代码生成之间的关系。其方法是：,先用PL/0语言的语法图和EBNF检查例子的语言是否合乎语法规则。阅读PL/0源程序文本。方法是从主程序开始，例中遇到什么语法成分就转到相应的语法处理过程。遇到语义处理造名字表或生成目标代码时，用纸记录下它们操作的结果，以及名字表table和目标代码code的信息变化，并分析这些变化的目的。例如，对过程入口的拉链返填方法。,遇到看不懂的地方再回头看教材文本和注释中的说明和解释。检查你所得到的代码是否与例中的相同，若不同则找出原因。,编译原理第二章习题 第1题:PL/
25、0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。,第2题:若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b=10时运行栈的布局示意图。,var x,y;procedure p;var a;procedure q;var b;begin(q)b=10;end(q);procedure s;var c,d;procedure r;var e,f;begin(r)call q;end(r);begin(s)call r;end(s);begin(p)call s;end(
26、p);begin(main)call p;end(main).,第3题：写出题2中当程序编译到r的过程体时的名字表table的内容。,第4题：指出栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途。,第5题：PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。INT 0 A OPR 0 0 CAL L A,第6题：给出对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述。(1)扩充条件语句的功能使其为：if条件then语句else语句(2)扩充repeat语句为：repeat语句；语句until条件,第2章作业题P30：1.5.6.,
