第二章PL0编译程序课件.ppt（31页）

1、第第2 2章章 PL/0PL/0编译程序编译程序l PL/0语言和语言和类类pcode的的描述描述l PL/0编译程序的结构编译程序的结构l PL/0编译程序的语法语义分析编译程序的语法语义分析l PL/0编译程序的编译程序的错误处理错误处理2.1 2.1 PL/0语言和类语言和类pcode的描述的描述 PL/0编译程序编译程序 PL/0 语言程序语言程序 类类 pcode 代码代码源语言源语言(PL/0)目标语言目标语言(类类pcode)实现语言实现语言(pascal)PL/0 类类 pcode pascal PL/0PL/0编译程序编译程序类类 pcodepcode解释解释程序程序类类 p

2、code代码代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架2.1.1 PL/02.1.1 PL/0语言语言z PL/0 PL/0程序示例程序示例z PL/0PL/0的的语法描述图语法描述图z PL/0PL/0语言语言文法的文法的EBNFEBNF表示表示 PL/0 PL/0程序示例程序示例 CONST A=10;CONST A=10;（*常量说明部分常量说明部分 *）VAR B,C;VAR B,C;（*变量变量说明部分说明部分 *）PROCEDURE PROCEDURE P;P;（*过程过程说明部分说明部分 *）VAR D;VAR D;PROCEDU

3、RE PROCEDURE Q;Q;VAR X;VAR X;BEGINBEGIN READ(X);READ(X);D:=X;D:=X;WHILE X#0 WHILE X#0 DO CALL P;DO CALL P;END;END;BEGINBEGIN WRITE(D);WRITE(D);CALL Q;CALL Q;END;END;BEGINBEGIN CALL P;CALL P;END.END.Q的过程体的过程体p的过程体的过程体主主程序程序体体程序程序分程序分程序.内的文字表示内的文字表示非终结符非终结符或内的文字或符号表示内的文字或符号表示终结符终结符PL/0PL/0的语法描述图的语法描述图

4、PL/0PL/0的语法描述图的语法描述图varprocedure分程序分程序语句语句分程序分程序const标识符标识符标识符标识符标识符标识符numberPL/0PL/0的语法描述图的语法描述图end表达式表达式:=begin语句语句语句语句)(,read标识符标识符标识符标识符语句语句PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示 EBNFEBNF 引入的符号引入的符号(元符号元符号)：用左右尖括号括起来的语法成分为用左右尖括号括起来的语法成分为非终结符非终结符=()()定义为定义为 =()=()的的左部由左部由右部右部定义定义|或或 表示花括号内的语法成分表示花括号内的语法成

5、分可重复可重复任意次或限任意次或限 定次数定次数 表示方括号内的语法成分为表示方括号内的语法成分为任选项任选项()()表示圆括号内的成分表示圆括号内的成分优先优先 例：用例：用EBNFEBNF描述描述 的定义的定义 ：=+|-=+|-=0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9 或更好的写法或更好的写法 =+|-=+|-|0|0=1|2|3|4|5|6|7|8|9=1|2|3|4|5|6|7|8|9 =0|=0|PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示 2.1.2 2.1.2 目标代码目标代码类类pcodepcode目标代码目标代码类类p

6、codepcode是一种是一种假想栈式计算机假想栈式计算机的的汇编语言汇编语言。指令格式：指令格式：f l af f功能码功能码l l层次差层次差 （标识符（标识符引用层引用层减去减去定义层定义层）a a根据不同的指令有所区别根据不同的指令有所区别L LI IT T 0 0 a a将将常常数数值值取取到到栈栈顶顶，a a为为常常数数值值L LO OD D l l a a将将变变量量值值取取到到栈栈顶顶，a a为为偏偏移移量量，l l为为层层差差S ST TO O l l a a将将栈栈顶顶内内容容送送入入某某变变量量单单元元中中，a a为为偏偏移移量量，l l为为层层差差C CA AL L l

7、 l a a调调用用过过程程，a a为为过过程程地地址址，l l为为层层差差I IN NT T 0 0 a a在在运运行行栈栈中中为为被被调调用用的的过过程程开开辟辟a a个个单单元元的的数数据据区区J JM MP P 0 0 a a无无条条件件跳跳转转至至a a地地址址J JP PC C 0 0 a a条条件件跳跳转转，当当栈栈顶顶布布尔尔值值非非真真则则跳跳转转至至a a地地址址，否否则则顺顺序序执执行行O OP PR R 0 0 0 0过过程程调调用用结结束束后后,返返回回调调用用点点并并退退栈栈O OP PR R 0 0 1 1栈栈顶顶元元素素取取反反O OP PR R 0 0 2 2

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

9、是否否相相等等，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 9 9次次栈栈顶顶与与栈栈顶顶是是否否不不等等，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 1 10 0次次栈栈顶顶是是否否小小于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 1 11 1次次栈栈顶顶是是否否大大于于等等于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 1 12 2次次栈栈顶顶是是否否大大于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 1 13

10、 3次次栈栈顶顶是是否否小小于于等等于于栈栈顶顶，退退两两个个栈栈元元素素，结结果果值值进进栈栈O OP PR R 0 0 1 14 4栈栈顶顶值值输输出出至至屏屏幕幕O OP PR R 0 0 1 15 5屏屏幕幕输输出出换换行行O OP PR R 0 0 1 16 6从从命命令令行行读读入入一一个个输输入入置置于于栈栈顶顶类类pcode指令功能表指令功能表 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

11、(b);while while b b0 0 do do begin 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 取常数取常数

12、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 退栈并返回调用点退栈并返回调用点(16)(16)(8)(8)int 0 5 int 0 5 主程序入口开辟主程序入口开辟5 5个栈空间个栈空间(9)opr 0 16(9)opr 0 16 从命令行读入值置于栈顶从命令行读入值置于栈顶(10)sto 0 3 (10)sto 0 3 将栈顶值存入变量将栈顶值存入变量b b中中(11)lod 0 3 (11)lod 0 3 将变量将变量b

13、b的值取至栈顶的值取至栈顶(12)lit 0 0 (12)lit 0 0 将常数值将常数值0 0进栈进栈(13)opr 0 9 (13)opr 0 9 次栈顶与栈顶是否不等次栈顶与栈顶是否不等(14)(14)jpc 0 24jpc 0 24 等时转等时转(24)(24)（条件不满足转条件不满足转）(15)(15)cal 0 2cal 0 2 调用过程调用过程p p(16)lit 0 2 (16)lit 0 2 常数值常数值2 2进栈进栈(17)lod(17)lod 0 0 4 4 将变量将变量c c的值取至栈顶的值取至栈顶(18)opr 0 4 (18)opr 0 4 次栈顶与栈顶相乘次栈顶与

14、栈顶相乘(2(2*c)c)(19)opr 0 14(19)opr 0 14 栈顶值输出至屏幕栈顶值输出至屏幕(20)opr 0 15(20)opr 0 15 换行换行(21)opr 0 16(21)opr 0 16 从命令行读取值到栈顶从命令行读取值到栈顶(22)sto(22)sto 0 0 3 3 栈顶值送变量栈顶值送变量b b中中(23)jmp 0 11(23)jmp 0 11 无条件转到循环入口无条件转到循环入口(11)(11)(24)opr 0 0 (24)opr 0 0 结束退栈结束退栈 2.2 PL/02.2 PL/0编译程序的结构编译程序的结构词法分析程词法分析程序序语法语义分析

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

16、则调用代码生成程序。生成程序。z 表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信息的登信息的登录与查找录与查找。z 出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇到的错误给语义分析遇到的错误给出在源程序中出在源程序中出错的位置出错的位置和与和与错误错误 性质有关性质有关的编号，并的编号，并进行错误恢复。进行错误恢复。编译程序总体流程图编译程序总体流程图启动启动置初值置初值调用G E TSYM取 单 词调用G E TSYM取 单 词调用B L OCK过 程调用B L OCK过 程当前单词当前单词是否为源程序结束符是否为源程序结束符.？.？出错出

17、错源程序中源程序中是否有错误？是否有错误？调用解释过程I N T E R P RET调用解释过程I N T E R P RET解释执行目标程序解释执行目标程序打印错误打印错误结束结束N NY YY YN N2.2.22.2.2 词法分析词法分析的设计与实现的设计与实现识别的单词：识别的单词：y保留字或关键字：如：保留字或关键字：如：BEGINBEGIN、ENDEND、IFIF、THENTHEN等等y运算符：运算符：如：如：+、-、*、/、：、：=、#、=、=等等y标识符：标识符：用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名y常数：常数：如：如：1010、2525、10010

18、0等整数等整数y界符：界符：如：如：,、.、;、(、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：y读源程序（读源程序（getch)getch)y滤空格滤空格y识别识别保留字保留字y识别标识符识别标识符y拼数拼数y识别单字符单词识别单字符单词y拼双字符单词拼双字符单词z词法分析过程（词法分析过程（GETSYMGETSYM）当识别到标识符时先查）当识别到标识符时先查保保留字留字表表z保留字保留字表：表：word1:=word1:=begin begin ；word2:=word2:=callcall ；.word13:=word13:=writewrite

19、 ；查到时找到相应的查到时找到相应的内部表示内部表示wsym1=beginsym;wsym2=callsym；wsym13=writesym；词法分析程序词法分析程序 GETSYMz 字符对应的字符对应的单词表：单词表：ssym+=ssym+=plusplus;ssym-=;ssym-=minusminus;ssym:=ssym:=becomesbecomes ssym;=ssym;=semicolonsemicolon;z 词法分析如何把单词传递给语法分析词法分析如何把单词传递给语法分析 type symbol=(type symbol=(nulnul,identident,numbernu

20、mber,plusplus,),)；3 3个个全程量全程量 SYMSYM:symbol;:symbol;IDIDNUMNUM:integer;:integer;词法分析程序词法分析程序 GETSYM通过三个通过三个全程量全程量 SYMSYM、IDID和和NUMNUM 将识别出的单词信息将识别出的单词信息传递传递给给语法分析语法分析程序。程序。ySYMSYM：存放单词的类别：存放单词的类别 如：有程序段落为：如：有程序段落为：begin initial:=60begin initial:=60；endend 对应单词翻译后变为：对应单词翻译后变为：begin begin beginsymbegi

21、nsym,initial ,initial identident,:=:=becomesbecomes,60 ,60 numbernumber,；semicolonsemicolon，end end endsymendsym 。yIDID：存放用户所定义的标识符的名字存放用户所定义的标识符的名字 如：如：initialinitial（在（在SYMSYM中放中放identident，在，在IDID中放中放initialinitial）yNUMNUM：存放用户定义的数：存放用户定义的数 如：如：initialinitial在在NUMNUM中放中放6060）词法分析程序词法分析程序 GETSYM词法

22、分析程序的设计词法分析程序的设计-使用状态转换图实现使用状态转换图实现表示表示状态状态，对应每个状态编一段程序，对应每个状态编一段程序，每个状态每个状态调用调用取字符取字符程序，根据当前字程序，根据当前字符符转到不同的状态，并做相应操作。转到不同的状态，并做相应操作。表示表示终态终态，已，已识别出一个识别出一个单词单词。1 12 23 35 514141313121210109 97 78 86 64 41111空格空格字母字母字母数字字母数字非字母数字非字母数字数字数字数字数字非数字非数字：=非非=,+-(标识符标识符数字数字:=2.2.3 2.2.3 PL/0PL/0编译程序编译程序语法语

23、义分析语法语义分析的设计的设计 PL/0PL/0编译程序语法、语义分析的的核心编译程序语法、语义分析的的核心程序是程序是BLOCKBLOCK过程过程z 说明部分的分析与处理说明部分的分析与处理z 语法分析语法分析z 语义分析语义分析1 1、说明部分的分析与处理、说明部分的分析与处理 对每个过程（含主程序）对每个过程（含主程序）说明的对象说明的对象（变量变量，常量常量和和过过程程）造符号表，造符号表，在符号表中登录在符号表中登录标识符标识符的属性。的属性。标识符的属性标识符的属性:种类，所在种类，所在层次层次,值值和分配的和分配的相对位置相对位置。登录信息由登录信息由ENTERENTER过程完成

24、。过程完成。N NA AM ME E：A A N NA AM ME E：B B N NA AM ME E：C C N NA AM ME E：D D N NA AM ME E：E E N NA AM ME E：P P K KI IN ND D：C CO ON NS ST TA AN NT T K KI IN ND D：C CO ON NS ST TA AN NT T K KI IN ND D：V VA AR RI IA AB BL LE E K KI IN ND D：V VA AR RI IA AB BL LE E K KI IN ND D：V VA AR RI IA AB BL LE E K

25、KI IN ND D：P PR RO OC CE ED DU UR R V VA AL L：3 35 5 V VA AL L：4 49 9 L LE EV VE EL L：L LE EV V L LE EV VE EL L：L LE EV V L LE EV VE EL L：L LE EV V L LE EV VE EL L：L LE EV V A AD DR R：D DX X A AD DR R：D DX X+1 1 A AD DR R：D DX X+2 2 A AD DR R：S SI IZ ZE E：4 4 N NA AM ME E：G G K KI IN ND D：V VA AR RI

26、 IA AB BL LE E L LE EV VE EL L：L LE EV V+1 1 A AD DR R：D DX X 例：程序说明部分为：例：程序说明部分为：CONST A=35CONST A=35，B=49B=49；VAR CVAR C，D D，E E；PROCEDURE PPROCEDURE P；VAR G VAR G；符号表符号表 名字名字 种类种类 层次层次/值值 地址地址 存储空间存储空间对应名字表对应名字表VAR A;VAR A;BEGINBEGIN READ(A)READ(A)END.END.为文法的为文法的开始符号开始符号，以开，以开始符号作为根结始符号作为根结点构造一棵

27、倒挂点构造一棵倒挂着的语法树。着的语法树。AA程序程序分程序分程序变量说明部分变量说明部分语句语句.VAR标识符标识符；复合语句复合语句BEGIN语句语句END读语句读语句READ（标识符标识符）2 2、PL/0PL/0编译程序编译程序语法分析语法分析3 3、PL/0PL/0编译程序编译程序语义分析语义分析y语义分析：语义分析：当遇到当遇到标识符的引用时标识符的引用时就调用就调用POSITIONPOSITION函数函数查查符号符号表表，看是否，看是否有有过过正确定义正确定义，若已有，则从表中若已有，则从表中取相应取相应的有关的有关信息信息，供代码，供代码的生成使用。的生成使用。若无定义则调用出

28、错处理程序若无定义则调用出错处理程序。y当当语法语义正确时语法语义正确时，就，就生成生成相应语句功能的相应语句功能的目目标代码标代码2.2.4 2.2.4 目标代码生成目标代码生成z代码生成是由过程代码生成是由过程GENGEN完成。完成。zGENGEN有有3 3个个参数参数，分别代表目标代码的，分别代表目标代码的功能码功能码，层差层差和和位移量位移量。例如。例如 gen(opr,0,16);gen(opr,0,16);gen(sto,gen(sto,levlev-levellevel,adr),adr)levlev：当前：当前处理的处理的过程过程层次层次 levellevel：被引用变量或过程所在：被引用变量或过程所在层次层次p 经常不断地学习,你就什么都知道。你知道得越多,你就越有力量p Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日