文档介绍：词法分析算法
第1页，此课件共25页哦
1、从正规式到NFA
实验目的：实现由正规式构造NFA的算法，
加深对该算法的理解。
实验要求：
输入：任意一个正规式r；
输出：接受L(r)的
begin
标记T；
For 每个输入符号a do
begin
U:= ε_closure(s0)(move(T,a));
If U没在Dstates中 then
将U作为一个未标记的状态添加到Dstates中；
end
end
第12页，此课件共25页哦
实现思路
1、构造数据结构：
图的数据结构；
转换关系的数据结构。
2、求图的开始节点的ε-closure ，作为子集链表的头节点。然后对其ε-closure 中的每个节点，根据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。
第13页，此课件共25页哦
实现方法
构造主要的数据结构：
struct diagram {
int snum; //节点编号
move *transfer; //转换关系
diagram *next;
};//图的数据结构
第14页，此课件共25页哦
实现方法
构造主要的数据结构：
struct subset {
int snum; //节点编号，
char closure[MAX]; //该节点中包含原来
的哪些节点，也就是其ε_closure
move *transfer; //来源关系
subset *next;
};//子集的数据结构
第15页，此课件共25页哦
实现方法
构造主要的数据结构：
struct move{
int point; //来自或转向哪一个节点
char input; //转向条件
move *next;
};//存储来源关系
第16页，此课件共25页哦
程序流程
（1）读取文件中的数据，组成图的初始链表。
（2）将图的开始节点加入到其子集节点的closure数组中，调用求ε-closure的子函数求出图开始节点的ε-closure 存储在该子集节点的closure数组中。将该子集作为作为子集链表的头节点。
（3）遍历子集链表，对子集节点中closure数组中的每个元素，对其转换输入中的非ε元素，构造一个新的子集节点，将该输入之后所到达的节点插入新构造的子集节点的closure数组中，调用求ε-closure的子函数求该子集节点的ε-closure ，存储在该子集节点的closure数组中。同时构造构造转换关系节点，将该输入字母和来源节点编号填入该转换节点中，将该转换节点挂在刚才新构造的子集节点上。
（4）将新构造的子集节点插入子集链表中。
第17页，此课件共25页哦
关键算法实现思路
求ε-closure：
遍历closure数组中的每个元素，如果该元素节点的转换输入（图数据结构）中存在ε，则把输入ε之后能到达的那个节点插入closure数组（尾插法）。
第18页，此课件共25页哦
注意事项
（1）所有的插入操作，在插入的时候都需要比较即将插入的元素是否已经存在于插入对象中，如果已经存在，则不插入。
（2）对于子集的插入，采用尾插法，插入的时候给新的子集编号。比较两个子集是否相同，是比较子集数据结构中的closure数组中的元素是否相同。如个有相同的子集，则只把转换关系节点加入到已有的子集节点的转换关系链表中，不插入该子集节点。
（3）由于新的子集是在插入时才获得编号，所以，子集节点中转换关系链表和图中的转换链表有含义有所差别。图中的是目的节点，输入字符；子集中是来源节点，输入字符。
（4）为了便于比较closure数组，在每次求完ε-closure之后，有必要对closure数组中的元素进行排序。
第19页，此课件共25页哦
3、DFA的最小化
实验目的：
掌握最小化DFA的算法。
实验要求：
输入：任意一个DFA D；
输出：一个接受同样语言的DFA D`，且状态数最少。
注：DFA的表现形式不限。
第20页，此课件共25页哦
算法回顾
所有状态分成两个子集－终态集和非终态集；
运用判定状态可区别原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子集，若发现不等价，继续划分；
当无法运用可区别原则时，则看Ia是否全包含在现行划分中，是则不可区分，不是则继续划分
从每个子集中选出