第二讲 (PL/0) PL/0 编译程序导读.

Presentation on theme: "第二讲 (PL/0) PL/0 编译程序导读."— Presentation transcript:

1 第二讲 (PL/0) PL/0 编译程序导读

2 PL/0编译程序导读 类 P-code 虚拟机 PL/0 编译程序的词法分析 PL/0 编译程序的语法分析 PL/0 编译程序的语义分析

3 PL/0编译程序总体结构 T-型图 PL/0 类P-code C/Pascal

4 PL/0编译程序总体结构 PL/0编译程序的组织：一个以语法、语义 分析程序为中心的单遍编译程序 PL/0 程序 类P-code程序
语法、语义分析程序 词法分析程序 代码生成程序

5 PL/0 语言简介 PL/0 语言为一种简化的类Pascal 语言 PL/0 程序示例 PL/0 语言的语法描述图
PL/0 语言的EBNF表示 PL/0 语言的语义规则

6 PL/0 程序示例 CONST A=10; /*主程序常量说明部分*/ VAR B,C; /*主程序变量说明部分*/
PROCEDURE P; /*主程序过程说明部分*/ VAR D; /*过程P的局部变量说明部分*/ PROCEDURE Q; /*过程P的局部过程说明部分*/ VAR X; /*过程Q的局部变量说明部分*/ BEGIN READ(X); D:=X; WHILE X#0 DO CALL P; END; BEGIN WRITE(D); CALL Q; END BEGIN CALL P; END. P 的过程体 Q 的过程体 主程序的过程体

7 PL/0 程序示例 计算最大公约数 begin read(m); read(n); var m, n, r, q;
if m < n then r := m; m := n; n := r; end; r:=1; call gcd; write(m); end. var m, n, r, q; { 计算m和n的最大公约数 } procedure gcd; begin while r#0 do q := m / n; r := m - q * n; m := n; n := r; end end;

8 PL/0 程序示例 计算 begin {读入n } read(n); sum := 0; while n > 0 do m := n;
sum = 1! + 2 ! n!, (n从控制台读入) begin {读入n } read(n); sum := 0; while n > 0 do m := n; fact := 1; call factorial; sum := sum + fact; n := n - 1; end; {输出n! } write(sum); end. var n, m, fact, sum; { 递归计算 fact = m! } procedure factorial; begin if m > 0 then fact := fact * m; m := m - 1; call factorial; end;

9 PL/0 语言的语法描述图 每个语法单位对应一个语法描述图 一个入口和一个出口的有向图 从入口可到达任何节点 每个节点都可以到达出口
从入口到出口的路径表示该语法单位的 一种合法中间形式（短语） 有两种类型的节点 内的文字表示所用到的其他语法单位 或 内的文字表示单词符号

10 PL/0 语言的语法描述图 例：程序和分程序语法单位的语法描述图 . 程序 分程序 分程序 分程序 语句 const ident =
number ， ； var ident ， ； ； procedure ident ； 分程序 语句

11 PL/0 语言的EBNF表示 EBNF 的元符号 ‘< >’ 是用左右尖括号括起来的中文字表示语法构造
‘< >’ 是用左右尖括号括起来的中文字表示语法构造 成分，或称语法单位，为非终结符。 ‘::=’ 该符号的左部由右部定义，可读作‘定义为’ ‘|’ 表示‘或’，即左部可由多个右部定义 ‘{ }’ 表示花括号内的语法成分可以重复；在不加上 下界时可重复0到任意次数，有上下界时为可重复次 数的限制 ‘[ ]’ 表示方括号内的成分为任选项 ‘( )’ 表示圆括号内的成分优先

12 PL/0 语言的EBNF表示 例：PL/0 语言的EBNF表示片断 <程序> ::= <分程序>.
<分程序> ::= [<常量说明部分>] [<变量说明部分>] [<过程说明部分>] <语句> <常量说明部分> ::= CONST <常量定义> { ,<常量定义> } ; <常量定义> ::= <标识符> = <无符号整数> <无符号整数> ::= <数字> {<数字>} <变量说明部分> ::= VAR <标识符 > { , <标识符 > } ; <标识符> ::= <字母> {<字母>|<数字>} <过程说明部分> ::= <过程首部><分程序>{; <过程说明部分> }; <过程首部> ::= PROCEDURE <标识符> ； ……

13 PL/0 语言的语义规则 类型、上下文约束与作用域规则 数据类型只有整数类型 数据结构只支持简单变量和常数
所支持的数字为最长 9 位的十进制数 标识符的有效长度为10 标识符引用前先要声明 过程无参数 过程可嵌套，最多嵌套 3 层 过程可递归调用 内层过程可以引用包围它的外层过程的标识符

14 类P-code虚拟机 类P-code 虚拟机 输入数据 输出数据 PL/0 程序 类P-code程序 PL/0 编译程序

15 类P-code虚拟机 类 P-code 语言 指令格式 f l a 一种栈式机的语言 此类栈式机没有累加器和通用寄存器，有一
个栈式存储器，有四个控制寄存器（指令寄 存器 I，指令地址寄存器 P，栈顶寄存器 T 和基址寄存器 B），算逻运算都在栈顶进行 指令格式 f l a f ： 操作码 l ： 层次差 （标识符引用层减去定义层） a ： 不同的指令含义不同

16 类P-code虚拟机 指令 “INT 0 A” 在栈顶开辟 A 个存储单元，服务于被调用的过程 A 等于该过程的局部变量数加 3
3 个特殊的联系单元

17 类P-code虚拟机 指令 “OPR 0 0” 过程调用结束后,返回调用点并退栈 重置基址寄存器和栈顶寄存器

18 类P-code虚拟机 指令 “CAL L A” 调用地址为 A 的过程（置指令地址寄存器为A） L 为调用过程与被调用过程的层差
设置被调用过程的3 个联系单元

19 类P-code虚拟机 指令 “LIT 0 A” 指令 “LOD L A” 指令 “STO L A”
态链SL开始向前第L层的SL作为基址，加上A，即为该 单元的地址

20 类P-code虚拟机 指令 “OPR 0 1” 指令 “OPR 0 6” 求栈顶元素的相反数，结果值留在栈顶
栈顶元素的奇偶判断，若为奇数，结果为1；若为偶 数，结果为0 ；结果值留在栈顶

21 类P-code虚拟机 指令 “OPR 0 2” 指令 “OPR 0 3” 指令 “OPR 0 4” 指令 “OPR 0 5”
次栈顶与栈顶的值相加，结果存入次栈顶 T 减 1 指令 “OPR 0 3” 次栈顶的值减去栈顶的值，结果存入次栈顶 T 减 1 指令 “OPR 0 4” 次栈顶的值乘以栈顶的值，结果存入次栈顶 T 减 1 指令 “OPR 0 5” 次栈顶的值除以栈顶的值，结果存入次栈顶 T 减 1

22 类P-code虚拟机 指令 “OPR 0 8” 比较次栈顶与栈顶是否相等 指令 “OPR 0 9” 比较次栈顶与栈顶是否不相等
若相等，结果为0；存结果至次栈顶；T 减1 指令 “OPR 0 9” 比较次栈顶与栈顶是否不相等 若不相等，结果为0；存结果至次栈顶；T 减1 指令 “OPR ” 比较次栈顶是否小于栈顶 若小于，结果为0；存结果至次栈顶；T 减1 指令 “OPR ” 比较次栈顶是否大于等于栈顶 若大于等于，结果为0；存结果至次栈顶；T 减1 指令 “OPR ” 比较次栈顶是否大于栈顶 若大于，结果为0；存结果至次栈顶；T 减1 指令 “OPR ” 比较次栈顶是否小于等于栈顶 若小于等于，结果为0；存结果至次栈顶；T 减1

23 类P-code虚拟机 指令 “JMP 0 A” 指令 “JPC 0 A” 无条件转移至地址 A，即置指令地址寄存器为A 条件转移指令

24 类P-code虚拟机 指令 “OPR 0 14” 指令 “OPR 0 15” 指令 “OPR 0 16” 栈顶的值输出至控制台屏幕
T 减 1 指令 “OPR ” 控制台屏幕输出一个换行 指令 “OPR ” 从控制台读入一行输入，置入栈顶 T 加 1

25 类P-code虚拟机 类P-code 解释程序 数据结构 栈顶寄存器 int t； 运行栈 int s[stacksize]
指令寄存器 struct instruction { enum fct f; /*操作码*/ int l; /*引用层与声明层的层差*/ int a; /*因不同的f各异*/ } i 指令地址寄存器 int p; 基址寄存器 int b; 栈顶寄存器 int t； 虚拟机代码段 struct instruction code[cxmax];

26 类P-code虚拟机 类P-code 解释程序 处理流程 （1）初始化 p=b=t=0； s[0]=s[1]=s[2]=0；
（2）取指令到指令寄存器 i=code[p]； p++； （3）分析并解释执行指令 i （4）若程序未结束（p != 0），转（2） （5）返回

27 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 p 例 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. b t

28 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. p b t

29 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. p t b

30 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 5 p b

31 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t p 5 b

32 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 5 p 5 b

33 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 5 p 5 b

34 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 1 5 p b

35 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 5 p b

36 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. p 16 b t 5

37 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. p t 16 b 5

38 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 5 p 16 b 5

39 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 10 p 5 16 b 5

40 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 p 16 b 5

41 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t p 16 b 15 5

42 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 5 p b

43 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 2 15 5 p b

44 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 2 15 5 p b

45 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 30 15 5 p b

46 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 5 p b

47 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 5 p b

48 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 5 b p

49 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 b p

50 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. p t 15 b

51 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t p 15 b

52 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t p 15 b

53 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 p b

54 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. t 15 b p

55 类P-code虚拟机 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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. b t P=0

56 PL/0编译程序的词法分析 词法分析子程序 功能 int getsym( ) 从当前输入符号起扫描下一个词法单位，即单词
通过下列全局变量传递单词的类别 enum symbol sym; 通过下列全局变量传递标识符单词的值 char id [al+1]; /*al为标识符的最大长度*/ 通过下列全局变量传递常量单词的值 int num;

57 PL/0编译程序的词法分析 单词类别 保留字 BEGIN、 END、 IF、 THEN、...... 运算符
、、、、:=、=、、、、…… 标识符 自定义的变量名、常数名、过程名 常数 如：10，25，100等整数 界符 如：‘，’、‘.’、‘；’、‘（’、‘）’、……

58 PL/0编译程序的词法分析 词法分析子程序 getsym( ) 的处理流程 从源程序扫描下一个字符(调用getch子程序)
忽略空格、换行和TAB (每忽略一个，扫描下一个) enum symbol sym; 识别单词 (每扫描过一个字符，调用一次getch子程序) 识别保留字 识别标识符 拼数 识别单字符单词 拼双字符单词 根据单词类别设置sym，id 和 num

59 PL/0编译程序的词法分析 单词的识别 可以借助于状态转换图进行设计 状态转换图类似于有限状态自动机 识别标识符单词、数字单词、单字符单词和
双字符单词的状态转换图见下页 保留字单词的识别可以在识别标识符单词的 基础上，再去检索保留字表

60 PL/0编译程序的词法分析 实现单词识别的状态转换图

61 PL/0 编译程序的语法分析 功能 分析 PL/0 源程序的单词流是否符合 PL/0 语法 报告语法错误
产生源程序的语法分析结果，以语法分析树或 与之等价的形式体现出来

62 PL/0 编译程序的语法分析 分析方法 借助于PL/0的语法描述图或EBNF表示进行 自顶向下分析
造的语法分析树 语法分析树的根节点为<程序>，叶节点为构 成源程序的单词，每个内部节点代表构成源 程序的各种不同的语法单位

63 PL/0 编译程序的语法分析 自顶向下分析举例 . 自顶向下进行 递归下降分析 ； ( ) <程序> VAR A; BEGIN
READ(A) END. <分程序> . <变量说明部分> <语句> <标识符> VAR ； <复合语句> A <语句> BEGIN END <读语句> 自顶向下进行 递归下降分析 ( ) <标识符> READ A

64 PL/0 编译程序的语法分析 实现方法 递归子程序法 可以自然实现递归下降分析过程 每个语法单位都对应一个分析子程序，其设
计基于该语法单位的语法描述图或EBNF表示 递归下降分析过程从调用语法单位<程序>对 应的子程序开始，运行时的调用关系反映了 语法分析树的结构

65 PL/0 编译程序的语法分析 递归子程序的设计 沿语法分析图箭头所指方向进行如下工作： 遇到一个语法单元，调用相应的子程序
遇到一个词法单位，则判断当前读入的单词 是否与该词法单位相匹配，若匹配，再读取 下一个单词继续分析；若不匹配，则进行出 错处理 利用EBNF的方法与此相似

66 PL/0 编译程序的语法分析 递归子程序的设计实例
<表达式> ::= [ + | - ] <项> {（ + | - ） <项> } int expression(…) { if (sym==plus || sym==minus) {/* 此时表达式被看作正的或负的项 */ getsym(); term (…); /* 处理<项> */ } else /* 此时表达式被看作项的加减 */ while (sym==plus || sym==minus) getsym; term (…); /* 处理<项> */ return 0;

67 PL/0 编译程序的语法分析 递归子程序的设计实例
<项> ::= <因子> { （* | / ） <因子> } int term(…) { factor（…）; /*处理<因子>*/ while (sym==times || sym==slash) getsym(); factor (…); /* 处理<因子> */ } return 0;

68 PL/0 编译程序的语法分析 递归子程序的设计实例
<因子> ::= <标识符> | <无符号整数> | ‘（’ <表达式> ‘）’ int factor (…) { if (sym==ident) {/* <因子>为常量或变量 */ getsym(); else if (sym==number) /*<因子>为立即数*/ else if (sym==lparen); /* <因子>为立即数*/ expression(…); if (sym==rparen) else error(22); /*提示22号出错信息：缺少右括号*/ } return 0;

69 PL/0 编译程序的语法分析 PL/0 语法分析程序入口 <程序> ::= <分程序> . int main() {
<程序> ::= <分程序> . int main() { … /*初始化*/ … /*读写文件*/ getsym()； block(…) /* 处理<分程序>*/ … if (sym != period) error(9); /*提示 9 号出错信息：缺少程序结束符’.’*/ return 0; }

70 PL/0 编译程序的语法分析 主要语法单位相应子程序之间的调用关系

71 PL/0 编译程序的语义分析 功能 借助符号表进行上下文相关的静态语义分析 确保符号表可以体现作用域规则 确保标识符属性与上下文环境一致
确保标识符先声明后引用 确保标识符的长度、数字的位数、过程嵌套 说明的层数符合PL/0语言的约定 提示语义错误信息

72 PL/0 编译程序的语义分析 符号表结构 Enum object { constant, variable, procedur };
Struct tablestruct { char name[al]; /*al-名字最大长度*/ enum object kind; int val; /*constant标识符的数值*/ int level; /*标识符所在的层，constant标识符不用*/ int adr; /*标识符相对地址，constant标识符不用*/ int size; /*需分配的数据区大小，仅procedur标识符用到*/ Struct tablestruct table[txmax]; /*txmax-符号表容量*/

73 PL/0 编译程序的语义分析 符号表结构 例：右边程序的说明 部分分析后的符 号表如下所示
CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G，X，Y，Z ；

74 PL/0 编译程序的语义分析 符号表与作用域规则 例：右边程序在处理 到/*here*/时的符 号表如下所示 const a=25;
var x,y; procedure p; var z; begin …… end; procedure r; var x, s; procedure t; var v; begin /*here*/ end. 符号表与作用域规则 例：右边程序在处理 到/*here*/时的符 号表如下所示

75 PL/0 编译程序的语义分析 符号表管理 - 登录(在符号表中插入一项) - 查询 返回所查标识符在符号表栈中的位置，没查到则返回0*/
void enter(enum object k, int* ptx, int lev, int* pdx) /* k: 名字种类 const,var or procedure ptx: 名字表尾指针的指针 lev: 名字所在的层次 pdx: 当前应分配变量的相对地址，分配后增加1 */ - 查询 int position(char * idt, int tx) /* idt: 被查标识符名字串 tx: 符号表栈当前栈顶的位置 返回所查标识符在符号表栈中的位置，没查到则返回0*/

76 PL/0 编译程序的语义分析 语义处理举例  变量声明语句的处理
<变量说明部分> ::= var <标识符> {，<标识符>}； if (sym == varsym){ /* 收到变量声明符号，开始处理变量声明 */ getsymdo; /*调用 getsym ( )的宏*/ do { vardeclarationdo(&tx, lev, &dx); /*见下页*/ while (sym == comma) { getsymdo; vardeclarationdo(&tx, lev, &dx); } if (sym == semicolon){ }else error(5); } while (sym == ident);

77 PL/0 编译程序的语义分析 语义处理举例  变量声明语句的处理 (接上页)
int vardeclaration(int* ptx,int lev,int* pdx) /* ptx: 符号表尾位置； lev: 当前层； pdx: 在当前层的偏移量；*/ { if (sym == ident){ enter(variable, ptx, lev, pdx); //填写名字表 getsymdo; } else error(4); /* var 后应是标识符 */ } return 0;

78 PL/0 编译程序的语义分析 语义处理举例  变量引用的处理 当遇到标识符的引用时就调用POSITION函数
查符号表，看是否有过正确定义，若已有， 则从表中取相应的有关信息，供代码的生成 使用；若无定义则报错 若在符号表有过正确定义，检查引用与说明 的属性是否一致，若不一致则报错

79 PL/0 编译程序的语义分析 语义处理举例 变量引用的处 理 (以赋值语 句中的变量引 用为例)
if (sym == ident){ /* 准备按照赋值语句处理 */ i = position(id, *ptx); if (i == 0){ error(11); /* 变量未找到 */ }else { if (table[i].kind != variable) { error(12); /* 赋值语句格式错误 */ i = 0; ...... gendo(sto, …); /*生成目标代码*/ }

80 PL/0 编译程序的错误处理 错误处理的原则 PL/0 编译程序的错误处理 尽可能准确指出错误位置和错误属性 尽可能进行校正
短语层恢复（phrase-level error recovery）

81 PL/0 编译程序的错误处理 短语层恢复 在进入某个语法单位时，调用TEST函数, 检查当前 符号是否属于该语法单位的开始符号集合. 若不属
符号是否属于该语法单位的开始符号集合. 若不属 于，则滤去开始符号和后跟符号集合外的所有符号 在语法单位分析结束时，调用TEST函数, 检查当前 符号是否属于调用该语法单位时应有的后跟符号集 合. 若不属于，则滤去后跟符号和开始符号集合外 的所有符号 ╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳ TEST

82 PL/0 编译程序的错误处理 开始符号集合与后跟符号集合 语法单位 开始符号集合 后跟符号集合 分程序
const var procedure ident I f call begin while read write . ; 语句 ident call begin if while read write . ; end 条件 odd + - ( ident number Then do 表达式 + - ( . ; ) rop end then do 项 ident number ( . ; ) rop + - end then do 因子 . ; ) rop + - * / end then do

83 PL/0 编译程序的错误处理 test函数 /* s1-需要的集合，s2-补救的集合 */
int test(bool* s1, bool* s2, int n) /* s1-需要的集合，s2-补救的集合 */ { if (!inset(sym, s1)) error(n); while ((!inset(sym,s1)) && (!inset(sym,s2))) getsymdo; } return 0;

84 PL/0 编译程序的错误处理 例：因子的处理过程 int factor(bool* fsys, …) /* fsys-后跟符号集合 */ {
int i; testdo(facbegsys, fsys, 24); /* facbegsys-开始符号集合 */ while(inset(sym, facbegsys)) /* 循环直到不是因子开始符号 */ if(…) … testdo(fsys, facbegsys, 23); /* 跳过因子后的非法符号 */ } return 0;

85 PL/0 编译程序的错误处理 后跟符号集随调用深度逐层增加 增加的符号与调用位置相关 例：调用 expression(fsys，…)；
在 write 语句的下一层，则为 expression([rparen,comma]+fsys，…)； 在 factor 的下一层，则为 expression([rparen]+fsys，…); 附： write 语句的语法 write(<exp>{,<exp>})； factor 的语法：factor∷=...|‘(’ exp ’)

86 PL/0 编译程序的目标代码生成 目标代码生成函数
#define gendo(a, b, c) if (-1 == gen(a, b, c)) return -1 …… int gen(enum fct x, int y, int z ) { if (cx >= cxmax) printf("Program too long"); return -1; } code[cx].f = x; code[cx].l = y; code[cx].a = z; cx++; return 0;

87 PL/0 编译程序的目标代码生成 例 int statement(bool* fsys, int* ptx, int lev) { …
if (sym == ident) /* 准备按照赋值语句处理 */ i = position(id, *ptx); gendo(sto, lev-table[i].level, table[i].adr); }

88 PL/0 编译程序的目标代码生成 跳转指令与地址返填
if (sym == ifsym) /* 准备按照 if c then s 语句处理 */ { getsymdo; conditiondo(...); /* 调用条件处理（逻辑运算）函数*/ if (sym == thensym) else error(16); /* 缺少 then */ cx1 = cx; /* 保存当前指令地址 */ gendo(jpc, 0, 0); /* 生成条件跳转指令，跳转地址未知，暂时写0 */ statementdo(fsys, ptx, lev); /* 处理 then 后的语句 */ code[cx1].a = cx; /* 地址返填 */ }

89 PL/0 编译程序的目标代码生成 ( 0) jmp 转向主程序入口 ( 1) jmp 转向过程p入口 ( 2) int 过程p入口,为过程p开辟空间 ( 3) lod 取变量b的值到栈顶 ( 4) lit 取常数10到栈顶 ( 5) opr 次栈顶与栈顶相加 ( 6) sto 栈顶值送变量c中 ( 7) opr 退栈并返回调用点(16) ( 8) int 主程序入口开辟5个栈空间 ( 9) opr 从命令行读入值置于栈顶 (10) sto 将栈顶值存入变量b中 (11) lod 将变量b的值取至栈顶 (12) lit 将常数值0进栈 (13) opr 次栈顶与栈顶是否不等 (14) jpc 相等时转(24)（条件不满足转） (15) cal 调用过程p (16) lit 常数值2进栈 (17) lod 将变量c的值取至栈顶 (18) opr 次栈顶与栈顶相乘(2*c) (19) opr 栈顶值输出至屏幕 (20) opr 换行 (21) opr 从命令行读取值到栈顶 (22) sto 栈顶值送变量b中 (23) jmp 无条件转到循环入口(11) (24) opr 结束退栈 例 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.

90 课后作业 （1）仔细阅读类P-code解释程序 void interpret( ) 初步理解相关的子程序 int base(…)
（2）仔细阅读PL/0编译程序的词法分析子程序 int getsym( ) 及其相关的子程序 int getch( )

91 课后作业 （3）读懂各语法单位相应子程序的结构以及他 们之间的调用关系 （4）读懂各语法单位相应子程序内部的语义处
理部分，理解符号表栈的结构及（随处理 进程的）变化情况 （5）读懂各语法单位相应子程序内部的错误处 理部分的代码 （6）读懂各语法单位相应子程序内部的代码生 成部分的代码（特别是地址反填技术）

92 Happy holidays! Thank You