编译原理实验指导

实

原验指

理

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

10; 1+2; (1+2)*3+(5+6*7); ((1+2)*3+4; 1+2+3+(*4+5); (a+b)*(c+d); ((ab3+de4)**5)+1;

正确结果：

（1）10; 输出：正确 （2）1+2; 输出：正确

（3）(1+2)*3+(5+6*7); 输出：正确 （4）((1+2)*3+4 输出：错误 （5）1+2+3+(*4+5) 输出：错误 （6）(a+b)*(c+d) 输出：正确

（7）((ab3+de4)**5)+1 输出：错误

七、实验报告要求

实验报告应包括以下几个部分： 1、 给定文法的LL（1）形式； 2、 递归下降分析程序的算法和结构； 3、 程序运行流程； 4、 程序的测试结果和问题； 5、 实验总结。

八、思考题

1、 为什么文法必须先转化为LL（1）文法再来做递归下降分析？2、 如果用预测分析法来改写本程序，如何来实现？

11

实验5 语法分析程序的设计（2）

一、实验目的

通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。

二、实验内容

设计一个文法的算法优先分析程序，判断特定表达式的正确性。

三、实验要求

1、给出文法如下：

G[E] E->T|E+T; T->F|T*F; F->i(E);

可以构造算符优先表如下： + * ( ) i

2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式； 3、 给出算符优先分析算法如下：

k:=1; S[k]:=‘#’; REPEAT

把下一个输入符号读进a中；

IF S[k]∈VT THEN j:=k ELSE j:=k-1; WHILE S[j] a DO BEGIN REPEAT Q:=S[j];

IF S[j-1]∈VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q

把S[j+1]…S[k]归约为某个N； k:=j+1;

12

+ * ( ) i S[k]:=N;

END OF WHILE;

IF S[j] a OR S[j]

BEGIN

k:=k+1;S[k]:=a END

ELSE ERROR UNTIL a=‘#’

a THEN

4、 根据给出算法，利用适当的数据结构实现算符优先分析程序； 5、 利用算符优先分析程序完成下列功能：

1） 手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束； 2） 读入文本文件中的表达式；

3） 调用实验2中的词法分析程序搜索单词；

4） 把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语

言），若错误，应给出错误信息；

5） 完成上述功能，有余力的同学可以对正确的表达式计算出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

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

五、实验步骤

1、分析文法中终结符号的优先关系； 2、存放优先关系或构造优先函数；

3、 利用算符优先分析的算法编写分析程序； 4、写测试程序，包括表达式的读入和结果的输出； 5、 程序运行效果，测试数据可以参考下列给出的数据。

六、测试数据

输入数据：

编辑一个文本文文件expression.txt，在文件中输入如下内容：

10; 1+2; (1+2)*3+(5+6*7); ((1+2)*3+4; 1+2+3+(*4+5); (a+b)*(c+d); ((ab3+de4)**5)+1;

13

正确结果：

（1）10; 输出：正确 （2）1+2; 输出：正确

（3）(1+2)*3+(5+6*7); 输出：正确 （4）((1+2)*3+4 输出：错误 （5）1+2+3+(*4+5) 输出：错误 （6）(a+b)*(c+d) 输出：正确

（7）((ab3+de4)**5)+1 输出：错误

七、实验报告要求

实验报告应包括以下几个部分： 6、 给定文法优先关系和存放方式； 7、 算符优先分析程序的算法和结构； 8、 程序运行流程； 9、 程序的测试结果和问题； 10、 实验总结。

八、思考题

1、 算符优先关系表示的是一种什么样的关系，它在自下而上的分析中起到了什么作

用？

2、 比较本实验和实验4，实现同样的功能，两种方法有什么不同？

14

实验6 逆波兰式的翻译和计算

一、实验目的

通过实验加深对语法指导翻译原理的理解，掌握算符优先分析的方法，将语法分析所识别的表达式变换成中间代码的翻译方法。

二、实验内容

设计一个表示能把普通表达式（中缀式）翻译成后缀式，并计算出结果的程序。

三、实验要求

1、给出文法如下：

G[E] E->T|E+T; T->F|T*F; F->i(E);

对应的转化为逆波兰式的语义动作如下：

(1)(2)(1)(2)

E-> Eop E {E.CODE:= E.CODE||E.CODE||op}

(1)(1)

E->(E) { E.CODE := E.CODE}

E->id { E.CODE := id}

2、利用实验5中的算符优先分析算法，结合上面给出的语义动作实现逆波兰式的构造； 3、利用栈，计算生成的逆波兰式，步骤如下：

1） 中缀表达式，从文本文件读入，每一行存放一个表达式，为了降低难度，表达

式采用常数表达式；

2） 利用结合语法制导翻译的算符优先分析，构造逆波兰式； 3） 利用栈计算出后缀式的结果，并输出；

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

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

五、实验步骤

1、了解语法制导翻译的方法，学习后缀式构造的语义动作； 2、结合实验5的算符优先程序，设计程序构造后缀式；

3、利用栈，编程实现后缀式的计算；

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

六、测试数据

输入数据：

15

编辑一个文本文文件expression.txt，在文件中输入如下内容：

1+2; (1+2)*3; (10+20)*30+(50+60*70);

正确结果：

（1）1+2; 输出：1,2,+ 3 （2）(1+2)*3; 输出：1,2,+,3,* 9 （3）(10+20)*30+(50+60*70)

输出：10,20,+30,*50,60,70,*,+,+ 5150

七、实验报告要求

实验报告应包括以下几个部分： 1、 构造逆波兰式的语义动作；

2、 结合算符优先分析构造逆波兰式的算法和过程； 3、 语法制导翻译的运行方法； 4、 程序的测试结果和问题； 5、 实验总结。

八、思考题

1、 语法制导翻译的工作方式？

2、 为什么编译程序要设计生成中间代码方式？

16

实验7 语法制导的三地址代码生成

一、实验目的

掌握计算机语言的语法分析程序设计与属性文法应用的实现方法。

二、实验内容

编制一个能够进行语法分析并生成三地址代码的微型编译程序。

三、实验要求

1、考虑下述语法制导定义中文法，采用递归子程序法，改写文法，构造语法分析程序； 2、考虑下述语法制导定义中语义规则，改写语法分析程序，构造三地址代码生成程序。 产生式 S->id = E ; S->if C then S C.true = newlabel; C.false = S.next; S1.next = S.next; S.code = C.code || gen(E.true’:’) || S1.code S->while C do S S.begin = newlabel; C.true = newlabel; C.false = S.next; S1.next = S.begin; S.code = gen(S.begin’:’) || C.code || gen(E.true’:’) || S1.code || gen(‘goto’S.begin); C->E1 > E2 C.code = E1.code || E2.code || gen(‘if’E1.place’>’E2.place’goto’C.true) || gen(‘goto’C.false) C->E1 < E2 C.code = E1.code || E2.code || gen(‘if’E1.place’<’E2.place’goto’C.true) || gen(‘goto’C.false) C->E1 = E2 C.code = E1.code || E2.code || gen(‘if’E1.place’=’E2.place’goto’C.true) || gen(‘goto’C.false) E->E1 + T E.place = newtemp; E.code = E1.code||T.code|| gen(E.place’:=’E1.place’+’T.place) E->E1 - T E.place = newtemp; E.code = E1.code || T.code || gen(E.place’:=’E1.place’-’T.place) 语义规则 S.code = E.code || gen(id.place’:=’E.place) 17

T->T1 * F T.place = newtemp; T.code = T1.code || F.code || gen(T.place’:=’T1.place’*’F.place) T->T1 / F T.place = newtemp; T.code = T1.code || F.code || gen(T.place’:=’T1.place’/’F.place) F->( E ) F->id F->int8 F->int10 F->int16 F.place = E.place; F.code = E.code F.place = id.name; F.code = ‘ ‘ F.place = int8.value; F.code = ‘ ‘ F.place = int10.value; F.code = ‘ ‘ F.place = int16.value; F.code = ‘ ‘ 四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

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

五、实验步骤

1、考虑给定的文法，消除左递归，提取左因子。 2、编制并化简语法图 3、编制递归子程序的算法 4、编制各个递归子程序函数

5、连接实验一的词法分析函数scan( )，进行测试 6、设计三地址代码生成的数据结构和算法 7、将各个递归子程序函数改写为代码生成函数 8、编制测试程序（main函数）

9、调试程序：输入一个语句，检查输出的三地址代码

六、测试数据

输入数据例：while (a3+15)>0xa do if x2 = 07 then while y

正确结果：等效的三地址代码序列

L1: t1 := a3 + 15 L2: L3:

if t1 > 10 goto L2 goto L0

if x2 > 7 goto L4 goto L1

18

L4: if y < z goto L5 goto L1 L5: t2 = x * y

t3 = t2 / z y = t3 goto L3

goto L1

L0:

// S.next

七、实验报告要求

实验报告应包括以下几个部分： 1、语法制导定义 2、改写后的产生式集合 3、化简后的语法图 4、 递归子程序的算法

5、三地址代码生成器的数据结构 6、程序结构的说明

八、思考题

1、生成的三地址代码可否直接输出（不采用数据结构来实现属性code）？2、如何保证四则运算的优先关系和左结合性？

3、如何采用代码段相对地址代替三地址代码序列中的标号？

19

20

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