编译原理第三章(4-3)详解.ppt

北京交通大学　于双元1第三章词法分析§3.1设计扫描器时应考虑的问题§3.2正则文法和状态转换图§3.3有限自动机§3.4正则表达式和正规集§3.5词法分析程序的实现北京交通大学　于双元2§3.3.1确定的有限自动机（DFA）§3.3.2非确定的有限自动机(NFAM′)§3.3.3DFAM与NFAM′的等价性§3.3有限自动机北京交通大学　于双元3§3.3有限自动机(FA)§3.3.1确定的有限自动机（DFA）一个DFA有以下五个元素组成:DFAM=（K，∑，f，S0，Z）其中K：状态的集合（有限个状态）∑：允许输入的字符的集合Vtf：状态转换函数，单值函数K×∑→KS0：初始状态S0∈KZ：终止状态集KZf(Si,a)=Sj北京交通大学　于双元4讨论：(1)①确定性f是单值函数从某一状态读一字符的下一状态唯一确定②有限的K集合元素个数有限(2)f定义的推广f单值函数K×∑→KK×Σ*→KΣ*=∑+∪{ε}记为ｆ^①ｆ^(S,ε)=S②ｆ^(S,aω)=ｆ^(f(S,a),ω)a∈∑,ω∈Σ*f(S,a)=Sk=ｆ^(Sk,ω)=…=StSt∈Kｆ^:K×Σ*→K单值映射北京交通大学　于双元5③ｆ^是在Σ*上定义,f是在∑上定义,ｆ^包含f,将ｆ^和f合并为一个f,记为f(推广后)(3)有限自动机的功能:识别句子L(M)={}x|f(S0,x)∈Z,x∈Σ*特别:f(So,ε)=So且So∈Z称ε可为DFAM识别S0北京交通大学　于双元6(4)DFA可非形式地表示成状态图和状态矩阵例:DFAM=({S,A,B,C},{0,1},δ,S,{S})δ(S,0)=Bδ(S,1)=Aδ(A,0)=Cδ(A,1)=Sδ(B,0)=Sδ(B,1)=Cδ(C,0)=Aδ(C,1)=B状态输入0输入1SBAACSBSCCAB101011δ(S,101011)=δ(δ(S,1),01011)=δ(A,01011)=δ(C,1011)=δ(B,011)=δ(S,11)=δ(A,1)=S计算机易存状态转换矩阵北京交通大学　于双元7(5)正则文法G一定DFAM反之L(G)L(M)等价北京交通大学　于双元8§3.3.2非确定的有限自动机(NFAM′)一个NFAM′有以下五个元素组成,NFAM′=(K′,Σ,f′,S0′,Z′)其中:K′:状态的集合(有限状态)Σ:允许输入的字符集合Vtf′:状态转换函数,多值函数,K′×Σ→2k’(K的所有子集的集合)f(Si,a)={Sk,St，…}S0:初始状态S0∈K′Z:终止状态集K′另外形式：弧线上有εNFAM′=(K′,Σ∪{ε},f′,S0′,Z′)Z北京交通大学　于双元9讨论:1)①不确定:f′是多值函数,一对多②有限:K′有限2)f′定义推广到Σ*上,K′×Σ*→2k’,记为ｆ^′①ｆ^′(S,ε)={S}②ｆ^′(S，aw）=ｆ^′(f′(S,a),w)设：f′(S,a)={S1,S2,…..,Sk}=ｆ^′({S1,S2,…..,Sk},w)=∪ｆ^′(Si,w)i=1k③将ｆ^′和f′合并为一个f′,记为f′是2k’中的元素满足映射K′×Σ*→2k’北京交通大学　于双元10(3)NFAM′所确定的语言L(M′)={x|f′(S0′,x)∩Z≠Ø,x∈Σ*}(4)NFAM′通常用状态转换图来表示例:NFAM′=({S,A,B,C},{a,b},f′,S,{C})符号串ababb可由此NFAM′所识别.北京交通大学　于双元11§3.3.3DFAM与NFAM′的等价性一、对于∑上NFAM′一定DFAML(M′)L(M)二、方法:确定化1、读ε不动作的NFAM′（弧线上无ε）2、读ε动作的NFAM′（弧线上有ε）最小化等价DFA状态数最少北京交通大学　于双元121、读ε不动作的NFAM′的确定化问题：设有一NFAM′=(K′,∑,f′,S0′,Z′)现构造一∑上的DFAM=(K,∑,f,S0,Z)使L(M′)=L(M)①K由K’的全部子集组成K=2K’特别S0=[S0′]=q0②映射f的定义当且仅当f′({S1,S2,…Si},a)={R1,R2,…,Rj}时,Si、Rj∈K′则f([S1,S2,…Si],a)=[R1,R2,…Rj]qiqjf(qi,a)=qjK′×Σ→2k’{q0,q1,…qi,..qj,…qn}确定性北京交通大学　于双元13③DFAM的终态集Z的定义是:M的某一状态[R1,R2,…Rj]=qi,其中至少含有一个M′的一个终态则[R1,R2,…Rj]∈ZZ={[R1,R2,…,Rj]|[R1,R2,…,Rj]∈K且{R1,R2,…,Rj}∩Z′≠Ø}北京交通大学　于双元14abq0=[s0]q1=[s1]q2=[s2]q3=[s0,s1]q4=[s0,s2]q5=[s1,s2]q6=