第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器
1,PL/0编译程序的结构
PL/0编译 程序PL/0 语言程序 类 p－ code 代码源语言 (PL/0)
目标语言 (类 p－ code)
实现语言（ pascal/C)
PL/0 类 p－ code
pascal/C
PL/0编译程序类 p－ code解释 程序类 p－ code代码
PL/0源程序输入数据 输出数据
PL/0编译系统的结构框架
PL/0语言
PL/0语言,PASCAL语言的 子集
PL/0程序示例
PL/0的 语法描述图
PL/0语言 的 EBNF表示
PL/0程序示例
CONST A=10; （ * 常量说明部分 *）
VAR B,C; （ * 变量说明部分 *）
PROCEDURE P; （ * 过程说明部分 *）
VAR D;（ * P的局部变量说明部分 *）
PROCEDURE Q; （ * P的局部过程说明部分 *）
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过程体主 程序 体输入圆柱的半径和高，计算一些面积、体积等
var r,h,len,a1,a2,volumn;
begin
read(r);
read(h);
len,= 2 * 3 * r;
a1,= 3 * r * r;
a2,= a1 + a1 + len * h;
volumn,= a1 * h;
write(len);
write(a1);
write(a2);
write(volumn);
end.
计算最大公约数
var m,n,r,q;
{ 计算 m和 n的最大公约数 }
procedure gcd;
begin
while r#0 do
begin
q,= m / n;
r,= m - q * n;
m,= n;
n,= r;
end
end;
begin
read(m);
read(n);
{ 为了方便，规定 m >= n }
if m < n then
begin
r,= m;
m,= n;
n,= r;
end;
begin
r:=1;
call gcd;
write(m);
end;
end.
pl/0程序 --递规调用
var n;
procedure rec;
begin
if n # 0 then
begin
write(n);
n,= n - 1;
call rec;
end;
end;
begin
read(n);
call rec;
end.
计算 sum = 1! + 2 ! +,.,+ n!,
n从控制台读入
var n,m,fact,sum;
{ 递规计算 fact = m! }
procedure factorial;
begin
if m > 0 then
begin
fact,= fact * m;
m,= m - 1;
call factorial;
end;
end;
begin
{ 读入 n }
read(n);
sum,= 0;
while n > 0 do
begin
m,= n;
fact,= 1;
call factorial;
sum,= sum + fact;
n,= n - 1;
end;
{ 输出 n !}
write(sum);
end.
程序 分程序,
内的文字表示 语法成分（短语）
或 内的文字表示单词符号程序内的文字表示 语法成分（短语）
语法图
const ident number=
,;
var ident
,;
procedure ident ; 分程序语句分程序
PL/0语言的 EBNF表示构成 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语言的 子集同 PASCAL
作用域规则（内层 可引用包围它的外层定义的 标识符），
上下文约束，
过程可 嵌套定义,可递归调用子集
数据类型,只有整型
数据结构,只有简变和常数
数字最多为 14位
标识符的有效长度是 10
语句种类
过程无参，最多可 嵌套 三层目标代码 类 p-code
目标代码 类 p-code是 一种 栈式机 的 汇编语言 。
栈式机系统结构,没有累加器和寄存器，只有存储栈指针所有运算都在栈顶（零地址机）
指令格式：
f l a
f 功能码
l 层次差 （标识符 引用层 减去 定义层 ）
a 根据不同的指令有所区别
LIT 0 a 将常数值取到栈顶,a 为常数值
LOD l a 将变量值取到栈顶,a 为偏移量,l 为层差
STO l a 将栈顶内容送入某变量单元中,a 为偏移量,l 为层差
CAL l a 调用过程,a 为过程地址,l 为层差
INT 0 a 在运行栈中为被调用的过程开辟 a 个单元的数据区
JMP 0 a 无条件跳转至 a 地址
JPC 0 a 条件跳转，当栈顶布尔值非真则跳转至 a 地址，否则顺序执行
OPR 0 0 过程调用结束后,返回调用点并退栈
OPR 0 1 栈顶元素取反
OPR 0 2 次栈顶与栈 顶相加，退两个栈元素，结果值进栈
OPR 0 3 次栈顶减去栈顶，退两个栈元素，结果值进栈
OPR 0 4 次栈顶乘以栈顶，退两个栈元素，结果值进栈
OPR 0 5 次栈顶除以栈顶，退两个栈元素，结果值进栈
OPR 0 6 栈顶元素的奇偶判断，结果值在栈顶
OPR 0 7
OPR 0 8 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈
OPR 0 9 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈
OPR 0 10 次栈顶是否小于栈顶，退两个栈元素，结果值进栈
OPR 0 11 次栈顶是 否大于等于栈顶，退两个栈元素，结果值进栈
OPR 0 12 次栈顶是否大于栈顶，退两个栈元素，结果值进栈
OPR 0 13 次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈
OPR 0 14 栈顶值输出至屏幕
OPR 0 15 屏幕输出换行
OPR 0 16 从命令行读入一个输入置于栈顶指令功能表
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 结束退栈
PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序表格管理程序 出错处理程序
PL/0源程序目标程序
PL/0编译程序的总体设计
以语法,语义分析 程序 为核心词法分析 程序和 代码生成 程序都作为一个 过程,
当语法分析需要读单词时就调用词法分析程序，
而当语法,语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。
表格管理 程序实现 变量,常量 和 过程 标识符的 信息的登录与查找 。
出错处理 程序，对词法和语法,语义分析遇到的错误给出在源程序中 出错的位置 和与 错误 性质有关 的编号，并进行错误恢复。
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器
2 PL/0编译程序的分析工作 (词法，语法和语义）
2.1PL/0编译程序词法分析的实现识别的单词：
保留字或关键字：如,BEGIN,END,IF,THEN等
运算符,如,+,-,*,/、,=,#,>=,<=等
标识符,用户定义的变量名、常数名、过程名
常数,如,10,25,100等整数
界符,如,‘,’,‘,’,‘ ;’,‘ (’,‘ )’等词法分析过程 GETSYM所要完成的任务：
从源程序读字符（ getch)
滤空格
识别 保留字
识别标识符
拼数
识别单字符单词
拼双字符单词
词法分析过程,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；
字符对应的 单词表：
ssym[‘+’]:=plus; ssym[‘-’]:=minus;
…
ssym[‘;’]:=semicolon;
词法分析如何把单词传递给语法分析
type symbol=(nul,ident,number,plus,…,varsym,procsym)；
3个 全程量
SYM:symbol;
ID:alfa;
NUM:integer;
通过三个 全程量 SYM,ID和 NUM 将识别出的单词信息 传递 给 语法分析 程序。
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）
使用状态转换图实现词法分析程序的设计方法词法分析程序的设计 ---使用状态转换图实现表示 状态,对应每个状态编一段程序，
每个状态 调用 取字符 程序，根据当前字符 转到不同的状态，并做相应操作。
表示 终态,已 识别出一个 单词 。
1 2 3
5
14
13
12
10
9
7
8
6
4
11
·?
3·
3· êù 3?
2? 3· êù 3?
êù 3?
êù 3?
2? êù 3?
￡1
=
<
=
2? =
> =
2? =
,+ - (? -?-
2.2 PL/0编译程序语法分析自顶向下 的语法分析递归子程序法
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型的 过程，或者说是某个 推导 的构造过程。
对于一个给定的文法，要想判定一个符号串是否为该文法的句子，需要考察是否可以从该文法的开始符号派生出（推导出）此符号串。－编译程序的语法分析工作。
分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,寻找 与 输入符号串 匹配 的 推导,或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
语法分析－（从概念上讲）建立一棵与输入串相匹配的语法树。
语法树－推导的几何表示
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
两种方法反映了语法树的两种构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树自上而下的语法分析的一般过程例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
程序 分程序,
const ident number=
,;
var ident
,;
procedure ident ; 分程序语句分程序
ident
read
end;
语句 表达式,=
begin 语句语句
)( ident
,
自顶向下的语法分析
VAR A;
BEGIN
READ(A)
END.
<程序 >
<分程序 >,
<变量说明部分 > <语句 >
VAR <标识符 > ； <复合语句 >
A BEGIN <语句 > END
<读语句 >
READ （ <标识符 > ）
A
<程序 >为文法的开始符号,以开始符号作为根结点构造一棵倒挂着的语法树。
递归子程序法 -语法分析程序由一组递归过程组成对应 每个非终结符（ 语法单元），编一个独立的处理过程（或函数，子程序）。
由 <程序 >（ 即开始符）开始，沿语法描述图箭头 所指出的方向进行分析（规则右部）
遇到 非终结符 （进入了又一个语法单元），
则 调用 相应的 处理过程遇到 终结符,则判断当前读入的单词是否与该终结符 相匹配,若匹配，再读取下一个单词继续分析。
－－也称为 递归下降分析器（ recursive-descent
parser ）
例：表达式的语法分析程序（递归子程序）
项表达式
+
-
项
+
-
项 因子因子
*
/
语法图因子的语法图因子 ident
number
( 表达式 )
表达式的 EBNF
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
pascal
〈 表达式 〉 的分析程序（ 递归子程序）
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;
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
pascal
〈 项 〉 的分析程序（ 递归子程序）
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
else getsym
end
else getsym
end;
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 } in C
int expression(bool* fsys,int* ptx,int lev)
{
if(sym==plus || sym==minus) /* 开头的正负号，当前表达式被看作一个正的或负的项 */
{
getsymdo;
termdo(nxtlev,ptx,lev); /* 处理项 */
}
else /* 此时表达式被看作项的加减 */
{
termdo(nxtlev,ptx,lev); /* 处理项 */
}
while (sym==plus || sym==minus)
{
getsymdo;
termdo(nxtlev,ptx,lev); /* 处理项 */
}
return 0;
}
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
int term(bool* fsys,int* ptx,int lev)
{
factordo(nxtlev,ptx,lev); /* 处理因子 */
while(sym==times || sym==slash)
{ getsymdo;
factordo(nxtlev,ptx,lev);
}
return 0;
}
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
getsymdo;
else { if(sym == number) /* 因子为 */
getsymdo;
else if (sym == lparen) /* 因子为表达式 */
{expressiondo(nxtlev,ptx,lev);
if (sym == rparen)
getsymdo;
else error(22); /* 缺少右括号 */
}
}
return 0;
}
<程序 >∷=< 分程序 >?
begin（ *main*)
… (*initialize*)
… (*r/w file set*)
getsym;
block( );
…
if sym < > period then error...
end.
。
程序 pl0
分程序 block
语句 statement
条件 condition
表达式 expression
项 term
因子 factor
语法调用关系图编译系统总体流程图
ˉ
3μ
μ? ó? G E T S Y M è? μ￥ ′ê
μ? ó? B L O C K?ù 3ì
μ±?°μ￥ ′ê
ê? 2a?′ 3ì Dò?á ê÷ 2?
',' ￡?
3? ′í
′ 3ì Dò?D
ê? 2? óD ′í?ó ￡?
μ? óa êí?ù 3ì I N T E R P R E T
a êí?′ D ±ê 3ì Dò
′ò ó? ′í?ó
á ê÷
N
Y
Y
N
2.3 PL/0编译程序语义分析的设计与实现
PL/0编译程序语法、语义分析的的核心 程序是 BLOCK过程哪些语义分析工作？
如何实现？ --语义分析环境（符号表）
说明部分的分析 与处理
表格管理
过程体 (语句）的分析 与处理
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
语义分析
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
{
i = position(id,*ptx); /* 查找名字 */
if (i == 0)
{error(11); /* 标识符未声明 */
}
else
{switch (table[i].kind)
{case constant,/* 名字为常量 */
break;
case variable,/* 名字为变量 */
break;
case procedur,/* 名字为过程 */
error(21); /* 不能为过程名 */
……
登录符号表说明部分的分析 与处理对每个过程（含主程序） 说明的对象 （ 变量,常量 和 过程 ） 造符号表登录 标识符的 属性 。
标识符的属性,种类，所在 层次,值 和分配的 相对位置 。
登录信息由 ENTER过程完成。
符号表结构
Enum object {
constant,
variable,
procedur
};
Struct tablestruct {
char name[al];
enum object kind;
int val;
int level;
int adr;
int size;
};
Struct tablestruct table[txmax];
符号表结构
说明种类的定义：
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);
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,CONSTANT
KIND,CONSTANT
KIND,VARIABLE
KIND,VARIABLE
KIND,VARIABLE
KIND,PROCEDUR
VAL,35
VAL,49
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,
S I Z E,4
NAME,G
……
KIND,VARIABLE
……
LEV EL,L E V + 1
……
ADR,DX
……
例程序说明部分为,CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G ； …
符号表名字 种类 层次 /值 地址 存储空间对应名字表
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码 时再 放在 code中的 a域变量定义语句的处理 (C)
语法,<变量说明部分 >:,= var <标识符 >{,<标识符 >}；
程序：
if (sym == varsym){ /* 收到变量声明符号，开始处理变量声明 */
getsymdo;
do {
vardeclarationdo(&tx,lev,&dx);
while (sym == comma) {
getsymdo;
vardeclarationdo(&tx,lev,&dx);
}
if (sym == semicolon){
getsymdo;
}else error(5);
} while (sym == ident);
}
注意,&tx
变量说明处理 (C)
int vardeclaration(int* ptx,int lev,int* pdx)
{
if (sym == ident){
enter(variable,ptx,lev,pdx);//填写名字表
getsymdo;
}else
{
error(4);/* var后应是标识 符 */
}
return 0;
}
变量定义语句的处理语法,<变量说明部分 >:,= 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;
变量说明处理
procedure vardeclaration;
begin
if sym=ident then
begin
enter(variable);
getsym
end
else error(4)
end(*vardeclaration*);
过程 ENTER的实现 (C)
/*
* 在名字表中加入一项
*
* k,名字种类 const,var or procedure
* ptx,名字表尾指针的指针
* lev,名字所在的层次,以后所有的 lev都是这样
* pdx,当前应分配变量的相对地址，分配后增加 1
*/
void enter(enum object k,int* ptx,
int lev,int* pdx)
过程 ENTER的实现 (C)
{
(*ptx)++;
strcpy(table[(*ptx)].name,id);
/* 全局变量 id中已存有当前名字的名字 */
table[(*ptx)].kind = k;
switch (k){
case constant,/* 常量名字 */
if (num > amax)
{ error(31);/* 数越界 */
num = 0;
}
table[(*ptx)].val = num;
break;
过程 ENTER的实现 (C)
case variable,/* 变量名字 */
table[(*ptx)].level = lev;
table[(*ptx)].adr = (*pdx);
(*pdx)++;
break;
case procedur,/* 过程名字 */
table[(*ptx)].level = lev;
break;
}
}
过程 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;* )
过程 ENTER的实现
case k of
constant,
begin
if num>amax then
begin
error(31);
num:=0;
end;
val:=num;(* table[tx].val:=num;*)
end;
过程 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*);
过程体的处理
/*
* 编译程序主体
*
* lev,当前分程序所在层
* tx,名字表当前尾指针
* fsys,当前模块后跟符号集合
*/
int block(int lev,int tx,bool* fsys)
过程体的处理
......//main()函数
if(-1 == block(0,0,nxtlev)){
......
}
......
if (sym != period) error(9);
......
interpret();/* 调用解释执行程序 */
......
过程体的处理
while (sym == procsym) // block()函数
{ getsymdo;
if (sym == ident){
enter(procedur,&tx,lev,&dx);
.....
}
......
if (-1 == block(lev+1,tx,nxtlev))
}
过程体的处理－ 变量引用的处理
对 语句进行 语法 分析
语义分析 当遇到 标识符的引用时 就调用 POSITION函数 查
TABLE表,看是否 有 过 正确定义,若已有，则从表中 取相应的有关 信息,供代码的生成使用。 若无定义则错 。
语义分析 TABLE表 若已 有 过 正确定义,检查引用与说明的属性是否一致,若不一致则错 。
当 语法语义正确时,就 生成 相应语句功能的 目标代码赋值 语句的处理 (C)
if (sym == ident){ /* 准备按照赋值语句处理 */
i = position(id,*ptx);
if (i == 0){
error(11); /* 变量未找到 */
}else
{
if(table[i].kind != variable){
error(12); /* 赋值语句格式错误 */
i = 0;
}else
{
......
gendo(sto,lev-table[i].level,table[i].adr);
......
}
}
}
赋值 语句的处理
if sym = ident then
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
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器编译程序的错误处理错误处理的原则：尽可能准确指出出错位置，
错误性质，尽可能进行校正。
PL/0编译程序对语法错误的处理：
(1) 对于 易于校正 的错误，如丢了逗号，分号等，指出出错位置,加以校正,继续进行分析。
(2) 对于 难于校正 的错误，给出错误的位置与性质,跳过后面的一些单词,直到下一个可以进行正常语法分析的语法单位。
在 进入 某个 语法单位 时，调用 TEST,检查当前符号是否属于该 语法单位的开始符号集合 。若不属于，
则 滤去 开始 符号 和 后跟 符号 集合外 的所有符号。
在 语法单位 分析结束 时，调用 TEST,检查当前符号是否属于调用该语法单位时应有的 后跟 符号集合。
若不属于，则 滤去 后跟 符号和 开始 符号 集合外 的所有符号 。
╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳
TEST TEST
开始符号集合与后跟符号集合非终结符名 开始符号集合 后跟符号集合分程序 const var procedure
ident if call begin
while read write
,;
语句 ident call begin
if while read write
,; end
条件 odd + - (
ident number
Then do
表达式 + - (
ident number
,; ) rop
end then do
项 ident number (,; ) rop + -
end then do
因子 ident number (,; ) rop + -
* / end then do
开始符号 集合
symset=set of symbol;
declbegsys,statbegsys,facbegsys:symset;
开始符号集合（ *主程序 *）
declbegsys:=[constsym,varsym,procsym];
statbegsys:=[beginsym,callsym,ifsym,
whilesym,readsym,writesym];
facbegsys:=[ident,number,lparen];
后 跟 符 号集合 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);
READ语句的分析处理 (C)
if (sym == readsym){//处理 read语句
getsymdo;
if (sym != lparen){
error(34); //格式错误,应是左括号
}else
{
do {
getsymdo;
READ语句的语法语义分析处理
if sym=readsym then
begin
getsym;
if sym<>lparen then error(34)
else
repeat
getsym;
READ语句的语法语义分析处理
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;
READ语句的语法语义分析处理
getsym
until sym<>comma;
if sym<>rparen then
begin
error(33);
while not(sym in fsys)
do getsym
end
else getsym
end
出错处理跳过不应出现的符号正确 出 口
TEST
SYM在 S1中打印出错编号 n
S1:=S1+S2
SYM在 S1中
GETSYM
返回
Y
Y
N
N
TE
ST
测试过程流程图因子的处理过程
例：因子的处理过程
procedure factor(fsys:symset);
var i:integer;
begin
入口,test(facbegsys,fsys,24);
while sym in facbegsys do
begin
if
...
出口,test(fsys,facbegsys,23);
end
end;
因子的处理过程
Facbegsys
y
处理 ident
number,
lparen
test
n
test
增加后跟符 与 调用位置有关例：调用 expression(fsys);
write语句的 语法 write(<exp>{,<exp>});
write语句 (后 调用 expression时 后跟符
expression([rparen,comma]+fsys);
factor的 语法,factor∷=,..|‘(’ exp ’)
在 factor(后 调用 expression时 后跟符
expression([rparen]+fsys);
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器代码生成代码生成是由过程 GEN完成。
GEN有 3个 参数,分别代表目标代码的 功能码,
层差 和 位移量 。例如
gen(opr,0,16);
gen(sto,lev-level,adr)
lev：当前 处理的 过程 层次
level：被引用变量或过程所在 层次
CX：为目标代码 code数组的下标指针代码结构变换,地址返填
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
类 p－ code代码解释器的实现
类 p－ code目标机结构
目标代码解释执行时 数据栈的布局 （运行栈的存储分配）
目标代码 类 p-code
目标代码 类 p-code是 一种 栈式机 的 汇编语言 。
栈式机系统结构,没有累加器和寄存器，只有存储栈指针所有运算都在栈顶（零地址机）
指令格式：
f l a
f 功能码
l 层次差 （标识符 引用层 减去 定义层 ）
a 根据不同的指令有所区别类 p－ code解释器的结构目标代码（ 指令） 存放在数组 CODE中（ 程序地址寄存器 p） 。
解释程序定义一个一维整型数组 S作为 运行栈栈顶寄存器 （指针） t,基址寄存器 （指针） b，
指令寄存器 i（当前正在解释的目标指令）
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 结束退栈目标代码解释执行时数据栈的布局
（运行栈的存储分配）
在每个过程调用时在栈顶分配 3个联系单元：
SL,静态链,指向 定义 该过程的 直接外过程
（或主程序）运行时 最新 数据段的基地址 。
DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
Var x,y;
Procedure P;
var a;
procedure Q;
var b;
begin(*Q*)
b:= 10;
end (*Q*);
procedure S;
var c,d;
procedure R;
var e,f;
begin(*R*)
call Q;
end(*R*);
begin(*S*)
call R;
end(*S*);
begin(*P*)
call S;
end;(*P*)
begin(*MAIN*)
call P;
end(*MAIN*).
目标代码的解释执行 运行栈 S
M调用过程 P M调用过程 P P调用过程 S
RA
DL
SLb
t
t
b
P
M
P
M
S
目标代码的解释执行几条 特殊指令 在 code中的 位置 和 功能
INT 0 A
在 过程 目标程序的 入口处,开辟 A个单元的数据段。
A为 局部变量 的 个数 +3。
OPR 0 0
在 过程 目标程序的 出口处,释放数据段 （退栈），
恢复调用 该过程 前 正在运行的过程 的数据段 基址寄存器 B和 栈顶寄存器 T的值，并将 返回地址 送 到指令地址寄存器 P中，以使调用前的程序从 断点 开始 继续执行 。
目标代码的解释执行几条 特殊 指令在 code中的 位置 和 功能
CAL L A
调用过程,还完成 填写 静态链,动态链,返回地址,给出 被调 用 过程 的 基地址 值,送 入基址寄存器 B中，目标程序的 入口 地址 A的值 送 指令地址寄存器 P中，使指令从 A开始执行。
附
CX：为目标代码 code数组的下标指针。 code为一维数组，数组元素为 记录型数据 。每一个记录就是一条目标指令。 CX 为整数变量，由 0开始顺序增加。
实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码 时再 放在 code中的 a域 。
下标指针 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
p
m
b
Table表的 下标指针 tx补充说明,
主程序
BLOCK
第 1次 调用 block
BLOCK（ 0,0,… ）
0
0
...
BLOCK BLOCK（ LEV+1,TX,… ）
(递归 进入 分程序 )
LEV
tx
LEV
tx
（ 6）
6 （ 9）
1
tx是 BLOCK的实际 值参附 PL/0编译程序的实现
procedure gen(x:fct; y,z:integer);
begin
if cx>cxmax then（ *指针越界 *）
begin
write(‘ program too long’ );
close(fin);（ *关闭文件 *）
writeln;
exit
end;
附 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*);
附 PL/0编译程序的实现对 分程序的定义（ 见教材 417,437页）
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/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的作用）
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,C O N S T A N T
KIND,C O N S T A N T
KIND,V A R I A B L E
KIND,V A R I A B L E
KIND,V A R I A B L E
KIND,P R O C E D U R
VAL,35
VAL,49
LEVEL,L E V
LEVEL,L E V
LEVEL,L E V
LEVEL,L E V
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,1 SIZE,4
NAME,G
……
KIND,V A R I A B L E
……
LEVEL,L E V + 1
……
ADR,DX
……
CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G
附 table表格管理名字 类型 层次 /值 地址 存储空间
(0) jmp 0 0
CX (1 ) jmp 0 0
.
.
记录 过程在 code的 入口到 table中的 adr域附 PL/0编译程序的实现过程 体 入口 时的处理
code[table[tx0].adr].a:=cx;
（过程入口地址填 写在 code中 ）
with table[tx0] do
begin
adr:=cx; （ 过程的 入口 填 写在 table中 ）
size:=dx; （ 过程 占的空间 填 写在 table中 ）
end;
cxo:=cx; （保留 过程在 code中的 入口地址）
gen(int,0,dx);（ 生成 过程 入口指令 ）
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;
P=0?
返回解释执行的流程图执行指令 i
N
Y
主程序的 RA
s[3]=0
附 目标代码的解释执行几条 特殊指令 的 解释执行,
过程 入口,开辟 a个单元 （见教材 425页）
int,t:=t+a; （ t是当前 栈顶值）
过程 出口,释放数据段 （退栈）（ 见教材 425页）
opr,case a of (*operator*)
0,begin (*return*)
t:=b-1; 恢复调用前栈顶
p:=s[t+3]; 送返回地址到 p
b:=s[t+2] 恢复调用前基地址
end;
附 目标代码的解释执行过程 出口
RA
DL
SLb
.
,
t
M
t
b
t:=b-1;
p:=s[t+3];
b:=s[t+2]
Q
附 目标代码的解释执行调用过程,
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;
附 目标代码的解释执行
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*);
附 目标代码的解释执行
base (l:integer),integer;
b
b
b
m
p
0
b
b
q
附 运行时数据栈 S的变化状态
…
Procedure A;
…
procedure B;
…
procedure C;
…
call B;
…
…
call C;
…
…
call B;
…
…
Call A;
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器
1,PL/0编译程序的结构
PL/0编译 程序PL/0 语言程序 类 p－ code 代码源语言 (PL/0)
目标语言 (类 p－ code)
实现语言（ pascal/C)
PL/0 类 p－ code
pascal/C
PL/0编译程序类 p－ code解释 程序类 p－ code代码
PL/0源程序输入数据 输出数据
PL/0编译系统的结构框架
PL/0语言
PL/0语言,PASCAL语言的 子集
PL/0程序示例
PL/0的 语法描述图
PL/0语言 的 EBNF表示
PL/0程序示例
CONST A=10; （ * 常量说明部分 *）
VAR B,C; （ * 变量说明部分 *）
PROCEDURE P; （ * 过程说明部分 *）
VAR D;（ * P的局部变量说明部分 *）
PROCEDURE Q; （ * P的局部过程说明部分 *）
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过程体主 程序 体输入圆柱的半径和高，计算一些面积、体积等
var r,h,len,a1,a2,volumn;
begin
read(r);
read(h);
len,= 2 * 3 * r;
a1,= 3 * r * r;
a2,= a1 + a1 + len * h;
volumn,= a1 * h;
write(len);
write(a1);
write(a2);
write(volumn);
end.
计算最大公约数
var m,n,r,q;
{ 计算 m和 n的最大公约数 }
procedure gcd;
begin
while r#0 do
begin
q,= m / n;
r,= m - q * n;
m,= n;
n,= r;
end
end;
begin
read(m);
read(n);
{ 为了方便，规定 m >= n }
if m < n then
begin
r,= m;
m,= n;
n,= r;
end;
begin
r:=1;
call gcd;
write(m);
end;
end.
pl/0程序 --递规调用
var n;
procedure rec;
begin
if n # 0 then
begin
write(n);
n,= n - 1;
call rec;
end;
end;
begin
read(n);
call rec;
end.
计算 sum = 1! + 2 ! +,.,+ n!,
n从控制台读入
var n,m,fact,sum;
{ 递规计算 fact = m! }
procedure factorial;
begin
if m > 0 then
begin
fact,= fact * m;
m,= m - 1;
call factorial;
end;
end;
begin
{ 读入 n }
read(n);
sum,= 0;
while n > 0 do
begin
m,= n;
fact,= 1;
call factorial;
sum,= sum + fact;
n,= n - 1;
end;
{ 输出 n !}
write(sum);
end.
程序 分程序,
内的文字表示 语法成分（短语）
或 内的文字表示单词符号程序内的文字表示 语法成分（短语）
语法图
const ident number=
,;
var ident
,;
procedure ident ; 分程序语句分程序
PL/0语言的 EBNF表示构成 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语言的 子集同 PASCAL
作用域规则（内层 可引用包围它的外层定义的 标识符），
上下文约束，
过程可 嵌套定义,可递归调用子集
数据类型,只有整型
数据结构,只有简变和常数
数字最多为 14位
标识符的有效长度是 10
语句种类
过程无参，最多可 嵌套 三层目标代码 类 p-code
目标代码 类 p-code是 一种 栈式机 的 汇编语言 。
栈式机系统结构,没有累加器和寄存器，只有存储栈指针所有运算都在栈顶（零地址机）
指令格式：
f l a
f 功能码
l 层次差 （标识符 引用层 减去 定义层 ）
a 根据不同的指令有所区别
LIT 0 a 将常数值取到栈顶,a 为常数值
LOD l a 将变量值取到栈顶,a 为偏移量,l 为层差
STO l a 将栈顶内容送入某变量单元中,a 为偏移量,l 为层差
CAL l a 调用过程,a 为过程地址,l 为层差
INT 0 a 在运行栈中为被调用的过程开辟 a 个单元的数据区
JMP 0 a 无条件跳转至 a 地址
JPC 0 a 条件跳转，当栈顶布尔值非真则跳转至 a 地址，否则顺序执行
OPR 0 0 过程调用结束后,返回调用点并退栈
OPR 0 1 栈顶元素取反
OPR 0 2 次栈顶与栈 顶相加，退两个栈元素，结果值进栈
OPR 0 3 次栈顶减去栈顶，退两个栈元素，结果值进栈
OPR 0 4 次栈顶乘以栈顶，退两个栈元素，结果值进栈
OPR 0 5 次栈顶除以栈顶，退两个栈元素，结果值进栈
OPR 0 6 栈顶元素的奇偶判断，结果值在栈顶
OPR 0 7
OPR 0 8 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈
OPR 0 9 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈
OPR 0 10 次栈顶是否小于栈顶，退两个栈元素，结果值进栈
OPR 0 11 次栈顶是 否大于等于栈顶，退两个栈元素，结果值进栈
OPR 0 12 次栈顶是否大于栈顶，退两个栈元素，结果值进栈
OPR 0 13 次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈
OPR 0 14 栈顶值输出至屏幕
OPR 0 15 屏幕输出换行
OPR 0 16 从命令行读入一个输入置于栈顶指令功能表
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 结束退栈
PL/0编译程序的结构词法分析程序语法语义分析程序代码生成程序表格管理程序 出错处理程序
PL/0源程序目标程序
PL/0编译程序的总体设计
以语法,语义分析 程序 为核心词法分析 程序和 代码生成 程序都作为一个 过程,
当语法分析需要读单词时就调用词法分析程序，
而当语法,语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。
表格管理 程序实现 变量,常量 和 过程 标识符的 信息的登录与查找 。
出错处理 程序，对词法和语法,语义分析遇到的错误给出在源程序中 出错的位置 和与 错误 性质有关 的编号，并进行错误恢复。
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器
2 PL/0编译程序的分析工作 (词法，语法和语义）
2.1PL/0编译程序词法分析的实现识别的单词：
保留字或关键字：如,BEGIN,END,IF,THEN等
运算符,如,+,-,*,/、,=,#,>=,<=等
标识符,用户定义的变量名、常数名、过程名
常数,如,10,25,100等整数
界符,如,‘,’,‘,’,‘ ;’,‘ (’,‘ )’等词法分析过程 GETSYM所要完成的任务：
从源程序读字符（ getch)
滤空格
识别 保留字
识别标识符
拼数
识别单字符单词
拼双字符单词
词法分析过程,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；
字符对应的 单词表：
ssym[‘+’]:=plus; ssym[‘-’]:=minus;
…
ssym[‘;’]:=semicolon;
词法分析如何把单词传递给语法分析
type symbol=(nul,ident,number,plus,…,varsym,procsym)；
3个 全程量
SYM:symbol;
ID:alfa;
NUM:integer;
通过三个 全程量 SYM,ID和 NUM 将识别出的单词信息 传递 给 语法分析 程序。
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）
使用状态转换图实现词法分析程序的设计方法词法分析程序的设计 ---使用状态转换图实现表示 状态,对应每个状态编一段程序，
每个状态 调用 取字符 程序，根据当前字符 转到不同的状态，并做相应操作。
表示 终态,已 识别出一个 单词 。
1 2 3
5
14
13
12
10
9
7
8
6
4
11
·?
3·
3· êù 3?
2? 3· êù 3?
êù 3?
êù 3?
2? êù 3?
￡1
=
<
=
2? =
> =
2? =
,+ - (? -?-
2.2 PL/0编译程序语法分析自顶向下 的语法分析递归子程序法
（ 上下文无关文法） 句型的分析句型分析 就是 识别 一个符号串是否为某文法的 句型的 过程，或者说是某个 推导 的构造过程。
对于一个给定的文法，要想判定一个符号串是否为该文法的句子，需要考察是否可以从该文法的开始符号派生出（推导出）此符号串。－编译程序的语法分析工作。
分析算法分类分析算法可分为：
自上而下分析法,
从文法的开始符号出发,寻找 与 输入符号串 匹配 的 推导,或者说，为输入串寻找一个最左推导。
自下而上分析法,
从 输入符号串 开始,逐步进行 归约,直至归约 到 文法的 开始符号 。
语法分析－（从概念上讲）建立一棵与输入串相匹配的语法树。
语法树－推导的几何表示
句型 aabbaa的可能 推导 序列和语法树例,G[S]:
S→ aAS
A→ SbA
A→ SS
S→ a
A→ ba
S
a A S
S b A a
a b a
S?aAS?aAa?aSbAa?aSbbaa?aabbaa
S?aAS?aSbAS?aabAS?aabbaS?aabbaa
S?aAS?aSbAS?aSbAa?aabAa?aabbaa
两种方法反映了语法树的两种构造过程。
自上而下方法 是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法 则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树自上而下的语法分析的一般过程例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否为该文法的 句子
S S S
c A d c A d
a b
推导过程,S? cAd cAd? cabd
程序 分程序,
const ident number=
,;
var ident
,;
procedure ident ; 分程序语句分程序
ident
read
end;
语句 表达式,=
begin 语句语句
)( ident
,
自顶向下的语法分析
VAR A;
BEGIN
READ(A)
END.
<程序 >
<分程序 >,
<变量说明部分 > <语句 >
VAR <标识符 > ； <复合语句 >
A BEGIN <语句 > END
<读语句 >
READ （ <标识符 > ）
A
<程序 >为文法的开始符号,以开始符号作为根结点构造一棵倒挂着的语法树。
递归子程序法 -语法分析程序由一组递归过程组成对应 每个非终结符（ 语法单元），编一个独立的处理过程（或函数，子程序）。
由 <程序 >（ 即开始符）开始，沿语法描述图箭头 所指出的方向进行分析（规则右部）
遇到 非终结符 （进入了又一个语法单元），
则 调用 相应的 处理过程遇到 终结符,则判断当前读入的单词是否与该终结符 相匹配,若匹配，再读取下一个单词继续分析。
－－也称为 递归下降分析器（ recursive-descent
parser ）
例：表达式的语法分析程序（递归子程序）
项表达式
+
-
项
+
-
项 因子因子
*
/
语法图因子的语法图因子 ident
number
( 表达式 )
表达式的 EBNF
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 }
pascal
〈 表达式 〉 的分析程序（ 递归子程序）
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;
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
pascal
〈 项 〉 的分析程序（ 递归子程序）
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
else getsym
end
else getsym
end;
〈 表达式 〉 ∷= [+|-]〈 项 〉 {（ +|-） 〈 项 〉 } in C
int expression(bool* fsys,int* ptx,int lev)
{
if(sym==plus || sym==minus) /* 开头的正负号，当前表达式被看作一个正的或负的项 */
{
getsymdo;
termdo(nxtlev,ptx,lev); /* 处理项 */
}
else /* 此时表达式被看作项的加减 */
{
termdo(nxtlev,ptx,lev); /* 处理项 */
}
while (sym==plus || sym==minus)
{
getsymdo;
termdo(nxtlev,ptx,lev); /* 处理项 */
}
return 0;
}
〈 项 〉 ∷= 〈 因子 〉 {（ *|/） 〈 因子 〉 }
int term(bool* fsys,int* ptx,int lev)
{
factordo(nxtlev,ptx,lev); /* 处理因子 */
while(sym==times || sym==slash)
{ getsymdo;
factordo(nxtlev,ptx,lev);
}
return 0;
}
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
getsymdo;
else { if(sym == number) /* 因子为 */
getsymdo;
else if (sym == lparen) /* 因子为表达式 */
{expressiondo(nxtlev,ptx,lev);
if (sym == rparen)
getsymdo;
else error(22); /* 缺少右括号 */
}
}
return 0;
}
<程序 >∷=< 分程序 >?
begin（ *main*)
… (*initialize*)
… (*r/w file set*)
getsym;
block( );
…
if sym < > period then error...
end.
。
程序 pl0
分程序 block
语句 statement
条件 condition
表达式 expression
项 term
因子 factor
语法调用关系图编译系统总体流程图
ˉ
3μ
μ? ó? G E T S Y M è? μ￥ ′ê
μ? ó? B L O C K?ù 3ì
μ±?°μ￥ ′ê
ê? 2a?′ 3ì Dò?á ê÷ 2?
',' ￡?
3? ′í
′ 3ì Dò?D
ê? 2? óD ′í?ó ￡?
μ? óa êí?ù 3ì I N T E R P R E T
a êí?′ D ±ê 3ì Dò
′ò ó? ′í?ó
á ê÷
N
Y
Y
N
2.3 PL/0编译程序语义分析的设计与实现
PL/0编译程序语法、语义分析的的核心 程序是 BLOCK过程哪些语义分析工作？
如何实现？ --语义分析环境（符号表）
说明部分的分析 与处理
表格管理
过程体 (语句）的分析 与处理
〈 因子 〉 ∷= 〈 标识符 〉 |〈 无符号整数 〉 |‘（ ’ 〈 表达式 〉 ‘） ’
语义分析
int factor(bool* fsys,int* ptx,int lev)
{ if(sym == ident) /* 因子为常量或变量 */
{
i = position(id,*ptx); /* 查找名字 */
if (i == 0)
{error(11); /* 标识符未声明 */
}
else
{switch (table[i].kind)
{case constant,/* 名字为常量 */
break;
case variable,/* 名字为变量 */
break;
case procedur,/* 名字为过程 */
error(21); /* 不能为过程名 */
……
登录符号表说明部分的分析 与处理对每个过程（含主程序） 说明的对象 （ 变量,常量 和 过程 ） 造符号表登录 标识符的 属性 。
标识符的属性,种类，所在 层次,值 和分配的 相对位置 。
登录信息由 ENTER过程完成。
符号表结构
Enum object {
constant,
variable,
procedur
};
Struct tablestruct {
char name[al];
enum object kind;
int val;
int level;
int adr;
int size;
};
Struct tablestruct table[txmax];
符号表结构
说明种类的定义：
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);
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,CONSTANT
KIND,CONSTANT
KIND,VARIABLE
KIND,VARIABLE
KIND,VARIABLE
KIND,PROCEDUR
VAL,35
VAL,49
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
LEVEL,LEV
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,
S I Z E,4
NAME,G
……
KIND,VARIABLE
……
LEV EL,L E V + 1
……
ADR,DX
……
例程序说明部分为,CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G ； …
符号表名字 种类 层次 /值 地址 存储空间对应名字表
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码 时再 放在 code中的 a域变量定义语句的处理 (C)
语法,<变量说明部分 >:,= var <标识符 >{,<标识符 >}；
程序：
if (sym == varsym){ /* 收到变量声明符号，开始处理变量声明 */
getsymdo;
do {
vardeclarationdo(&tx,lev,&dx);
while (sym == comma) {
getsymdo;
vardeclarationdo(&tx,lev,&dx);
}
if (sym == semicolon){
getsymdo;
}else error(5);
} while (sym == ident);
}
注意,&tx
变量说明处理 (C)
int vardeclaration(int* ptx,int lev,int* pdx)
{
if (sym == ident){
enter(variable,ptx,lev,pdx);//填写名字表
getsymdo;
}else
{
error(4);/* var后应是标识 符 */
}
return 0;
}
变量定义语句的处理语法,<变量说明部分 >:,= 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;
变量说明处理
procedure vardeclaration;
begin
if sym=ident then
begin
enter(variable);
getsym
end
else error(4)
end(*vardeclaration*);
过程 ENTER的实现 (C)
/*
* 在名字表中加入一项
*
* k,名字种类 const,var or procedure
* ptx,名字表尾指针的指针
* lev,名字所在的层次,以后所有的 lev都是这样
* pdx,当前应分配变量的相对地址，分配后增加 1
*/
void enter(enum object k,int* ptx,
int lev,int* pdx)
过程 ENTER的实现 (C)
{
(*ptx)++;
strcpy(table[(*ptx)].name,id);
/* 全局变量 id中已存有当前名字的名字 */
table[(*ptx)].kind = k;
switch (k){
case constant,/* 常量名字 */
if (num > amax)
{ error(31);/* 数越界 */
num = 0;
}
table[(*ptx)].val = num;
break;
过程 ENTER的实现 (C)
case variable,/* 变量名字 */
table[(*ptx)].level = lev;
table[(*ptx)].adr = (*pdx);
(*pdx)++;
break;
case procedur,/* 过程名字 */
table[(*ptx)].level = lev;
break;
}
}
过程 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;* )
过程 ENTER的实现
case k of
constant,
begin
if num>amax then
begin
error(31);
num:=0;
end;
val:=num;(* table[tx].val:=num;*)
end;
过程 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*);
过程体的处理
/*
* 编译程序主体
*
* lev,当前分程序所在层
* tx,名字表当前尾指针
* fsys,当前模块后跟符号集合
*/
int block(int lev,int tx,bool* fsys)
过程体的处理
......//main()函数
if(-1 == block(0,0,nxtlev)){
......
}
......
if (sym != period) error(9);
......
interpret();/* 调用解释执行程序 */
......
过程体的处理
while (sym == procsym) // block()函数
{ getsymdo;
if (sym == ident){
enter(procedur,&tx,lev,&dx);
.....
}
......
if (-1 == block(lev+1,tx,nxtlev))
}
过程体的处理－ 变量引用的处理
对 语句进行 语法 分析
语义分析 当遇到 标识符的引用时 就调用 POSITION函数 查
TABLE表,看是否 有 过 正确定义,若已有，则从表中 取相应的有关 信息,供代码的生成使用。 若无定义则错 。
语义分析 TABLE表 若已 有 过 正确定义,检查引用与说明的属性是否一致,若不一致则错 。
当 语法语义正确时,就 生成 相应语句功能的 目标代码赋值 语句的处理 (C)
if (sym == ident){ /* 准备按照赋值语句处理 */
i = position(id,*ptx);
if (i == 0){
error(11); /* 变量未找到 */
}else
{
if(table[i].kind != variable){
error(12); /* 赋值语句格式错误 */
i = 0;
}else
{
......
gendo(sto,lev-table[i].level,table[i].adr);
......
}
}
}
赋值 语句的处理
if sym = ident then
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
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器编译程序的错误处理错误处理的原则：尽可能准确指出出错位置，
错误性质，尽可能进行校正。
PL/0编译程序对语法错误的处理：
(1) 对于 易于校正 的错误，如丢了逗号，分号等，指出出错位置,加以校正,继续进行分析。
(2) 对于 难于校正 的错误，给出错误的位置与性质,跳过后面的一些单词,直到下一个可以进行正常语法分析的语法单位。
在 进入 某个 语法单位 时，调用 TEST,检查当前符号是否属于该 语法单位的开始符号集合 。若不属于，
则 滤去 开始 符号 和 后跟 符号 集合外 的所有符号。
在 语法单位 分析结束 时，调用 TEST,检查当前符号是否属于调用该语法单位时应有的 后跟 符号集合。
若不属于，则 滤去 后跟 符号和 开始 符号 集合外 的所有符号 。
╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳
TEST TEST
开始符号集合与后跟符号集合非终结符名 开始符号集合 后跟符号集合分程序 const var procedure
ident if call begin
while read write
,;
语句 ident call begin
if while read write
,; end
条件 odd + - (
ident number
Then do
表达式 + - (
ident number
,; ) rop
end then do
项 ident number (,; ) rop + -
end then do
因子 ident number (,; ) rop + -
* / end then do
开始符号 集合
symset=set of symbol;
declbegsys,statbegsys,facbegsys:symset;
开始符号集合（ *主程序 *）
declbegsys:=[constsym,varsym,procsym];
statbegsys:=[beginsym,callsym,ifsym,
whilesym,readsym,writesym];
facbegsys:=[ident,number,lparen];
后 跟 符 号集合 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);
READ语句的分析处理 (C)
if (sym == readsym){//处理 read语句
getsymdo;
if (sym != lparen){
error(34); //格式错误,应是左括号
}else
{
do {
getsymdo;
READ语句的语法语义分析处理
if sym=readsym then
begin
getsym;
if sym<>lparen then error(34)
else
repeat
getsym;
READ语句的语法语义分析处理
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;
READ语句的语法语义分析处理
getsym
until sym<>comma;
if sym<>rparen then
begin
error(33);
while not(sym in fsys)
do getsym
end
else getsym
end
出错处理跳过不应出现的符号正确 出 口
TEST
SYM在 S1中打印出错编号 n
S1:=S1+S2
SYM在 S1中
GETSYM
返回
Y
Y
N
N
TE
ST
测试过程流程图因子的处理过程
例：因子的处理过程
procedure factor(fsys:symset);
var i:integer;
begin
入口,test(facbegsys,fsys,24);
while sym in facbegsys do
begin
if
...
出口,test(fsys,facbegsys,23);
end
end;
因子的处理过程
Facbegsys
y
处理 ident
number,
lparen
test
n
test
增加后跟符 与 调用位置有关例：调用 expression(fsys);
write语句的 语法 write(<exp>{,<exp>});
write语句 (后 调用 expression时 后跟符
expression([rparen,comma]+fsys);
factor的 语法,factor∷=,..|‘(’ exp ’)
在 factor(后 调用 expression时 后跟符
expression([rparen]+fsys);
第 2章 PL/0编译程序本章目的：以 PL/0编译程序 为实例,学习编译程序实现的基本步骤和相关技术
1 PL/0编译程序的结构
2 PL/0编译程序的分析工作 (词法，语法和语义）实现
3 PL/0编译程序的 错误处理方法
4 目标代码生成和 类 pcode代码解释器代码生成代码生成是由过程 GEN完成。
GEN有 3个 参数,分别代表目标代码的 功能码,
层差 和 位移量 。例如
gen(opr,0,16);
gen(sto,lev-level,adr)
lev：当前 处理的 过程 层次
level：被引用变量或过程所在 层次
CX：为目标代码 code数组的下标指针代码结构变换,地址返填
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
类 p－ code代码解释器的实现
类 p－ code目标机结构
目标代码解释执行时 数据栈的布局 （运行栈的存储分配）
目标代码 类 p-code
目标代码 类 p-code是 一种 栈式机 的 汇编语言 。
栈式机系统结构,没有累加器和寄存器，只有存储栈指针所有运算都在栈顶（零地址机）
指令格式：
f l a
f 功能码
l 层次差 （标识符 引用层 减去 定义层 ）
a 根据不同的指令有所区别类 p－ code解释器的结构目标代码（ 指令） 存放在数组 CODE中（ 程序地址寄存器 p） 。
解释程序定义一个一维整型数组 S作为 运行栈栈顶寄存器 （指针） t,基址寄存器 （指针） b，
指令寄存器 i（当前正在解释的目标指令）
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 结束退栈目标代码解释执行时数据栈的布局
（运行栈的存储分配）
在每个过程调用时在栈顶分配 3个联系单元：
SL,静态链,指向 定义 该过程的 直接外过程
（或主程序）运行时 最新 数据段的基地址 。
DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
Var x,y;
Procedure P;
var a;
procedure Q;
var b;
begin(*Q*)
b:= 10;
end (*Q*);
procedure S;
var c,d;
procedure R;
var e,f;
begin(*R*)
call Q;
end(*R*);
begin(*S*)
call R;
end(*S*);
begin(*P*)
call S;
end;(*P*)
begin(*MAIN*)
call P;
end(*MAIN*).
目标代码的解释执行 运行栈 S
M调用过程 P M调用过程 P P调用过程 S
RA
DL
SLb
t
t
b
P
M
P
M
S
目标代码的解释执行几条 特殊指令 在 code中的 位置 和 功能
INT 0 A
在 过程 目标程序的 入口处,开辟 A个单元的数据段。
A为 局部变量 的 个数 +3。
OPR 0 0
在 过程 目标程序的 出口处,释放数据段 （退栈），
恢复调用 该过程 前 正在运行的过程 的数据段 基址寄存器 B和 栈顶寄存器 T的值，并将 返回地址 送 到指令地址寄存器 P中，以使调用前的程序从 断点 开始 继续执行 。
目标代码的解释执行几条 特殊 指令在 code中的 位置 和 功能
CAL L A
调用过程,还完成 填写 静态链,动态链,返回地址,给出 被调 用 过程 的 基地址 值,送 入基址寄存器 B中，目标程序的 入口 地址 A的值 送 指令地址寄存器 P中，使指令从 A开始执行。
附
CX：为目标代码 code数组的下标指针。 code为一维数组，数组元素为 记录型数据 。每一个记录就是一条目标指令。 CX 为整数变量，由 0开始顺序增加。
实际上目标代码的顺序是内层过程的在前边，主程序的目标代码在最后。
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码 时再 放在 code中的 a域 。
下标指针 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
p
m
b
Table表的 下标指针 tx补充说明,
主程序
BLOCK
第 1次 调用 block
BLOCK（ 0,0,… ）
0
0
...
BLOCK BLOCK（ LEV+1,TX,… ）
(递归 进入 分程序 )
LEV
tx
LEV
tx
（ 6）
6 （ 9）
1
tx是 BLOCK的实际 值参附 PL/0编译程序的实现
procedure gen(x:fct; y,z:integer);
begin
if cx>cxmax then（ *指针越界 *）
begin
write(‘ program too long’ );
close(fin);（ *关闭文件 *）
writeln;
exit
end;
附 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*);
附 PL/0编译程序的实现对 分程序的定义（ 见教材 417,437页）
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/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的作用）
NAME,A
NAME,B
NAME,C
NAME,D
NAME,E
NAME,P
KIND,C O N S T A N T
KIND,C O N S T A N T
KIND,V A R I A B L E
KIND,V A R I A B L E
KIND,V A R I A B L E
KIND,P R O C E D U R
VAL,35
VAL,49
LEVEL,L E V
LEVEL,L E V
LEVEL,L E V
LEVEL,L E V
ADR,DX
ADR,DX+1
ADR,DX+2
ADR,1 SIZE,4
NAME,G
……
KIND,V A R I A B L E
……
LEVEL,L E V + 1
……
ADR,DX
……
CONST A=35,B=49；
VAR C,D,E；
PROCEDURE P；
VAR G
附 table表格管理名字 类型 层次 /值 地址 存储空间
(0) jmp 0 0
CX (1 ) jmp 0 0
.
.
记录 过程在 code的 入口到 table中的 adr域附 PL/0编译程序的实现过程 体 入口 时的处理
code[table[tx0].adr].a:=cx;
（过程入口地址填 写在 code中 ）
with table[tx0] do
begin
adr:=cx; （ 过程的 入口 填 写在 table中 ）
size:=dx; （ 过程 占的空间 填 写在 table中 ）
end;
cxo:=cx; （保留 过程在 code中的 入口地址）
gen(int,0,dx);（ 生成 过程 入口指令 ）
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;
P=0?
返回解释执行的流程图执行指令 i
N
Y
主程序的 RA
s[3]=0
附 目标代码的解释执行几条 特殊指令 的 解释执行,
过程 入口,开辟 a个单元 （见教材 425页）
int,t:=t+a; （ t是当前 栈顶值）
过程 出口,释放数据段 （退栈）（ 见教材 425页）
opr,case a of (*operator*)
0,begin (*return*)
t:=b-1; 恢复调用前栈顶
p:=s[t+3]; 送返回地址到 p
b:=s[t+2] 恢复调用前基地址
end;
附 目标代码的解释执行过程 出口
RA
DL
SLb
.
,
t
M
t
b
t:=b-1;
p:=s[t+3];
b:=s[t+2]
Q
附 目标代码的解释执行调用过程,
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;
附 目标代码的解释执行
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*);
附 目标代码的解释执行
base (l:integer),integer;
b
b
b
m
p
0
b
b
q
附 运行时数据栈 S的变化状态
…
Procedure A;
…
procedure B;
…
procedure C;
…
call B;
…
…
call C;
…
…
call B;
…
…
Call A;
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
B 的局部变量
RA
DL
SL
…
C 的局部变量
RA
DL
SL
…
B 的局部变量
RA
DL
SL
…
A 的局部变量
RA
DL
SL
…
主程序变量区
0
0
0
T
B
