词法分析算法

1、从正规式到NFA试验目的：实现由正规式构造NFA的算法，加深对该算法的理解。试验要求：输入：随意一个正规式r；输出：接受L(r)的NFAN。注：NFA的表现形式不限。

算法回顾

首先构造识别和字母表中一个符号的NFAi开始识别正规式的NFAafif开始识别正规式a的NFA构造识别主算符为选择的正规式的NFAfi开始识别正规式s|t的NFAN(s)N(t)构造识别主算符为连接的正规式的NFA

iN(s)f开始识别正规式st的NFAN(t)构造识别主算符为闭包的正规式的NFA

N(s)f开始识别正规式s*的NFAi对于加括号的正规式(s)，运用N(s)本身作为它的NFA。所用数据结构提示用字符串存储正规式;用结构体数组或链表存放状态转换图

structNFA{intfrom;intto;char*varch;}表示经过字符串varch,from到to状态。中间过程可借助栈完成。

算法提示利用算符优先的思想来处理正规式中所涉及的各种算符（*，|，（，），·）所对应的操作。依据各运算符间的优先关系，构造相应的算符优先关系表。如右表。用字符串存储输入的正规式，利用算符优先分析过程，来分析输入的字符串。程序流程‘#’入符号栈；输入串+‘#’(将输入串中的连接用‘·’代替)；While(输入字符！=‘#’||符号栈顶元素！=‘#’){ if(输入字符是小写字母或数字) {构造识别正规式a的NFA；NFA的弧入队列；起始节点入状态栈；读取下一个字符。} else{比较符号栈顶元素和输入字符的优先关系（查表）

{case’<’:{当前输入符号进符号栈；读取下一个字符；}case‘=’:{符号栈栈顶元素出栈；读取下一个字符；}程序流程case‘>’:{符号栈栈顶元素出栈；

if（符号栈顶元素==‘|’）

{状态栈2个栈顶元素出栈，分别为s,t；构造识别正规式s|t的NFA；NFA的弧入队列；起始节点入状态栈；}elseif（符号栈顶元素==‘·’）

{状态栈2个栈顶元素出栈，分别为s,t；构造识别正规式s·t的NFA；NFA的弧入队列；起始节点入状态栈；}elseif(输入字符==‘*’){状态栈1栈顶元素s出栈；构造识别正规式s*的NFA；NFA的弧入队列；起始节点入状态栈；读取下一个字符。}elseerror!}}}}把状态栈顶元素出栈，该元素的弧的起始节点为整个NFA的起始节点，该弧的终止节点为整个NFA的终止节点。2、从NFA到DFA试验目的：驾驭子集法，即将NFA转换为与之等价的DFA的算法。试验要求：输入：随意一个NFAN；输出：一个接受同样语言的DFAD。注：DFA的表现形式不限。子集法回顾初始时，ε_closure(s0)是Dstates中唯一的状态且未被记；WhileDstates中存在一个未标记的状态Tdobegin

标记T；

For每个输入符号adobeginU:=ε_closure(s0)(move(T,a));IfU没在Dstates中then

将U作为一个未标记的状态添加到Dstates中；

endend实现思路1、构造数据结构：图的数据结构；转换关系的数据结构。2、求图的起先节点的ε-closure，作为子集链表的头节点。然后对其ε-closure中的每个节点，依据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。实现方法构造主要的数据结构：structdiagram{ intsnum;//节点编号

move*transfer;//转换关系

diagram*next;};//图的数据结构实现方法构造主要的数据结构：structsubset{ intsnum;//节点编号，

charclosure[MAX];//该节点中包含原来的哪些节点，也就是其ε_closure move*transfer;//来源关系

subset*next;};//子集的数据结构实现方法构造主要的数据结构：structmove{ intpoint;//来自或转向哪一个节点

charinput;//转向条件

move*next;};//存储来源关系程序流程（1）读取文件中的数据，组成图的初始链表。（2）将图的起先节点加入到其子集节点的closure数组中，调用求ε-closure的子函数求出图起先节点的ε-closure存储在该子集节点的closure数组中。将该子集作为作为子集链表的头节点。（3）遍历子集链表，对子集节点中closure数组中的每个元素，对其转换输入中的非ε元素，构造一个新的子集节点，将该输入之后所到达的节点插入新构造的子集节点的closure数组中，调用求ε-closure的子函数求该子集节点的ε-closure，存储在该子集节点的closure数组中。同时构造构造转换关系节点，将该输入字母和来源节点编号填入该转换节点中，将该转换节点挂在刚才新构造的子集节点上。（4）将新构造的子集节点插入子集链表中。关键算法实现思路求ε-closure：遍历closure数组中的每个元素，假如该元素节点的转换输入（图数据结构）中存在ε，则把输入ε之后能到达的那个节点插入closure数组（尾插法）。留意事项（1）全部的插入操作，在插入的时候都须要比较即将插入的元素是否已经存在于插入对象中，假如已经存在，则不插入。（2）对于子集的插入，接受尾插法，插入的时候给新的子集编号。比较两个子集是否相同，是比较子集数据结构中的closure数组中的元素是否相同。如个有相同的子集，则只把转换关系节点加入到已有的子集节点的转换关系链表中，不插入该子集节点。（3）由于新的子集是在插入时才获得编号，所以，子集节点中转换关系链表和图中的转换链表有含义有所差别。图中的是目的节点，输入字符；子集中是来源节点，输入字符。（4）为了便于比较closure数组，在每次求完ε-closure之后，有必要对closure数组中的元素进行排序。3、DFA的最小化试验目的：驾驭最小化DFA的算法。试验要求：输入：随意一个DFAD；输出：一个接受同样语言的DFAD`，且状态数最少。注：DFA的表现形式不限。算法回顾全部状态分成两个子集－终态集和非终态集；运用判定状态可区分原则分别对两个子集的状态进行分析和划分，把相互等价的状态构成一个子集，若发觉不等价，接着划分；当无法运用可区分原则时，则看Ia是否全包含在现行划分中，是则不行区分，不是则接着划分从每个子集中选出一个状态做代表，即可构成简化的DFA；含有原来初态的子集仍为初态，各终态的子集仍为终态。主要数据结构用链表实现DFA的构造，由节点链表和转换弧链表组成：

structnode//节点的定义

{ intpos;//节点在哪个组中

intnum;//节点的序号

intaccept;//节点是否为接受状态

structnode*next; }NODE; 主要数据结构structarc//弧的定义{intstart;//起先的顶点位置charinput; //弧上所接受的输入字符intend;//结束的顶点位置structarc*next;}ARC；主要数据结构NODE*fenzu[MAX];//划分（组）的定义structgroups//分组后各节点所在组位置

{intn;//属于哪个组

inti;//在组中的位置

}GROUPS;GROUPSGROUP[MAX]程序流程“尾插法”构建各链表；从文件中读入DFA；进行初次划分debided1()形成∏0，将accept为0的全部结点构建链表fenzu[0]，其pos为0，将accept为1的全部结点构建链表fenzu[MAX