第2章 PL/0编译程序 2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析

Presentation on theme: "第2章 PL/0编译程序 2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析"— Presentation transcript:

1 第2章 PL/0编译程序 2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析

2 PL/0编译程序 PL/0 语言程序 PL/0编译程序 类 pcode 代吗 源语言(PL/0) 目标语言(类 pcode) 实现语言（pascal) 类 pcode PL/0 pascal

3 PL/0编译系统的结构框架 PL/0源程序 PL/0编译程序 类 pcode代码 类 pcode解释程序 输入 输出

4 PL/0语言 PL/0程序示例 PL/0的语法描述图 PL/0语言文法的EBNF表示 PL/0语言：PASCAL语言的子集

5 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的过程体 主程序体

6 程序 . 分程序 内的文字表示非终结符 或 内的文字或符号表示终结符

7 ident = number 分程序 const , ; var ident , ; ; procedure 分程序 ident ; 语句

8 { } 表示花括号内的语法成分可重复任意次或限 定次数 [ ] 表示方括号内的语法成分为任选项 ( ) 表示圆括号内的成分优先
PL/0语言文法的EBNF表示 EBNF 引入的符号(元符号)： < > 用左右尖括号括起来的语法成分为非终结符 ∷= (→) ‘定义为’ ∷=(→) 的左部由右部定义 | ‘或’ { } 表示花括号内的语法成分可重复任意次或限 定次数 [ ] 表示方括号内的语法成分为任选项 ( ) 表示圆括号内的成分优先

9 例：用EBNF描述<整数>的定义 ： <整数>∷=[+|-]<数字>{<数字>} <数字>∷=0|1|2|3|4|5|6|7|8|9
或更好的写法 <整数>∷=[+|-]<非零数字>{<数字>}|0 <非零数字>∷=1|2|3|4|5|6|7|8|9 <数字>∷=0|<非零数字>

10 PL/0语言是PASCAL语言的子集 同PASCAL 作用域规则（内层可引用包围它的外层定义的标识符），上下文约束，
过程可嵌套定义，可递归调用 子集 数据类型,只有整型 数据结构 ,只有简变和常数 数字最多为14位 标识符的有效长度是10 语句种类 过程最多可嵌套三层

11 目标代码类pcode f l a 目标代码类pcode是一种假想栈式计算机的汇编语言。 指令格式： f 功能码

12 指 令 功 能 表

13 const a=10; var b,c; procedure p; begin c:=b+a; end; begin read(b); while b#0 do 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 将栈顶值存入变量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 无条件转到循环入口(11) (24) opr 0 0 结束退栈

14 PL/0编译程序的结构 PL/0源程序 词法分析程序 表格管理程序 语法语义分析程序 出错处理程序 代码生成程序 目标程序

15 PL/0编译程序的总体设计 其编译过程采用一趟扫描方式 以语法、语义分析程序为核心
词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。 表格管理程序实现变量，常量和过程标识符的信息的登录与查找。 出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误 性质有关的编号，并进行错误恢复。

16 PL/0编译程序词法分析的设计与实现 识别的单词： 保留字或关键字：如：BEGIN、 END、 IF、 THEN等 运算符： 如：+、-、*、/、：=、#、>=、<=等 标识符： 用户定义的变量名、常数名、过程名 常数： 如：10、25、100等整数 界符： 如：‘,’、‘.’ 、‘;’ 、‘(’ 、‘)’等

17 词法分析过程GETSYM所要完成的任务：
读源程序（getch) 滤空格 识别保留字 识别标识符 拼数 识别单字符单词 拼双字符单词

18 词法分析过程:GETSYM框图（见教材图2.5）
程序（ procedure getsym） 当识别到标识符时先查保留字表 保留字表：（ begin (* main * ) ） word[1]:=‘begin ‘；word[2]:=‘call ‘； ... word[13]:=‘write ‘； 查到时找到相应的内部表示 Wsym[1]:=beginsym; wsym[2]:=callsym； … wsym[13]:=writesym；

19 字符对应的单词表： ssym[‘+’]:=plus; ssym[‘-’]:=minus; … ssym[‘;’]:=semicolon; 词法分析如何把单词传递给语法分析 type symbol=(nul,ident,number,plus,…,varsym,procsym)； 3个全程量 sym:symbol; id:alfa; num:integer;

20 通过三个全程量 SYM 、ID和NUM 将识别出的单词信息传递给语法分析程序。
如：有程序段落为： begin initial := 60；end 对应单词翻译后变为： begin beginsym, initial ident, ‘:= ‘ becomes, number, ‘；’ semicolon， end endsym 。 ID： 存放用户所定义的标识符的值 如： initial （在SYM中放ident，在ID中放initial） NUM：存放用户定义的数 如：60 （在SYM中放在number在NUM中放60）

21 使用状态转换图实现词法分析程序的设计方法
词法分析程序的设计---使用状态转换图实现 表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操作。 表示终态，已识别出一个单词。

22

23 PL/0编译程序语法语义分析 PL/0编译程序语法分析的设计与实现
自顶向下的语法分析 递归子程序法

24 程序 . 分程序

25 ident = number 分程序 const , ; var ident , ; ; procedure 分程序 ident ; 语句

26 ：= ident 表达式 语句 end begin 语句 语句 ; read ( ident ) ,

27 自顶向下的语法分析 VAR A; BEGIN READ(A) END. <程序> <分程序> .
<分程序> <变量说明部分> <语句> VAR <标识符> ； <复合语句> A BEGIN <语句> END <读语句> READ （ <标识符> ） A <程序>为文法的 开始符号，以开 始符号作为根结 点构造一棵倒挂 着的语法树。

28 递归子程序法 递归子程序法：对应每个非终结符语法单元，，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符<程序>（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。

29 例：如何用递归子程序法实现表达式的语法分析
语法图 + 表达式 项 - + 项 - 项 因子 * 因子 /

30 因子的语法图 因子 ident number ( ) 表达式

31 表达式的EBNF 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} 〈项〉∷=〈因子〉{（

32 〈表达式〉的递归子程序实现 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;

33 〈项〉的递归子程序实现 procedure term; begin factor; while sym in [ times, slash ] do begin getsym; factor; end end;

34 getsym else error end else error
〈因子〉的递归子程序实现 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;

35 <程序>∷=<分程序> begin（*main*) …(*initialize*)
…(*r/w file set*) getsym; block( ); … if sym < > period then error... end. 。

36 语 法 调 用 关 系 图 程序 pl0 分程序 block 语句 statement 条件 condition 表达式expression
项 term 因子 factor

37 编译程序总体流程图

38 PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，
说明部分的分析与处理 表格管理 过程体(语句）的分析与处理

39 说明部分的分析与处理 对每个过程（含主程序）说明的对象（变量，常量和过程）造符号表 标识符的属性:种类，所在层次,值和分配的相对位置。
登录标识符的属性。 标识符的属性:种类，所在层次,值和分配的相对位置。 登录信息由ENTER过程完成。

40 说明部分的分析与处理（程序） 说明种类的定义： object= (constant, variable,procedur)
（定义纯量/枚举类型） 符号表的定义 table:array[0..txmax] of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer);

41 符号表 对应名字表 名字 种类 层次/值 地址 存储空间
例程序说明部分为：CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G ；… 对应名字表 名字 种类 层次/值 地址 存储空间

42 tx ：table表的下标指针,是以值参数形式使用的。
dx: 计算每个变量在运行栈中相对本过程基地址的偏移量 ，放在table表中的adr域，生成目标代码时再放在code中的a域

43 变量定义语句的处理 语法：<变量说明部分>: := var <标识符>{， <标识符>}； 程序：
if sym=varsym then begin getsym; repeat vardeclaration;(*变量说明处理*) while sym=comma do begin getsym; vardeclaration end; if sym=semicolon then getsym else error(5) until sym<>ident; end;

44 变量说明处理 procedure vardeclaration; begin if sym=identthen begin enter(variable); getsym end else error(4) end(*vardeclaration*);

45 过程ENTER的实现 tx ：table表的指针
procedure enter(k:object ); begin (* enter object into table *) tx:=tx+1; with table[tx] do (* 开域语句 *） begin name:=id;(* 表示table[tx].name:=id;*） kind:=k;(* 表示table[tx].kind:=k;* )

46 过程ENTER的实现 case k of constant: begin if num>amax then
begin error(31); num:=0; end; val:=num;(* table[tx].val:=num;*) end;

47 过程ENTER的实现 variable: begin level:=lev;
（*表示table[tx].level:=lev*） adr:=dx; （*表示table[tx].adr:=dx*） dx:=dx+1; end; procedur: level:=lev (* 表示table[tx].level:=lev;*） end(* case *); end end(*enter*);

48 过程体的处理 对语句进行语法分析 语义分析 当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。 当语法语义正确时，就生成相应语句功能的目标代码

49 赋值语句的处理 if sym = ident then getsym; begin i:= position(id);
if i= 0 then error(11) else if table[i].kind <>variable then begin error(12); i:= 0 end; getsym; if sym = becomes then getsym else error(13); expression(fsys); if i <>0 then with table [i] do gen(sto,lev-level,adr) end

50 代码生成 代码生成是由过程GEN完成。 GEN有3个参数，分别代表目标代码的功能码，层差和位移量。例如 lev：当前处理的过程层次
gen(opr,0,16); gen(sto,lev-level,adr) lev：当前处理的过程层次 level：被引用变量或过程所在层次 CX：为目标代码code数组的下标指针

51 If c then s getsym; condition; if sym=thensym then getsym
结构变换， 地址返填 If c then s getsym; condition; if sym=thensym then getsym else error(16); cx1:= cx; gen(jpc,0,0) statement( ); code[cx1].a:=cx

52 PL/0编译程序错误处理的实现 对语法错误的两种处理方法： (1) 对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析。 (2) 对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。

53 在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。
╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳ TEST TEST 在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。 在语法单位分析结束时，调用TEST,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于，则滤去后继符号和开始符号集合外的所有符号。

54 开始符号集合与后继符号集合

55 开始符号集合 symset=set of symbol; declbegsys, statbegsys, facbegsys:symset; 开始符号集合（*主程序*） declbegsys:=[constsym,varsym,procsym]; statbegsys:=[beginsym,callsym,ifsym, whilesym,readsym,writesym]; facbegsys:=[ident,number,lparen];

56 后继符号集合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);

57 READ语句的语法语义分析处理 if sym=readsym then begin getsym;
if sym<>lparen then error(34) else repeat

58 READ语句的语法语义分析处理 if i=0 then error(35) else with table[i] do begin
if sym=ident then i:=position(id) else i:=0; if i=0 then error(35) else with table[i] do begin gen(opr,0,16); gen(sto,lev-level,adr) end;

59 READ语句的语法语义分析处理 getsym until sym<>comma;
if sym<>rparen then begin error(33); while not(sym in fsys) do getsym end else getsym 出错处理 跳过不应出现的符号 正确出口

60 TEST测试过程流程图 TEST Y SYM在S1中? N 打印出错编号n 返回 S1:=S1+S2 Y SYM在S1中? N GETSYM

61 因子的处理过程 例：因子的处理过程 procedure factor(fsys:symset); var i:integer; begin
入口： test(facbegsys,fsys,24); while sym in facbegsys do if ... 出口： test(fsys,facbegsys,23); end end;

62 因子的处理过程 test Facbegsys n y 处理ident number, lparen test

63 增加后跟符与调用位置有关 例：调用expression(fsys); write语句的语法write(<exp>{,<exp>}); write语句(后调用expression时后跟符 expression([rparen,comma]+fsys); factor的语法：factor∷=...|‘(’ exp ’) 在factor(后调用expression时后跟符 expression([rparen]+fsys);

64 类pcode代码解释器的实现 类pcode解释器的结构 目标代码解释执行时数据栈的布局（运行栈的存储分配）

65 类pcode解释器的结构 目标代码存放在数组CODE中。 解释程序定义一个一维整型数组S作为运行栈
栈顶寄存器（指针）t，基址寄存器（指针）b，程序地址寄存器p，指令寄存器i

66 目标代码解释执行时数据栈的布局（运行栈的存储分配）
在每个过程调用时在栈顶分配3个联系单元： SL： 静态链，指向定义该过程的直接外过程 （或主程序）运行时最新数据段的基地址。 DL： 动态链，指向调用该过程前正在运行过 程的数据段基地址。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。

67 目标代码的解释执行 运行栈S M调用过程Q t . Q RA DL SL b t M b

68 目标代码的解释执行 几条特殊指令在code中的位置和功能
INT 0 A 在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。 OPR 0 0 在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。

69 目标代码的解释执行 几条特殊指令在code中的位置和功能
CAL L A 调用过程，还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。

70 附 PL/0编译程序代码生成的实现 tx ：table表的下标指针,是以值参数形式使用的。
CX：为目标代码code数组的下标指针。 code为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。CX 为整数变量，由0开始顺序增加。实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。 tx ：table表的下标指针,是以值参数形式使用的。 dx: 计算每个变量在运行栈中相对本过程基地址的偏移量 ，放在table表中的adr域，生成目标代码时再放在code中的a域。

71 code [cx] table[tx] s [t] (运行栈) cx tx t(运行时栈指针)
附 PL/0编译程序代码生成的实现 下标指针cx，tx和变量dx的作用 code [cx] table[tx] s [t] (运行栈) cx tx t(运行时栈指针) (0) jmp 0 0 (1) int 0 7 . (cx ) . (0) name …adr... (1) b (dx) ... ( tx) q b p m

72 附 PL/0编译程序代码生实现 Table表的下标指针tx补充说明： tx是BLOCK的 实际值参 tx tx
6 （9） LEV 1 BLOCK（LEV+1,TX，…） (递归进入分程序) BLOCK ... tx （6） LEV 第1次调用block BLOCK（0，0，…） BLOCK 主程序

73 附 PL/0编译程序代码生成的实现 procedure gen(x:fct; y, z:integer); begin if cx>cxmax then（*指针越界*） begin write(‘program too long’); close(fin);（*关闭文件*） writeln; exit end;

74 附 PL/0编译程序代码生成的实现 with code[cx] do begin f:=x;（* 表示code[cx].f:=x; *)
l:=y;（* 表示code[cx].l:=y; *) a:=z;（* 表示code[cx].a:=z; *) end; cx:=cx+1 end (*gen*);

75 附 PL/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的初值）

76 附 PL/0编译程序代码生成的实现 对分程序体人口的处理（见程序文本block 的过程体） begin (*block*) dx:=3;
tx0:=tx; （保留当前table表指针值） table[tx].adr:=cx;（保留当前code指针值到过程名 的adr域 ） gen(jmp,0,0);（生成转向过程体入口的指令，该指令的地址 为cx 已保留在过程名的adr域，等生成 过程 体入口的指令时，再由table[tx].adr中取出 cx将过程体入口返填到cx中，即 （ jmp,0,0）的第3区域。 … （注意dx， tx， cx的作用）

77 附 table表格管理 (0) jmp 0 0 CX (1 ) jmp 0 0
. CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G 记录 过程在code的入 口到table中的adr域 名字 类型 层次/值 地址 存储空间

78 附 PL/0编译程序代码生成的实现 过程体入口时的处理 code[table[tx0].adr].a:=cx;
with table[tx0] do begin adr:=cx; （过程的入口填 写在table中） size:=dx; （过程占的空间填 写在table中） end; cxo:=cx; （保留过程在code中的入口地址） gen(int,0,dx);（生成过程入口指令）

79 解释执行的流程图 主程序 的RA s[3]=0 interpret 三个寄存器赋初值 t:=0; b:=1; p:=0;
主程序的SL，DL，RA赋初值 s[1]:=0; s[2]=0; s[3]=0; i:=code[p]; p:=p+1; 执行指令i 主程序 的RA s[3]=0 P=0? N Y 返回

80 附 目标代码的解释执行 几条特殊指令的解释执行： 过程入口：开辟a个单元（见教材304页） int: t:=t+a; （ t是当前栈顶值）
附 目标代码的解释执行 几条特殊指令的解释执行： 过程入口：开辟a个单元（见教材304页） int: t:=t+a; （ t是当前栈顶值） 过程出口：释放数据段（退栈）（见教材302页） opr: case a of (*operator*) 0: begin (*return*) t:=b-1; 恢复调用前栈顶 p:=s[t+3]; 送返回地址到p b:=s[t+2] 恢复调用前基地址 end;

81 附 目标代码的解释执行 过程出口 t . t:=b-1; p:=s[t+3]; b:=s[t+2] Q RA DL SL b t M b

82 附 目标代码的解释执行 调用过程： cal: begin (*generat new block mark*)
附 目标代码的解释执行 调用过程： cal: begin (*generat new block mark*) s[t+1]:=base(l); 填写静态链 s[t+2]:=b; 填写动态链 s[t+3]:=p; 填写返回地址 b:=t+1; 被调用过程的基地址 p:=a 过程入口地址a送p end;

83 附 目标代码的解释执行 function base(l:integer): integer; var b1:integer;
附 目标代码的解释执行 function base(l:integer): integer; var b1:integer; begin b1:=b; (*find base l level down*) while l>0 do begin b1:=s[b1]; l:=l-1; end; base:=b1 end (*base*);

84 附 目标代码的解释执行 base (l:integer): integer; q b b p b b m b

85 附 运行时数据栈S的变化状态 教材25页