词法分析算法教程文件.ppt

《词法分析算法教程文件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、词法分析算法构造识别主算符为选择的正规式的NFAfi开始识别正规式s

2、t的NFAN(s)N(t)构造识别主算符为连接的正规式的NFAiN(s)f开始识别正规式st的NFAN(t)构造识别主算符为闭包的正规式的NFAN(s)f开始识别正规式s*的NFAi对于加括号的正规式(s)，使用N(s)本身作为它的NFA。所用数据结构提示用字符串存储正规式;用结构体数组或链表存放状态转换图structNFA{intfrom;intto;char*varch;}表示经过字符串varch,from到to状态。中间过程可

3、借助栈完成。算法提示利用算符优先的思想来处理正规式中所涉及的各种算符（*，

4、，（，），·）所对应的操作。根据各运算符间的优先关系，构造相应的算符优先关系表。如右表。用字符串存储输入的正规式，利用算符优先分析过程，来分析输入的字符串。·

5、()*#·>><><>

6、<><><>(<<<=>E>>>*>>E>>>#<<

7、

8、符号栈顶元素！=‘#’){if(输入字符是小写字母或数字){构造识别正规式a的NFA；N

9、FA的弧入队列；起始节点入状态栈；读取下一个字符。}else{比较符号栈顶元素和输入字符的优先关系（查表）{case’<’:{当前输入符号进符号栈；读取下一个字符；}case‘=’:{符号栈栈顶元素出栈；读取下一个字符；}程序流程case‘>’:{符号栈栈顶元素出栈；if（符号栈顶元素==‘

10、’）{状态栈2个栈顶元素出栈，分别为s,t；构造识别正规式s

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

12、弧入队列；起始节点入状态栈；}elseif(输入字符==‘*’){状态栈1栈顶元素s出栈；构造识别正规式s*的NFA；NFA的弧入队列；起始节点入状态栈；读取下一个字符。}elseerror!}}}}把状态栈顶元素出栈，该元素的弧的起始节点为整个NFA的起始节点，该弧的终止节点为整个NFA的终止节点。2、从NFA到DFA实验目的：掌握子集法，即将NFA转换为与之等价的DFA的算法。实验要求：输入：任意一个NFAN；输出：一个接受同样语言的DFAD。注：DFA的表现形式不限。子集法回顾初始时，ε_closure(s0)

13、是Dstates中唯一的状态且未被记；WhileDstates中存在一个未标记的状态Tdobegin标记T；For每个输入符号adobeginU:=ε_closure(s0)(move(T,a));IfU没在Dstates中then将U作为一个未标记的状态添加到Dstates中；endend实现思路1、构造数据结构：图的数据结构；转换关系的数据结构。2、求图的开始节点的ε-closure，作为子集链表的头节点。然后对其ε-closure中的每个节点，根据转换关系，求出新的子集，将新求出的子集插入到子集链表的尾部。实现

14、方法构造主要的数据结构：structdiagram{intsnum;//节点编号move*transfer;//转换关系diagram*next;};//图的数据结构实现方法构造主要的数据结构：structsubset{intsnum;//节点编号，charclosure[MAX];//该节点中包含原来的哪些节点，也就是其ε_closuremove*transfer;//来源关系subset*next;};//子集的数据结构实现方法构造主要的数据结构：structmove{intpoint;//来自或转向哪一个节点c

15、harinput;//转向条件move*next;};//存储来源关系程序流程（1）读取文件中的数据，组成图的初始链表。（2）将图的开始节点加入到其子集节点的closure数组中，调用求ε-closure的子函数求出图开始节点的ε-closure存储在该子集节点的closure数组中。将该子集作为作为子集链表的头节点。（3）遍历子集链表，对子集节点中closure数组中的每个元素，对其转换输入中的非ε元素，构造一个新的子集节点，将该输入之后所到达的节点插入新构造的子集节点的closure数组中，调用求ε-closur

16、e的子函数求该子集节点的ε-closure，存储在该子集节点的closure数组中。同时构造构造转换关系节点，将该输入字母和来源节点编号填入该转换节点中，将该转换节点挂在刚才新构造的子集节点上。（4）将新构造的子集节点插入子集链表中。关键算法实现思路求ε-closure：遍历closure数组中的每个元素，如果该元素节点的转换输入（图数据结构）