PL0编译程序的实现(4学时).ppt

第2章 PL/0编译程序的实现,2.1 PL/0语言描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的词法分析 2.4 PL/0编译程序的语法语义分析 2.5 PL/0编译程序的目标代码结构和代码生成 2.6 PL/0编译程序的语法错误处理 2.7 PL/0编译程序的目标代码解释执行时的存储分配,何为PL/0语言?,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.,PL/0编译程序,pcode解释程序,PL/0源程序,注：此处的pcode代码专指PL/0的目标代码，与传统pcode有区别,pcode代码,2019/8/9,2.1 PL/0语言描述,语法描述的目的： 用有穷的文法形式，描述（验证）无穷的句子形式。 语法描述的常用形式： 非形式化描述（不规范） 语法描述图：直观、易读。 EBNF（扩充的巴科斯-瑙尔范式）,NEXT,PL/0 语言的非形式描述,数据类型只有整型 标识符的有效长度是10，以字母开始的字母数字串 过程无参，可嵌套（最多三层），可递归调用 变量的作用域同PASCAL，常量为全局的，无标 语句类型：赋值语句，if.then., while.do., read, write, call, 复合语句begin. end， 说明语句： const., var., procedure 13个保留字：if, then, while, do, read, write, call, begin, end, const, var, procedure, odd,2019/8/9,PL/0 语言的语法描述图,（1）终结符VT 语法成分中的最小单位，构成语言文法的单词。 椭圆或圆圈内的单词表示VT （2）非终结符VN 语法成分，在书写程序时并不出现，但可一直追溯成 VT 表示的形式。 矩形内的符号表示VN （13-15页）,BNF（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur来命名的，它从语法上描述程序设计语言的元语言。 采用BNF可说明哪些符号序列是对于某给定语言在语法上有效的程序。,BNF引入的符号： 表示语法构造成分（语法单位），为非终结符 = 定义为 | 或 EBNF引入的符号： 表示花括号内的语法成分可重复 表示方括号内的语法成分为任选项 ( ) 表示圆括号内的成分优先,PL/0 语言文法的 EBNF 表示,8,两个用EBNF描述“整数”的例子, = +|- = 0|1|2|3|4|5|6|7|8|9 或 = +|-|0 = 1|2|3|4|5|6|7|8|9 = 0|1|2|3|4|5|6|7|8|9 PL/0语言文法 参见 P15,16,练习：P.31 题6（2）（3）,9,2.2 PL/0编译程序的结构,PL/0 编译过程采用一趟扫描方式 以语法语义分析程序为核心,词法分析程序和代码生成程序都作为一个独立的过程。 当语法分析需要读单词时，就调用词法分析程序 当语法分析正确需要生成相应的目标代码时，则调用代码生成程序 用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。 用出错处理程序对词法和语法分析遇到的错误，给出在源程序中出错的位置和错误性质。,10,目标程序,PL/0 编译程序的结构图,PL/0源程序,编译过程,解释执行过程,11,编译程序总体流程图 17页,12,所需识别的单词： 关键字： 如 BEGIN、END、IF、THEN 等 运算符： 如 +、-、*、/、：=、#、=、= 等 标识符： 用户定义的变量名、常数名、过程名 常数： 如 10、25、100 等整数 界符： 如 , . ; ( ) 等,2.3 PL/0编译程序的词法分析,词法分析过程GETSYM 所要完成的任务：滤空格、识别保留字、识别标识符、拼数、拼复合词、输出源程序 参见 P.19 图,通过 三个全程量 将识别出的单词信息传递给语法分析程序 SYM： 存放单词的类别,如 beginsym, ident, number ID ： 存放用户所定义的标识符的值 NUM： 存放用户定义的数,13,2.4 PL/0编译程序的语法语义分析,语法分析的任务： 识别由词法分析给出的单词符号序列在“结构”上是否符合给定的“文法规则”。 语法分析的过程： 从读入第一个单词开始，由VN “程序”出发，沿语法图箭头所指进行分析: 遇到VN ，调用相应的处理过程 遇到VT ，判断当前单词是否与VT 匹配 若匹配：执行语义程序，翻译成目标代码 若不匹配：报错,PL/0语法调用关系图：,14,说明部分的处理 （1）判别语法结构 （2）标识符（变量，常量和过程名）信息写入名字表，即表格管理。 名字表需要填写： 所在层次 标识符的属性 分配的相对位置 （标识符的属性不同时，所需填入的信息也不同。登录信息由ENTER过程完成。） 程序体的处理 （1）判别语法结构 （2）根据名字表的信息，进行语义分析,15,名字 类型 层次/值 地址 存储空间,CONST A=35，B=49； VAR C，D，E； PROCEDURE P； VAR G,表格管理举例,TX0,TX1,注：TX为索引表的指针,16,名字 类型 层次/值 地址 存储空间,练习：P.31 题3,TX0,TX1,TX2,TX3,TX4,17,目标代码pcode是一种假想栈式计算机的汇编语言。 指令格式,2.5 PL/0编译程序的目标代码结构和代码生成,功能码,层次差,通常为“位移量” 根据不同的指令有所不同,18,目标指令,19,0 jmp 0 8 无条件跳转至8 1 jmp 0 2 无条件跳转至2 2 int 0 3 在栈顶中申请3个栈空间 3 lod 1 3 将变量取至栈顶（1层差, 3相对位置） 4 lit 0 10 将常数10取至栈顶 5 opr 0 2 次栈顶与栈顶相加 6 sto 1 4 将栈顶值存入变量 7 opr 0 0 函数调用结束后返回 8 int 0 5 在运行栈中申请5个栈空间 9 opr 0 16 从命令行读入输入置于栈顶 10 sto 0 3 将栈顶值存入变量 11 cal 0 2 调用过程 12 lod 0 4 将变量取至栈顶 13 opr 0 14 栈顶值输出至屏幕 14 opr 0 15 换行 15 opr 0 0 函数调用结束后返回,Const a=10; var b,c; procedure p; begin c:=b+a; end; begin read(b); call p; write(c); end.,目标代码举例,参见P24,20,PL/0语言的代码生成是由过程GEN 完成。 GEN有三个参数，分别代表目标代码的功能码，层差和位移量。 gen(opr,0,16); gen(sto,lev-level,adr) 生成的代码顺序放在数组CODE中。 CODE为一维数组，数组元素为记录型数据。 每一个记录就是一条目标指令。 CX为指令的指针，由0开始顺序增加。 实际上目标代码的顺序：内层过程在前边，主程序的目标代码在最后。,PL/0编译程序的代码生成,常见错误： 语法错误 语义错误 运行错误,2.6 PL/0编译程序的语法错误处理,NEXT,（1）对于易于校正的错误，如丢了逗号，分号等 处理：指出出错位置，加以校正，继续进行分析。 （2） 对于难于校正的错误 处理：给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。 具体做法： 在进入某个语法单位时，调用测试程序TEST滤去开始符号前的所有符号。 在语法单位分析结束时，调用测试程序TEST滤去当前符号到后继符号之间的所有符号。,对语法错误的两种处理方法：,若标识符未加说明就引用，或引用与说明的属性不一致 处理：只给出错误位置和信息，编译器继续工作。,对语义错误的处理方法：,对运行错误（下标越界、数组溢出等）的处理方法：,处理：编译器无法指出源程序的出错位置。,25,2.7 目标代码解释执行时的存储分配,一、pcode解释器的结构 参见P.28 目标代码存放在数组CODE中 解释程序定义的 一维整型数组S 作为运行栈 4个寄存器： T 栈项寄存器 B 基址寄存器 P 程序地址寄存器 I 指令寄存器 3个联系单元： SL 静态链：指向定义该过程的直接外过程运行时最新数据段基地址 DL 动态链：指向调用该过程前正运行过程的数据段基地址 RA 返回地址：记录调用该过程时目标程序的断点,26,interpret,三个寄存器赋初值 t:=0; b:=1; p:=0;,主程序的SL，DL，RA赋初值 s1:=0; s2=0; s3=0;,i:=codep; p:=p+1;,执行指令i,P=0?,返回,二、 解释执行的流程图,27,INT 0 A 位于过程目标程序的入口，开辟A个单元的数据段。A为局部变量个数+3 OPR 0 0 位于过程目标程序的出口，释放数据段（退栈），恢复调用该