搜索
第1页共22页一、上机实践要求“编译原理与技术”的上机实验要求你对PL/0语言及其编译器进行扩充和修改。每个扩充或修改方式可得到不同的分数，满分为100分。完成上机作业后，必须提交下列文档：（1）修改后的PL/0语言文本。包含词法分析（正规式），语法分析（BNF）。（2）有关修改后的PL/0编译/解释器的说明。详细说明你的编译器是如何编译新的PL/0语言程序的。指出你的程序中最精彩的部分，以及你为什么这样做，你是如何控制和恢复语义错误的。（3）给出你所改动后的编译器源程序清单，并标记出你所修改的部分。比较你的编译器和原来的编译器之间的差别。（4）说明你的编译器中可能存在的错误。（5）总结经验与教训，如果重做一遍，你会有哪些新的改进？对现存的PL/0编译程序可做如下修改或扩充，其中（1）、（2）、（11）和（12）必须完成，剩余的均可任意选择，但总分必须超过70分。（1）注释（5分）注释由(*和*)包含，不允许嵌套。（2）布尔类型的数据（10分）布尔类型的BNF为：var_option→ε|varvar_decl_listvar_decl_list→var_decl|var_decl_listvar_declvar_decl→ident_list:data_typedata_type→integer|boolean这种修改包括：（i）区别整型与布尔型变量、常量和表达式。（ii）增加按严格计算的布尔类型运算符and、or和not。这些算符以及己有的运算符的优先级与Pascal语言相同。（iii）能够使用布尔常量true和false。（iv）把PL/0语言中的“条件”概念一般化为Pascal语言那样。（v）布尔表达式可以比较大小：falsetrue（3）布尔表达式的短路计算（5分）增加布尔类型（见（2），除（2）的（ii）外），但对and和or采取短路计算。（4）数组（10分）增加由任何数据类型构造的一维数组。数组的下标限于纯量类型。注意：数组可以由其它的数组来构造，因而必须考虑多维数组的情况。数组的上下界可为任意的纯量常数。数组的定义如下：data_type→integer|boolean|array[const..const]ofdata_typeconst→ident|number语言中允许有数组说明，对数组元素赋值，在表达式中引用数组元素。为了便于解释执行，可能要增加新的PL/0机器操作指令。（5）参数（10分）语法同Pascal，采用值-结果方式传递（不用var声明）。（6）函数（10分）语法同Pascal。第2页共22页（7）else子句和repeat语句（5分）（8）for语句，语法参照Pascal或C语言（5分）（9）exit语句（退出当前执行过程）和break语句（跳出包含它的最内层循环），（5分）（10）记录（结构）,语法同Pascal语言（10分）。（11）更有力的语法错误恢复机制（20分）（12）分离解释和编译器（5分）注意：上面的这些要求有时会互相影响：例如实现布尔类型数据，则数组和参数就应该能处理其相互组合的情况，如布尔型数组（包括多维数组）、布尔型作为下标的数组、布尔型作为参数传递。甚至能够实现数组作为参数传递等。另外，为了实现以上功能，你可任意增加PL/0处理机的指令。但要注意指令的简单与合理。选做题：此题不计入总分，仅做为学生在有余力的情况下的进一步练习。实现PL/0语言的输入、输出语句。其语法、语义定义和Pascal语言相同。可以仅仅实现一次输入或输出一个值的语句——语句参数固定；也可以实现完全和Pascal语言一样，能够接受任意个数参数的输入或输出语句。二、实验原理：就像一个翻译要把汉语翻译成英语，必须对汉语和英语的单词、语法结构都很精通，才有可能翻译得准确无误。另外，编译程序既然是为了完成这种功能的一个程序，就存在用什么语言来编写这个程序的问题。这些问题在本节将逐步介绍。现对PL/0语言编译程序的功能用“T”型图表示，并用图形概括描述PL/0编译程序的结构框架。用语法图描述语法规则的优点是直观、易读。在图1.1的语法图中用椭圆和圆圈中的英文字表示终结符，用长方形内的中文字表示非终结符。所谓终结符，是构成语言文法的单词，是语法成分的最小单位，而每个非终结符也是一个语法成分。但非终结符可由其它文法符号定义，终结符不能由其它文法符号定义。例如，程序是由非终结符'分程序'和终结符.组成的串定义的。由于对某些非终结符可以递归定义，如图1.1(b)、2.1(c)、2.1(e)中：分程序、表达式和语句。第一个非终结符'程序'为文法的开始符号。程序1.1（a）语句序列1.1(c)条件分程序.语句;表达式odd表达式===第3页共22页1.1(e)分程序1.1(b)语句constidentnumber=var;identprocedure,ident;;程序体;语句identcallbeginwhileendident:=ifdothen语句语句表达式语句序列条件条件,表达式第4页共22页1.1(d)表达式1.1(f)项1.1(g)因子1.1(h)如：{*}表示*重复任意次，{*}38表示*重复3-8次。[]：方括号表示其内的成分为任选项。()：表示圆括号内的成分优先。例：用EBNF描述整数文法的定义：整数∷=[+|-]数字{数字}数字∷=0|1|2|3|4|5|6|7|8|9或更好的写法整数∷=[+|-]非零数字{数字}|0项项+--+因子因子/*identnumber表达式()第5页共22页非零数字∷=1|2|3|4|5|6|7|8|9数字∷=0|非零数字PL/0语言文法的EBNF表示为：〈程序〉∷=〈分程序〉．〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义〉{，〈常量定义〉}；〈常量定义〉∷=〈标识符〉=〈无符号整数〉〈无符号整数〉∷=〈数字〉{〈数字〉}〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉}〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}；〈过程首部〉∷=PROCEDURE〈标识符〉；〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉〈赋值语句〉∷=〈标识符〉∶=〈表达式〉〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉}〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')'〈加法运算符〉∷=+|-〈乘法运算符〉∷=*|/〈关系运算符〉∷=#|=|＜|＜=|＞|＞=〈条件语句〉∷=IF〈条件〉THEN〈语句〉〈过程调用语句〉∷=CALL〈标识符〉〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉〈读语句〉∷=READ'('〈标识符〉{，〈标识符〉}')'〈写语句〉∷=WRITE'('〈表达式〉{，〈表达式〉}')'〈字母〉∷=a|b|…|X|Y|Z〈数字〉∷=0|1|2|…|8|9EBNF表示的符号说明。〈〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。∷=：该符号的左部由右部定义，可读作'定义为'。|：表示'或'，为左部可由多个右部定义。{}：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。用语法图描述语言的语法与EBNF描述相比较：语法图描述：直观，易读，易写。EBNF表示：形式化强，易机器识别。无论用语法图或EBNF作为描述程序设计语言语法的工具，对描述的语法可以检查哪些符号序列是所给语言的合法程序，一个程序设计语言如C或JAVA，用户可用它写出成千上万个不同的程序，但C或JAVA它们各自的语法只有一个，这就使得无穷的句子集可用有穷的文法（语法）描述。PL/0编译程序的使用限制◇标识符的有效长度是10第6页共22页◇数字最多为14位◇过程最多可嵌套三层，可递归调用◇标识符的作用域同PASCAL，内层可引用包围它的外层定义的标识符（如：变量名，过程名，常量名）目标指令有8条：①LIT：将常量值取到运行栈顶。a域为常数值。②LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置,l为调用层与说明层的层差值。③STO：将栈顶的内容送入某变量单元中。a,l域的含意同LOD指令。④CAL：调用过程的指令。a为被调用过程的目标程序入口地址，l为层差。⑤INT：为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。⑥JMP：无条件转移指令，a为转向地址。⑦JPC：条件转移指令，当栈顶的布尔值为非真时，转向a域的地址，否则顺序执行。⑧OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令，具体操作由a域值给出。（详见解释执行程序）。类pcode代码指令的详细解释（指令功能表）认识目标代码类pcode目标代码类pcode是一种假想栈式计算机的汇编语言。指令格式：flaf功能码l层次差（标识符引用层减去定义层）a根据不同的指令有所区别指令功能表LIT0a将常数值取到栈顶，a为常数值LODla将变量值取到栈顶，a为偏移量，l为层差STOla将栈顶内容送入某变量单元中，a为偏移量，l为层差CALla调用过程，a为过程地址，l为层差INT0a在运行栈中为被调用的过程开辟a个单元的数据区JMP0a无条件跳转至a地址JPC0a条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行OPR00过程调用结束后,返回调用点并退栈OPR01栈顶元素取反OPR02次栈顶与栈顶相加，退两个栈元素，结果值进栈OPR03次栈顶减去栈顶，退两个栈元素，结果值进栈OPR04次栈顶乘以栈顶，退两个栈元素，结果值进栈OPR05次栈顶除以栈顶，退两个栈元素，结果值进栈OPR06栈顶元素的奇偶判断，结果值在栈顶OPR07OPR08次栈顶与栈顶是否相等，退两个栈元素，结果值进栈OPR09次栈顶与栈顶是否不等，退两个栈元素，结果值进栈第7页共22页OPR010次栈顶是否小于栈顶，退两个栈元素，结果值进栈OPR011次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈OPR012次栈顶是否大于栈顶，退两个栈元素，结果值进栈OPR013次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈OPR014栈顶值输出至屏幕OPR015屏幕输出换行OPR016从命令行读入一个输入置于栈顶PL/0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。本书所提供的PL/0语言编译器的基本工作流程如图1-1所示：由于PL/0编译程序采用一趟扫描方法，所以语法分析过程BLOCK是整个编译过程的核心。下面我们将在语法分析词法分析语义分析代码生成代码执行源程序执行结果符号表管理错误诊断处理图1-1PL/0编译器基本工作流程第8页共22页图2.4中先给出编译程序的总体流程，以弄清BLOCK过程在整个编译程序中的作