编译原理实验指导

实

原验指

理

1

编译 导

目 录

实验1：文法的读入和输出......................................................................................... 3 实验2：词法分析程序的设计..................................................................................... 5 实验3：LL（1）文法构造 .......................................................................................... 7 实验4：语法分析程序的设计（1）......................................................................... 10 实验5：语法分析程序的设计（2）......................................................................... 12 实验6：逆波兰式的翻译和计算............................................................................... 15 实验7：语法制导的三地址代码生成....................................................................... 17

2,3,5,6/7

2

实验1 文法的读入和输出

一、实验目的

熟悉文法的结构，了解文法在计算机内的表示方法。

二、实验内容

1、 设计一个表示文法的数据结构；

2、 从文本文件中读入文法，利用定义的数据结构存放文法，并输出； 3、 本实验结果还将用于实验3。

三、实验要求

1、 了解文法定义的4个部分：

G（Vn, Vt, S, P）

Vn 文法的非终结符号集合，在实验中用大写的英文字母表示； Vt 文法的终结符号集合，在实验中用小写的英文字母表示； S 开始符号，在实验中是Vn集合中的一个元素；

P 产生式，分左部和右部，左部为非终结符号中的一个，右部为终结符号或非终结符号组成的字符串，如S->ab|c

2、 根据文法各个部分的性质，设计一个合理的数据结构用来表示文法，

1） 若使用C语言编写，则文法可以设计成结构体形式，结构体中应包含上述的4

部分，

2） 若使用C++语言编写，则文法可以设计成文法类形式，类中至少含有4个数据

成员，分别表示上述4个部分

文法数据结构的具体设计由学生根据自己想法完成，并使用C或C++语言实现设计的数据结构。

3、 利用完成的数据结构完成以下功能：

1） 从文本文件中读入文法（文法事先应写入文本文件）；

2） 根据文法产生式的结构，分析出文法的4个部分，分别写入定义好的文法数据

结构的相应部分； 3） 整理文法的结构；

4） 在计算机屏幕或者文本框中输出文法，文法输出按照一个非终结符号一行，开

始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

3

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五、实验步骤

1、根据文法定义，设计出文法数据结构 2、用学生选择的语言，实现文法的数据结构

3、编写调试文法读入和输出程序，

4、 测试程序运行效果：从文本文件中读入一个文法，在屏幕上输出，检查输出结果。

六、测试数据

输入数据：

编辑一个文本文文件g.txt，在文件中输入如下内容： S->Qc; S->c; Q->Rb; Q->b; R->Sa; R->a;

正确结果：

上述文法整理后的输出形式： S->Qc|c; Q->Rb|b; R->Sa|a;

七、实验报告要求

实验报告应包括以下几个部分： 1、 文法数据结构的设计和实现； 2、 文法的读入算法 3、 文法的输出方法 4、 程序的测试结果和问题 5、 实验总结

八、思考题

1、 如何让设计的文法结构满足各种文法的要求？

2、 如何设计文法才能跟简单地表示文法，同时又降低程序编写难度？

4

实验2 词法分析程序的设计

一、实验目的

掌握计算机语言的词法分析程序的开发方法。

二、实验内容

编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。

三、实验要求

1、根据以下的正规式，编制正规文法，画出状态图；

标识符

<字母>(<字母>|<数字字符>)*

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）（0|1|2|3|4|5|6|7）*

0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）* + - * / > < = ( ) ； if then else while do

十进制整数 八进制整数 十六进制整数 运算符和界符 关键字

2、根据状态图，设计词法分析函数int scan( )，完成以下功能：

1） 从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 2） 以二元式形式输出单词<单词种类，单词属性>

其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数

运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下：

标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空

3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五、实验步骤

1、 根据正规式，画出状态转换图； 2、 根据状态图，设计词法分析算法；

5