《清华大学-编译原理第二章》由会员分享，可在线阅读，更多相关《清华大学-编译原理第二章（86页珍藏版）》请在金锄头文库上搜索。
1、第2章 PL/0编译程序,2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析 2.4 PL/0编译程序的错误处理 2.5 类pcode代码解释器 本章目的：以PL/0为实例,学习编译程序实现的基本步骤和相关技术,PL/0编译程序,PL/0编译程序,PL/0 语言程序,类 pcode 代吗,源语言(PL/0) 目标语言(类 pcode) 实现语言（pascal),PL/0,类 pcode,pascal,PL/0编译程序,类 pcode解释程序,类 pcode代码,PL/0源程序,输入,输出,PL/0编译系统的结构框架,PL/0语言,P
2、L/0程序示例 PL/0的语法描述图 PL/0语言文法的EBNF表示 PL/0语言：PASCAL语言的子集,PL/0程序示例,CONST A=10; （* 常量说明部分 *） VAR B,C; （* 变量说明部分 *） PROCEDURE P; （* 过程说明部分 *） VAR D; PROCEDURE Q; VAR X; BEGIN READ(X); D:=X; WHILE X#0 DO CALL P; END; BEGIN WRITE(D); CALL Q; END; BEGIN CALL P; END.,Q的过程体,p的过程体,主程序体,程序,分程序,.,内的文字表示非终结符,或,内的文
3、字或符号表示终结符,const,ident,number,=,;,ident,;,;,procedure,ident,;,分程序,语句,分程序,PL/0语言文法的EBNF表示,EBNF 引入的符号(元符号)： 用左右尖括号括起来的语法成分为非终结符 = () 定义为 =() 的左部由右部定义 | 或 表示花括号内的语法成分可重复任意次或限 定次数 表示方括号内的语法成分为任选项 ( ) 表示圆括号内的成分优先,例：用EBNF描述的定义 ： =+|- =0|1|2|3|4|5|6|7|8|9 或更好的写法 =+|-|0 =1|2|3|4|5|6|7|8|9 =0|,PL/0语言是PASCAL语言
4、的子集,同PASCAL 作用域规则（内层可引用包围它的外层定义的标识符），上下文约束， 过程可嵌套定义，可递归调用 子集 数据类型,只有整型 数据结构 ,只有简变和常数 数字最多为14位 标识符的有效长度是10 语句种类 过程最多可嵌套三层,目标代码类pcode,目标代码类pcode是一种假想栈式计算机的汇编语言。 指令格式：,f l a,f 功能码 l 层次差 （标识符引用层减去定义层） a 根据不同的指令有所区别,指 令 功 能 表,const a=10; var b,c; procedure p; begin c:=b+a; end; begin read(b); while b#0 d
5、o begin call p; write(2*c); read(b); end end.,( 0) jmp 0 8 转向主程序入口 ( 1) jmp 0 2 转向过程p入口 ( 2) int 0 3 过程p入口,为过程p开辟空间 ( 3) lod 1 3 取变量b的值到栈顶 ( 4) lit 0 10 取常数10到栈顶 ( 5) opr 0 2 次栈顶与栈顶相加 ( 6) sto 1 4 栈顶值送变量c中 ( 7) opr 0 0 退栈并返回调用点(16) ( 8) int 0 5 主程序入口开辟5个栈空间 ( 9) opr 0 16 从命令行读入值置于栈顶 (10) sto 0 3 将栈顶
6、值存入变量b中 (11) lod 0 3 将变量b的值取至栈顶 (12) lit 0 0 将常数值0进栈 (13) opr 0 9 次栈顶与栈顶是否不等 (14) jpc 0 24 等时转(24)（条件不满足转） (15) cal 0 2 调用过程p (16) lit 0 2 常数值2进栈 (17) lod 0 4 将变量c的值取至栈顶 (18) opr 0 4 次栈顶与栈顶相乘(2*c) (19) opr 0 14 栈顶值输出至屏幕 (20) opr 0 15 换行 (21) opr 0 16 从命令行读取值到栈顶 (22) sto 0 3 栈顶值送变量b中 (23) jmp 0 11 无条
7、件转到循环入口(11) (24) opr 0 0 结束退栈,PL/0编译程序的结构,词法分析程序,语法语义分析程序,代码生成程序,表格管理程序,出错处理程序,PL/0源程序,目标程序,PL/0编译程序的总体设计,其编译过程采用一趟扫描方式 以语法、语义分析程序为核心 词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。 表格管理程序实现变量，常量和过程标识符的信息的登录与查找。 出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误 性质有关的编号，并进行错误恢复。,P
8、L/0编译程序词法分析的设计与实现,识别的单词： 保留字或关键字：如：BEGIN、 END、 IF、 THEN等 运算符： 如：+、-、*、/、：=、#、=、=等 标识符： 用户定义的变量名、常数名、过程名 常数： 如：10、25、100等整数 界符： 如：,、. 、; 、( 、)等,词法分析过程GETSYM所要完成的任务： 读源程序（getch) 滤空格 识别保留字 识别标识符 拼数 识别单字符单词 拼双字符单词,词法分析过程:GETSYM框图（见教材图2.5） 程序（ procedure getsym） 当识别到标识符时先查保留字表 保留字表：（ begin (* main * ) ） w
9、ord1:=begin ；word2:=call ； . word13:=write ； 查到时找到相应的内部表示 Wsym1:=beginsym; wsym2:=callsym； wsym13:=writesym；,字符对应的单词表： ssym+:=plus; ssym-:=minus; ssym;:=semicolon; 词法分析如何把单词传递给语法分析 type symbol=(nul,ident,number,plus,varsym,procsym)； 3个全程量 sym:symbol; id:alfa; num:integer;,通过三个全程量 SYM 、ID和NUM 将识别出的单词
10、信息传递给语法分析程序。 SYM：存放单词的类别 如：有程序段落为： begin initial := 60；end 对应单词翻译后变为： begin beginsym, initial ident, := becomes, 60 number, ； semicolon， end endsym 。 ID： 存放用户所定义的标识符的值 如： initial （在SYM中放ident，在ID中放initial） NUM：存放用户定义的数 如：60 （在SYM中放在number在NUM中放60）,使用状态转换图实现词法分析程序的设计方法,词法分析程序的设计-使用状态转换图实现,表示状态，对应每个状态
11、编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。,表示终态，已识别出一个单词。,PL/0编译程序语法语义分析 PL/0编译程序语法分析的设计与实现,自顶向下的语法分析 递归子程序法,程序,分程序,.,const,ident,number,=,;,var,ident,;,;,procedure,ident,;,分程序,语句,分程序,ident,read,end,;,语句,表达式,：=,begin,语句,语句,),(,ident,自顶向下的语法分析,VAR A; BEGIN READ(A) END., . VAR ； A BEGIN END READ （ ） A,为文
12、法的 开始符号，以开 始符号作为根结 点构造一棵倒挂 着的语法树。,递归子程序法,递归子程序法：对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。
13、,例：如何用递归子程序法实现表达式的语法分析,项,表达式,+,-,项,+,-,项,因子,因子,*,/,语法图,因子的语法图,因子,ident,number,(,表达式,),表达式的EBNF 表达式=+|-项（+|-）项 项=因子（*|/）因子 因子=标识符|无符号整数|（表达式）,表达式的递归子程序实现 procedure expr; begin if sym in plus, minus then begin getsym; term; end else term; while sym in plus, minus do begin getsym; term; end end;,项的递归子程
14、序实现 procedure term; begin factor; while sym in times, slash do begin getsym; factor; end end;,因子的递归子程序实现 procedure factor; begin if sym ident then begin if sym number then begin if sym = ( then begin getsym; expr; if sym = ) then getsym else error end else error end end end;,= begin（*main*) (*initialize*) (*r/w file set*) getsym; block( ); if sym period then error. end. 。,程序 pl0,分程序 block,语句 statement,条件 condition,表达式expression,项 term,因子 factor,语 法 调 用 关 系 图,编译程序总体流程图,PL/0编译程序语义分析的设计与实现,PL
