程序设计语言程序设计语言编译原理编译原理张张 淑淑 艳艳zhang_shu_yan163.comzhang_shu_yan163.com状态转换图状态转换图计算机实现计算机实现等价等价等价等价温故知新温故知新不确定有不确定有限自动机限自动机确定有限确定有限自动机自动机有限自动机有限自动机最简确定有最简确定有限自动机限自动机子集法子集法子集法子集法正规式正规式等价等价等价等价?手工实现手工实现手工实现手工实现正规文法正规文法?3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.6 确定有限自动机的化简确定有限自动机的化简合并等价的状态合并等价的状态BD开始开始aAabbaa, bCbaEb死状态死状态死状态死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死状态左图无须加死状态，右图加入死状态E E E E。a a0 01 13 32 25 54 46 6a aa ab ba ab ba aa aa ab bb bb bb bb b3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.6 确定有限自动机的化简确定有限自动机的化简可区别的状态和等价的状态可区别的状态和等价的状态1 1 1 1和和和和2 2 2 2是可区别的状态是可区别的状态是可区别的状态是可区别的状态3 3 3 3和和和和6 6 6 6是等价的状态是等价的状态是等价的状态是等价的状态a a0 01 13 32 25 54 46 6a aa ab ba ab ba aa aa ab bb bb bb bb b3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.6 确定有限自动机的化简确定有限自动机的化简最小化的思路：最小化的思路： 将将M的状态集合分成一些不相交的子集，的状态集合分成一些不相交的子集， 使任何不同的两个子集的状态都是可区别的，使任何不同的两个子集的状态都是可区别的， 而同一子集中的任何两个状态都是等价的。而同一子集中的任何两个状态都是等价的。 最后，在每个子集选出一个代表，同时消去其他等价最后，在每个子集选出一个代表，同时消去其他等价状态。状态。3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.6 确定有限自动机的化简确定有限自动机的化简1.1.把把DFADFA状态分割成两个状态状态分割成两个状态S S1 1( (终止状态集终止状态集) )和和S S2 2( (非终止非终止状态集状态集) )。2.2.对每个状态集按下述方法进行分割：对每个状态集按下述方法进行分割： 设第设第i i次分割把集合分割成次分割把集合分割成S=SS=S1 1(i)(i)SS2 2(i)(i)SSk k(i)(i)，检查，检查状态集状态集S Sj j(i)(i)(j=1,2,(j=1,2,k)k)设设S Sj j和和S Sj j” S Sj j(i)(i)，(S(Sj j,a)= S,a)= Sm m ，(S(Sj j”,a)= S,a)= Sn n 若若S Sm m，S Sn n处于同一集合中，则放在同一集；处于同一集合中，则放在同一集； 若若S Sm m，S Sn n不处于同一集合中，则放在两个集。不处于同一集合中，则放在两个集。3.3.重复重复2 2直至不产生新的分割为止直至不产生新的分割为止4.4.合并等价状态：在状态集中选一代表其它删除。如合并等价状态：在状态集中选一代表其它删除。如I=qI=q1 1,q,q2 2, , , q, qk k 不可再分，则可选择不可再分，则可选择q q1 1代表这个子集，凡导入到代表这个子集，凡导入到q q2 2, , , q, qk k的弧都改成导入到的弧都改成导入到q q1 1，若，若I I中含有原来的初态，则中含有原来的初态，则q q1 1是是新的初态，若新的初态，若I I中含有原来的终态，则中含有原来的终态，则q q1 1是新的终态。是新的终态。例：书例：书P51 图图3.8化简：化简：化简：化简：终态集合终态集合终态集合终态集合S S1 13,4,5,63,4,5,6 非终态集合非终态集合非终态集合非终态集合S S2 20,1,20,1,23,4,5,63,4,5,6a a=3,6=3,6 S S1 1 3,4,5,63,4,5,6b b=4,5=4,5 S S1 1 S S1 1不再分割不再分割不再分割不再分割 0,1,2a=1,3 0,1,2a=1,3 S S1 1且且且且 S S2 2 (0,a)=1(0,a)=1， (1,a)=3(1,a)=3， (2,a)=1(2,a)=1 S S2 2分割为：分割为：分割为：分割为：0,2,10,2,1此时状态集合为此时状态集合为此时状态集合为此时状态集合为:0,2,1,:0,2,1,3,4,5,63,4,5,6 0,20,2b b=2,5 =2,5 S S1 1且且且且 0,20,2且且且且 11 (0,b)=2(0,b)=2， (2,b)=5(2,b)=5 0,20,2再分为：再分为：再分为：再分为：0,20,2 最终状态分为：最终状态分为：最终状态分为：最终状态分为：0,1,2,3,4,5,60,1,2,3,4,5,62 20 01 13 3a aa ab ba ab bb ba,ba,b化简后的状态转换图为化简后的状态转换图为化简后的状态转换图为化简后的状态转换图为: : : :a a0 01 13 32 25 54 46 6a aa ab ba ab ba aa aa ab bb bb bb bb b3.3 正规表达式与有限自动机正规表达式与有限自动机状态转换图状态转换图计算机实现计算机实现等价等价等价等价不确定有不确定有限自动机限自动机确定有限确定有限自动机自动机有限自动机有限自动机最简确定有最简确定有限自动机限自动机子集法子集法子集法子集法正规式正规式等价等价等价等价?合并等合并等合并等合并等价状态价状态价状态价状态手工实现手工实现手工实现手工实现正规文法正规文法?3.3 正规表达式与有限自动机正规表达式与有限自动机补：正规文法与正规式的等价性补：正规文法与正规式的等价性关系：对任意一个正规文法，存在定义同关系：对任意一个正规文法，存在定义同一语言的正规式，对于每一个正规式，存一语言的正规式，对于每一个正规式，存在定义同一语言的正规文法。在定义同一语言的正规文法。两者存在等价关系两者存在等价关系文法文法文法文法 G G = (= (V VT T , , V VN N , , S S, , P P) )右线性文法：右线性文法：右线性文法：右线性文法：A A B B或或或或A A ，A, BA, B V VNN , , V VT T* *左线性文法：左线性文法：左线性文法：左线性文法：A A B B 或或或或A A ，A, BA, B V VNN , , V VT T* *3.3 正规表达式与有限自动机正规表达式与有限自动机补：补： 正规文法与正规式的等价性正规文法与正规式的等价性正规式正规式正规式正规式r r正规文法正规文法正规文法正规文法G=(VG=(VN N,V,VT T,S,P), ,S,P), 使得使得使得使得L(r)=L(G)L(r)=L(G)首先有首先有首先有首先有 S Sr r按以下三个规则进行转换，直到全部形如正规文按以下三个规则进行转换，直到全部形如正规文按以下三个规则进行转换，直到全部形如正规文按以下三个规则进行转换，直到全部形如正规文法之产生式为止法之产生式为止法之产生式为止法之产生式为止规则规则规则规则1 1： 若若若若A Axy xy ，则，则，则，则A AxB, BxB, By y规则规则规则规则2 2： 若若若若A Ax|yx|y，则，则，则，则A Ax, Ax, Ay y规则规则规则规则3 3： 若若若若A Ax*yx*y，则，则，则，则A AxA, AxA, Ay y3.3 正规表达式与有限自动机正规表达式与有限自动机补：补： 正规文法与正规式的等价性正规文法与正规式的等价性例：将正规式例：将正规式例：将正规式例：将正规式a(a|d)*a(a|d)*转换为正规文法转换为正规文法转换为正规文法转换为正规文法(1) S(1) S a(a|d)* (S a(a|d)* (Sr) r)(2) S(2) SaA, AaA, A(a|d)* (a|d)* (规则规则规则规则1)1)(3) S(3) SaA, AaA, A(a|d)A, A(a|d)A, A ( (规则规则规则规则3)3)(4) S(4) SaA, AaA, AaA|dA, AaA|dA, A ( (分配率分配率分配率分配率) )(5) S(5) SaA, AaA, AaA, AaA, AdA, AdA, A ( (规则规则规则规则2)2)所以，所以，所以，所以， 最终文法最终文法最终文法最终文法G=(VG=(VT T,V,VN N,S,P),S,P),其中，其中，其中，其中，V VT T=a,d, =a,d, V VN N=S,A, P=S=S,A, P=SaA, AaA, AaA, AaA, AdA, AdA, A 3.3 正规表达式与有限自动机正规表达式与有限自动机补：补： 正规文法与正规式的等价性正规文法与正规式的等价性正规文法正规文法正规文法正规文法G=(VG=(VN N,V,VT T,S, P),S, P)正规式正规式正规式正规式r r, , 使得使得使得使得L(r)=L(G)L(r)=L(G)逆过程逆过程按以下三个规则替换，直至右部不含非终结符按以下三个规则替换，直至右部不含非终结符规则规则规则规则1 1： 若若若若A AxB, BxB, By y，则，则，则，则A Axy xy 规则规则规则规则2 2： 若若若若A Ax, Ax, Ay y，则，则，则，则A Ax|yx|y规则规则规则规则3 3： 若若若若A AxA, AxA, Ay y，则，则，则，则A Ax*yx*y3.3 正规表达式与有限自动机正规表达式与有限自动机补：补： 正规文法与正规式的等价性正规文法与正规式的等价性例例： (1) SaA, (2)Sa, (3)AaA, (4)AdA, (5)Aa, (6)Ad步骤步骤1，由由(1)(2) SaA|a步骤步骤2，由由(3)(4) AaA|dA步骤步骤3，由步骤由步骤2 A(a|d)A步骤步骤4，由由(5)(6) Aa|d步骤步骤5，由步骤由步骤3,4 A(a|d)+步骤步骤6，由步骤由步骤1,5 Sa(a|d)+ |a， 即即Sa(a|d)*所以正规式为所以正规式为 a(a|d)*3.3 正规表达式与有限自动机正规表达式与有限自动机状态转换图状态转换图计算机实现计算机实现等价等价等价等价不确定有不确定有限自动机限自动机确定有限确定有限自动机自动机有限自动机有限自动机最简确定有最简确定有限自动机限自动机子集法子集法子集法子集法正规式正规式等价等价等价等价?合并等合并等合并等合并等价状态价状态价状态价状态手工实现手工实现手工实现手工实现正规文法正规文法?3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性对正规文法对正规文法G和有限自动机和有限自动机M，如果，如果L(G)=L(M)，则称，则称G和和M是等价的。是等价的。右线性文法右线性文法 FAFA 右线性文法右线性文法左线性文法左线性文法 FAFA 左线性文法左线性文法文法文法文法文法 G G = (= (V VT T , , V VN N , , S S, , P P) )右线性文法：右线性文法：右线性文法：右线性文法：A A B B或或或或A A ，A, BA, B V VNN , , V VT T* *左线性文法：左线性文法：左线性文法：左线性文法：A A B B 或或或或A A ，A, BA, B V VNN , , V VT T* *已知已知已知已知 文法文法文法文法G=(VG=(VT T,V,VN N,S, ,S, ) ) FAFA M=(Q, , M=(Q, , ,q ,q0 0,F,F) )1. 1. 另另另另Q Q =V=VN N f (f f (f为新增加的终态为新增加的终态为新增加的终态为新增加的终态) ) , =V, =VT T, q, q0 0=S,F= f =S,F= f 2. 2. 若对于若对于若对于若对于 中每条产生式中每条产生式中每条产生式中每条产生式A A a a ，引入映射，引入映射，引入映射，引入映射 (A, (A, a a)=f)=f 对于对于对于对于 中每条产生式中每条产生式中每条产生式中每条产生式A A a a A Ai i，引入映射，引入映射，引入映射，引入映射 (A, (A, a a)=A)=Ai i 对于对于对于对于 中有中有中有中有A A a aA A1 1| | a a A A2 2| | |a a A Ak k，引入映射，引入映射，引入映射，引入映射 (A, (A, a a)=)=AA1 1, A, A2 2, A, Ak k, , 其中其中其中其中 例：例：例：例：S SaS|aA|aB|aS|aA|aB| A AbA|bbA|b B BcB|cC|ccB|cC|c C Cd dQ=S,A,B,C,fQ=S,A,B,C,f=a,b,c,d=a,b,c,dq q0 0=S=SF=fF=fS SA AB BC CT Ta ad da ab bc ca a c cc cb b3.3 正规表达式与有限自动机正规表达式与有限自动机右线性文法右线性文法 FA已知已知已知已知DFA DFA M=(S, ,M=(S, , ,s ,s0 0,F),F) GGR R=(, S, s=(, S, s0 0, , ), ),1. 1.若若若若s s0 0 F F，令，令，令，令GGR R=(, S, s=(, S, s0 0, , ), ), 的产生式有：的产生式有：的产生式有：的产生式有： 若有若有若有若有 (A, a) = B(A, a) = B ( ( ,A,B S) )，则，则，则，则： (a) (a)若若若若B BF F，则引入产生式，则引入产生式，则引入产生式，则引入产生式A Aa| a|aBaB (b)(b)若若若若B B F F，则引入产生式，则引入产生式，则引入产生式，则引入产生式A AaBaB2. 2.若若若若s s0 0F F，则引入，则引入，则引入，则引入s s0 0 ，且，且，且，且s s0 0 s s0 0| | ，且，且，且，且s s0 0 替代替代替代替代s s0 0为文法起为文法起为文法起为文法起始符。始符。始符。始符。 A A0B|1D|0 0B|1D|0 B B0D|1C0D|1C C C1D|0B|01D|0B|0 D D0D|1D0D|1DA AD DC CB B1 11 10 00,10,10 01 10 0例：例：例：例：3.3 正规表达式与有限自动机正规表达式与有限自动机FA 右线性文法右线性文法 已知文法已知文法G=(VT,VN,S, ) FA M=(Q, ,q,q0 0, ,F)1.另另Q=VN q0 (q0为新增加的初态为新增加的初态)，=VT, F= S 2.若对于若对于中每条规则中每条规则Aa，引入映射，引入映射(q0,a)=A 对于对于中每条规则中每条规则AiAa，引入映射，引入映射(A,a)=Ai 对于对于对于对于 中有中有中有中有A A1 1 A A a a, A, A2 2 A A a a, A, Ak k A A a a ，引入映，引入映，引入映，引入映射射射射 (A, (A, a a)=A)=A1 1, A, A2 2, A, Ak k, , 其中其中其中其中a a q q0 0S Sb bc cB Bc c3.3 正规表达式与有限自动机正规表达式与有限自动机左线性文法左线性文法 FA例：例： S SSa|Aa| Sa|Aa| c cA AAb|Bc|bAb|Bc|bB BBc|cBc|cAc ca aa ac cb b已知已知已知已知FA FA M=(S, ,M=(S, , ,s ,s0 0,F),F) GGL L=(, S, f,=(, S, f, ), ),1. 1.若若若若s s0 0 F F，令，令，令，令GGR R=(, S, s=(, S, s0 0, , ), ), 的产生式有：的产生式有：的产生式有：的产生式有： 若有若有若有若有 (A, a) = B(A, a) = B ( ( ,A,B S) )，则，则，则，则： (a) (a)若若若若A A s0s0，则引入产生式，则引入产生式，则引入产生式，则引入产生式B Ba a (b)(b)若若若若A A s0 s0，则引入产生式，则引入产生式，则引入产生式，则引入产生式B BAaAa2. 2.若若若若s s0 0F F，则引入，则引入，则引入，则引入s s0 0 ，且，且，且，且s s0 0 s s0 0| | ，且，且，且，且s s0 0 替代替代替代替代s s0 0为文法起为文法起为文法起为文法起始符。始符。始符。始符。 f f0|C0 0|C0 C CB1B1 B B0|C00|C0 D D1|D1|D0|C1|B01|D1|D0|C1|B03.3 正规表达式与有限自动机正规表达式与有限自动机FA 左线性文法左线性文法 A Af f0 00,10,1D D1 1B B0 00 01 10 0C C1 10 03.3 正规表达式与有限自动机正规表达式与有限自动机状态转换图状态转换图计算机实现计算机实现等价等价等价等价不确定有不确定有限自动机限自动机确定有限确定有限自动机自动机有限自动机有限自动机最简确定有最简确定有限自动机限自动机子集法子集法子集法子集法正规式正规式等价等价等价等价?合并等合并等合并等合并等价状态价状态价状态价状态手工实现手工实现手工实现手工实现正规文法正规文法?对任何对任何FA M，都存在一个正规式，都存在一个正规式r，使，使L(r)=L(M)。对任何正规式对任何正规式r，都存在一个，都存在一个FA M，使得，使得L(M)=L(r)。正规文法、正规式、确定有限自动机正规文法、正规式、确定有限自动机和和非非确定有限自动机确定有限自动机在接收语言的能力上是等在接收语言的能力上是等价的。价的。3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性FA M 正规式正规式在在M的状态转换图加进两个结点的状态转换图加进两个结点X,Y,从从X引引弧连接至所有弧连接至所有初态结点，从终止状态结点引初态结点，从终止状态结点引弧至弧至Y。按下述方法合并结点：按下述方法合并结点： 代之以代之以 代之以代之以 代之以代之以1 12 23 3R R1 1R R2 21 13 3R R1 1R R2 21 12 2R R1 1R R2 21 12 2R R1 1 | | R R2 21 12 23 3R R1 1R R3 3R R2 21 13 3R R1 1R R2 2* *R R3 33.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性x x5 5 6 62 2Y Yaaaabbbb a|ba|ba|ba|bx xY Y(a|b)*( aa|bb)(a|b)*(a|b)*( aa|bb)(a|b)*(a|b)*( aa|bb)(a|b)*(a|b)*( aa|bb)(a|b)*3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性例：例：例：例：Y Ya aX Xa aa a 5 5 b b1 13 34 4a ab bb b2 2 6 6 b bx x5 5 6 62 2Y Yaa|bbaa|bb a|ba|ba|ba|b正规式正规式 FA 正规式正规式正规式正规式r r r r有有有有0 0 0 0个运算符，则个运算符，则个运算符，则个运算符，则 r=r= 或或或或 r= r= 或或或或 r=ar=aq q0 0 或或或或q0q1q q0 0q1q q0 0a aq13.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性q q0 0q q1 1f f1 1MM1 1q q2 2f f2 2MM2 2 q q0 0MM1 1 q q1 1f f1 1 f f0 0q q1 1MM1 1 f f1 1q q2 2MM2 2f f2 2f f0 02.若若r1，r2为上正规式，相应的为上正规式，相应的NFA为为 M1，M2正规式正规式r=r1 | r2正规式正规式r=r1r2 正规式正规式rr1*3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性01*01*的分解的分解的分解的分解010 0 23451 1 r r7 70 0r r9 9r r3 3r r2 2r r1 11 1* * 0 09 9b ba a8 81 1a ab b 6 62 23 34 45 5 7 7 r r5 5* *r r4 4) )( (r r3 3r r2 2r r1 1a a| |b br r7 7r r6 6a ar r9 9r r8 8b b( (a a| |b b) )* *abab的分解的分解的分解的分解 3.3 正规表达式与有限自动机正规表达式与有限自动机3.3.5 正规式与有限自动机的等价性正规式与有限自动机的等价性3.3 正规表达式与有限自动机正规表达式与有限自动机状态转换图状态转换图计算机实现计算机实现等价等价等价等价不确定有不确定有限自动机限自动机确定有限确定有限自动机自动机有限自动机有限自动机最简确定有最简确定有限自动机限自动机子集法子集法子集法子集法正规式正规式等价等价等价等价?合并等合并等合并等合并等价状态价状态价状态价状态手工实现手工实现手工实现手工实现正规文法正规文法非形式化语言非形式化语言非形式化语言非形式化语言状态列举法状态列举法状态列举法状态列举法用语法结构指导构造过程用语法结构指导构造过程用语法结构指导构造过程用语法结构指导构造过程例：例：识别识别 = = 0,10,1上能被能上能被能5 5整除的二进制数整除的二进制数开始开始开始开始0 01 12 23 34 41 10 00 01 10 01 10 01 10 01 13.3 正规表达式与有限自动机正规表达式与有限自动机补充：从非形式化语言到补充：从非形式化语言到DFA练习：练习：构造构造 DFA，接受接受 0和和1的个数都是偶的个数都是偶数的二进制串。数的二进制串。eg: 0011, 00, 1100, 1010, 111100提示：共四个状态提示：共四个状态0 0奇奇奇奇1 1奇奇奇奇0 0奇奇奇奇1 1偶偶偶偶1 1偶偶偶偶0 0奇奇奇奇1 1偶偶偶偶0 0偶偶偶偶3.3 正规表达式与有限自动机正规表达式与有限自动机补充：从非形式化语言到补充：从非形式化语言到DFA 用用Lex建立词法分析器的步骤建立词法分析器的步骤LexLexLexLex编译器编译器编译器编译器LexLexLexLex源源源源 程程程程 序序序序lex.llex.llex.llex.llex.yy.clex.yy.clex.yy.clex.yy.cC C C C编译器编译器编译器编译器lex.yy.lex.yy.lex.yy.lex.yy.c c c ca.outa.outa.outa.outa.outa.outa.outa.out输入流输入流输入流输入流单词符号单词符号单词符号单词符号3.4 词法分析器的自动产生词法分析器的自动产生3.4 词法分析器的自动产生词法分析器的自动产生正规定义正规定义对正规式命名，使表示简洁。对正规式命名，使表示简洁。对正规式命名，使表示简洁。对正规式命名，使表示简洁。 d d1 1 r r1 1 d d2 2 r r2 2 . . . . . . d dn n r rn n各个各个各个各个d di i的名字都不同的名字都不同的名字都不同的名字都不同每个每个每个每个r ri i都是都是都是都是 d d1 1, , d d2 2, , , , d di i-1-1 上的正规式上的正规式上的正规式上的正规式这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名这样就保证了，每个名字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用字对应的正规式中使用的各种符号已经在前面的各种符号已经在前面的各种符号已经在前面的各种符号已经在前面定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免定义了，从而可以避免递归定义的情况。递归定义的情况。递归定义的情况。递归定义的情况。3.4 词法分析器的自动产生词法分析器的自动产生例例 PascalPascal语言的标识符集合语言的标识符集合语言的标识符集合语言的标识符集合letterletter A A | | B B | | | | Z Z | | a a | | b | b | | | z zdigit digit 0 0 | 1 | | 9| 1 | | 9id id letter(letter|digit) letter(letter|digit)* * 3.4 词法分析器的自动产生词法分析器的自动产生例例Pascal无符号数集合，如无符号数集合，如 4096, 3.1415926, 6.18E3, 6.18E-3 4096, 3.1415926, 6.18E3, 6.18E-3digitdigit 0 0 | 1 | | 9| 1 | | 9digitsdigits digit digitdigit digit* *fractionfraction . .digitsdigitsexponentexponent (E ( + | (E ( + | | | ) digits ) ) digits ) numnumdigits (fraction| digits (fraction| ) ) (exponent| (exponent| ) )简化表示简化表示简化表示简化表示numnum digitdigit+ + ( (. .digitdigit+ +) ) | | ) () (E(+|(E(+| | | ) digit) digit+ + ) ) | | ) ) 简化规则：简化规则：简化规则：简化规则：r+=rr*3.4 词法分析器的自动产生词法分析器的自动产生LexLex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程Lex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n3.4 词法分析器的自动产生词法分析器的自动产生例例-声明部分声明部分%/* * 常常量量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义的定义* */%/* * 正规定义正规定义 * */delim t n wsdelim+letterA Za zdigit0 9idletter(letter|digit)* *numberdigit+( .digit+)?(E+ ?digit+)?3.4 词法分析器的自动产生词法分析器的自动产生例例-翻译规则部分翻译规则部分wsws/ /* * * * 没有没有没有没有动动作，也不返回作，也不返回作，也不返回作，也不返回 * * * */ /whilewhilereturn (WHILE);return (WHILE);dodoreturn (DO);return (DO);ididyylval = install_id ( ); return (ID);yylval = install_id ( ); return (ID);numbernumber yylval yylval = = install_num( install_num( ); ); return return (NUMBER);(NUMBER);“ ”“ ”yylval = LT; return (RELOP);yylval = LT; return (RELOP); “ = ” “ = ” yylval = LE; return (RELOP);yylval = LE; return (RELOP);“ = ”“ = ”yylval = EQ; return (RELOP);yylval = EQ; return (RELOP);“ ”“ ”yylval = NE; return (RELOP);yylval = NE; return (RELOP);“ ”“ ”yylval = GT; return (RELOP);yylval = GT; return (RELOP);“ = ”“ = ”yylval = GE; return (RELOP);yylval = GE; return (RELOP);3.4 词法分析器的自动产生词法分析器的自动产生例例-辅助过程部分辅助过程部分install_ id ( ) install_ id ( ) / /* * * * 把把把把词词法法法法单单元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指元装入符号表并返回指针针。yytextyytext指向指向指向指向该词该词法法法法单单元的第一个字符，元的第一个字符，元的第一个字符，元的第一个字符，yylengyyleng给给出的它的出的它的出的它的出的它的长长度度度度* * * */ / install_num ( ) install_num ( ) / /* * * * 类类似似似似上上上上面面面面的的的的过过程程程程，但但但但词词法法法法单单元元元元不不不不是是是是标标识识符符符符而而而而是是是是数数数数 * * * */ / 总结总结源程序源程序字符流字符流词法分析词法分析单词单词符号符号非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母组合组合串串语言语言集合集合集合集合字母表字母表名名字字连接连接 指数指数连接连接 UVUV闭包闭包 U*U*正闭包正闭包 U+U+计算机计算机实现实现状态转状态转换图换图不确不确定有定有限自限自动机动机确定确定有限有限自动自动机机等等价价子集子集构造构造法法最简最简确定确定有限有限自动自动机机状态列举法状态列举法合并合并不可不可区别区别状态状态手工手工实现实现自动实现自动实现 LexLex正规式语正规式语法结构法结构正规文法正规文法作业作业P64 第第7题题 第第2小题小题第第8题题 第第(1)(7)小题小题第第9题题 第第(1)小题小题第第12题题 第第(b)小题小题, 只需最小化只需最小化第第15题题