转眼大学生活就要结束,编译原理课程学的东西很多都忘记了。当时我们编译原理课程实践是PL/0语言编译器扩展,在原有PL/0语言文法进行扩展。我写这次博文一是为了回忆以前学的知识,加深记忆;二是和大家分享一下,希望可以互相学习,想对一些新手有所帮助。
首先,我先简单介绍一下PL/0语言。PL/0 语言是 Pascal 语言的一个子集,是 Pascal 语言的设计者 Niklaus Wirth 在其专著Algorithms + Data Structures = Programs 一书(译著书名:算法+数据结构=程序)中给出的。 PL/0 是一个小巧的高级语言。虽然它只有整数类型,但它是相当完全的可嵌套的分程序(block)的程序结构,分程序中可以有常量定义、变量声明和无参过程声明,过程体又是分程序。PL/0 有赋值语句、条件语句、循环语句、过程调用语句、复合语句和空语句。 PL/0 语言的文法如下:
Program → Block .
Block → [ConstDecl] [VarDecl][ProcDecl] Stmt
ConstDecl → const ConstDef {, ConstDef} ;
ConstDef → ident = number
VarDecl → var ident {, ident} ;
ProcDecl → procedure ident ; Block ; {procedure ident ; Block ;}
Stmt → ident := Exp | call ident | begin Stmt {; Stmt} end |
if Cond then Stmt | while Cond do Stmt | ε
Cond → odd Exp | Exp RelOp Exp
RelOp → = | <> | < | > | <= | >=
Exp → [+ | − ] Term {+ Term | − Term}
Term → Factor {∗ Factor | / Factor}
Factor → ident | number | ( Exp )
其中的标识符 ident 是字母开头的字母数字串,number 是无符号整数,begin、call、const、do、end、if、odd、procedure、then、var、while 是保留字。
在《算法+数据结构=程序》一书中,Niklaus Wirth 设计的 PL/0 语言编译器分成两部分,把源语言翻译成中间语言的编译器和中间语言解释器,编译器用的是递归下降的预测分析方法中间语言是一种栈机器代码,其指令集是根据 PL/0 语言的需要来设计的。编译器源码及测试程序可从project.rar下载。一条指令由三个域组成:
(1)操作码 f:上面已经列出了所有 8 种操作码。
(2)层次差 l:这里的层次差就是 5.3.2 节介绍嵌套深度时的 n p − n a 。该域仅用于存取指令和调用指令。
(3)多用途 a:在运算指令中,a 的值用来区分不同的运算;在其他情况,a 或是一个数(lit,int),或是一个程序地址(jmp,jpc,cal),或是一个数据地址(lod,sto)。
编译器对 PL/0 源程序进行一遍扫描,并逐行输出源程序。在源程序无错的情况下,编译器每编译完一个分程序,就列出该分程序的代码,这由编译器的 listcode 过程完成。每个分程序的第一条指令是 jmp 指令,其作用是绕过该分程序声明部分产生的代码(即绕过内嵌过程的代码)。listcode 过程没有列出这条代码。 解释器是编译器中的一个过程,若源程序无错,则编译结束时调用解释过程 interpret。由于 PL/0 语言没有输出语句,解释器按执行次序,每遇到对变量赋值时就输出该值。 由于 PL/0 语言是过程嵌套语言,因此程序运行时,活动记录栈中每个活动记录需要包含控制链和访问。活动记录栈的栈顶以外的存储空间作为代码执行过程中所需要的计算栈,无需另外设立计算栈。
扩展后的PL/0语言的语法:
课程实践要完成下列要求
(1)给PL/0语言增加像C语言那样的形式为/* …… */的注释。
(2)给PL/0语言增加带else子句的条件语句和exit语句。
(3)给PL/0语言增加输入输出语句。
(4)给PL/0语言增加带参数的过程。
(5)给PL/0语言增加布尔类型。
(6)给PL/0语言增加数组类型。
(7)给PL/0语言增加函数类型。
(8)给PL/0语言增加实数类型。
(9)分离解释器和编译器为两个独立的程序。
有关该扩展的说明如下:
(1)描述语言的部分符号的解释
符号®、|、[、]、{和}是描述语言的符号,其中方括号[…]中的部分可以出现0次或1次,花括号{…}中的部分可以出现任意次数,包括0次。
被描述语言若使用上述这些符号,则需要用单引号,例如在数组类型的定义和下标变量的引用中。
(2)词法部分
· 形式为/* …… */的注释也是词法单元之间的分隔符。
· 标识符ident是字母开头的字母数字串。
· number是无符号数,若是实数,则采用小数点前后都有非空数字串这一种形式。
· 新增保留字:type、array、of、integer、real、Boolean、function、else、write、read、exit、or、and、not、div、mod、true、false。
· div:整数除,mod:取模,/ :实数除
(3)静态检查和动态检查
· 若exit语句没有处于任何while语句中,则是一个错误。
· 读写语句的变量引用和表达式只能是整型或实型。
· 表达式和赋值语句中float和integer之间的混合运算或赋值,自动类型转换按C语言的方式。
· 数组类型是按名字等价而不是结构等价。其他场合也是如此。
· 数组类型不能作为过程和函数的参数类型,也不能作为函数的结果类型。
· 除上述几点之外的静态检查都是大家应该知道的,不在此叙述。
· 运行时检查下标表达式是否越界,越界则报告错误,停止程序的运行。
(4)语句的语义
只对特殊部分加以说明。
· exit语句作为while语句的非正常出口语句。若处于多层while语句中,则它只作为包含该exit的最内层while语句的非正常出口。
· 读语句接受从键盘输入的数据,数据之间用空格分隔。读语句具有忽略当前输入行剩余字符,下一个读语句接受的数据另起一行的功能。
· 写语句输出的数据显示在屏幕上,数据之间用空格分隔。写语句具有结束当前输出行,下次输出另起一行的功能。
· 增加了写语句后,原来sto指令的输出功能取消,以免输出数据过多,不宜发现所关心的数据。
· 程序员定义的函数和过程的参数都是值调用参数,函数的结果类型不能是数组类型。
· 布尔类型的表达式按短路方式计算。
· 函数中没有return语句,在函数中把函数名当作局部变量,通过对函数名赋值来把函数值返回。
(5)分离解释器和编译器为两个独立的程序
· 编译器和解释器的接口是二进制的中间代码文件。
· 原编译器中listcode方式的中间代码列表输出功能略去,以便编译过程中的屏幕输出简洁(只有源程序和报错信息);增加把完整的中间代码列表输出到文件的功能,以便实验评测时使用,该功能对于你测试和调试程序来说也是有用的。
以后博文具体介绍程序实现。