编译原理 第二章词法分析精选文档.ppt

《编译原理 第二章词法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《编译原理 第二章词法分析精选文档.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理 第二章词法分析第二章词法分析本讲稿第一页，共四十四页这不是一个这不是一个DFA。如果不使用系统化的方法将所有。如果不使用系统化的方法将所有的记号都合并为一个巨大的的记号都合并为一个巨大的DFA，将非常复杂。，将非常复杂。13letterletter,digit2other5digitdigit4other76=910 S的子集的子集4.S0 S 初始状态初始状态 5.A S 接受状态集合接受状态集合本讲稿第四页，共四十四页NFA 类似于类似于 DFA，除了，除了扩展扩展 包括包括 NFA 可以包含可以包含-转换转换无需考虑输入串就无需考虑输入串就有可能发生的转换有可能发生的转

2、换12扩展扩展T的定义的定义每一个字符都可以导致多个状态。因此每一个字符都可以导致多个状态。因此T的值是状的值是状态的一个集合而不是单独的状态态的一个集合而不是单独的状态本讲稿第五页，共四十四页例例 NFA M=NFA M=（SS，P P，Z,0Z,0，1,f,S,Z1,f,S,Z）其中其中 f f（S S，0 0）=P =P f f（S S，1 1）=S=S，ZZ f f（Z Z，0 0）=P=P f f（Z Z，1 1）=P=P f f（P P，1 1）=Z=Z矩阵表示矩阵表示:01SPS,ZPZZPP001状态图表示状态图表示:SPZ00,1111Z本讲稿第六页，共四十四页L(M):由自

3、动机由自动机 M 所接受（识别）的语所接受（识别）的语言言L(M)：is the set of strings of character字符字符c1c2cn，每一个，每一个ci 都都属于属于，且存在关系：且存在关系：s1 在在T(S0,c1)中中,s2在在T(S1,c2)中中,Sn 在在T(Sn-1,cn)中，中，s0 是初始状态，是初始状态，Sn 是是A的元素的元素c1c2cn 中的任一中的任一 ci 都可能是都可能是真正被接受的串是删除了真正被接受的串是删除了的串的串 c1c2cn本讲稿第七页，共四十四页非确定性非确定性接受特定串的转换序列并不由状态和下接受特定串的转换序列并不由状态和下一

4、个输入字符在每一步确定下来一个输入字符在每一步确定下来本讲稿第八页，共四十四页例如例如1234aab下面两个转换序列都可接受串下面两个转换序列都可接受串“abb”:12424abb134242ab4b本讲稿第九页，共四十四页2.3.3 用代码实现有穷自动机用代码实现有穷自动机构建扫描程序（词法分析程序）的过程构建扫描程序（词法分析程序）的过程:正则表达式正则表达式DFA扫描程序扫描程序正则表达式表示一种模式，用来描述记号正则表达式表示一种模式，用来描述记号DFAs 表示按照正则表达式描述的模式接受符号串表示按照正则表达式描述的模式接受符号串的算法的算法本讲稿第十页，共四十四页从正则表达式到从正

5、则表达式到DFA（2.4节节)有穷自动机构造词法分析程序有穷自动机构造词法分析程序本讲稿第十一页，共四十四页1 用代码实现用代码实现 DFA用代码实现用代码实现DFA的一般算法的一般算法用一个变量保持当前的状态用一个变量保持当前的状态将转换写成一个双层嵌套的将转换写成一个双层嵌套的case语句而语句而不是一个循环不是一个循环第一个第一个case语句测试当前的状态语句测试当前的状态嵌套着的第嵌套着的第2层测试输入字符及所给的状层测试输入字符及所给的状态态本讲稿第十二页，共四十四页state:=1;startwhile state=1 or 2 docase state of1:case inpu

6、t character of letter:advance the input;state:=2;else state:=error or other;end case例如例如:接受标识符的接受标识符的DFA13letterletterdigit2other本讲稿第十三页，共四十四页2:case input character of letter,digit:advance the input;state:=2;else state:=3;end case;end case;end while;if state=3 then accept else error;13letterletterdi

7、git2other本讲稿第十四页，共四十四页2 用代码实现用代码实现DFA的状态转换表的状态转换表使用转换表，可以用代码实现任一使用转换表，可以用代码实现任一DFA本讲稿第十五页，共四十四页代码图解中用到的变量代码图解中用到的变量转换被保存在一个转换数组转换被保存在一个转换数组“T”中，中，T由由状态和输入字符索引；状态和输入字符索引；先行输入的转换是由布尔数组先行输入的转换是由布尔数组“Advance”给出给出,它们也由状态和输入字符索引；它们也由状态和输入字符索引；由布尔数组由布尔数组“Accept”给出的接受状态由给出的接受状态由状态索引状态索引本讲稿第十六页，共四十四页代码图解代码图解

8、 state:=1;ch:=next input character;while not Acceptstate and not error(state)donewstate:=Tstate,ch;if Advancestate,ch then ch:=next input char;state:=newstate;end while;if Acceptstate then accept;本讲稿第十七页，共四十四页表驱动的优点表驱动的优点代码的长度缩短了代码的长度缩短了相同的代码可以解决许多不同的问题相同的代码可以解决许多不同的问题代码较易改变（维护）代码较易改变（维护）缺点缺点表格会变得非常

9、大，使得程序要求使用的表格会变得非常大，使得程序要求使用的空间也变得非常大空间也变得非常大本讲稿第十八页，共四十四页3 代码的动作代码的动作进行转换时发生的典型动作是：将字符进行转换时发生的典型动作是：将字符从输入串中移到属于单个记号累积字符从输入串中移到属于单个记号累积字符的字符串中的字符串中在达到某个接受状态时的典型动作是：在达到某个接受状态时的典型动作是：将刚被识别的记号及相关属性返回将刚被识别的记号及相关属性返回遇到出错状态的典型动作是：在输入中遇到出错状态的典型动作是：在输入中备份（回溯）或生成错误记号备份（回溯）或生成错误记号本讲稿第十九页，共四十四页2.4 从正则表达式到从正则表

10、达式到 DFAs正则表达式与正则表达式与 DFA的等价性的等价性从正则表达式到从正则表达式到DFA从正则表达式到从正则表达式到 NFA(2.4.1)从从 NFA 到到 DFA(2.4.2)DFA的最小化的最小化(2.4.3)本讲稿第二十页，共四十四页2.4.1 从正则表达式到从正则表达式到 NFA“语法制导语法制导”法法:按正则表达式的语法结构指引构造过程按正则表达式的语法结构指引构造过程 本讲稿第二十一页，共四十四页正则表达正则表达式构造式构造NFANFA的基本语法结构的构的基本语法结构的构造规则造规则2对于正则表达式对于正则表达式 ,构造的构造的NFA为为:3对于正则表达式对于正则表达式a

11、,a ，构造的，构造的NFA为为1对于正则表达式对于正则表达式,构造的构造的NFA为为:yxyx yxa a本讲稿第二十二页，共四十四页复合正则表达式复合正则表达式e的构造规则的构造规则2 然后按下述三种情况进行分解，直至每条弧上标记一个字符然后按下述三种情况进行分解，直至每条弧上标记一个字符1 先构造如下的正则表达式先构造如下的正则表达式“e”的的NFA:e e1 1Xye=e1|e2e e2 2X1e e1 1ye2e=e1e2X1ye1e=e1*yxe e本讲稿第二十三页，共四十四页例如例如:将正则表达式将正则表达式(a|b)*abb 翻译成翻译成NFAX(a|b)*abbYX (a|b

12、)*1a 2bb 3 YX 4 1 b 3 a 2 b a|b YX 4 1 b 3 a 2 b a b Y本讲稿第二十四页，共四十四页2.4.2 从从 NFA 到到 DFA1 转换需解决的问题转换需解决的问题1)删除删除-转换（转换（合并）合并）如果如果 ,则删除则删除S2S1S2ijkmaban（a）i,jmkaabn（b）本讲稿第二十五页，共四十四页2)状态合并（消除在单个字符上的多重转状态合并（消除在单个字符上的多重转换）换）0123aabc（a）01,23abc（b）本讲稿第二十六页，共四十四页2 转换方法转换方法子集法子集法让让DFA 的每个状态对应的每个状态对应NFA 的一个状态

13、的一个状态集合。集合。即即DFA用它的一个状态记录在用它的一个状态记录在NFA读入读入一个输入符号后可能达到的所有状态。一个输入符号后可能达到的所有状态。本讲稿第二十七页，共四十四页3 对状态集合对状态集合I的有关运算的有关运算1)状态集合状态集合 I 的的闭包闭包_closure(I)是状态集是状态集I I中的任何状态中的任何状态S S以及经任意条以及经任意条弧而能到达的状态的集合。弧而能到达的状态的集合。IIS2S2S1S1S3S3_ Close(I)本讲稿第二十八页，共四十四页以下将以下将_closure(I)简写为简写为closure(I)Closure(I)=I Sk|if Sj S

14、k,Sj Closure(I)，Sk Closure(I)状态集合的空闭包状态集合的空闭包_closure 总是包含状总是包含状态集合本身态集合本身本讲稿第二十九页，共四十四页if I=0,the _closure(I)=例如例如:NFA 100124536789ababb74,2,1,0,本讲稿第三十页，共四十四页2)Ia子集子集I 是状态集合是状态集合,a 是字母表的一个字符是字母表的一个字符Move（I，a）=t|s I,and s tIa=_closure(Move(I,a)a本讲稿第三十一页，共四十四页Ib =_closure(例如例如:NFA 100124536789ababbif

15、 I=0,1,2,4,7 thenIa =_closure()3,8=3,8,6,7,1,2,4 5 6,)=5,7,2,1,4本讲稿第三十二页，共四十四页4 由由NFA M 构造构造DFA M 的算法的算法将将M的初始状态的空闭包作为的初始状态的空闭包作为 M的初始状态的初始状态为这个集合，以及此后的每个后续集合为这个集合，以及此后的每个后续集合S，为每个输，为每个输入入a，计算计算Sa子集子集，这将由转换S Sa定义一个新的状态a继续这个过程，直到没有新状态或转换生成继续这个过程，直到没有新状态或转换生成将包含将包含M接受状态的状态标记为接受状态接受状态的状态标记为接受状态本讲稿第三十三页

16、，共四十四页0,1,7,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,48,3,6,7,1,2,4IbIaIT0T1T2T3T4000010124536789ababb10本讲稿第三十四页，共四十四页40b213bbaaababa重新命名重新命名 DFA的状态集合的状态集合,我们

17、得到我们得到0,1,7,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2,48,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,48,3,6,7,1,2,4IbIaIT0T1T2T3T400001本讲稿第三十五页，共四十四页2.4.3 将将DFA中的状态数最小化中的状态数最小化它们都是正则表达式它们都是正则表达式a*的的DFA,但是后者

18、但是后者是最小的是最小的理论理论对于任何给定的对于任何给定的DFA，都有一个含有最，都有一个含有最少量状态的等价的少量状态的等价的DFA,而且这个最小状而且这个最小状态的态的DFA是唯一的是唯一的aaa本讲稿第三十六页，共四十四页等价状态等价状态如果如果 s 和和 t 是两个状态，它们是等价当是两个状态，它们是等价当且仅当且仅当:s 和和 t 都是接受状态或非接受状态。都是接受状态或非接受状态。对于任何一个字符对于任何一个字符 a,s 和和 t必须转换到等必须转换到等价的状态里价的状态里本讲稿第三十七页，共四十四页C和和F同是终态同是终态,C和和F读入读入a都到达都到达C,读入读入b都到达都到

19、达E,所以所以 C和和F等等价价S和和C不等价，因为不等价，因为C是终态，而是终态，而S不是终态不是终态例如例如aCDBAEFSbaaaaabbbbbab本讲稿第三十八页，共四十四页最小化算法最小化算法分割法分割法 把一个把一个DFADFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等的，而同一子集中的任何两个状态都是等价的价的.本讲稿第三十九页，共四十四页首先首先,分割为两个状态集合，一个包含所有分割为两个状态集合，一个包含所有接受状态，一个包含所有非接受状态。接受状态，一个

20、包含所有非接受状态。考虑每个子集中状态针对字母表中每个字符考虑每个子集中状态针对字母表中每个字符 a 的转换，来决定子集中的所有状态是的转换，来决定子集中的所有状态是等价的还是应该分割的。等价的还是应该分割的。如果一个子集中的两个状态如果一个子集中的两个状态s 和和 t 在在 a 上有上有转换且位于不同的集合，则我们称转换且位于不同的集合，则我们称 a 区分了区分了状态状态 s 和和 t 本讲稿第四十页，共四十四页必须根据考虑中状态集合的必须根据考虑中状态集合的 a-转换的位置将它转换的位置将它们分隔开们分隔开继续这个过程直到每个集合仅包含一个元素继续这个过程直到每个集合仅包含一个元素（原始（

21、原始DFA最小）或一直是到再没有集合可最小）或一直是到再没有集合可以分隔了以分隔了本讲稿第四十一页，共四十四页DBASaaabbbba,CDBAEFSbaaaaaabbbbbba1.将状态分为接受状态和非接受状态将状态分为接受状态和非接受状态S,A,B C,D,E,F2 继续分割（寻找子集中不等价状态）继续分割（寻找子集中不等价状态）S,A,B=S,BA=SABC,D,E,F3 让让 D 表示表示 C,D,E,F P=S,A,B,D本讲稿第四十二页，共四十四页考虑非接受的错误状态的错误转换考虑非接受的错误状态的错误转换有两个状态有两个状态 S 和和 T 如果如果 S 有一个到其他状态的有一个到其他状态的 a-转换，而转换，而 T 却根本没有却根本没有 a-转换转换(即即,错误转换）错误转换）,那么那么a 就将就将 S 和和 T区分开了区分开了如果如果 S 和和 T 都没有都没有a-转换，则转换，则a不能将不能将它们区分它们区分本讲稿第四十三页，共四十四页1abbb231)所有的状态都是接受状态所有的状态都是接受状态:1,2,32)b 不能区分所有的状态不能区分所有的状态3)a 将状态将状态 1 和状态和状态 2 与与 3区分开来区分开来:1 2,34)对于任何一个输入对于任何一个输入a或或b都不能区分都不能区分2,31abb2,3本讲稿第四十四页，共四十四页