编译原理第3章

1、编译原理及编译程序构造2022-4-212第三章 词法分析本章主要内容结构RgReNFADFAMinDFA算法结构2022-4-2133.1 正规文法与有限自动机 一、正规文法、正规集、正规式1、正规文法（Rg：Chomsky 3型文法）： 只能含有产生式：(左线性文法) 或者 (右线性文法) 二者不能同时存在 举例|a|b|z|A|B|Z|_0|1|2|3|4|5|6|7|8|92022-4-2143.1 正规文法与有限自动机 一、正规文法、正规集、正规式2、正规集 由正规文法产生的语言集合,称为正规集. 正规集是集合，可有穷也可无穷。可通过正规式(Re:Regular Expression

2、)来形式化表示2022-4-2153.1 正规文法与有限自动机 一、正规文法、正规集、正规式3、正规式（Re）：正规文法所产生的语言用一种表达式来表示,称为正规式。 定义：设A是非空的有限字母表，A=ai| i=1,2,n,则 1) ，和ai(i=1,2,n)都是正规式。 2) 若、是正规式，则|、 、*、 *也是正规式。 3) 正规式只能通过有限次使用1，2规则获得 注意： 仅由字母表A=ai| i=1,2,n上的正规式所组成的语言称作正规集，记作L() 利用正规集相同，可用来证明相应正规式等价 “|”读作为“或”，也可写作为“+”或“，”；“”读作连接2022-4-2163.1 正规文法与

3、有限自动机 一、正规文法、正规集、正规式3、正规式（Re） 例： A=ai|i=1,2,n,则,a1,a1|a5a7,a5(a3|a2)*,都是A上的ReV=0,1，则,0,1,0011,(01)*10,(01)*|1)*,等二进制字符串都是V上的Re2022-4-2173.1 正规文法与有限自动机 一、正规文法、正规集、正规式例：证明b(ab)*=(ba)*b证明：L(b(ab)*)=b,bab,babab, L(ba)*b)=b,bab,babab,由于正规集的前n项相同可知它们的正规集是相等的 正规式 b(ab)*=(ba)*b2022-4-2183.1 正规文法与有限自动机 一、正规文

4、法、正规集、正规式定理1：令,是Re，则 (1) + = + (2) +( + )=( + )+ () =( ) (3) ( + )= + (+) = + (4) = = (5) (*)*=* (6) *= * = * (7) (+ )*= (* + *)*= (* *)*2022-4-2193.1 正规文法与有限自动机 一、正规文法、正规集、正规式定理2:设若、是字母表A上的正规式，且L()，则： = | 当且仅当 = * = | 当且仅当 = *2022-4-21103.1 正规文法与有限自动机 一、正规文法、正规集、正规式4、如何由正规文法得到对应的正规式？ 1) 由正规文法G的各个产生

5、式写出对应的正规方程式，得到联立方程组 2) 把方程组中的非终结符当作变元 3) 求此正规式方程组的解，得到关于开始符号S的解：S=, VT*，就是所求正规式。2022-4-21113.1 正规文法与有限自动机例：已知正规文法G1的产生式，求出它所定义的正规式。产生式为：SaS|aB BbB|bA AcA|c 解：由产生式写出对应的联立方程组： SaS|aB（1）BbB|bA（2）AcA|c（3）运用定理2求解(1)(2)(3):2022-4-21123.1 正规文法与有限自动机 二、有限自动机（FA：Finite Automata）1、说明： 有限自动机是具有离散输入输出系统的数学模型。它具

6、有有限有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去输入处理的信息 a b c d e 有限状态控制器输入带读头2022-4-21133.1 正规文法与有限自动机 二、有限自动机电梯是典型的有限状态自动机那电梯如何描述呢?电梯的程序又如何构造呢?2022-4-21143.1 正规文法与有限自动机 二、有限自动机分别讲解2、确定有限自动机（DFA） 确定有限自动机DFA是一个五元组 M(S,f,s0,Z），其中： S：有限状态集 ：有限字母表 f：S S上的单值映射，f(s,a)=s s0：唯一的初态，s0 S Z：终止状态集，ZS2022

7、-4-21153.1 正规文法与有限自动机 二、有限自动机2、确定有限自动机（DFA） 注解： 1）用矩阵表示转换便于计算机处理，但不直观，而用状态转换图表示比较直观 2）在整个状态转换图中只有一个初始状态结点，用“”射入的结点表示初始状态。可有若干终止状态(也可能没有)，用双圆圈表示 3）若初始状态结点同时又是终止状态结点，则表示空串可为相应DFA识别1012022-4-21163.1 正规文法与有限自动机 例： DFA M=(0,1,2,3,a,b,f,0,3)f: f(0,a)=1 f(0,b)=2 f(1,a)3 f(1,b)2 f(2,a)=1 f(2,b)=3 f(3,a)3 f(

8、3,b)3 输入 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3 1 a a0 3 2 b b a bab2022-4-21173.1 正规文法与有限自动机 例：构造一个DFA M，它接受字母表a,b,c上，以a或b开始的字符串，或以c开始但所含的a不多于一个的字符串:解：01 a bb c a2 cc b 3 ac b体现了直观性2022-4-21183.1 正规文法与有限自动机故：DFA: M=(0,1,2,3,a,b,c,f,0,1,2,3)其中：f： f(0,a)=1 f(0,b)=1 f(0,c)=1 f(1,a)=1 f(1,b)=1 f(1,c)=1 f(2,a)=

9、3 f(2,b)=2 f(2,c)=2 f(3,b)=3 f(3,c)=32022-4-21193.1 正规文法与有限自动机 二、有限自动机2、确定有限自动机（DFA） 一步操作： 每读一个字符，状态就向前进至下一状态。记为：“ ” K 表示自动机做了K步动作 * 表示自动机做了0步动作或0步以上动作 + 表示自动机做了1步动作或1步以上动作2022-4-21203.1 正规文法与有限自动机 二、有限自动机2、确定有限自动机（DFA） DFA识别字符串： 串*为 DFA M=(S, ,f,s0,Z) 所识别，当且仅当(s0, ) *(s,),且s Z 与文法中的S*类似 能被DFA M所接受的

10、字符串的集合，称为自动机M所能识别的语言，记为L(M) 不能被DFA识别的两种情形： (s0,) *(s,),且s Z 在读过程中出现不存在的映射，使自动机无法继续动作2022-4-21213.1 正规文法与有限自动机S0S1S2S311110000板书”110101”、”11100”的识别过程例2022-4-2122作业2022-4-21233.1 正规文法与有限自动机 构造一个DFA,使它识别0,1上以00结尾的字符串。 （国防科技大学考博题）2022-4-21243.1 正规文法与有限自动机 二、有限自动机3、不确定有限自动机（NFA） 定义：不确定有限自动机是一个五元式M=（S,f,S

11、0,Z）其中： S：有限状态集（同DFA） ：有限字母表（同DFA） f： S2S(S的子集)上的映射 S0：非空的初态集，S0 S（与DFA的区别） Z：终止状态集，ZS，可为空集 注： “不确定”指后继状态可有多个 DFA是NFA的特例2022-4-21253.1 正规文法与有限自动机 例：设NFA M(q0,q1，0,1，f，q0，q1) f映射为： 字符状态01q0 q0 q1q1 q0， q1 q0q0q111000f(q1,0)=q0,q1f(q0,0100)=?2022-4-21263.1 正规文法与有限自动机 二、有限自动机3、不确定有限自动机（NFA） 不同自动机FA M,M

12、之间的等价问题： 若它们识别的语言相同，L(M)=L(M)2022-4-21273.1 正规文法与有限自动机 二、有限自动机4、NFADFA(NFA的确定化) 重点内容 子集法 实质： f(q1,0)=q0,q1= f(q1,0)=q0,q1= f(s0,0)=s1 转化理论 设L是由一NFA接受的正规集，则存在一个DFA接受L2022-4-21283.1 正规文法与有限自动机 二、有限自动机算法：NFA M=(S,f,S0,Z)DFA M=(Q, ,I0,F） 1. 取I0=S0 2. 若状态集Q中有状态Ii=s0,s1,sj , skS , 0 kj;而且M机中有f(s0,s1,sj,a)

13、= f(s0,a)f(s1,a)f(sj,a)=s0,s1,st =It，若It不在Q中，则将It加入Q。 3. 重复第(2)步，直至Q中没有新的状态加入 4.取终态F=I | I Q,且I Z 2022-4-21293.1 正规文法与有限自动机 例：解：列表将NFA确定化为DFA： Q01I0 =q0I0 =q0I1 =q1I1 =q1I2 =q0,q1I0 =q0I2 =q0,q1I2 =q0,q1I2 =q0,q12022-4-21303.1 正规文法与有限自动机01I0I0I1 I1 I2I0I2I2I2F=I1 ,I2，所得DFA的状态转换图：I0I111000I212022-4-2

14、1313.1 正规文法与有限自动机 二、有限自动机4、NFADFA(NFA的确定化) 以P52 3-4为例强化理解 解： Q01I0=SI1=A,CI2=B,CI1=A,CI3=A,C,ZI2=B,CI2=B,CI1=A,CI4=B,C,ZI3=A,C,ZI3=A,C,ZI4=B,C,ZI4=B,C,ZI3=A,C,ZI4=B,C,Z2022-4-21323.1 正规文法与有限自动机I0I1I2I3I401010101012022-4-21333.1 正规文法与有限自动机5.Re=DFA 两核心理论（关系定理）： 定理3： 上的NFA M所能识别的语言L(M)可以用上的正规式Re来表示 对上的

15、NFA M ，可构造一个正规式，使得L()=L(M) 定理4： 上任何正规式 ，存在DFA M使得L(M)=L() 即：由 正规式可以构造一个DFA M，使得L(M)L() 构造步骤：Re=NFA=DFA 构造证明上述两定理2022-4-21345.Re=DFA 构造的步骤：Re=NFA=DFA2022-4-2135Re =DFA 基本过程：1）由正规式 构造一个如下仅有两个结点x,y的状态图：2）按所引入的3条正规式分裂规则（与前者互逆）分裂 3）重复步骤2直到每个弧上的标记是上的一个字符或为止4）将所得的NFA M(因为包含弧)进行确定化就得到DFA x y 2022-4-2136Re =

16、DFA 12| 1 22 1 12* 121 1212022-4-2137Re =DFA 例：根据正规式(a|b)*(aa|bb)(a|b)*, 构造DFA M，使之等价解： x y (a|b)*(aa|bb)(a|b)* 1y(a|b)*(a|b)* 2 x(aa|bb) 1y 2 xaa 5 bba|b 6 a|b2022-4-2138Re =DFA 1y 2 xa 5 ba 6 abb34ab2022-4-2139Re =DFA 列状态转换矩阵将NFA确定化： SabI0=x,5,1I1=5,3,1I2=5,4,1I1=5,3,1I3=5,3,1,2,6,yI2=5,4,1I2=5,4,

17、1I1=5,3,1I4=5,4,1,2,6,yI3=5,3,1,2,6,yI3=5,3,1,2,6,yI5=5,4,1,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI5=5,4,1,6,yI6=5,3,1,6,yI4=5,4,1,2,6,yI6=5,3,1,6,yI3=5,3,1,2,6,yI5=5,4,1,6,y2022-4-2140Re =DFADFA为： I0 I1 I2 I3 I4 I6 I5a b aa a babbbbbaa2022-4-2141Re =DFA 最小化为： I0 I1 I2 I3a b aabbba万事大吉2022-4-21

18、423.1 正规文法与有限自动机 6、DFA的化简（最小化） 化简的原则： 化简前后接受的语言必须相同 化简的基本思想 1.将DFA M 中的状态划分为互不相交的子集，每个子集内部的状态都等价；而在不同子集间的状态均不等价。 可理解成等价类划分 2.从每个子集中任选一个状态作为代表，删除其它。 3.把那些原来射入其它等价状态的弧改为射入相应的代表状态2022-4-2143 2022-4-21443.重复步骤重复步骤2，直到所含的子集数不再增加为，直到所含的子集数不再增加为止。止。4.对每个子集任取一状态为代表。若该子集对每个子集任取一状态为代表。若该子集包含原有的初态，则相应代表状态就是最包含

19、原有的初态，则相应代表状态就是最小化后小化后M的初态；同样，若该子集包含原的初态；同样，若该子集包含原有的终态，则相应代表状态就是最小化后有的终态，则相应代表状态就是最小化后M的终态。的终态。 2022-4-21456、DFA的化简（最小化） 状态状态s,t等价等价 (s, ) *(s1, )同时同时(t, ) *(t1, )，s1,t1都是终态，都是终态， VT* ，即如果从状态，即如果从状态s出发能读出某个字出发能读出某个字 而而 停于停于 终态，终态，从从t出发也能读出同样的字出发也能读出同样的字 而停于终态，则称而停于终态，则称s,t 等价等价 s,t可区分可区分 ： 如果如果s,t不

20、等价，则称为不等价，则称为s,t可区分可区分 通过实例讲解化简步骤通过实例讲解化简步骤2022-4-21466、DFA的化简（最小化） P52 3-4续：将 的DFA进行化简。解：0=I0,I1,I2,I3,I4因为f(I0,I1,I2,0)=I1,I3所以1=I0,I2,I1,I3,I4又因为f(I0,I2,1)=I2,I4所以1=I0,I2,I1,I3,I4而f(I3,I4,0)= f(I3,I4,1)=I3,I4所以I3,I4不可再分，取I3作为该子集的代表2022-4-21476、DFA的化简（最小化）I0I1I2I3010101012022-4-21486、DFA的化简（最小化） 课

21、堂练习P52 3-7(b) Answer：0=2,3,4,5,0,11=2,4,3,5,0,1不可再分：023ababab2022-4-21496、DFA的化简（最小化） 课堂练习将下列DFA最小化： 答案S0S1S2S3S4S610010S510101012022-4-21503.1 正规文法与有限自动机 7.NFA=Re 1) 把状态转换图的概念拓广，令每条弧上都可以用一个正规式作标记 2) 在M的转换图上加两个结点：x,y。从 x用弧连接到M的所有初态结点；从M的所有终态结点用弧连接到y。这个新的NFA为M，且L(M)=L(M) 3) 通过引入的3条有限自动机替换规则逐步消去M中的所有结

22、点，直到只剩下x和y为止。这样，在x至y的弧线上的标记就是上的正规式，也就是M接受的正规式 注：在消除结点过程中，逐步用正规式来标记弧。2022-4-21517.NFA=Re 1 1 1 1 132|2 23 12* 2如何理解？2022-4-21527.NFA=Re 例：将下面的DFA M所接受的语言表示为正规式：解：111113200 00 0 xy2022-4-21537.NFA=Rex0 310|0101|1000|1100|11y x 0 y00|11(10|01)(00|11)*(01|10) x y (10|01)(00|11)*(01|10)|(00|11)*2022-4-21

23、547.NFA=Re 补充：求下列FA对应的正规式：03421abcdb答案2022-4-21553.1 正规文法与有限自动机 8. 文法FA理论前提： 设G=(VN,VT,P,S)是正规文法，则存在一个有限自动机M=(Q,f,q0,Z)使得L(G)=L(M)曾经说过的 1）正规文法右线性文法左线性文法 2）对每个有限自动机 M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)=L(GR)=L(GL)2022-4-2156右线性文法=FAG=(VN,VT,P,S)M=(Q,f, q0,Z)VNT如P中有S,则Z=S,T否则Z=TfT是新增的终态结点2022-4-2157右线性文法

24、=FAf 映射的确定： 对于P中每一条形如 A1 aA2的产生式，在M中设为 f(A1,a)= A2 对于P中每一条形如 A1 a的产生式，在M中设为 f(A1,a)= T 对上的所有a，取 f(T,a)=,即在终态下FA无动作2022-4-2158右线性文法=FA 例：构造与下述文法等价的FA：SaS|aBBbB|bAAcA|c解：构造FA对应的五元组：M=(S,B,A,T,a,b,c,f,S,T)，其中f为：f(S,a)=S f(S,a)=Bf(B,b)=B f(B,b)=Af(A,c)=A f(A,c)=T2022-4-2159右线性文法=FA确定化： BTac A Sbabc状态abc

25、0=S1=S,B1=S,B1=S,B2=B,A2=B,A2=B,A3=A,T3=A,T3=A,T2022-4-2160右线性文法=FA 13ac2 0bcab教材中状态还是命名为S,B,A,T,不太合适2022-4-2161FA=右线性文法G=(VN,VT,P, S)M=(Q, , f, q0, Z)2022-4-2162FA=右线性文法产生式P的产生： 若M中有f(A1,a)=A2,则有产生式A1aA2 若f(A1,a)=A2且A2Z（终态集合），则有产生式A1a 若初态q0Z，则P中有S 此时应写成S |S2022-4-2163FA=右线性文法 例：写出下列DFA对应的右线性文法Rg： C

26、 0 1 A D1 0 10|1 B 0解：Rg=(A,B,C,D,0,1,P,A) A 0B | 1D | 0 B 1C | 0D C 0B | 1D | 0 D 0D | 1D2022-4-2164左线性文法=FAG=(VN,VT, P, S)M=(Q,f, q0,Z)VNq0如P中有S,则Z=S, q0否则Z=S2022-4-2165左线性文法=FA f 映射的确定：a) 对于P中每一条形如 A1 A2a的产生式，在M中设映射式 f(A2,a)= A1b) 对于P中每一条形如 A1 a的产生式，在M中设置映射式f(q0,a)= A1，即从初态引一箭头指向A12022-4-2166左线性文

27、法=FA 例：构造与下述文法等价的FA：TTc|AcAAb|BbBBa|a解：TcAa q0 Bbcab添加的初态2022-4-2167从上DFA看左（右）线性文法： 对应的右线性文法：SaBBaB|bAAbA|cTTcT| 对应的左线性文法：TTc|AcAAb|BbBBa|a 两种文法产生的语言是一样的：L(a+b+c+) 思考：两种文法的开始符为什么不一样？TcAa S Bbcab作业2022-4-21683.2 词法分析程序 词法分析器在编译中的位置词法分析器语法分析器符号表源程序单词取下一个单词单词记号2022-4-21693.2 词法分析程序 词法分析器的基本功能1）预处理工作2）识别符号串3）把源程序改造成等价的计算机内部表示单词记号 属性字、单词记号