第 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语言
PL/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的过程体主 程序 体程序 分程序,
内的文字表示 非终结符或 内的文字或符号表示 终结符
const ident number=
,;
var 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语言的 子集同 PASCAL
作用域规则(内层 可引用包围它的外层定义的 标识符),
上下文约束,
过程可 嵌套定义,可递归调用子集
数据类型,只有整型
数据结构,只有简变和常数
数字最多为 14位
标识符的有效长度是 10
语句种类
过程最多可 嵌套 三层目标代码 类 pcode
目标代码 类 pcode是 一种 假想栈式计算机 的 汇编语言 。
指令格式:
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编译程序的总体设计
其编译过程采用 一趟扫描方式
以语法,语义分析 程序 为核心词法分析 程序和 代码生成 程序都作为一个 过程,当语法分析需要读单词时就调用词法分析程序,而当语法,语义分析正确,需要生成相应的目标代码时,则调用代码生成程序。
表格管理 程序实现 变量,常量 和 过程 标识符的 信息的登录与查找 。
出错处理 程序,对词法和语法,语义分析遇到的错误给出在源程序中 出错的位置 和与 错误 性质有关 的编号,并进行错误恢复。
PL/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? =
,+ - (? -?-
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
<程序 >为文法的开始符号,以开始符号作为根结点构造一棵倒挂着的语法树。
递归子程序法
递归子程序法,对应 每个非终结符 语法单元,,编一个独立的处理过程(或子程序)。语法分析从读入第一个单词开始,由非终结符 <程序 >( 即开始符)出发,沿语法描述图 箭头 所指出的方向进行分析。当遇到非终结符时,则 调用 相应的 处理过程,从语法描述图看,也就进入了一个语法单元,再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是 终结符 时,则判断当前读入的单词是否与图中的终结符 相匹配,若匹配,再读取下一个单词继续分析。遇到 分支点 时,将当前的单词与分支点上多个终结符 逐个相比较,若都不匹配时可能是进入下一个非终结符语法单位或是出错。
例:如何用递归子程序法实现表达式的语法分析项表达式
+
-
项
+
-
项 因子因子
*
/
语法图因子的语法图因子 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;
〈 项 〉 的 递归子程序 实现
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
语法调用关系图编译程序总体流程图
ˉ
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
PL/0编译程序语义分析的设计与实现
PL/0编译程序语法、语义分析的的核心 程序是 BLOCK过程
,
说明部分的分析 与处理
表格管理
过程体 (语句)的分析 与处理说明部分的分析 与处理对每个过程(含主程序) 说明的对象 ( 变量,常量 和 过程 ) 造符号表登录 标识符的 属性 。
标识符的属性,种类,所在 层次,值 和分配的 相对位置 。
登录信息由 ENTER过程完成。
说明部分的分析与处理( 程 序)
说明种类的定义:
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域变量定义语句的处理语法,<变量说明部分 >:,= 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=identthen
begin
enter(variable);
getsym
end
else error(4)
end(*vardeclaration*);
过程 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*);
过程体的处理
对 语句进行 语法 分析
语义分析 当遇到 标识符的引用时 就调用 POSITION函数 查
TABLE表,看是否 有 过 正确定义,若已有,则从表中 取相应的有关 信息,供代码的生成使用。 若无定义则错 。
当 语法语义正确时,就 生成 相应语句功能的 目标代码赋值 语句的处理
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
代码生成
代码生成是由过程 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
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语句的语法语义分析处理
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);
类 pcode代码解释器的实现
类 pcode解释器的结构
目标代码解释执行时 数据栈的布局 (运行栈的存储分配)
类 pcode解释器的结构
目标代码存放在数组 CODE中。
解释程序定义一个一维整型数组 S作为 运行栈栈顶寄存器 (指针) t,基址寄存器 (指针) b,
程序地址寄存器 p,指令寄存器 i
目标代码解释执行时数据栈的布局
(运行栈的存储分配)
在每个过程调用时在栈顶分配 3个联系单元:
SL,静态链,指向 定义 该过程的 直接外过程
(或主程序)运行时 最新 数据段的基地址 。
DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
目标代码的解释执行 运行栈 S
M调用过程 Q
RA
DL
SLb
.
,
t
t
b
Q
M
目标代码的解释执行几条 特殊指令 在 code中的 位置 和 功能
INT 0 A
在 过程 目标程序的 入口处,开辟 A个单元的数据段。
A为 局部变量 的 个数 +3。
OPR 0 0
在 过程 目标程序的 出口处,释放数据段 (退栈),
恢复调用 该过程 前 正在运行的过程 的数据段 基址寄存器 B和 栈顶寄存器 T的值,并将 返回地址 送 到指令地址寄存器 P中,以使调用前的程序从 断点 开始 继续执行 。
目标代码的解释执行几条 特殊 指令在 code中的 位置 和 功能
CAL L A
调用过程,还完成 填写 静态链,动态链,返回地址,给出 被调 用 过程 的 基地址 值,送 入基址寄存器 B中,目标程序的 入口 地址 A的值 送 指令地址寄存器 P中,使指令从 A开始执行。
附 PL/0编译程序代码生成的实现
CX:为目标代码 code数组的下标指针。 code为一维数组,数组元素为 记录型数据 。每一个记录就是一条目标指令。 CX 为整数变量,由 0开始顺序增加。
实际上目标代码的顺序是内层过程的在前边,主程序的目标代码在最后。
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码时再 放在 code中的 a域 。
附 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
p
m
b
附 PL/0编译程序代码生实现
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编译程序代码生成的实现对 分程序的定义( 见教材 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/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个单元 (见教材 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;
附 目标代码的解释执行
过程 出口
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的变化状态教材 25页
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语言
PL/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的过程体主 程序 体程序 分程序,
内的文字表示 非终结符或 内的文字或符号表示 终结符
const ident number=
,;
var 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语言的 子集同 PASCAL
作用域规则(内层 可引用包围它的外层定义的 标识符),
上下文约束,
过程可 嵌套定义,可递归调用子集
数据类型,只有整型
数据结构,只有简变和常数
数字最多为 14位
标识符的有效长度是 10
语句种类
过程最多可 嵌套 三层目标代码 类 pcode
目标代码 类 pcode是 一种 假想栈式计算机 的 汇编语言 。
指令格式:
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编译程序的总体设计
其编译过程采用 一趟扫描方式
以语法,语义分析 程序 为核心词法分析 程序和 代码生成 程序都作为一个 过程,当语法分析需要读单词时就调用词法分析程序,而当语法,语义分析正确,需要生成相应的目标代码时,则调用代码生成程序。
表格管理 程序实现 变量,常量 和 过程 标识符的 信息的登录与查找 。
出错处理 程序,对词法和语法,语义分析遇到的错误给出在源程序中 出错的位置 和与 错误 性质有关 的编号,并进行错误恢复。
PL/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? =
,+ - (? -?-
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
<程序 >为文法的开始符号,以开始符号作为根结点构造一棵倒挂着的语法树。
递归子程序法
递归子程序法,对应 每个非终结符 语法单元,,编一个独立的处理过程(或子程序)。语法分析从读入第一个单词开始,由非终结符 <程序 >( 即开始符)出发,沿语法描述图 箭头 所指出的方向进行分析。当遇到非终结符时,则 调用 相应的 处理过程,从语法描述图看,也就进入了一个语法单元,再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是 终结符 时,则判断当前读入的单词是否与图中的终结符 相匹配,若匹配,再读取下一个单词继续分析。遇到 分支点 时,将当前的单词与分支点上多个终结符 逐个相比较,若都不匹配时可能是进入下一个非终结符语法单位或是出错。
例:如何用递归子程序法实现表达式的语法分析项表达式
+
-
项
+
-
项 因子因子
*
/
语法图因子的语法图因子 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;
〈 项 〉 的 递归子程序 实现
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
语法调用关系图编译程序总体流程图
ˉ
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
PL/0编译程序语义分析的设计与实现
PL/0编译程序语法、语义分析的的核心 程序是 BLOCK过程
,
说明部分的分析 与处理
表格管理
过程体 (语句)的分析 与处理说明部分的分析 与处理对每个过程(含主程序) 说明的对象 ( 变量,常量 和 过程 ) 造符号表登录 标识符的 属性 。
标识符的属性,种类,所在 层次,值 和分配的 相对位置 。
登录信息由 ENTER过程完成。
说明部分的分析与处理( 程 序)
说明种类的定义:
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域变量定义语句的处理语法,<变量说明部分 >:,= 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=identthen
begin
enter(variable);
getsym
end
else error(4)
end(*vardeclaration*);
过程 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*);
过程体的处理
对 语句进行 语法 分析
语义分析 当遇到 标识符的引用时 就调用 POSITION函数 查
TABLE表,看是否 有 过 正确定义,若已有,则从表中 取相应的有关 信息,供代码的生成使用。 若无定义则错 。
当 语法语义正确时,就 生成 相应语句功能的 目标代码赋值 语句的处理
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
代码生成
代码生成是由过程 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
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语句的语法语义分析处理
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);
类 pcode代码解释器的实现
类 pcode解释器的结构
目标代码解释执行时 数据栈的布局 (运行栈的存储分配)
类 pcode解释器的结构
目标代码存放在数组 CODE中。
解释程序定义一个一维整型数组 S作为 运行栈栈顶寄存器 (指针) t,基址寄存器 (指针) b,
程序地址寄存器 p,指令寄存器 i
目标代码解释执行时数据栈的布局
(运行栈的存储分配)
在每个过程调用时在栈顶分配 3个联系单元:
SL,静态链,指向 定义 该过程的 直接外过程
(或主程序)运行时 最新 数据段的基地址 。
DL,动态链,指向 调用 该过程前正在运行过程的数据段基地址。
RA,返回地址,记录调用该过程时 目标程序的 断点,即调用过程指令的下一条指令的地址。
目标代码的解释执行 运行栈 S
M调用过程 Q
RA
DL
SLb
.
,
t
t
b
Q
M
目标代码的解释执行几条 特殊指令 在 code中的 位置 和 功能
INT 0 A
在 过程 目标程序的 入口处,开辟 A个单元的数据段。
A为 局部变量 的 个数 +3。
OPR 0 0
在 过程 目标程序的 出口处,释放数据段 (退栈),
恢复调用 该过程 前 正在运行的过程 的数据段 基址寄存器 B和 栈顶寄存器 T的值,并将 返回地址 送 到指令地址寄存器 P中,以使调用前的程序从 断点 开始 继续执行 。
目标代码的解释执行几条 特殊 指令在 code中的 位置 和 功能
CAL L A
调用过程,还完成 填写 静态链,动态链,返回地址,给出 被调 用 过程 的 基地址 值,送 入基址寄存器 B中,目标程序的 入口 地址 A的值 送 指令地址寄存器 P中,使指令从 A开始执行。
附 PL/0编译程序代码生成的实现
CX:为目标代码 code数组的下标指针。 code为一维数组,数组元素为 记录型数据 。每一个记录就是一条目标指令。 CX 为整数变量,由 0开始顺序增加。
实际上目标代码的顺序是内层过程的在前边,主程序的目标代码在最后。
tx,table表的下标指针,是以 值参数 形式使用的。
dx,计算每个变量在运行栈中相对本 过程 基地址 的偏移量,放在 table表 中的 adr域,生成 目标代码时再 放在 code中的 a域 。
附 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
p
m
b
附 PL/0编译程序代码生实现
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编译程序代码生成的实现对 分程序的定义( 见教材 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/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个单元 (见教材 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;
附 目标代码的解释执行
过程 出口
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的变化状态教材 25页