编译关键技术试验参考指导书.doc

《编译技术》实验指引书

湘潭大学信息工程学院
计算机工程系
何春梅

-09-01
实验学时阐明

《编译技术》课总学时为32/8学时，其中实验学时为8学时，学时分派为：前三个实验是必做实验：其中DFA模仿程序2学时、DFA化简2学时、LL(1)文法判断程序4学时。背面3个实验为学生依照自己安排选做实验。

目 录

实验1 DFA模仿程序 1
实验2 DFA化简 2
实验3 LL(1)文法判断程序 4
实验4 基于预测分析表法语法分析程序(1) 5
实验5 基于预测分析表法语法分析程序(2) 6
实验6 中间代码生成：逆波兰式产生与计算 8

实验1 词法程序设计——DFA模仿程序
一、实验目
通过实验教学，加深学生对所学关于编译理论知识理解，增强学生对所学知识综合应用能力，并通过实践达到对所学知识进行验证。通过对DFA模仿程序实验，使学生掌握词法分析实现技术，及详细实现办法。通过本实验加深对词法分析程序功能及实现办法理解 。
二、实验环境
供Windows系统PC机，可用C++/C#/Java等编程工具编写
三、实验内容
1、定义一种右线性正规文法，示例如(仅供参照)
G[S]：S→aU|bV U→bV|aQ
V→aU|bQ Q→aQ|bQ|e
实验前要考虑清晰用哪种数据构造存储上述文法。
2、构造其有穷拟定自动机，如

3、运用有穷拟定自动机M=(K,Σ,f，S,Z）行为模仿程序算法，来对于任意给定串，若属于该语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”。
K:=S；
c:=getchar;
while c<>eof do
{K:=f(K,c)；
c:=getchar； };
if K is in Z then return (‘yes’)
else return (‘no’)
四、实验方式与规定
1、每位同窗定义语言或文法不同，上机编程实现
2、实验报告格式规定书写要点：概要设计（总体设计思想）；详细设计（程序主流程、自动机存储格式、核心函数流程图）；成果分析（输入与输出成果、存在问题及有待改进善地方、实验心得）。

实验2 DFA（拟定有穷自动机）化简
一、 实验目与规定
通过设计、编写和调试将拟定有穷自动机状态数变为至少C程序，使得学生掌握化简为有穷自动机过程中有关概念和办法。DFA体现形式可觉得表格或图形。
二、 问题描述
每一种正规集都可以由一种状态数至少DFA所辨认，这个DFA是唯一（不考虑同构状况）。任意给定一种DFA，依照如下算法设计一种C程序，将该DFA 化简为与之等价最简DFA。
三、 算法
（1）构造具备两个组状态集合初始划分I：接受状态组 F 和非接受状态组 Non-F。
（2）对I采用下面所述过程来构造新划分I-new.
For I 中每个组G do
Begin
当且仅当对任意输入符号a,状态s和读入a后转换到I同一组中； /*最坏状况下，一种状态就也许成为一种组*/
用所有新形成小组集代替I-new中G;
end
（3）如果I-new=I，令I-final=I,再执行第（4）步，否则令I=I=new,重复环节（2）。
（4）在划分I-final每个状态组中选一种状态作为该组代表。这些代表构成了化简后DFA　M＇状态。令s是一种代表状态，并且假设：在DFA M中，输入为a时有从s到t转换。令t所在组代表是r,那么在M’中有一种从s到r转换，标记为a。令包括s0状态组代表是M’开始状态，并令M’接受状态是那些属于F状态所在组代表。注意,I-final每个组或者仅含F中状态，或者不含F中状态。
（5）如果M’具有死状态（即一种对所有输入符号均有刀自身转换非接受状态d）,则从M’中去掉它；删除从开始状态不可到达状态；取消从任何其她状态到死状态转换。
四、基本规定
1、输入一种DFA M,输出一种与之等价最小化DFA M’，上机编程实现。
2、实验报告格式规定书写要点：
概要设计（总体设计思想）；
详细设计：程序主流程、DFA存储格式（即数据构造）、核心函数流程图；
成果分析（输入与输出成果、存在问题及有待改进善地方、实验心得）
五、测试数据
输入下图DFA M,得到其最简DFA M’。

DFA M
六、 实现提示：
（1） 可将输入DFA存储在外部文本文献中，也可以直接从NFA转换得到。对DFA最小化分两某些进行化简，即分别对状态（结点）和途径（弧）进行最小化，最后输出最小化DFA。
（2） 实现数据构造：
用链表实现DFA构造：由结点链表和转换弧链表构成：
struct node //结点定义
{int pos;//结点在哪个组中
int num；//结点序号
int accept；//结点与否为接受状态
struct node *next；
}NODE;
struct arc//弧定义
{int start； //开始顶点位置
char input； //弧上所接受输入字符
int end； //结束顶点位置
struct arc *next;
}ARC;
Struct groups //分组后各结点所在组位置
{int n；//属于哪个组
int i;//在组中位置
}GROUPs;
（3） 实现办法：
依照accept值为0还是1进行初次划分I，将accept为0所有结点构建成一种链表，将accept为1所有结点构建一种链表。然后执行最小化函数，对每一种输入字符遍历以上个链表，对每个结点.num=弧.start状况，查看该弧.end组号与否相等，相等则不划分；若不相等，则需进一步划分，构建新链表等。
划分完毕后选头结点为代表，删除结点链表上其她结点，并将弧线链表上需被删弧.start或弧.end该为头结点。
实验3 LL(1)文法判断程序
一、实验目
一方面能让顾客输入一种文法，然后让计算机自动判断与否是一种LL(1)文法，通过实验教学，加深学生对所学关于编译理论知识理解，增强学生对所学知识综合应用能力，并通过实践达到对所学知识进行验证。。
二、实验环境
供Windows系统PC机，可用C++/C#/Java等编程工具编写
三、实验环节
1、让计算机接受一种文法，示例如(仅供参照)：
G[S] 为:
S→AB S→bC
A→ε A→b
B→ε B→aD
C→AD C→b
D→aS D→c
1. 2、编程实现对上述文法与否是LL(1)文法判断，是则给出必定回答，否则给出否定回答。
2. 鉴别与否是LL(1)文法
以链表或数组等数据构造保存文法.
求出能推出ε非终结符.
计算FIRST集,FOLLOW集和SELECT集
SELECT(A→α)∩SELECT(A→β)=Φ?

输出必定回答
是
输出否定回答
否
实验流程图如下：

实验4-5基于预测分析表法语法分析程序
一、实验目
通过对基于LL(1)文法预测分析表法实现DFA模仿程序实验，使学生掌握拟定自上而下语法分析实现技术，及详细实现办法。通过本实验加深对语词法分析程序功能及实现办法理解。
二、实验环境
供Windows系统PC机，可用C++/C#/Java等编程工具编写
三、实验环节
1、定义一种LL(1)文法，示例如(仅供参照)
G[E]：E →TE' E'→+TE'|ε
T →FT' T' → *FT'|ε
F → i|(E)
2、构造其预测分析表，如

3、LL(1)文法预测分析表模型示意图

4、预测分析控制程序算法流程

5、运营成果，示例如下

四、实验方式与规定
1、每位同窗定义文法不同，上机编程实现;
2、实验报告格式规定书写要点：
概要设计（总体设计思想）；
详细设计（程序主流程、自动机存储格式、核心函数流程图）；
成果分析（输入与输出成果、存在问题及有待改进善地方、实验心得）.

实验6 逆波兰式产生及计算
一、实验目：
将非后缀式用来表达算术表达式转换为用逆波兰式来表达算术表达式，并计算用逆波兰式来表达算术表达式值。
二、实验内容: 
1.定义某些：定义常量、变量、数据构造。
2.初始化：设立算符优先分析表、初始化变量空间（涉及堆栈、构造体、数组、暂时变量等）；
3.控制某些：从键盘输入一种表达式符号串；
4.运用算符优先分析算法进行表达式解决：依照算符优先分析表对表达式符号串进行堆栈（或其她）操作，输出分析成果，如果遇到错误则显示错误信息。
5.对生成逆波兰式进行计算。
三、实验预习提示：
1、逆波兰式定义
将运算对象写在前面，而把运算符号写在背面。用这种表达法表达表达式也称做后缀式。逆波兰式特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以较好表达简朴算术表达式，其长处在于易于计算机解决表达式。
2、产生逆波兰式前提
中缀算术表达式
3、逆波兰式生成实验设计思想及算法 　
(1)一方面构造一种运算符栈，此运算符在栈内遵循越往栈顶优先级越高原则。
(2)读入一种用中缀表达简朴算术表达式，为以便起见,设该简朴算术表达式右端多加上了优先级最低特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一种字符开始判断，如果该字符是数字，则分析到该数字串结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：将该字符与运算符栈顶运算符优先关系相比较。如果，该字符优先关系高于此运算符栈顶运算符，则将该运算符入栈。倘若不是话，则将此运算符栈顶运算符从栈中弹出，将该字符入栈。
(5)重复上述操作(1)-(2)直至扫描完整个简朴算术表达式，拟定所有字符都得到对的解决，咱们便可以将中缀式表达简朴算术表达式转化为逆波兰表达简朴算术表达式。
四、逆波兰式计算实验设计思想及算法 　
(1)构造一种栈，存储运算对象。
(2)读入一种用逆波兰式表达简朴算术表达式。
(3)自左至右扫描该简朴算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部两个运算对象进行该运算，将运算成果入栈，并且将执行该运算两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部元素实行该运算，将该栈顶部元素弹出，将运算成果入栈。
(4)重复上述操作直至扫描完整个简朴算术表达式逆波兰式，拟定所有字符都得到对的解决，咱们便可以求出该简朴算术表达式值。
五、实验环节：
（一）准备： 
1.阅读课本关于章节，
2.考虑好设计方案；
3.设计出模块构造、测试数据，初步编制好程序。
（二）上课上机： 
将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。
（三）程序规定：
程序输入/输出示例： 
输出格式如下：
(1)逆波兰式生成及计算程序，编制人：姓名，学号，班级
(2)输入一以#结束中缀表达式(涉及+—*/（）数字#)：在此位置输入符号串如(28+68)*2# 
(3)逆波兰式为：28&68+2* 
(4)逆波兰式28&68+2*计算成果为192
备注：(1)在生成逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔；
(2)在此位置输入符号串为顾客自行输入符号串。 
注意：1.表达式中容许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 
2.如果遇到错误表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力同窗，测试用表达式事先放在文本文献中，一行存储一种表达式，同步以分号分割。同步将预期输出成果写在另一种文本文献中，以便和输出进行对照。