第2章 PL0编译程序的实现(4学时)

1、12何为何为PL/0PL/0语言语言? ?l PL/0PL/0语言：语言：PASCALPASCAL语言的子集，功语言的子集，功能简单，结构清晰，可能简单，结构清晰，可读性强，具备了一般高读性强，具备了一般高级语言的必备部分。级语言的必备部分。PL/0PL/0程序示例：程序示例：CONST A=10;CONST A=10;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; WHIL

2、E X#0 DO CALL P; WHILE X#0 DO CALL P; END; END; BEGINBEGIN WRITE(D); WRITE(D); CALL Q; CALL Q;END;END;BEGINBEGINCALL P;CALL P;END.END.3PL/0PL/0编译程序编译程序pcodepcode解释程序解释程序PL/0PL/0源程序源程序注：此处的注：此处的pcodepcode代码专指代码专指PL/0PL/0的的目标代码，与传统目标代码，与传统pcodepcode有区别有区别pcodepcode代码代码42022-5-25NEXT51.1.数据类型只有数据类型只有整型

3、整型2.2.标识符标识符的有效长度是的有效长度是1010，以字母开始的字母数字串，以字母开始的字母数字串3.3.过程过程无参，可嵌套（最多三层），可递归调用无参，可嵌套（最多三层），可递归调用4.4.变量的变量的作用域作用域同同PASCALPASCAL，常量为全局的，无标常量为全局的，无标5.5.语句类型语句类型：赋值语句，：赋值语句，if.then., while.do., if.then., while.do., read, write, call, read, write, call, 复合语句复合语句begin. endbegin. end， 说明语句：说明语句： const., va

4、r., procedureconst., var., procedure6.6.1313个个保留字保留字：if, then, while, do, read, write, call, if, then, while, do, read, write, call, begin, end, const, var, procedure, oddbegin, end, const, var, procedure, odd62022-5-25（1 1）语法成分中的最小单位，构成语言文法的单词。语法成分中的最小单位，构成语言文法的单词。（2 2）语法成分，在书写程序时并不出现，但可一直追溯语法成分，在书

5、写程序时并不出现，但可一直追溯成成 V VT T 表示的形式。表示的形式。（13-1513-15页）页）7BNFBNF（BACKUS-NAUR FORMBACKUS-NAUR FORM）是根据美国的是根据美国的John W.BackusJohn W.Backus与丹麦的与丹麦的Peter NaurPeter Naur来命名的，它从语法上描述程序设计语言的元语言。来命名的，它从语法上描述程序设计语言的元语言。采用采用BNFBNF可说明哪些符号序列是对于某给定语言在语法上有效的程序。可说明哪些符号序列是对于某给定语言在语法上有效的程序。BNFBNF引入的符号：引入的符号： 表示语法构造成分（语法单

6、位），为表示语法构造成分（语法单位），为= 定义为定义为| | 或或EBNFEBNF引入的符号：引入的符号： 表示花括号内的语法成分表示花括号内的语法成分可重复可重复 表示方括号内的语法成分为表示方括号内的语法成分为任选项任选项( )( ) 表示圆括号内的成分表示圆括号内的成分优先优先88两个用两个用EBNFEBNF描述描述“整数整数”的例子的例子练习：练习：P.31 P.31 题题6 6（2 2）（）（3 3） 991010语法语义分析程序语法语义分析程序词法分析程序词法分析程序表格管理程序表格管理程序出错处理程序出错处理程序代码生成程序代码生成程序目标程序目标程序PL/0PL/0源程序源程

7、序目标程序目标程序解释执行程序输入数据结果结果1111启动启动置初值置初值调用GETSYM取单词调用GETSYM取单词调用BLOCK过程调用BLOCK过程当前单词当前单词是否为源程序结束符是否为源程序结束符.？.？出错出错源程序中源程序中是否有错误？是否有错误？调用解释过程INTERPRET调用解释过程INTERPRET解释执行目标程序解释执行目标程序打印错误打印错误结束结束N NY YY YN N编译程序总体流程图编译程序总体流程图 17页页1212所需识别的单词：所需识别的单词： 关键字关键字： 如如 BEGINBEGIN、ENDEND、IFIF、THEN THEN 等等 运算符运算符：

8、如如 + +、- -、* *、/ /、：、：= =、# #、=、= = 等等 标识符标识符： 用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名 常数常数： 如如 10 10、2525、100 100 等整数等整数 界符界符： 如如 , . ; ( ) , . ; ( ) 等等2.3 PL/02.3 PL/0编译程序的词法分析编译程序的词法分析词法分析过程词法分析过程GETSYM GETSYM 所要完成的任务：所要完成的任务：滤空格、识别保留字、识别滤空格、识别保留字、识别标识符、拼数、拼复合词、输出源程序标识符、拼数、拼复合词、输出源程序 参见参见 P.19 P.19 图图通过

9、通过 将识别出的单词信息传递给语法分析程序将识别出的单词信息传递给语法分析程序SYMSYM： 存放单词的类别存放单词的类别, ,如如 beginsym, ident, numberbeginsym, ident, numberIDID ： 存放用户所定义的标识符的值存放用户所定义的标识符的值NUMNUM： 存放用户定义的数存放用户定义的数1313 程序程序 pl/0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factor语法分析的语法分析的任务任务：识别由词法分析给出的单词符号识别由词法分析给出的单词符

10、号序列在序列在“结构结构”上是否符合给定上是否符合给定的的“文法规则文法规则”。语法分析的语法分析的过程过程：从读入第一个单词开始，由从读入第一个单词开始，由V VN N “程序程序”出发，沿语法图箭头所出发，沿语法图箭头所指进行分析指进行分析: : 遇到遇到V VN N ，调用相应的处理过程调用相应的处理过程 遇到遇到V VT T ，判断当前单词是否与判断当前单词是否与V VT T 匹配匹配l 若若匹配匹配：执行语义程序，：执行语义程序，翻译成目标代码翻译成目标代码l 若若不匹配不匹配：报错：报错PL/0PL/0语法调用关系图语法调用关系图：1414 说明部分说明部分的处理的处理名字表需要填

11、写：名字表需要填写： 所在层次所在层次 标识符的属性标识符的属性 分配的相对位置分配的相对位置（标识符的属性不同时，所需填入的信息也不同。登录信息由（标识符的属性不同时，所需填入的信息也不同。登录信息由ENTERENTER过程完成。）过程完成。） 程序体程序体的处理的处理1515名字名字 类型类型 层次层次/ /值值 地址地址 存储空间存储空间N NA AM ME E：A AN NA AM ME E：B BN NA AM ME E：C CN NA AM ME E：D DN NA AM ME E：E EN NA AM ME E：P PK KI IN ND D：C CO ON NS ST TA A

12、N NT TK KI IN ND D：C CO ON NS ST TA AN NT TK KI IN ND D：V VA AR RI IA AB BL LE EK KI IN ND D：V VA AR RI IA AB BL LE EK KI IN ND D：V VA AR RI IA AB BL LE EK KI IN ND D：P PR RO OC CE ED DU UR RV VA AL L：3 35 5V VA AL L：4 49 9L LE EV VE EL L：L LE EV VL LE EV VE EL L：L LE EV VL LE EV VE EL L：L LE EV VL

13、LE EV VE EL L：L LE EV VA AD DR R：D DX XA AD DR R：D DX X+ +1 1A AD DR R：D DX X+ +2 2A AD DR R：S SI IZ ZE E：4 4N NA AM ME E：G G K KI IN ND D：V VA AR RI IA AB BL LE EL LE EV VE EL L：L LE EV V+ +1 1A AD DR R：D DX XCONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G表格管理举例表格管理举例TX0TX1注：注：TXTX为索引表的指针为索引表的指针1616名字名

14、字 类型类型 层次层次/ /值值 地址地址 存储空间存储空间TX0TX1TX2TX3TX41717 目标代码目标代码pcodepcode是是一种假想栈式计算机的汇编语言。一种假想栈式计算机的汇编语言。 指令格式指令格式 f l af l a2.5 2.5 PL/0PL/0编译程序的目标代码结构和代码生成编译程序的目标代码结构和代码生成功能码功能码层次差层次差通常为通常为“位移量位移量”根据不同的指令根据不同的指令有所不同有所不同1818LIT 0 aLIT 0 a将常量值取到运行栈顶将常量值取到运行栈顶LOD l aLOD l a将变量值放到栈顶将变量值放到栈顶STO l aSTO l a将栈

15、顶内容送入某变量单元中将栈顶内容送入某变量单元中CAL l aCAL l a调用过程调用过程INT 0 aINT 0 a在运行栈中为被调用的过程开辟在运行栈中为被调用的过程开辟a a个单元的数据区个单元的数据区JMP 0 aJMP 0 a无条件跳转至无条件跳转至a a地址地址JPC 0 aJPC 0 a条件跳转，当栈顶布尔值非真则跳转至条件跳转，当栈顶布尔值非真则跳转至a a地址，否则顺地址，否则顺序执行序执行OPR 0 0OPR 0 0函数调用结束后的返回函数调用结束后的返回OPR 0 1OPR 0 1栈顶元素取反栈顶元素取反OPR 0 2OPR 0 2次栈顶与栈顶相加，退两个栈元素，相加值

16、进栈次栈顶与栈顶相加，退两个栈元素，相加值进栈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次栈顶与栈顶是否相等次栈顶与栈顶是否相等OPR 0 9OPR 0 9次栈顶与栈顶是否不等次栈顶与栈顶是否不等OPR 0 10OPR 0 10次栈顶是否小于栈顶次栈顶是否小于栈顶OPR 0 11OPR 0 11次栈顶是否大于等于栈顶次栈顶是否大于等于栈顶OPR 0 1

17、2OPR 0 12次栈顶是否大于栈顶次栈顶是否大于栈顶OPR 0 13OPR 0 13次栈顶是否小于等于栈顶次栈顶是否小于等于栈顶OPR 0 14OPR 0 14栈顶值输出至屏幕栈顶值输出至屏幕OPR 0 15OPR 0 15屏幕输出换行屏幕输出换行OPR 0 16OPR 0 16从命令行读入一个输入置于栈顶从命令行读入一个输入置于栈顶目标指令目标指令19190 jmp 0 8 无条件跳转至81 jmp 0 2 无条件跳转至22 int 0 3 在栈顶中申请在栈顶中申请3个栈空间个栈空间3 lod 1 3 将变量取至栈顶将变量取至栈顶（1层差层差, 3相对位置）相对位置）4 lit0 10 将

18、常数将常数1010取至栈顶取至栈顶5 opr 0 2 次栈顶与栈顶相加次栈顶与栈顶相加6 sto1 4 将栈顶值存入变量将栈顶值存入变量7 opr 0 0 函数调用结束后返回函数调用结束后返回8 int 0 5 在运行栈中申请在运行栈中申请5个栈空间个栈空间9 opr 0 16 从命令行读入输入置于栈顶从命令行读入输入置于栈顶10 sto 0 3 将栈顶值存入变量将栈顶值存入变量11 cal 0 2 调用过程调用过程12 lod 0 4 将变量取至栈顶将变量取至栈顶13 opr 0 14 栈顶值输出至屏幕栈顶值输出至屏幕14 opr 0 15 换行换行15 opr 0 0 函数调用结束后返回函

19、数调用结束后返回Const a=10;Const a=10;var b,c;var b,c; procedure p;procedure p; begin begin c:=b+a; c:=b+a; end; end;beginbegin read(b); read(b); call p; call p; write(c); write(c);end.end.目标代码举例目标代码举例参见P242020 PL/0PL/0语言的代码生成是由过程语言的代码生成是由过程GEN GEN 完成。完成。 GENGEN有三个参数，分别代表目标代码的有三个参数，分别代表目标代码的功能码功能码，层差层差和和位位移量移量。gen(opr,0,16); gen(sto,lev-level,adr)gen(opr,0,16); gen(sto,lev-level,adr) 生成的代码顺序放在数组生成的代码顺序放在数组CODECODE中。中。CODECODE为一维数组，数组元素为记录型数据。为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。每一个记录就是一条目标指令。CXCX为指令的指针，由为指令的指针，由0 0开始顺序增加。开始顺序增加。实际上目标代码的顺序：内层过程在前边，主程序的目标代码实际上目标代码的顺序：内层过程在前边，主程序