编译原理实验指导书

编译原理实验指导

《编译原理》实验指导书

毛红梅 吴振华 编

南昌航空大学计算机学院 2003年1月初稿 2007年10月修改

编译原理实验指导

目录

编译原理一共开设了三个实验，它们是： 1. 词法分析程序，占2个学时 2. 语法分析程序，占2个学时

3. 扩充的PL/0分析程序（综合实验），占

6个学时。

编译原理实验指导

实验报告格式

1. 姓名 班级 学号 2. 实验名称 3. 实验目的 4. 实验要求

5. 实验内容(这个是实验报告的主要部分) 6. 实验总结(实验心得) 7. 实验报告人 报告时间

编译原理实验指导

实验一 PL/O语言的词法分析程序GETSYM

过程GETSYM的说明：由于一个单词往往是由一个或几个字符组成，

所以在词法分析过程GETSYM中又定义一个取字符过程GETCH，由词法分析需要取字符时调用。

实验目的：

1. 为了更好的配合《编译原理》有关词法分析章节的教学 2. 加深和巩固学生对于词法分析的了解和掌握

3. 让学生初步的认识PL/0语言的基础和简单的程序编写

4. 学生通过本实验能够初步的了解和掌握程序词法分析的整个过程 5. 提高学生的上机和编程过程中处理具体问题的能力

实验要求:

1. 做本实验之前要先阅读完总体的预备知识以及本实验相关的基础知识 2. 实验要求自己独立的完成,不允许抄袭别人的实验结果

3. 编写和调试过程中出现的问题最好做一下记录

4. 实验程序调试完成后, 用给定的PL0测试程序(test.pl0)进行测试，由老师检查测试结果，并给予相应的成绩 5. 实验完成后,要上交实验报告。

实验内容：

1. 阅读所给出的词法分析程序（pl0_lexical.c），搞懂程序中每一个变量的含义，

以及每一个过程的作用，并在该过程中进行中文注释。

2. 阅读完程序后，画出各过程的流程图。

3. 给出的程序包含两处输入错误，利用所给的pl/0源程序(test.pl0)对程序进行调

试，使其能正确对所给文件进行分析并能够解释运行。

4. 在阅读懂所给出的词法分析程序后，将你对词法分析的理解写在实验报告上。

实验环境：

1. 操作系统为Windows 2000或Dos6.2以上 2. 应用软件为Pascal或C语言

GETCH 所用单元说明：

CH ：存放当前读取的字符，初值为空， LINE：为一维数组，其数组元素是字符； 界对为1：80。用于读入一行字符的缓冲区； LL，CC: 为计数器，初值为0； GETSYM流程图的工作单元说明：

编译原理实验指导

A: 一维数组，数组元素为字符，界对[1:10]； ID：同A；

WORD:保留字，一维数组，数组元素为以字符为元素的一维数组。界对为[1:13]。查表方式采用二分法。

本实验基础知识:

PL/O语言的编译程序，是用高级语言PASCAL语言书写的。整个编译过程是由一些嵌套及并列的过程或函数完成。词法分析程序是独立的过程GETSYM完成，供语法分析读单词时使用。语法分析是由过程BLOCK完成。采用自顶向下的递归子程序法 。所产生的目标程序为假象栈式计算机的汇编语言。对目标程序的执行是由PASCAL语言书写的解释程序进行的。因此 PL/O语言可以在配备PASCAL语言的任何机器上实现。由于PL/O语言编译程序是适合教学用的实例，它的数据类型只有整形数，数据运算只有四则运算。语句有复制语句、条件语句、While型循环语句、输入、输出语句和不带参数允许递归调用过程语句及复合语句。 注意:程序流程图参见教材P19页,并不是本实验唯一的流程图，大家应该根据自己的思路作一个修改,争取能够体现自己的创新。这个流程图只是做一个参考，在大家上交的实验报告里要具体说明你所编写的程序关于这个过程实现的原理。词法分析程序的设计---使用状态转换图（如图1所示）实现

表示状态，对应每个状态编一段程序，每个状态调用取字符程序，根据当前字符转到不同的状态，并做相应操

作。

表示终态，已识别出一个单词。

图1 一个可能的状态机示例

词法分析程序GETSYM的功能包括：

1. 滤空格,空格在词法分析时是一种不可缺少的界符,而在语法分析时是无用的,所

编译原理实验指导

以必须滤掉。

2. 识别保留子：设有一张保留字表。对每个字母打头的字母、数字字符串要查此

表。若查着则为保留字，对应的类别放在SYM中。如IF对应值为THENSYM。 3. 识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中。 4. 拼数：当所取单词是数字时，将树的类别NUMBER放在SYM中，数值本身

的值放在NUM中。

5. 拼复合词：对两个字符组成的算符如：>=、：=、<= 等单词，识别后将类别送SYM中。

6. 打印源程序：为边读入字符边打印。

打印每个单词的识别类别（如果是标识符或数字应该给出其值即id和num中的值。图2所示即为给定PL0源程序的一个可能输出）。

图2 源程序中前七行一个可能的输出

编译原理实验指导

实验二 PL/O语言的语法分析过程BLOCK

实验目的：

1. 为了更好的配合《编译原理》有关词法分析章节的教学

2. 加深和巩固学生对于语法分析的了解和掌握

3. 让学生进一步的认识PL/0语言的基础和简单的程序编写

4. 使学生通过本实验能够初步的了解和掌握程序语法分析的整个过程 5. 提高学生的上机和编程过程中处理具体问题的能力

实验要求

1. 在做本实验之前要先阅读完总体的预备知识以及本实验相关的基础知识。 2. 本实验要求自己独立的完成,不允许抄袭别人的实验结果。 3. 在编写和调试过程中出现的问题最好做一下记录。

4. 阅读懂所给出的语法分析程序，然后进行改进。

5. 在阅读懂所给出的语法分析程序后,老师将进行逐个的检查以及提问，然后给出

成绩。

实验内容：

1. 阅读所给出的语法分析程序（pl0_syntax.c），搞懂程序中每一个变量的含义，

以及每一个过程的作用，并在该过程中进行中文注释。 2. 阅读完程序后，画出各过程的流程图。

3. 给出的程序包含两处输入错误，利用所给的pl/0源程序(test.pl0)对程序进行调

试，使其能正确对所给文件进行分析并能够解释运行。 4. 在阅读懂所给出的语法分析程序后，将你对语法分析的理解写在实验报告上。

实验环境：

1. 操作系统为Windows 2000或Dos6.2以上 2. 应用软件为Pascal或C语言

本实验预备知识：

语法分析的任务，是识别由词法分析给出的单词符号序列结构上是否符合给定的文法规则。文法规则可用语法定义给出。

用语法描述图表示文法规则的优点是直观、易读。语法描述图中用椭圆和圆圈中的英文字，表示终结符用长方形内的中文字表示非终结符。所谓终结符，是构成语言

文法的单词，是语法成分的最小单位。而每个非终结符是一个语法成分，在书写语言程序时并不出现，它由终结符和非终结符串、或终结符串定义的。例如：程序是由非终结符'分程序'和终结符"."这个串定义的。由于对某些非终结符可以递归定义，如：图中分程序、表达式、语句，这就使得无穷的句子集可用有穷的文法描

编译原理实验指导

述。而对于第一个非终结符如'程序'不能出现在对非终结符的定义部分，通常称这样的符号为开始符。

PL/0语言编译程序的语法分析是采用了自顶向下的递归子程序法。粗略地说：就是对应每个非终结符语法单元编一个独立的处理过程（或子过程）。语法分析从读入第一个单词由非终结符'程序'即开始符出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，则执行相应的语义程序（就是翻译程序）。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个相比，若都有不匹配时可能是进入下一非终结符语法单位或是出错。如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，并正确，直到程序结束符"."，这时就说所输入的程序是正确的。对于正确的语法分析做相应的语义翻译，最终得出目标程序。 过程BLOCK说明：

过程BLOCK的工作又可分为两步。

1. 说明部分的处理

由于PL/0语言允许过程调用语句，且允许过程嵌套定义。因此每个过程应有过程首部以定义局部于它自己定义的内过程引用。对于同一层过程的调用关系是先定义的可以被子后定义的引用，反之则不行。 说明部分的处理任务就是对每个过程（包括主程序，也可看成是一个主过程）的说明对象造名字表。填写所在层次（主程序为第0层，主程序定义的过程为第1层，随着嵌套的深度增加而层次数加大。PL/0最多允许3层），标识符的属性和分配的相对位置等。标识符的属性不同时，所需要填的信息也不同。 所造表放在全程量一维数组TABEL表中。TX为索引表的指针，表中的每个元素为记录型数据，LEV给出层次，DX给出每层局部量当前已分配到相对位置，可称地址指示器，每说明完一个变量后DX指示器加1。 例如：一个过程的说明部分为： CONST A=35,B=49; VAR C,D,E; PROCEDURE P;

VAR G

例题中说明处理后TABEL表中的信息对于过程名的ADR域,是在过程体的目标代码生成后反填过程体的入口地址。例中处理P过程的说明对LEV就增加1。在P过程中的变量名的层次为LEV+1后的值.至于造表和查表的过程中,如何保证每个过程的局部量不能被它的外层引用,请同学们看完程序后自己总结。

TABEL表的表头索引TX和层次单元LEV都以BLOCK的参数形式出现.在主程序调用BLOCK时实参值都为0.每个过程中变量的相对起始位置在BLOCK内置初值DX:=3。

2. 语句处理和代码生成

程序和主体是由语句构成的.处理完过程的说明后就处理由语句组成的过程体,从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标

编译原理实验指导

识符的引用时就查TABEL表,看是否有过正确的定义,若已有,则从表中取相应的有关信息,供代码的生成用。PL/0语言的代码生成是由过程GEN完成的。GEN过程有三个参数,分别代表目标代码的功能码、层差、和位移量。生成的代码顺序放在数组CODE中。CODE为一维数组,数组元素为记录型数据.每一个记录就是一条目标指令。CX为指令的指针,由0开始顺序增加。 PL/0语言的目标指令的格式:

其中f代表功能码,l层次差,a:位移量。 目标指令有8条:

① LIT:将常量放到运行栈顶.a域为常数。 ② LOD:将变量放到栈顶.a域为变量在所说明层中的相应位置,l为调用层与说明层的层差值。 ③ STO:将栈顶的内容送入某变量单元中,a,l域的含意同LOD。 ④ CAL:调用过程的指令.a为被调用过程的目标程序入口地址,l为层差。 ⑤ INT:为被调用的过程(或主程序)在运行栈中开辟数据区.a域为开辟的个数。 ⑥ JMP:无条件转移指令,a为转向地址。 ⑦ JPC无条件转移指令,当栈顶的布尔值为非真时,转向a域的地址,否则顺序执行。 ⑧ OPR:关系和算术运算.具体操作由a域给出.运算对象为栈顶和次栈顶的内容进行运算,结果存放在次栈顶,或是其他特殊功能的操作。

编译原理实验指导

综合实验

实验三 扩展功能的PL/O编译程序

——扩充PL/0编译程序使其能完成对如下三个扩充功能的编译

PL/0语言的三个扩充功能：

1. 一维数组的扩充，语法如下： VAR <数组标识符> ‘[’数组长度‘]’ 2. 条件语句的扩充，语法如下：

<条件语句> ::=IF<条件>THEN <语句> [ELSE <语句>] 3. 重复语句的扩充，语法如下： <重复语句> ::=REPEAT <语句>{; <语句>}UNTIL <条件>

实验目的：

1. 为了更好的配合《编译原理》有关词法分析章节的教学 2. 加深和巩固学生对于语法分析的了解和掌握

3. 让学生进一步的认识PL/0语言的基础和简单的程序编写 4. 使学生通过本实验能够扩大对pl/0的理解。 5. 提高学生的上机和编程过程中处理具体问题的能力

实验要求

1. 在做本实验之前要先阅读完总体的预备知识以及本实验相关的基础知识。 2. 本实验要求自己独立的完成,不允许抄袭别人的实验结果。 3. 在编写和调试过程中出现的问题最好做一下记录。 4. 阅读懂扩充语法图所给出的语法。

实验内容：

1. 给出三个扩充功能的语法描述图及EBNF的语法描述;

2. 在已理解所给出的pl/0编译程序的基础上，要求对其进行扩展，使扩展后的PL/0编译程序能够完成对三个扩充功能的编译; 3. 结合所给出的两个PL/0源程序(test1.pl0, test2.pl0)，对所改进的PL/0编译程序

进行调试;

4. 如果扩充后的编译程序可以完成对test1.pl0, test2.pl0的编译，并能运行得到运

行结果（如图1(a)、图1(b)所示），经老师检查后将有加分; 5. 如果能够使扩充后的编译程序可以支持用表达式作为数组的下表，即允许使用形如array[i]，调用数组元素（调试用源码为test3.pl0，运行结果如图1(c)所示），将额外加分; 6. 将实现对三个扩充功能进行编译的思路，以及你对语法分析的理解写在实验报

编译原理实验指导

告上。

(a) (b) (c)

图1 (a、b、c)分别为test1.pl0、test2.pl0、test3.pl0的一个可能运行结果

实验环境：

1. 操作系统为Windows 2000或Dos6.2以上。 2. 编程语言为Pascal或C语言。

提示：

1. 扩充的条件语句和重复语句都是语句，而所给的PL/0编译程序中有语句处理

函数，找到相应函数并进行扩充;

2. 所给的三个扩充功能中引入了几个新的关键字，从而必需对相应的全局变量其数据结构进行修改; 3. 注意跳转语句的处理，往往在一跳转语句处不知道所要跳转的指令地址，解决

办法是将该跳转语句地址保存，在知道所要跳转的指令地址后再回填; 4. 要能完成对数组的处理，即使只是用整型常数作为数组下标引用数组元素，所

要做的工作比较多。涉及的有，如何进名字表，如何定位到各个元素，各种语

句中哪些涉及到会直接使用数组元素等，分析清楚这些因素之后，找到各因素对应函数进行修改;

5. 如果要使数组的下标支持表达式，需扩充新的目标指令。

编译原理实验指导

附：

test1.pl0: const a=10; procedure p; var d;

procedure q; var x; begin repeat begin read(x); if odd x then

d:=2*x else d:=x; write(d)

end

until x=0

end

begin

call q

end begin

call p end. test2.pl0: const a=10; var e[10]; procedure p; var d; procedure q; var x; begin read(e[1],e[2],e[3],e[4],e[5]); d:=e[1]+e[3]; write(d)

end

编译原理实验指导

begin

call q

end

begin call p end. test3.pl0: const a=10; var e[10]; procedure p; var d; procedure q; var x,i;

begin i:=0; repeat begin read(x); if odd x then

e[i]:=2*x else e[i]:=x; write(e[i]); i:=i+1

end

until i=10 end

begin

call q

end

begin call p end.

本文来源：https://www.bwwdw.com/article/sy2m.html