《词法分析三个核心算法的实现ppt课件.ppt》由会员分享，可在线阅读，更多相关《词法分析三个核心算法的实现ppt课件.ppt（25页珍藏版）》请在三一办公上搜索。
1、词法分析三个核心算法的实现,从正规式到NFA 从NFA到DFA 最小化DFA,1、从正规式到NFA,实验目的：实现由正规式构造NFA的算法， 加深对该算法的理解。实验要求：输入：任意一个正规式r；输出：接受L(r)的NFA N。注：NFA的表现形式不限。,算法回顾,首先构造识别和字母表中一个符号的NFA,构造识别主算符为选择的正规式的NFA,构造识别主算符为连接的正规式的NFA,构造识别主算符为闭包的正规式的NFA,对于加括号的正规式(s)，使用N(s)本身作为它的NFA。,所用数据结构提示,用字符串存储正规式;用结构体数组或链表存放状态转换图 struct NFA int from; int
2、 to; char *varch; 表示经过字符串varch,from到to状态。中间过程可借助栈完成。,算法提示,利用算符优先的思想来处理正规式中所涉及的各种算符（*，|，（，），）所对应的操作。根据各运算符间的优先关系，构造相应的算符优先关系表。如右表。用字符串存储输入的正规式，利用算符优先分析过程，来分析输入的字符串。,程序流程,#入符号栈；输入串+#(将输入串中的连接用代替)；While(输入字符！=#|符号栈顶元素！=#) if(输入字符是小写字母或数字) 构造识别正规式a的NFA； NFA的弧入队列；起始节点入状态栈；读取下一个字符。else 比较符号栈顶元素和输入字符的优先关系（
3、查表） case : 当前输入符号进符号栈；读取下一个字符； case = : 符号栈栈顶元素出栈；读取下一个字符；,程序流程,case : 符号栈栈顶元素出栈； if（符号栈顶元素=|） 状态栈2个栈顶元素出栈，分别为s,t；构造识别正规式s|t 的NFA； NFA的弧入队列；起始节点入状态栈； else if （符号栈顶元素=） 状态栈2个栈顶元素出栈，分别为s,t；构造识别正规式st的NFA； NFA的弧入队列；起始节点入状态栈； else if(输入字符=*) 状态栈1栈顶元素s出栈；构造识别正规式s*的NFA； NFA的弧入队列；起始节点入状态栈；读取下一个字符。 else erro
4、r! 把状态栈顶元素出栈，该元素的弧的起始节点为整个NFA的起始节点，该弧的终止节点为整个NFA的终止节点。,2、从NFA到DFA,实验目的： 掌握子集法，即将NFA转换为与之等价的DFA的算法。实验要求：输入：任意一个NFA N；输出：一个接受同样语言的DFA D。注：DFA的表现形式不限。,子集法回顾,初始时，_closure(s0)是Dstates中唯一的状态且未被记；While Dstates中存在一个未标记的状态T do begin 标记T； For 每个输入符号a do begin U:= _closure(s0)(move(T,a); If U没在Dstates中 then 将U
5、作为一个未标记的状态添加到Dstates中； end end,实现思路,1、构造数据结构： 图的数据结构； 转换关系的数据结构。2、求图的开始节点的-closure ，作为子集链表的头节点。然后对其-closure 中的每个节点，根据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。,实现方法,构造主要的数据结构：struct diagram int snum; /节点编号move *transfer; /转换关系diagram *next;/图的数据结构,实现方法,构造主要的数据结构：struct subset int snum; /节点编号，char closureMAX; /该
6、节点中包含原来 的哪些节点，也就是其_closure move *transfer; /来源关系subset *next;/子集的数据结构,实现方法,构造主要的数据结构：struct moveint point; /来自或转向哪一个节点char input; /转向条件move *next;/存储来源关系,程序流程,（1）读取文件中的数据，组成图的初始链表。（2）将图的开始节点加入到其子集节点的closure数组中，调用求-closure的子函数求出图开始节点的-closure 存储在该子集节点的closure数组中。将该子集作为作为子集链表的头节点。（3）遍历子集链表，对子集节点中closu
7、re数组中的每个元素，对其转换输入中的非元素，构造一个新的子集节点，将该输入之后所到达的节点插入新构造的子集节点的closure数组中，调用求-closure的子函数求该子集节点的-closure ，存储在该子集节点的closure数组中。同时构造构造转换关系节点，将该输入字母和来源节点编号填入该转换节点中，将该转换节点挂在刚才新构造的子集节点上。（4）将新构造的子集节点插入子集链表中。,关键算法实现思路,求-closure：遍历closure数组中的每个元素，如果该元素节点的转换输入（图数据结构）中存在，则把输入之后能到达的那个节点插入closure数组（尾插法）。,注意事项,（1）所有的插
8、入操作，在插入的时候都需要比较即将插入的元素是否已经存在于插入对象中，如果已经存在，则不插入。（2）对于子集的插入，采用尾插法，插入的时候给新的子集编号。比较两个子集是否相同，是比较子集数据结构中的closure数组中的元素是否相同。如个有相同的子集，则只把转换关系节点加入到已有的子集节点的转换关系链表中，不插入该子集节点。（3）由于新的子集是在插入时才获得编号，所以，子集节点中转换关系链表和图中的转换链表有含义有所差别。图中的是目的节点，输入字符；子集中是来源节点，输入字符。（4）为了便于比较closure数组，在每次求完-closure之后，有必要对closure数组中的元素进行排序。,3
9、、DFA的最小化,实验目的： 掌握最小化DFA的算法。实验要求：输入：任意一个DFA D；输出：一个接受同样语言的DFA D，且状态数最少。注：DFA的表现形式不限。,算法回顾,所有状态分成两个子集终态集和非终态集；运用判定状态可区别原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子集，若发现不等价，继续划分；当无法运用可区别原则时，则看Ia是否全包含在现行划分中，是则不可区分，不是则继续划分从每个子集中选出一个状态做代表，即可构成简化的DFA；含有原来初态的子集仍为初态，各终态的子集仍为终态。,主要数据结构,用链表实现DFA的构造，由节点链表和转换弧链表组成： struct
10、node / 节点的定义 int pos; /节点在哪个组中 int num; /节点的序号 int accept; /节点是否为接受状态 struct node *next; NODE;,主要数据结构,struct arc / 弧的定义 int start; /开始的顶点位置 char input; /弧上所接受的输入字符 int end; /结束的顶点位置 struct arc *next; ARC；,主要数据结构,NODE *fenzuMAX; / 划分（组）的定义struct groups/分组后各节点所在组位置 int n; /属于哪个组 int i; /在组中的位置 GROUPS;
11、GROUPS GROUPMAX,程序流程,“尾插法”构建各链表；从文件中读入DFA；进行初次划分debided1()形成0，将accept为0的所有结点构建链表fenzu0，其pos为0，将accept为1的所有结点构建链表fenzuMAX-1，其pos为MAX-1，并形成GROUP0和GROUPMAX-1;执行最小化，对每一输入字符遍历以上各链表，对每个结点.num弧.start,查看该弧.end的GROUP.n是否相等，相等则不划分，若不相等则需划分，构建链表fenzu1、 fenzuMAX-2等 ；划分完成后，每组选取头结点为代表，删除节点链表上的多余结点和等价节点。包含原来开始节点所在的节点仍为开始节点，包含原来终态节点的所有节点均为终态节点。,
