《第二章 PL0编译程序》由会员分享，可在线阅读，更多相关《第二章 PL0编译程序（86页珍藏版）》请在金锄头文库上搜索。
1、第第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)目标语言目标语言(
2、类类 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;
3、 （* * 常量说明部分常量说明部分 * *） 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; CA
4、LL Q; END; END; BEGINBEGIN CALL P; CALL P; END. END.Q的过程体的过程体p的过程体的过程体主主程序程序体体 程序程序分程序分程序.内的文字表示内的文字表示非终结符非终结符或内的文字或符号表示内的文字或符号表示终结符终结符constidentnumber=,;varident,;procedureident;分程序分程序语句语句分程序分程序PL/0PL/0语言文法的语言文法的EBNFEBNF表示表示 EBNF EBNF 引入的符号引入的符号( (元符号元符号) )： 用左右尖括号括起来的语法成分为用左右尖括号括起来的语法成分为非终结符非终结符=
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
6、| PL/0PL/0语言是语言是PASCALPASCAL语言的语言的子集子集同同PASCALPASCAL 作用域规则（内层作用域规则（内层可引用包围它的外层定义的可引用包围它的外层定义的标识符），标识符），上下文约束，上下文约束， 过程可过程可嵌套定义嵌套定义，可递归调用可递归调用子集子集z数据类型数据类型, ,只有整型只有整型z数据结构数据结构 , ,只有简变和常数只有简变和常数z数字最多为数字最多为1414位位z标识符的有效长度是标识符的有效长度是1010z语句种类语句种类z过程最多可过程最多可嵌套嵌套三层三层 目标代码目标代码类类pcodepcode目标代码目标代码类类pcodepcod
7、e是是一种一种假想栈式计算机假想栈式计算机的的汇编语言汇编语言。指令格式：指令格式：f l af l af f功能码功能码l l层次差层次差 （标识符标识符引用引用层层减去减去定义定义层层）a a根据不同的指令有所区别根据不同的指令有所区别指指令令功功能能表表 const a=10;const a=10;var var 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
8、 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) ( 4) lit 0 10 lit 0 10 取常数取常数1010到栈顶到栈顶( 5) ( 5)
9、 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
10、b的值取至栈顶的值取至栈顶(12) (12) lit 0 0 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
11、次栈顶与栈顶相乘次栈顶与栈顶相乘(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编译程序的结构编译程序的结构词
12、法分析程词法分析程序序语法语义分析程序语法语义分析程序代码生成程序代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序PL/0PL/0源程序源程序目标程序目标程序PL/0PL/0编译程序的总体设计编译程序的总体设计z其编译过程采用其编译过程采用一趟扫描方式一趟扫描方式z以语法以语法、语义分析语义分析程序程序为核心为核心 词法分析词法分析程序和程序和代码生成代码生成程序都作为一个程序都作为一个过程过程，当语法分，当语法分析需要读单词时就调用词法分析程序，而当语法析需要读单词时就调用词法分析程序，而当语法、语义语义分析正确，需要生成相应的目标代码时，则调用代码生分析正确，需要生成相应的目标
13、代码时，则调用代码生成程序。成程序。z表格管理表格管理程序实现程序实现变量变量，常量常量和和过程过程标识符的标识符的信息的登信息的登录与查找录与查找。z出错处理出错处理程序，对词法和语法程序，对词法和语法、语义分析遇到的错误给语义分析遇到的错误给出在源程序中出在源程序中出错的位置出错的位置和与和与错误错误 性质有关性质有关的编号，并的编号，并进行错误恢复。进行错误恢复。 PL/0PL/0编译程序词法分析的设计与实现编译程序词法分析的设计与实现识别的单词：识别的单词：y保留字或关键字：如：保留字或关键字：如：BEGINBEGIN、 END END、 IF IF、 THEN THEN等等y运算符运
14、算符： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等y标识符标识符： 用户定义的变量名、常数名、过程名用户定义的变量名、常数名、过程名y常数常数： 如：如：1010、2525、100100等整数等整数y界符界符： 如：如：,、. . 、; ; 、( ( 、)等等词法分析过程词法分析过程GETSYMGETSYM所要完成的任务：所要完成的任务：y读源程序（读源程序（getchgetch) )y滤空格滤空格y识别识别保留字保留字y识别标识符识别标识符y拼数拼数y识别单字符单词识别单字符单词y拼双字符单词拼双字符单词z词法分析过程词法分析过程: :GETSYMGETSYM框
15、图（见教材图框图（见教材图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字符
16、对应的字符对应的单词表：单词表：ssymssym+:=+:=plusplus; ; ssymssym-:=-:=minusminus; ; ssymssym;:=;:=semicolonsemicolon; ;z词法分析如何把单词传递给语法分析词法分析如何把单词传递给语法分析 type symbol=(type symbol=(nulnul, ,identident, ,numbernumber, ,plusplus,varsymvarsym, ,procsymprocsym) )；3 3个个全程量全程量 symsym:symbol;:symbol;idid: :alfaalfa; ;numn
17、um:integer;:integer;通过三个通过三个全程量全程量 SYMSYM 、IDID和和NUMNUM 将识别出的单词信息将识别出的单词信息传递传递给给语法语法分析分析程序。程序。ySYMSYM：存放单词的类别存放单词的类别 如：有程序段落为：如：有程序段落为： begin initial := 60begin initial := 60；endend 对应单词对应单词翻译后变为：翻译后变为： begin begin beginsymbeginsym, initial, initial identident, ,:= := becomesbecomes, 60 , 60 numbern
18、umber, , ； semicolonsemicolon，end end endsymendsym 。yIDID： 存放用户所定义的标识符的值存放用户所定义的标识符的值 如：如： initial initial （在在SYMSYM中放中放identident，在在IDID中中放放initialinitial）yNUMNUM：存放用户定义的数存放用户定义的数 如：如：60 60 y（在在SYMSYM中放在中放在numbernumber在在NUMNUM中中放放6060）使用状态转换图实现词法分析程序的设计方法使用状态转换图实现词法分析程序的设计方法词法分析程序的设计词法分析程序的设计-使用状态转
19、换图实现使用状态转换图实现表示表示状态状态，对应每个状态编一段程序，对应每个状态编一段程序，每个状态每个状态调用调用取字符取字符程序，根据当前字程序，根据当前字符符转到不同的状态，并做相应操作。转到不同的状态，并做相应操作。表示表示终态终态，已，已识别出一个识别出一个单词单词。 PL/0PL/0编译程序语法语义分析编译程序语法语义分析 PL/0PL/0编译程序语法分析的设计与实现编译程序语法分析的设计与实现自顶向下自顶向下的语法分析的语法分析递归子程递归子程序法序法 程序程序分程序分程序.constidentnumber=,;varident,;procedureident;分程序分程序语句语
20、句分程序分程序identreadend;语句语句表达式表达式：=begin语句语句语句语句)(ident, 自顶向下的语法分析自顶向下的语法分析VAR A;VAR A;BEGINBEGIN READ(A) READ(A)END.END. . . VARVAR ； A A BEGINBEGIN ENDEND READREAD （ ） A A 为文法的为文法的开始符号开始符号，以开，以开始符号作为根结始符号作为根结点构造一棵倒挂点构造一棵倒挂着的语法树。着的语法树。递归子程序法递归子程序法z递归子程序法递归子程序法：对应对应每个非终结符每个非终结符语法单元，编一个独语法单元，编一个独立的处理过程（
21、或子程序）。语法分析从读入第一个单词立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符开始，由非终结符 （即开始符）出发，沿语法描述即开始符）出发，沿语法描述图图箭头箭头所指出的方向进行分析。当遇到非终结符时，则所指出的方向进行分析。当遇到非终结符时，则调调用用相应的相应的处理过程处理过程，从语法描述图看，也就进入了一个语，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是行分析。当遇到描述图中是终结符终结符时，则判断当前读入的时，则判断当前读入的单词是否与图中的终结符单词
22、是否与图中的终结符相匹配相匹配，若匹配，再读取下一个，若匹配，再读取下一个单词继续分析。遇到单词继续分析。遇到分支点分支点时，将当前的单词与分支点上时，将当前的单词与分支点上多个终结符多个终结符逐个相比较逐个相比较，若都不匹配时可能是进入下一个，若都不匹配时可能是进入下一个非终结符语法单位或是出错。非终结符语法单位或是出错。例：如何用递归子程序法实现表达式的语法分析例：如何用递归子程序法实现表达式的语法分析项项表达式表达式+-项项+-项项 因子因子 因子因子 */语法图语法图因子的语法图因子的语法图因子因子identnumber(表达式表达式)z表达式的表达式的EBNF表达式表达式=+|-+|
23、-项项 （+|-+|-）项）项 项项=因子因子 （*|/*|/）因子）因子 因子因子=标识符标识符| |无符号整数无符号整数| |（表达式表达式）z表达式表达式的的递归子程序递归子程序实现实现procedureprocedure 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, , m
24、inusminus do do begin begin getsym getsym; ; termterm; ; end endend;end; z z项项的的递归子程序递归子程序实现实现procedure procedure termterm; ;beginbegin factorfactor; ; while sym in while sym in timestimes, , slashslash do do begin begin getsym getsym; ; factorfactor; ; end endend;end;z因子因子的的递归子程序递归子程序实现实现procedure
25、procedure factorfactor; ;begin begin if sym if sym identident then then begin begin if sym if sym numbernumber then then begin begin if sym = if sym = ( ( then then begin begin getsymgetsym; ; exprexpr; ; if sym = if sym = ) ) then then getsym getsym else error else error end end else error else err
26、or end end end end end; end; = beginbegin（*main*)*main*)(*initialize*)(*initialize*) (*r/w file set*) (*r/w file set*) getsym getsym; ; block( ); block( ); if if sym sym period then error. period then error.end.end.。 程序程序 pl0分程序分程序 block语句语句 statement条件条件 condition表达式表达式expression项项 term因子因子 factor语
27、语法法调调用用关关系系图图编编译译程程序序总总体体流流程程图图 PL/0PL/0编译程序语义分析的设计与实现编译程序语义分析的设计与实现 PL/0PL/0编译程序语法编译程序语法、语义分析的的核心语义分析的的核心程序是程序是BLOCKBLOCK过程，过程， z说明部分的分析说明部分的分析与处理与处理z表格管理表格管理z过程体过程体( (语句）的分析语句）的分析与处理与处理说明部分的分析说明部分的分析与处理与处理对每个过程（含主程序）对每个过程（含主程序）说明的对象说明的对象（变量变量，常量常量和和过程过程）造造符号表符号表 登录登录标识符的标识符的属性属性。 标识符的属性标识符的属性: :种类
28、，所在种类，所在层次层次, ,值值和分配的和分配的相对位置相对位置。 登录信息由登录信息由ENTERENTER过程完成。过程完成。说明部分的分析说明部分的分析与处理与处理（程程序）序）z说明种类的定义： object= (constant, variable,procedur) （定义定义纯量纯量/ /枚举枚举类型）类型）z符号表的定义 table:array0.txmax of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer); 例
29、程序说明部分为：例程序说明部分为：CONST A=35CONST A=35，B=49B=49； VAR C VAR C，D D，E E； PROCEDURE P PROCEDURE P； VAR G VAR G ； 符号表符号表 名字名字 种类种类 层次层次/值值 地址地址 存储空间存储空间对应名字表对应名字表ztxtx ：tabletable表表的下标指针的下标指针, ,是以是以值参数值参数形式使用形式使用的。的。zdx: 计算每个变量在运行栈中相对本计算每个变量在运行栈中相对本过程过程基地址基地址的偏移量的偏移量 ，放在放在table表表中的中的adr域，域，生成生成目标目标代码代码时再时
30、再放在放在codecode中的中的a域域变量定义语句的处理变量定义语句的处理语法：语法：: := varvar ， ；程序：程序： if sym=if sym=varsymvarsym then then begin begin getsymgetsym; ; repeat repeat vardeclarationvardeclaration;(*;(*变量说明处理变量说明处理*) while sym=while sym=commacomma do do begin begin getsym getsym; ; vardeclarationvardeclaration end;end; if
31、 sym= if sym=semicolonsemicolon then then getsymgetsym else error(5)else error(5) until sym until symidentident; ; end; end;变量说明处理变量说明处理z procedure procedure vardeclarationvardeclaration; ; beginbegin if if sym=sym=identidentthenthen beginbegin enterenter( (variablevariable);); getsymgetsym endend e
32、lse else error(4)error(4) end(* end(*vardeclarationvardeclaration*);*);过程过程ENTERENTER的实现的实现ztxtx ：tabletable表表的指针的指针z procedure procedure enterenter( (k k:object );:object ); begin (* enter object into table *) begin (* enter object into table *) txtx:=:=txtx+1;+1; with tablewith tabletxtx do do (*(
33、* 开域开域语句语句 * *） beginbegin namename:=:=idid;(* ;(* 表示表示tabletabletxtx.namename:=:=idid;*;*） kindkind:=:=k k;(* ;(* 表示表示tabletabletxtx.kindkind:=:=k k;* );* )过程过程ENTERENTER的实现的实现 casecase k k of of constantconstant: : begin begin if if numnum amaxamax then then begin begin error(31); error(31); numnu
34、m:=0;:=0; end; end; valval:=:=numnum;(* ;(* tabletabletxtx.valval:=:=numnum;*);*) end; end;过程过程ENTERENTER的实现的实现 variablevariable: : begin begin levellevel:=:=levlev; ; （* *表示表示tabletabletxtx.levellevel:=:=levlev* *） adradr:=:=dxdx; ; （* *表示表示tabletabletxtx.adradr:=:=dxdx* *） dx dx:=:=dxdx+1;+1; end;
35、 end; procedurprocedur: : levellevel:=:=levlev (* (* 表示表示tabletabletxtx.levellevel:=:=levlev;*;*） end(* end(* casecase *); *); endendend(*enter*);end(*enter*);过程体的处理过程体的处理y对对语句进行语句进行语法语法分析分析y语义分析语义分析 当遇到当遇到标识符的引用时标识符的引用时就调用就调用POSITIONPOSITION函数函数查查TABLETABLE表表，看是否，看是否有有过过正确定义正确定义，若已有，则从表中，若已有，则从表中取相
36、应取相应的有关的有关信息信息，供代码的生成使用。，供代码的生成使用。若无定义则错若无定义则错。y当当语法语义正确时语法语义正确时，就，就生成生成相应语句功能的相应语句功能的目标代码目标代码赋值赋值语句的语句的处理处理 if if symsym = = ident ident then then begin begin i:= position(id); i:= position(id); if i= 0 then error(11) if i= 0 then error(11) else if tablei.kind variable else if tablei.kind variable
37、then then begin error(12); begin error(12); i:= 0 i:= 0 end; end; getsymgetsym; ; if if symsym = becomes then = becomes then getsymgetsym else error(13); else error(13); expression( expression(fsysfsys);); if i 0 then if i 0 then with table i do with table i do gengen( (stosto, ,levlev-level,-level,
38、adradr) ) end end 代码生成代码生成z代码生成是由过程代码生成是由过程GENGEN完成。完成。zGENGEN有有3 3个个参数参数，分别代表目标代码的，分别代表目标代码的功能码功能码，层差层差和和位移量位移量。例如。例如 gengen( (opropr,0,16); ,0,16); gengen( (stosto, ,levlev- -levellevel, ,adradr) ) levlev：当当前前处理的处理的过程过程层次层次 levellevel：被被引用变量或过程所在引用变量或过程所在层次层次CXCX：为目标代码为目标代码codecode数组的下标指针数组的下标指针结构
39、变换， 地址返填zIf c then s getsym;z condition;z if sym=thensymz then getsymz else error(16);z cx1:= cx;z gen(jpc,0,0)z statement( );z codecx1.a:=cx PL/0PL/0编译程序错误处理的实现编译程序错误处理的实现 对语法错误的两种处理方法：对语法错误的两种处理方法：(1) (1) 对于对于易于校正易于校正的错误，如丢了逗号，分的错误，如丢了逗号，分号等，指出出错位置，号等，指出出错位置，加以校正加以校正，继续进行，继续进行分析。分析。(2) (2) 对于对于难于校
40、正难于校正的错误，给出错误的位置的错误，给出错误的位置与性质，与性质，跳过后面的一些单词跳过后面的一些单词，直到下一个直到下一个可以进行正常语法分析的语法单位。可以进行正常语法分析的语法单位。 z在在进入进入某个某个语法单位语法单位时，调用时，调用TESTTEST, ,检查当前符号检查当前符号是否属于该是否属于该语法单位的开始符号集合语法单位的开始符号集合。若不属于，。若不属于，则则滤去滤去开始开始符号符号和和后继后继符号符号集合外集合外的所有符号。的所有符号。z在在语法单位语法单位分析结束分析结束时，调用时，调用TESTTEST, ,检查当前符号检查当前符号是否属于调用该语法单位时应有的是否
41、属于调用该语法单位时应有的后继后继符号集合。符号集合。若不属于，则若不属于，则滤去滤去后继后继符号和符号和开始开始符号符号集合外集合外的的所有符号所有符号。 TEST TESTTEST TEST开始符号集合与后继符号集合开始符号集合与后继符号集合z开始符号开始符号集合集合 symset=set of symbol;declbegsys, statbegsys, facbegsys:symset;z开始符号集合（开始符号集合（* *主程序主程序* *）declbegsys:=constsym,varsym,procsym; statbegsys:=beginsym,callsym,ifsym,
42、whilesym,readsym,writesym; facbegsys:=ident,number,lparen; z后继符后继符号集合号集合fsys作为参数：作为参数：procedure test(s1,s2:symset; n:integer);procedure block(lev,tx:integer; fsys:symset); procedure statement(fsys:symset);procedure expression (fsys:symset);procedure term (fsys:symset);procedure factor (fsys:symset);
43、READREAD语句的语法语义分析处理语句的语法语义分析处理 if sym=if sym=readsymreadsym then then begin begin getsymgetsym; ; if sym if symlparenlparen then error(34) then error(34) else else repeatrepeat getsym getsym; ; READREAD语句的语法语义分析处理语句的语法语义分析处理 if sym=if sym=identident then i:= then i:=positionposition(id)(id) else i:=
44、0; else i:=0; if i=0 then error(35) if i=0 then error(35) else else with tablei dowith tablei do beginbegin gengen( (opropr,0,16);,0,16); gen gen( (stosto, ,levlev- -levellevel, ,adradr) ) endend; ;READREAD语句的语法语义分析处理语句的语法语义分析处理 getsymgetsym untiluntil sym symcommacomma; ; if sym if symrparenrparen
45、then then begin begin error(33); error(33); while not(sym in while not(sym in fsysfsys) ) do do getsymgetsym endend else else getsym getsym endend出错处理出错处理跳过不应出现跳过不应出现的符号的符号正确正确出出口口TESTSYM在在S1中中?打印出错编号打印出错编号nS1:=S1+S2SYM在在S1中中?GETSYM返回返回YYNNTEST测测试试过过程程流流程程图图 因子的处理过程因子的处理过程z例：因子的处理过程例：因子的处理过程 procedu
46、re factor(fsys:symset); var i:integer; begin 入口：入口： test(facbegsys,fsys,24); while sym in facbegsys do begin if . 出口：出口： test(fsys,facbegsys,23); end end; 因子的处理过程因子的处理过程Facbegsysy 处理处理ident number, lparentestntestz增加后跟符增加后跟符与与调用位置有关调用位置有关 例：调用例：调用expression(fsys); z write语句的语句的语法语法write(,); write语句语
47、句(后后调用调用expression时时后跟符后跟符 expression(rparen,comma+fsys);zfactor的的语法语法：factor=.|.|( exp )在在factor(后后调用调用expression时时后跟符后跟符 expression(rparen+fsys); 类类pcodepcode代码解释器的实现代码解释器的实现z类类pcode解释器的结构解释器的结构z目标代码解释执行时目标代码解释执行时数据栈的布局数据栈的布局（运行（运行栈的存储分配）栈的存储分配）类类pcodepcode解释器的结构解释器的结构z目标代码存放在数组目标代码存放在数组CODECODE中。
48、中。z解释程序定义一个一维整型数组解释程序定义一个一维整型数组S S作为作为运行栈运行栈栈顶寄存器栈顶寄存器（指针）（指针）t t，基址寄存器基址寄存器（指针）（指针）b b，程序地址寄存器程序地址寄存器p p，指令寄存器指令寄存器i i目标代码解释执行时数据栈的布局目标代码解释执行时数据栈的布局（运行栈的存储分配）（运行栈的存储分配）在每个过程调用时在栈顶分配在每个过程调用时在栈顶分配3 3个联系单元：个联系单元：ySLSL： 静态链静态链，指向，指向定义定义该过程的该过程的直接外过程直接外过程 （或主程序）运行时（或主程序）运行时最新最新数据段的基地址数据段的基地址。yDLDL： 动态链动
49、态链，指向，指向调用调用该过程前正在运行过该过程前正在运行过 程的数据段基地址。程的数据段基地址。yRARA： 返回地址返回地址，记录调用该过程时，记录调用该过程时目标程序目标程序的的断点断点，即调用过程指令的下一条指令的地址。，即调用过程指令的下一条指令的地址。 目标代码的解释执行目标代码的解释执行 运行栈运行栈S SzM M调用过程调用过程Q Q RA RA DL DL SL SLb. ttbQM目标代码的解释执行目标代码的解释执行几条几条特殊指令特殊指令在在code中的中的位置位置和和功能功能yINT 0 AINT 0 A在在过程过程目标程序的目标程序的入口处入口处，开辟开辟A A个单元
50、的数据段。个单元的数据段。A A为为局部变量局部变量的的个数个数+ +3 3。yOPR 0 0OPR 0 0在在过程过程目标程序的目标程序的出口处出口处，释放数据段释放数据段（退栈），（退栈），恢复调用恢复调用该过程该过程前前正在运行的过程正在运行的过程的数据段的数据段基址寄基址寄存器存器B B和和栈顶寄存器栈顶寄存器T T的值，并将的值，并将返回地址返回地址送送到指令到指令地址寄存器地址寄存器P P中，以使调用前的程序从中，以使调用前的程序从断点断点开始开始继继续执行续执行。目标代码的解释执行目标代码的解释执行几条几条特殊特殊指令在指令在code中的中的位置位置和和功能功能yCAL L AC
51、AL L A调用过程调用过程，还完成，还完成填写填写静态链静态链、动态链动态链、返回返回地址地址，给出，给出被调被调用用过程过程的的基地址基地址值，值，送送入基址入基址寄存器寄存器B B中，目标程序的中，目标程序的入口入口地址地址A A的值的值送送指令指令地址寄存器地址寄存器P P中，使指令从中，使指令从A A开始执行。开始执行。 附附 PL/0PL/0编译程序代码生成的实现编译程序代码生成的实现zCXCX：为目标代码为目标代码codecode数组的下标指针。数组的下标指针。 codecode为一为一维数组，数组元素为维数组，数组元素为记录型数据记录型数据。每一个记录就是。每一个记录就是一条目
52、标指令。一条目标指令。CXCX 为整数变量，由为整数变量，由0 0开始顺序增加。开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。序的目标代码在最后。ztxtx ：tabletable表表的下标指针的下标指针, ,是以是以值参数值参数形式使用的。形式使用的。zdx: 计算每个变量在运行栈中相对本计算每个变量在运行栈中相对本过程过程基地址基地址的偏的偏移量移量 ，放在放在table表表中的中的adr域，域，生成生成目标代码目标代码时时再再放在放在codecode中的中的a域域。附附 PL/0PL/0编译程序代码生成的实现编译
53、程序代码生成的实现下标指针下标指针cx，tx和和变量变量dx的作用的作用code cx tabletx s t (运行栈运行栈)cx tx t(运行时栈指运行时栈指针针)(0) jmp 0 0(1) int 0 7 . .(cx ) .(0) name adr.(1) b (dx) . ( tx) q p mb附附 PL/0PL/0编译程序代码生实现编译程序代码生实现zTable表的表的下标指针下标指针tx补充说明：补充说明： 主程序主程序BLOCK第第1次次调用调用blockBLOCK（0，0，） 0 0 .BLOCK BLOCK（LEV+1,TX，）( (递归递归进入进入分程序分程序) )
54、LEVtxLEVtx（6）6 （9）1 tx是是BLOCK的的实际实际值参值参附附 PL/0PL/0编译程序代码生成的实现编译程序代码生成的实现 procedure procedure gengen( (x x: :fctfct; ; y y, , z z:integer); :integer); beginbegin if if cxcx cxmaxcxmax then then（* *指针越界指针越界* *） beginbegin write( write(program too longprogram too long);); close(fin); close(fin);（* *关闭文
55、件关闭文件* *） writelnwriteln; ; exit exit end; end;附附 PL/0PL/0编译程序代码生成的实现编译程序代码生成的实现 with codewith codecxcx do do beginbegin f f:=:=x x; ;（* * 表示表示codecodecxcx.f f:=:=x x; *); *) l l:=:=y y; ;（* * 表示表示codecodecxcx.l l:=:=y y; *) ; *) a a:=:=z z; ;（* * 表示表示codecodecxcx.a a:=:=z z; *); *) end;end; cx cx:=
56、:=cxcx+1+1end (*end (*gengen*);*);附附 PL/0PL/0编译程序代码生成的实现编译程序代码生成的实现对对分程序的定义（分程序的定义（见教材见教材292页）页） procedure block(lev,tx:integer;fsys:symset); var dx:integer; (*data allocationindex*) tx0:integer; (*initial table index*) cx0:integer; (*initial code index*) （ tx0，cx0是是tx，cx的初值）的初值）附附 PL/0PL/0编译程序代码生成的
57、实现编译程序代码生成的实现z对对分程序分程序体体人口的处理（见程序文本人口的处理（见程序文本block 的过程体的过程体） begin (*block*) dx:=3; tx0:=tx; （保留当前保留当前table表表指针值指针值） tabletx.adr:=cx;（保留当前保留当前codecode指针值到过程名指针值到过程名 的的adr域域 ） gen(jmp,0,0);（生成转向生成转向过程体入口的指令，该指令的地址过程体入口的指令，该指令的地址 为为cx 已已保留在过程名的保留在过程名的adr域，域，等生成等生成 过程过程 体入口的指令时，再由体入口的指令时，再由tabletx.adr
58、中取出中取出 cx将将过程体入口返填到过程体入口返填到cx中，即中，即 （ jmp,0,0）的第的第3区域。区域。 （注意注意dx， tx， cx的作用）的作用） CONST A=35CONST A=35，B=49B=49；VAR CVAR C，D D，E E；PROCEDURE PPROCEDURE P；VAR GVAR G附附 table表格管理表格管理 名字名字 类型类型 层次层次/值值 地址地址 存储空间存储空间 (0) jmp 0 0 CX (1 ) jmp 0 0 . .记录记录 过程在过程在code的的入入口到口到table中的中的adr域域附附 PL/0PL/0编译程序代码生成
59、的实现编译程序代码生成的实现过程过程体体入口入口时的处理时的处理codetabletx0.adr.a:=cx; （过程入口地址填过程入口地址填 写在写在code中中）with tabletx0 do begin adr:=cx; （过程的过程的入口入口填填 写在写在table中中） size:=dx; （过程过程占的空间占的空间填填 写在写在table中中） end; cxo:=cx; （保留保留过程在过程在code中的中的入口地址）入口地址）gen(int,0,dx);（生成生成过程过程入口指令入口指令）interpret三个寄存器赋初值三个寄存器赋初值t:=0; b:=1; p:=0;主程
60、序的主程序的SL，DL，RA赋初值赋初值s1:=0; s2=0; s3=0;i:=codep;p:=p+1;P=0?返回返回解解释释执执行行的的流流程程图图执行指令执行指令iNY主程序主程序的的RA s3=0附附 目标代码的解释执目标代码的解释执行行z几条几条特殊指令特殊指令的的解释执行解释执行：过程过程入口入口：开辟开辟a个单元个单元（见教材见教材304页）页）int: t:=t+a; （ t是当前是当前栈顶值）栈顶值）过程过程出口出口：释放数据段释放数据段（退栈）（退栈）（见教材见教材302页）页）opr: case a of (*operator*) 0: begin (*return*
61、) t:=b-1; 恢复调用前栈顶恢复调用前栈顶 p:=st+3; 送返回地址到送返回地址到p b:=st+2 恢复调用前基地址恢复调用前基地址 end;附附 目标代码的解释执行目标代码的解释执行z过程过程出口出口 RA RA DL DL SL SLb. tMtbt:=b-1;p:=st+3;b:=st+2Q附附 目标代码的解释执行目标代码的解释执行调用过程调用过程：cal: begin (*generat new block mark*) st+1:=base(l); 填写填写静态链静态链 st+2:=b; 填写填写动态链动态链 st+3:=p; 填写填写返回地址返回地址 b:=t+1; 被
62、调用过程的基地址被调用过程的基地址 p:=a 过程入口地址过程入口地址a送送p end;附附 目标代码的解释执行目标代码的解释执行function base(l:integer): integer; var b1:integer; begin b1:=b; (*find base l level down*) while l0 do begin b1:=sb1; l:=l-1; end; base:=b1 end (*base*);附附 目标代码的解释执行目标代码的解释执行zbase (l:integer): integer;bbbmp0bbq附附 运行时数据栈运行时数据栈S S的变化状态的变化状态教材25页
