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