编译原理与技术.ppt

《编译原理与技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理与技术词法分析(2)9/16/20211《编译原理与技术》讲义有限自动机有限自动机（FiniteAutomata－FA）是种更一般化的状态转换图。分为NFA和DFA。词法分析器自动生成：正规式NFADFA词法程序非确定有限自动机确定的有限自动机9/16/20212《编译原理与技术》讲义非确定有限自动机－NFANFAMn是一个五元组Mn=(,S,S0,F,)，其中：－有限字母表（输入符号集）S－有限状态集S0－非空初态集合，S0SF－终态集合，FS－状态转换函数，Sx*2S9/16/20213《编译原理与技术》讲义

2、确定的有限自动机－DFADFAMd是一个五元组Md=(,S,S0,F,)，其中:,S,S0,F同NFA中的定义，而定义如下：：SxS，为一单值映射函数。9/16/20214《编译原理与技术》讲义有限自动机的表示1）状态转换图开始状态一般状态终态s(s,a)=ttas(s,)=tt9/16/20215《编译原理与技术》讲义有限自动机的表示2）状态转换矩阵（表）*状态(集)ab…Si{Sj}…Sj……(Si,a)={Sj}9/16/20216《编译原理与技术》讲义有限自动机的表示e.g.7NFAMn=(,S,S0

3、,F,)，其中：={0,1},S={S0,S1,S2,S3,S4}，F={S2,S4}(S0,0)={S0,S3}(S0,1)={S0,S1}(S1,0)=∅(S1,1)={S2}(S2,0)={S2}(S2,1)={S2}(S3,0)={S4}(S3,1)=∅(S4,0)={S4}(S4,1)={S4}9/16/20217《编译原理与技术》讲义有限自动机的表示e.g.7中NFA的状态转换图如下：S0S3S10,1000,1110,1S2S49/16/20218《编译原理与技术》讲义有限自动机的表示e.g.7中N

4、FA的状态转换矩阵（表）如下：*状态(集)01S0{S0,S3}{S0,S1}S1∅{S2}S2{S2}{S2}S3{S4}∅S4{S4}{S4}9/16/20219《编译原理与技术》讲义有限自动机识别的语言e.g.8下面FA识别（接受）的串是什么？S0S1S201FA识别（接受）串∈*,如果存在一个从FA的初态到某个终态的（状态）转换路径，该路径上所有标记的字符依次连接为。FAM所识别的语言L(M)L(M)={

5、M识别∈*}9/16/202110《编译原理与技术》讲义有限自动机识别的语言e.g.9下面DFAM识别的语言L

6、(M)是什么？S2S101S0S3111000S109/16/202111《编译原理与技术》讲义有限自动机识别的语言e.g.9L(M)={含偶数个0和偶数个1的0,1串}S2S101S0S3111000S2S1S0S3偶数个“0”与偶数个“1”的0,1串偶数个“0”与奇数个“1”的0,1串奇数个“0”与偶数个“1”的0,1串奇数个“0”与奇数个“1”的0,1串9/16/202112《编译原理与技术》讲义有限自动机识别的语言e.g.10下面DFAM识别的语言L(M)是什么？S2S1S00101019/16/202113《编译原理与技术》讲

7、义有限自动机识别的语言e.g.10L(M)={能被“3”整除的二进制数(串)}S2S1S0010101S2S1S0能被3整除被3整除…余1被3整除…余29/16/202114《编译原理与技术》讲义有限自动机识别的语言e.g.10L(M)={能被“3”整除的二进制数(串)}二进制串10010,即十进制18的识别过程：S2S1S001010输入串100109/16/202115《编译原理与技术》讲义比较DFA和NFA（1）DFANFA：SxS：Sx2S没有转换有转换对∈*，DFA的“识别”路径唯一且完全由确定对∈*

8、的“识别”路径可能存在多条不同的路径对于正规式R，均有DFAMd和NFAMn，使得L(Md)=L(Mn)=L(R)，即两者识别正规语言能力相同（等价）9/16/202116《编译原理与技术》讲义比较DFA和NFA（2）DFANFA容易实现－当输入串结束时（或不存在相应状态转换）时，若当前状态为终态即为接受“已读入”的串，否则拒绝。由于面临同样输入符号存在多重状态转换或存在转换的选择，实现较为复杂。一般地，NFA接受串如果它在读完串后“能够”到达某终态。识别相同正规集的DFA和NFA：DFA的规模（在状态数和状态转换上）一般比相应的

9、NFA复杂（可以达到指数级）9/16/202117《编译原理与技术》讲义比较DFA和NFA（3）e.g.11识别正规式（0

10、1）*01的DFA和NFAS2S1S00011NFA:S2S1S0101100DF