第第2 2章章 PL/0PL/0编译程序编译程序2.1 PL/0语言和语言和类类pcode的的描述描述2.2 PL/0编译程序的结构编译程序的结构2.3 PL/0编译程序的语法语义分析编译程序的语法语义分析 2.4 PL/0编译程序的编译程序的错误处理错误处理2.5 类类pcodepcode代码解释器代码解释器本章目的：以本章目的：以PL/0PL/0为实例为实例, ,学习编译程序实现的基本步学习编译程序实现的基本步骤和相关技术骤和相关技术 PL/0PL/0编译程序编译程序 PL/0编译编译程序程序 PL/0 语言程序语言程序 类类 pcode 代吗代吗源语言源语言(PL/0)目标语言目标语言(类类 pcode)实现语言（实现语言（pascal) PL/0 类类 pcode pascal PL/0PL/0编译程序编译程序类类 pcodepcode解释解释程序程序类类 pcode代码代码PL/0源程序源程序输入输入输出输出PL/0PL/0编译系统的结构框架编译系统的结构框架PL/0PL/0语言语言zPL/0PL/0程序示例程序示例zPL/0PL/0的的语法描述图语法描述图zPL/0PL/0语言语言文法的文法的EBNFEBNF表示表示zPL/0PL/0语言：语言：PASCALPASCAL语言的语言的子集子集 PL/0PL/0程序示例程序示例 CONST A=10; CONST A=10; （* * 常量说明部分常量说明部分 * *） VAR B,C; VAR B,C; （* * 变量变量说明部分说明部分 * *） PROCEDURE PROCEDURE P; P; （* * 过程过程说明部分说明部分 * *） VAR D;VAR D; PROCEDURE 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的过程体的过程体主主程序程序体体 程序程序分程序分程序.内的文字表示内的文字表示非终结符非终结符或内的文字或符号表示内的文字或符号表示终结符终结符constidentnumber=,;varident,;procedureident;分程序分程序语句语句分程序分程序PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示 EBNFEBNF 引入的符号引入的符号( (元符号元符号) )： 用左右尖括号括起来的语法成分为用左右尖括号括起来的语法成分为非终结符非终结符= () = () 定义为定义为 =() =() 的的左部由左部由右部右部定义定义 | | 或或 表示花括号内的语法成分表示花括号内的语法成分可重复可重复任意次或限任意次或限 定次数定次数 表示方括号内的语法成分为表示方括号内的语法成分为任选项任选项( ) ( ) 表示圆括号内的成分表示圆括号内的成分优先优先例：用例：用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语言是语言是PASCALPASCAL语言的语言的子集子集同同PASCALPASCAL 作用域规则（内层作用域规则（内层可引用包围它的外层定义的可引用包围它的外层定义的标识符），标识符），上下文约束，上下文约束， 过程可过程可嵌套定义嵌套定义，可递归调用可递归调用子集子集z数据类型数据类型, ,只有整型只有整型z数据结构数据结构 , ,只有简变和常数只有简变和常数z数字最多为数字最多为1414位位z标识符的有效长度是标识符的有效长度是1010z语句种类语句种类z过程最多可过程最多可嵌套嵌套三层三层 目标代码目标代码类类pcodepcode目标代码目标代码类类pcodepcode是是一种一种假想栈式计算机假想栈式计算机的的汇编语言汇编语言。指令格式：指令格式：f l af l af f功能码功能码l l层次差层次差 （标识符标识符引用引用层层减去减去定义定义层层）a a根据不同的指令有所区别根据不同的指令有所区别指指令令功功能能表表 const a=10;const a=10;varvar b,c; 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 begin call p; call p; write(2*c); write(2*c); read(b); read(b); end endend.end.( 0) ( 0) jmpjmp 0 8 0 8 转向转向主程序入口主程序入口( 1) ( 1) jmpjmp 0 2 0 2 转向转向过程过程p p入口入口( 2)( 2) intint 0 3 0 3 过程过程p p入口入口, ,为过程为过程p p开辟空间开辟空间( 3) ( 3) lodlod 1 1 3 3 取变量取变量b b的值到栈顶的值到栈顶( 4) lit 0 10 ( 4) lit 0 10 取常数取常数1010到栈顶到栈顶( 5) ( 5) opropr 0 2 0 2 次栈顶与栈顶相加次栈顶与栈顶相加( 6) ( 6) stosto 1 1 4 4 栈顶值送变量栈顶值送变量c c中中( 7) ( 7) opropr 0 0 0 0 退栈并返回调用点退栈并返回调用点(16)(16)( 8)( 8) intint 0 5 0 5 主程序入口开辟主程序入口开辟5 5个栈空间个栈空间( 9) ( 9) opropr 0 16 0 16 从命令行读入值置于栈顶从命令行读入值置于栈顶(10) (10) stosto 0 3 0 3 将栈顶值存入变量将栈顶值存入变量b b中中(11) (11) lodlod 0 3 0 3 将变量将变量b b的值取至栈顶的值取至栈顶(12) lit 0 0 (12) lit 0 0 将常数值将常数值0 0进栈进栈(13) (13) opropr 0 9 0 9 次栈顶与栈顶是否不等次栈顶与栈顶是否不等(14) (14) jpcjpc 0 24 0 24 等时转等时转(24)(24)（条件不满足转条件不满足转）(15) (15) cal 0 2cal 0 2 调用过程调用过程p p(16) lit 0 2 (16) lit 0 2 常数值常数值2 2进栈进栈(17) (17) lodlod 0 0 4 4 将变量将变量c c的值取至栈顶的值取至栈顶(18) (18) opropr 0 4 0 4 次栈顶与栈顶相乘次栈顶与栈顶相乘(2(2*c)*c)(19) (19) opropr 0 14 0 14 栈顶值输出至屏幕栈顶值输出至屏幕(20) (20) opropr 0 15 0 15 换行换行(21) (21) opropr 0 16 0 16 从命令行读取值到栈顶从命令行读取值到栈顶(22) (22) stosto 0 0 3 3 栈顶值送变量栈顶值送变量b b中中(23) (23) jmpjmp 0 11 0 11 无条件转到循环入口无条件转到循环入口(11)(11)(24) (24) opropr 0 0 0 0 结束退栈结束退栈 PL/0PL/0编译程序的结构编译程序的结构词法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序PL/0PL/0编译程序的总体设计编译程序的总体设计z其编译过程采用其编译过程采用一趟扫描方式一趟扫描方式z以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过程过程，当语法分，当语法分析需要读单词时就调用词法分析程序，而当语法析需要读单词时就调用词法分析程序，而当语法、语义语义分析正确，需要生成相应的目标代码时，则调用代码生分析正确，需要生成相应的目标代码时，则调用代码生成程序。成程序。z表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信息的登信息的登录与查找录与查找。z出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇到的错误给语义分析遇到的错误给出在源程序中出在源程序中出错的位置出错的位置和与和与错误错误 性质有关性质有关的编号，并的编号，并进行错误恢复。进行错误恢复。 PL/0PL/0编译程序词法分析的设计与实现编译程序词法分析的设计与实现识别的单词：识别的单词：y保留字或关键字：如：保留字或关键字：如：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN等等y运算符：运算符： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等y标识符：标识符： 用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名y常数：常数： 如：如：1010、2525、100100等整数等整数y界符：界符： 如：如：,、. . 、; ; 、( ( 、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：y读源程序（读源程序（getchgetch) )y滤空格滤空格y识别识别保留字保留字y识别标识符识别标识符y拼数拼数y识别单字符单词识别单字符单词y拼双字符单词拼双字符单词z词法分析过程词法分析过程: :GETSYMGETSYM框图（见教材图框图（见教材图2.52.5）z程序（程序（ procedure procedure getsymgetsym）当识别到标识符时先查当识别到标识符时先查保留字保留字表表z保留保留字字表：（表：（ begin (* main * ) begin (* main * ) ）word1:=word1:=begin begin ；word2:=word2:=callcall ； .word13:=word13:=writewrite ；查到时找到相应的查到时找到相应的内部表示内部表示Wsym1:=beginsym; wsym2:=callsym； wsym13:=writesym；z字符对应的字符对应的单词表：单词表：ssymssym+:=+:=plusplus; ; ssymssym-:=-:=minusminus; ; ssymssym;:=;:=semicolonsemicolon; ;z词法分析如何把单词传递给语法分析词法分析如何把单词传递给语法分析 type symbol=(type symbol=(nulnul, ,identident, ,numbernumber, ,plusplus,varsymvarsym, ,procsymprocsym) )；3 3个个全程量全程量 symsym:symbol;:symbol;idid:alfa:alfa; ;numnum:integer;:integer;通过三个通过三个全程量全程量 SYMSYM 、IDID和和NUMNUM 将识别出的单词信息将识别出的单词信息传递传递给给语法语法分析分析程序。程序。ySYMSYM：存放单词的类别存放单词的类别 如：有程序段落为：如：有程序段落为： begin initial := 60begin initial := 60；endend 对应单词对应单词翻译后变为：翻译后变为： begin begin beginsymbeginsym, initial , initial identident, ,:= := becomesbecomes, 60 , 60 numbernumber, , ； semicolonsemicolon，end end endsymendsym 。yIDID： 存放用户所定义的标识符的值存放用户所定义的标识符的值 如：如： initial initial （在（在SYMSYM中放中放identident，在，在IDID中中放放initialinitial）yNUMNUM：存放用户定义的数存放用户定义的数 如：如：60 60 y（在在SYMSYM中放在中放在numbernumber在在NUMNUM中中放放6060）使用状态转换图实现词法分析程序的设计方法使用状态转换图实现词法分析程序的设计方法词法分析程序的设计词法分析程序的设计-使用状态转换图实现使用状态转换图实现表示表示状态状态，对应每个状态编一段程序，对应每个状态编一段程序，每个状态每个状态调用调用取字符取字符程序，根据当前字程序，根据当前字符符转到不同的状态，并做相应操作。转到不同的状态，并做相应操作。表示表示终态终态，已，已识别出一个识别出一个单词单词。 PL/0PL/0编译程序语法语义分析编译程序语法语义分析 PL/0PL/0编译程序语法分析的设计与实现编译程序语法分析的设计与实现自顶向下自顶向下的语法分析的语法分析递归子程递归子程序法序法 程序程序分程序分程序.constidentnumber=,;varident,;procedureident;分程序分程序语句语句分程序分程序identreadend;语句语句表达式表达式：=begin语句语句语句语句)(ident, 自顶向下的语法分析自顶向下的语法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. . . VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 为文法的为文法的开始符号开始符号，以开，以开始符号作为根结始符号作为根结点构造一棵倒挂点构造一棵倒挂着的语法树。着的语法树。递归子程序法递归子程序法z递归子程序法递归子程序法：对应对应每个非终结符每个非终结符语法单元，编一个独语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符开始，由非终结符 （即开始符）出发，沿语法描述即开始符）出发，沿语法描述图图箭头箭头所指出的方向进行分析。当遇到非终结符时，则所指出的方向进行分析。当遇到非终结符时，则调调用用相应的相应的处理过程处理过程，从语法描述图看，也就进入了一个语，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是行分析。当遇到描述图中是终结符终结符时，则判断当前读入的时，则判断当前读入的单词是否与图中的终结符单词是否与图中的终结符相匹配相匹配，若匹配，再读取下一个，若匹配，再读取下一个单词继续分析。遇到单词继续分析。遇到分支点分支点时，将当前的单词与分支点上时，将当前的单词与分支点上多个终结符多个终结符逐个相比较逐个相比较，若都不匹配时可能是进入下一个，若都不匹配时可能是进入下一个非终结符语法单位或是出错。非终结符语法单位或是出错。 程序程序 pl0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factor语语法法调调用用关关系系图图编编译译程程序序总总体体流流程程图图 PL/0PL/0编译程序语义分析的设计与实现编译程序语义分析的设计与实现 PL/0PL/0编译程序语法编译程序语法、语义分析的的核心语义分析的的核心程序是程序是BLOCKBLOCK过程，过程， z说明部分的分析说明部分的分析与处理与处理z表格管理表格管理z过程体过程体( (语句）的分析语句）的分析与处理与处理说明部分的分析说明部分的分析与处理与处理对每个过程（含主程序）对每个过程（含主程序）说明的对象说明的对象（变量变量，常量常量和和过程过程）造造符号表符号表 登录登录标识符的标识符的属性属性。 标识符的属性标识符的属性: :种类，所在种类，所在层次层次, ,值值和分配的和分配的相对位置相对位置。 登录信息由登录信息由ENTERENTER过程完成。过程完成。例程序说明部分为：例程序说明部分为：CONST A=35CONST A=35，B=49B=49； VAR CVAR C，D D，E E； PROCEDURE PPROCEDURE P； VAR G VAR G ； 符号表符号表 名字名字 种类种类 层次层次/值值 地址地址 存储空间存储空间对应名字表对应名字表ztxtx ：tabletable表表的下标指针的下标指针, ,是以是以值参数值参数形式使用形式使用的。的。zdx: 计算每个变量在运行栈中相对本计算每个变量在运行栈中相对本过程过程基地址基地址的偏移量的偏移量 ，放在放在table表表中的中的adr域，域，生成生成目标目标代码代码时再时再放在放在codecode中的中的a域域过程体的处理过程体的处理y对对语句进行语句进行语法语法分析分析y语义分析语义分析 当遇到当遇到标识符的引用时标识符的引用时就调用就调用POSITIONPOSITION函数函数查查TABLETABLE表表，看是否，看是否有有过过正确定义正确定义，若已有，则从表中，若已有，则从表中取相应取相应的有关的有关信息信息，供代码的生成使用。，供代码的生成使用。若无定义则错若无定义则错。y当当语法语义正确时语法语义正确时，就，就生成生成相应语句功能的相应语句功能的目标代码目标代码代码生成代码生成z代码生成是由过程代码生成是由过程GENGEN完成。完成。zGENGEN有有3 3个个参数参数，分别代表目标代码的，分别代表目标代码的功能码功能码，层差层差和和位移量位移量。例如。例如 gen(opr,0,16); gen(opr,0,16); gen(sto,gen(sto,levlev- -levellevel,adr,adr) ) levlev：当当前前处理的处理的过程过程层次层次 levellevel：被被引用变量或过程所在引用变量或过程所在层次层次CXCX：为目标代码为目标代码codecode数组的下标指针数组的下标指针PL/0PL/0编译程序错误处理的实现编译程序错误处理的实现 对语法错误的两种处理方法：对语法错误的两种处理方法：(1) (1) 对于对于易于校正易于校正的错误，如丢了逗号，分的错误，如丢了逗号，分号等，指出出错位置，号等，指出出错位置，加以校正加以校正，继续进行，继续进行分析。分析。(2) (2) 对于对于难于校正难于校正的错误，给出错误的位置的错误，给出错误的位置与性质，与性质，跳过后面的一些单词跳过后面的一些单词，直到下一个直到下一个可以进行正常语法分析的语法单位。可以进行正常语法分析的语法单位。 z在在进入进入某个某个语法单位语法单位时，调用时，调用TESTTEST, ,检查当前符检查当前符号是否属于该号是否属于该语法单位的开始符号集合语法单位的开始符号集合。若不属。若不属于，则于，则滤去滤去开始开始符号符号和和后继后继符号符号集合外集合外的所有符的所有符号。号。z在在语法单位语法单位分析结束分析结束时，调用时，调用TESTTEST, ,检查当前符检查当前符号是否属于调用该语法单位时应有的号是否属于调用该语法单位时应有的后继后继符号集符号集合。若不属于，则合。若不属于，则滤去滤去后继后继符号和符号和开始开始符号符号集合集合外外的所有符号的所有符号。 TEST TEST TEST TEST类类pcodepcode代码解释器的实现代码解释器的实现z类类pcode解释器的结构解释器的结构z目标代码解释执行时目标代码解释执行时数据栈的布局数据栈的布局（运行（运行栈的存储分配）栈的存储分配）类类pcodepcode解释器的结构解释器的结构z目标代码存放在数组目标代码存放在数组CODECODE中。中。z解释程序定义一个一维整型数组解释程序定义一个一维整型数组S S作为作为运行栈运行栈栈顶寄存器栈顶寄存器（指针）（指针）t t，基址寄存器基址寄存器（指针）（指针）b b，程序地址寄存器程序地址寄存器p p，指令寄存器指令寄存器i i目标代码解释执行时数据栈的布局目标代码解释执行时数据栈的布局（运行栈的存储分配）（运行栈的存储分配）在每个过程调用时在栈顶分配在每个过程调用时在栈顶分配3 3个联系单元：个联系单元：ySLSL： 静态链静态链，指向，指向定义定义该过程的该过程的直接外过程直接外过程 （或主程序）运行时（或主程序）运行时最新最新数据段的基地址数据段的基地址。yDLDL： 动态链动态链，指向，指向调用调用该过程前正在运行过该过程前正在运行过 程的数据段基地址。程的数据段基地址。yRARA： 返回地址返回地址，记录调用该过程时，记录调用该过程时目标程序目标程序的的断点断点，即调用过程指令的下一条指令的地址。，即调用过程指令的下一条指令的地址。 目标代码的解释执行目标代码的解释执行 运行栈运行栈S SzM M调用过程调用过程Q Q RA RA DL DL SL SLb. ttbQM目标代码的解释执行目标代码的解释执行几条几条特殊指令特殊指令在在code中的中的位置位置和和功能功能yINT 0 AINT 0 A在在过程过程目标程序的目标程序的入口处入口处，开辟开辟A A个单元的数据段。个单元的数据段。A A为为局部变量局部变量的的个数个数+ +3 3。yOPR 0 0OPR 0 0在在过程过程目标程序的目标程序的出口处出口处，释放数据段释放数据段（退栈），（退栈），恢复调用恢复调用该过程该过程前前正在运行的过程正在运行的过程的数据段的数据段基址寄基址寄存器存器B B和和栈顶寄存器栈顶寄存器T T的值，并将的值，并将返回地址返回地址送送到指令到指令地址寄存器地址寄存器P P中，以使调用前的程序从中，以使调用前的程序从断点断点开始开始继继续执行续执行。目标代码的解释执行目标代码的解释执行几条几条特殊特殊指令在指令在code中的中的位置位置和和功能功能yCAL L ACAL L A调用过程调用过程，还完成，还完成填写填写静态链静态链、动态链动态链、返回返回地址地址，给出，给出被调被调用用过程过程的的基地址基地址值，值，送送入基址入基址寄存器寄存器B B中，目标程序的中，目标程序的入口入口地址地址A A的值的值送送指令指令地址寄存器地址寄存器P P中，使指令从中，使指令从A A开始执行。开始执行。附附 运行时数据栈运行时数据栈S S的变化状态的变化状态教材25页