第2章PL0编译程序的实现

1、 PL/0语言简介语言简介 PL/0是一个非常小的程序设计语言，是一个非常小的程序设计语言，它是由它是由Pascal的发明人的发明人Niklaus Wirth所定所定义的。它是义的。它是Pascal的一个子集，有嵌套的的一个子集，有嵌套的过程，但过程不能有参数，没有函数，没过程，但过程不能有参数，没有函数，没有分支语句，没有有分支语句，没有for 循环，条件语句不支循环，条件语句不支持持else，只有一个整数数据类型。，只有一个整数数据类型。 PL/0编译程序编译程序 PL/0编译程序编译程序 PL/0 语言程序语言程序 类类 pcode 代吗代吗源语言源语言(PL/0)目标语言目标语言(类类

2、 pcode)实现语言（实现语言（pascal) PL/0 类类 pcode pascal PL/0PL/0编译程序编译程序类类 pcodepcode解释解释程序程序类类 pcode代码代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架PL/0语言语言PL/0PL/0程序示例程序示例PL/0PL/0的语法描述图的语法描述图PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示PL/0PL/0语言：语言：PASCALPASCAL语言的子集语言的子集 PL/0程序示例程序示例 CONST A=10; CONST A=10; （* * 常量说明部分常量

3、说明部分 * *） VAR B,C; VAR B,C; （* * 变量说明部分变量说明部分 * *） PROCEDURE P; PROCEDURE P; （* * 过程说明部分过程说明部分 * *） VAR D;VAR D; PROCEDURE Q; PROCEDURE Q; VAR X; VAR X; BEGIN BEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 WHILE X#0 DO CALL P; DO CALL P; END; END; BEGIN BEGIN WRITE(D); WRITE(D); CALL Q; CALL Q; END;

4、END; BEGIN BEGIN CALL P; CALL P; END. END.Q的过程体的过程体p的过程体的过程体主主程序程序体体程序程序分程序分程序.内的文字表示非终结符内的文字表示非终结符或内的文字或符号表示终结符内的文字或符号表示终结符分程序Constidentnumber=,;Varidentprocedureident分程序;语句,;语句ident:=callident;表达式.begin语句语句end条件语句ifthen条件语句Whiledo()readident()write,表达式条件表达式表达式表达式odd.=#=+-表达式项项.+-identnumber表达式因子.(

5、)*因子项因子/.1、EBNF表示的符号说明 ：是非终结符 ：左部由右部定义 | ：表示或 ：表示为可以重复部分 ：表示为任选项 ( )：表示成分优先2、PL/0 语言文法的EBNF表示为： CONST , = VAR, | ; procedure | := begin;end |odd +|- | ( ) + | - * | / != | | = Ifthen Call WhileDO Read(， ) Write(， ) a|b| X|Y|Z 0|1|2|8|9 3、PL/0编译程序是用PASCAL语言编写，可在任何配有PASCAL编译系统的计算机上运行。PL/0Compiler源文本PA

6、SCALCompilerPL/0Compiler目标文本PL/0源程序PL/0Compiler目标文本PL/0目标程序词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序PL/0编译程序的总体设计编译程序的总体设计其编译过程采用其编译过程采用一趟扫描方式一趟扫描方式以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过程过程，当语法分，当语法分析需要读单词时就调用词法分析程序，而当语法析需要读单词时就调用

7、词法分析程序，而当语法、语义语义分析正确，需要生成相应的目标代码时，则调用代码生分析正确，需要生成相应的目标代码时，则调用代码生成程序。成程序。表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信息的登录信息的登录与查找与查找。出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇到的错误给出语义分析遇到的错误给出在源程序中在源程序中出错的位置出错的位置和与和与错误错误 性质有关性质有关的编号，并进的编号，并进行错误恢复。行错误恢复。 2.3 PL/0编译程序的词法分析编译程序的词法分析识别的单词：识别的单词：保留字或关键字：如：保留字或关键字：如：BEG

8、INBEGIN、 ENDEND、 IFIF、 THENTHEN等等运算符运算符： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等标识符标识符： 用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名常数常数： 如：如：1010、2525、100100等整数等整数界符界符： 如：如：,、. . 、; ; 、( ( 、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：读源程序（读源程序（getch)getch)滤空格滤空格识别识别保留字保留字识别标识符识别标识符拼数拼数识别单字符单词识别单字符单词拼双字符单词拼双字符单词词法分

9、析过程词法分析过程:GETSYM:GETSYM框图（见教材图框图（见教材图2.52.5）程序（程序（ procedure getsymprocedure getsym）当识别到标识符时先查当识别到标识符时先查保留字保留字表表使用状态转换图实现词法分析程序的设计使用状态转换图实现词法分析程序的设计方法方法词法分析程序的设计词法分析程序的设计-使用状态转换图实现使用状态转换图实现表示表示状态状态，对应每个状态编一段程序，对应每个状态编一段程序，每个状态每个状态调用调用取字符取字符程序，根据当前字程序，根据当前字符符转到不同的状态，并做相应操作。转到不同的状态，并做相应操作。表示表示终态终态，已，已

10、识别出一个识别出一个单词单词。1 12 23 35 514141313121210109 97 78 86 64 41111空格空格字母字母字母数字字母数字非字母数字非字母数字数字数字数字数字非数字非数字：= = = =非非= =, + - ( 2.4 2.4 PL/0PL/0编译程序语法语义分析编译程序语法语义分析自顶向下自顶向下的语法分析的语法分析递归子程递归子程序法序法 程序程序分程序分程序.constidentnumbervaridentprocedureident分程序分程序语句语句分程序分程序identreadend语句语句表达式表达式：=begin语句语句语句语句)(ident,

11、 自顶向下的语法分析自顶向下的语法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. . . VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 为文法的为文法的开始符号开始符号，以开，以开始符号作为根结始符号作为根结点构造一棵倒挂点构造一棵倒挂着的语法树。着的语法树。递归子程序法递归子程序法递归子程序法递归子程序法：对应对应每个非终结符每个非终结符语法单元，编一个独立的语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符

12、由非终结符 （即开始符）出发，沿语法描述图即开始符）出发，沿语法描述图箭头箭头所指出的方向进行分析。当遇到非终结符时，则所指出的方向进行分析。当遇到非终结符时，则调用调用相应相应的的处理过程处理过程，从语法描述图看，也就进入了一个语法单元，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是当遇到描述图中是终结符终结符时，则判断当前读入的单词是否时，则判断当前读入的单词是否与图中的终结符与图中的终结符相匹配相匹配，若匹配，再读取下一个单词继续，若匹配，再读取下一个单词继续分析。遇到分析。遇到

13、分支点分支点时，将当前的单词与分支点上多个终结时，将当前的单词与分支点上多个终结符符逐个相比较逐个相比较，若都不匹配时可能是进入下一个非终结符，若都不匹配时可能是进入下一个非终结符语法单位或是出错。语法单位或是出错。例：如何用递归子程序法实现表达式的语例：如何用递归子程序法实现表达式的语法分析法分析项项表达式表达式+-项项+-项项 因子因子 因子因子 */语法图语法图因子的语法图因子的语法图因子因子identnumber(表达式表达式)表达式的表达式的EBNF表达式表达式=+|-+|-项项 （+|-+|-）项）项 项项=因子因子 （* *|/|/）因子）因子 因子因子=标识符标识符| |无符号

14、整数无符号整数|（表达式表达式）表达式表达式的的递归子程序递归子程序实现实现procedure procedure exprexpr; ;beginbegin if sym in if sym in plusplus, , minusminus then then begin begin getsym; getsym; termterm; ; end end else else termterm; ; while sym in while sym in plusplus, , minusminus do do begin begin getsym; getsym; termterm; ; en

15、d endend;end; 项项的的递归子程序递归子程序实现实现procedure procedure termterm; ;beginbegin factorfactor; ; while sym in while sym in timestimes, , slashslash do do begin begin getsym; getsym; factorfactor; ; end endend;end;因子因子的的递归子程序递归子程序实现实现procedure procedure factorfactor; ;begin begin if sym if sym identident th

16、en then begin begin if sym if sym numbernumber then then begin begin if sym = if sym = ( ( then then begin begin getsym;getsym; exprexpr; ; if sym = if sym = ) ) then then getsym getsym else error else error end end else error else error end end end end end; end; 程序程序 pl0分程序分程序 block语句语句 statement条件

17、条件 condition表达式表达式expression项项 term因子因子 factor语语法法调调用用关关系系图图编译程序总体流程图编译程序总体流程图启动启动置初值置初值调用G E TSYM取 单 词调用G E TSYM取 单 词调用B L OCK过 程调用B L OCK过 程当前单词当前单词是否为源程序结束符是否为源程序结束符.？.？出错出错源程序中源程序中是否有错误？是否有错误？调用解释过程I N T E R P RET调用解释过程I N T E R P RET解释执行目标程序解释执行目标程序打印错误打印错误结束结束N NY YY YN N 目标代码类目标代码类pcode目标代码类目

18、标代码类pcodepcode是一种假想栈式计算机的汇编语言。是一种假想栈式计算机的汇编语言。指令格式：指令格式：f l af l af f功能码功能码l l层次差层次差 （标识符引用层减去定义层）（标识符引用层减去定义层）a a根据不同的指令有所区别根据不同的指令有所区别LIT 0 aLIT 0 a将常数值取到栈顶，将常数值取到栈顶，a a为常数值为常数值LOD l aLOD l a将变量值取到栈顶，将变量值取到栈顶，a a为偏移量，为偏移量，l l为层差为层差STO l aSTO l a将栈顶内容送入某变量单元中，将栈顶内容送入某变量单元中，a a为偏移量，为偏移量，l l为层差为层差CAL

19、 l aCAL l a调用过程，调用过程，a a为过程地址，为过程地址，l l为层差为层差INT 0 aINT 0 a在运行栈中为被调用的过程开辟在运行栈中为被调用的过程开辟a a个单元的数据区个单元的数据区JMP 0 aJMP 0 a无条件跳转至无条件跳转至a a地址地址JPC 0 aJPC 0 a条件跳转，当栈顶布尔值非真则跳转至条件跳转，当栈顶布尔值非真则跳转至a a地址，否则顺地址，否则顺序执行序执行OPR 0 OPR 0 0 0过程调用结束后过程调用结束后, ,返回调用点并退栈返回调用点并退栈OPR 0 1OPR 0 1栈顶元素取反栈顶元素取反OPR 0 2OPR 0 2次栈顶与栈顶

20、相加，退两个栈元素，结果值进栈次栈顶与栈顶相加，退两个栈元素，结果值进栈OPR 0 3OPR 0 3次栈顶减去栈顶，退两个栈元素，结果值进栈次栈顶减去栈顶，退两个栈元素，结果值进栈OPR 0 4OPR 0 4次栈顶乘以栈顶，退两个栈元素，结果值进栈次栈顶乘以栈顶，退两个栈元素，结果值进栈OPR 0 5OPR 0 5次栈顶除以栈顶，退两个栈元素，结果值进栈次栈顶除以栈顶，退两个栈元素，结果值进栈OPR 0 6OPR 0 6栈顶元素的奇偶判断，结果值在栈顶栈顶元素的奇偶判断，结果值在栈顶OPR 0 7OPR 0 7OPR 0 8OPR 0 8次栈顶与栈顶是否相等，退两个栈元素，结果值进栈次栈顶与栈

21、顶是否相等，退两个栈元素，结果值进栈OPR 0 9OPR 0 9次栈顶与栈顶是否不等，退两个栈元素，结果值进栈次栈顶与栈顶是否不等，退两个栈元素，结果值进栈OPR 0 10OPR 0 10次栈顶是否小于栈顶，退两个栈元素，结果值进栈次栈顶是否小于栈顶，退两个栈元素，结果值进栈OPR 0 11OPR 0 11次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈OPR 0 12OPR 0 12次栈顶是否大于栈顶，退两个栈元素，结果值进栈次栈顶是否大于栈顶，退两个栈元素，结果值进栈OPR 0 13OPR 0 13次栈顶是否小于等于栈顶，退两个栈元素，结果值

22、进栈次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈OPR 0 14OPR 0 14栈顶值输出至屏幕栈顶值输出至屏幕OPR 0 15OPR 0 15屏幕输出换行屏幕输出换行OPR 0 16OPR 0 16从命令行读入一个输入置于栈顶从命令行读入一个输入置于栈顶指指令令功功能能表表 const a=10; const a=10;var b,c;var b,c;procedure p;procedure p; beginbegin c:=b+a; c:=b+a; end; end;beginbegin read(b); read(b); while while b#0b#0 do do begin

23、 begin call p; call p; write(2 write(2* *c);c); read(b); read(b); end endend.end.( 0) jmp 0 8 ( 0) jmp 0 8 转向转向主程序入口主程序入口( 1) jmp 0 2 ( 1) jmp 0 2 转向转向过程过程p p入口入口( 2)( 2) int 0 3int 0 3 过程过程p p入口入口, ,为过程为过程p p开辟空间开辟空间( 3) lod ( 3) lod 1 1 3 3 取变量取变量b b的值到栈顶的值到栈顶( 4) lit 0 10 ( 4) lit 0 10 取常数取常数1010到栈顶到栈顶( 5) opr 0 2 ( 5) opr 0 2 次栈顶与栈顶相加次栈顶与栈顶相加( 6) sto ( 6) sto 1 1 4 4 栈顶值送变量栈顶值送变量c c中中( 7) ( 7) opr 0 0opr 0 0 退栈并返回调用点退栈