《编译原理》实验教学大纲

一、实验的目的与任务

通过实验学习编译程序调试技巧和设计编译程序的一般原则，加深对词法分析、语法分析、语义分析和中间代码生成等编译阶段及实用编译系统的认识，初步掌握编译程序构造的基本原理与技术,从形式语言理论的角度,进一步认识与理解程序设计语言。

二、教学基本要求

通过编译程序的编写和调试能力的训练，激发学生进一步思考问题，培养学生的学习兴趣和创新能力。并进一步培养学生的抽象思维能力，进一步巩固《编译原理》课程所学知识。

三、实验项目与类型

四、实验教学内容及学时分配

实验一：消去C、C++程序中的注释(2学时)

1、目的要求：

掌握C语言文件的基本操作，消除源C语言程序中的注释，为以后的编译提供方便

2、方法原理：

逐字符读入源程序，并判断相邻2个字符是否为//或/*或*/，如果不是，则直接将读入的字符写入新文件中；如果是，则跳过注释部分。

3、主要实验仪器及材料：

微机及VC环境

4、掌握要点：

二种注释形式的定义

5、实验内容：

注释对于高级语言程序设计可以提高程序的可阅读性，但是对于编译系统而言，注释是没有实际意义的，所以编译系统在预编译阶段首先就要去掉注释。在VC中有两种注释，即单行注释，由//引入到行未，由/*…..*/所包围的注释。要求去掉VC中这两种注释而不改变程序的其它部分。

实验二 ：词法分析的构造(4学时)

1、目的要求：

通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法

2、方法原理：

这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。

3、主要实验仪器及材料：

微机及VC环境

4、掌握要点：

单词的构成规则及单词的分类

5、实验内容：

编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。

实验三 ：FIRST集的构造(2学时)

1、目的要求：

编制程序求给定的任意无左递归文法中所有非终结符的首符集。本次实验的目的主要是加深对求非终符的首符集方法的理解。

2、方法原理：

FIRST(a)={a|Ta*a…,a?VT}特别是，若Ta*e，则规定e?FIRST(a)。换句话说FIRST(a）是a的所有可能推导的开头终结符或可能的e。

对任意一个文法符号X?VTVN，构造FIRST(X)，其方法是连续使用下面的规则 ，直至每个集合FIRST不再增大为止。

1）、若X?VT，则FIRST（X）={X}

2）、X?VN，且有产生式X->a……，则将a加入到FIRST（X）中；若X->e也是一条产生式，则把e也加到FIRST（X）中

3）、若有X->Y……是一个产生式且Y?VN，则把FIRST(Y)中所有的非e元素加到FIST（X）中；若X->Y1Y2…Yk是一个产生式，Y1Y2…Yk都是非络结符，而且，对任何的j，1< ="j<=i-1，FIRST（Yj）都含e，则把FIRST（Yj）中的所有非e元素都加到FIRST（X）中。

3、主要实验仪器及材料：

微机及VC环境

4、掌握要点：

FIRST算法

5、实验内容：

对任意给定的不含左递归的文法求它的所有非终结符的first集

实验四 ：FOLLOW集的构造(2学时)

1、目的要求：

编制程序求给定的任意无左递归文法中所有非终结符的跟随集。本次实验的目的主要是加深对求非终符的FOLLOW集方法的理解

2、方法原理：

FOLLOW(B)的构造分为四条:

(1)如果B是文法的开始符号,则#属于FOLLOW(B)

(2)对形如: A?… Ba…,则把则a属于FOLLOW(B)

(3)对形如:A?... BP…的规则(其中P为非终结符),则FIRST(P)中的非e元素属于FOLLOW(B);

(4)对形如:A?…B,或者A?… Bb且b?e则FOLLOW(A)中的所有元素也属于FOLLOW(B);

3、主要实验仪器及材料：

微机与VC环境

4、掌握要点：

FOLLOW集构造的四个方面

5、实验内容：

对任意给定的不含左递归的文法求它的所有非终结符的FOLLOW集

实验五 ：预测分析表的构造（2学时)

1、目的要求：

根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。

2、方法原理：

构造分析表M的算法是：

（1）对文法G的每个产生式Aa?执行第二步和第三步；

（2）对于每个终结符a?FIRST(a)，把Aa?加到M[A,a]中；

（3）若?eFIRST(a)，则对任何的b?FOLLOW(A)把Aa?加至M[a,b]中；

（4）把所有无定义的M[A,a]标上“出错标志”

3、主要实验仪器及材料：

微机与VC环境

4、掌握要点：

分析表构造的算法

5、实验内容：

对任意给定的不含左递归的文法，通过前面的方法求得它的每一个非终符的FIRST与FOLLOW，在此基础上判断文法是否为LL（1）的，如果是求它的预测分析表。

实验六 ：FIRSTVT集的构造(2学时)

1、目的要求：

编制程序求给定的任意文法中所有非终结符的FIRSTVT集。本次实验的目的主要是加深对求非终符的FIRSTVT集方法的理解

2、方法原理：

一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：

…QR… 则我们称该文法为算符文法。

在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表有终结符和非终结符组成的任意序列，包括空字。

如果一个文法G中的任何终结符对（a, b）至多只满足下述三关系之一：

a=·b, a< ·b, a·>b

则称G是一个算符优先文法

构造集合FIRSTVT(P)的算法。

按定义，我们可用下面两条规则来构造集合FIRSTVT(P):

(1)若有产生式P?a…或P?Qa…,则a?FIRSTVT(P)

(2)若a?FIRSTVT(Q)，且有产生式P?Q… 则a?FIRSTVT(P)

3、主要实验仪器及材料：

微机与VC环境

4、掌握要点：

求的FIRSTVT集的算法

5、实验内容：

对任意给定的文法求它的所有非终结符的FIRSTVT集

实验七 ：LASTVT集的构造(2学时)

1、目的要求：

编制程序求给定的任意文法中所有非终结符的LASTVT集。本次实验的目的主要是加深对求非终符的LASTVT集方法的理解

2、方法原理：

一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：

…QR… 则我们称该文法为算符文法。

在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表有终结符和非终结符组成的任意序列，包括空字。

如果一个文法G中的任何终结符对（a, b）至多只满足下述三关系之一：

a=·b, a< ·b, a·>b

则称G是一个算符优先文法

构造集合LASTVT(P)的算法。

按定义，我们可用下面两条规则来构造集合LASTVT(P):

(1)若有产生式P?…a或P?…aQ,则a?LASTVT(P)

(2)若a?LASTVT(Q)，且有产生式P?…Q 则a?LASTVT(P)

3、主要实验仪器及材料：

微机及VC环境

4、掌握要点：

集合LASTVT(P)的算法

5、实验内容：

对任意给定的文法求它的所有非终结符的LASTVT集

实验八 ：逆波兰表达式(2学时)

1、目的要求：

编制程序求给定的任意表达式求它的逆波兰表达式，并通过逆波兰表达式求表达式的值。本次实验的目的主要是加深对后缀表达式逆波兰表示及求值过程的理解

2、方法原理：

(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式

3、主要实验仪器及材料：

微机与VC环境

4、掌握要点：

表达式的转换算法

5、实验内容：

将输入的中缀表达式转换成逆波兰表示

实验九 ：语法分析程序LR（1）(4学时)

1、目的要求：

构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

2、方法原理：

一个LR分析器实际是一个带先进后出存储器（栈）的确定下推自动机，它由一个输入串、一个下推栈和一个带有分析表的总控程序组成。栈中存放着由“历史”和“展望”材料抽象而来的各种“状态”。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放进栈里。LR分析器的每一动作都由栈顶状态和当前输入符号所唯一确定。

3、主要实验仪器及材料：

微机与VC环境

4、掌握要点：

分析器的构造算法

5、实验内容：

LR(K)方法是一种自下而上的语法分析方法，是当前最广义的无回溯的“移进-归约”方法。它根据栈中的符号串和向前查看的k(k≥0)个输入符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。

优点：文法适用范围广；识别效率高；查错能力强；可自动构造。

逻辑组成：总控程序＋LR分析表

五、考核办法

1.学生在做实验之前，指导教师预先告诉学生进行上机实践的题目，要求学生先编写好设计程序，上机时直接输入原程序，再进行调试。

2.实验完成后有些做成实验报告上交，由指导教师批改并评定等次，有些下机时直接由指导教师检查，并给定相关等次。

3.学生实验报告按四个等级评分，实验成绩与平时出勤按30%计入平时成绩。

六、实验教学指导书和参考书

实验指导书：

1、自编实验指导书。

2、《编译原理及实践》冯博琴等译，机械工业出版社

实验参考书：

1、《程序设计语言与编译》龚天富、侯文永编，电子工业出版社

2、《编译原理》吕映芝、张素琴、蒋维杜主编，清华大学出版社，1998

3、《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社2002

4、《编译原理》（第二版）蒋立源、康慕宁主编，西北工业大学出版社，2002

5、《编译原理习题精选》陈意云、张昱著，中国科技大学出版社，2002

6、《编译原理习题与解析》 伍春香著，清华大学出版社，2001

主 撰 人：朱素英

审 核 人：罗如为

2012.6