编译原理实验指导(3)

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