第4章词法分析2013

上传者：8**** 2022-05-27 23:43:31上传 PPT文件 928KB

《第4章词法分析2013》由会员分享，可在线阅读，更多相关《第4章词法分析2013（60页珍藏版）》请在文档大全上搜索。

1、 4.1 词法分析程序的设计词法分析程序的设计一、词法分析程序与语法分析程序的接口方式一、词法分析程序与语法分析程序的接口方式词法分析词法分析语法分析语法分析源程序源程序ASCII序列序列机内符序列机内符序列词法分析词法分析语法分析语法分析源程序源程序ASCII序列序列调用调用机内符机内符词法分析程序作为语法分析程序调用的子程序：词法分析程序作为语法分析程序调用的子程序：词法分析程序作为独立的一遍扫描程序：词法分析程序作为独立的一遍扫描程序：二、词法分析程序的输出二、词法分析程序的输出词法分析程序的功能：读入源程序，输出单词符号。词法分析程序的功能：读入源程序，输出单词符号。单词符号：是

2、一个程序设计语言的基本语法符号。单词符号：是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列程序设计语言的单词符号一般可分成下列5种：种： 1基本字基本字，也称关键字，也称关键字/保留字，如保留字，如PASCAL语言中语言中的的begin，end，if，while和和var等。等。 2标识符标识符，用来表示各种名字，如常量名、变量名和，用来表示各种名字，如常量名、变量名和过程名等。过程名等。 3常数常数，各种类型的常数，如，各种类型的常数，如25，3.1415，TRUE和和 “ABC”等。等。 4运算符运算符，如，如+，*，=等。等。 5界符界符，如逗点，分号，括号等

3、。，如逗点，分号，括号等。单词符号（机内符）的表达形式：单词符号（机内符）的表达形式：（单词种别（单词种别，单词自身的值），单词自身的值）词法信息词法信息词义信息词义信息说明说明:语法分析时使用词法信息语法分析时使用词法信息, 语义分析时使用词义信息语义分析时使用词义信息其中：其中：1）单词的种别可以用整数编码表示，假如）单词的种别可以用整数编码表示，假如标识符编码：标识符编码：1 常数编码：常数编码： 2 保留字编码：保留字编码：3 运算符编码：运算符编码：4 界符编码：界符编码： 5 2）单词自身的值：值本身或指向存放）单词自身的值：值本身或指向存放“值值”的信的信息息表的指针。

4、表的指针。例如：例如：( (标识符，指向该标识符所在符号表中位置的指针标识符，指向该标识符所在符号表中位置的指针) ) 例如程序段例如程序段： if i=5 then x:=y；对应的单词符号（机内符）序列为：对应的单词符号（机内符）序列为：保留字保留字 if (3，if) 标识符标识符 i (1， 0 ) 等号等号 = (4，= ) 常数常数 5 (2， 0 ) 保留字保留字then (3，then) 标识符标识符x (1， 1) 赋值号：赋值号： (4 , :=) 标识符标识符y (1， 2) 分号；分号； (5，；)ixy012符号表符号表(5)2012常数表常数表从开发实现编译

5、程序的角度考虑：从开发实现编译程序的角度考虑： 1使整个编译程序的结构更简洁、清晰和条理化使整个编译程序的结构更简洁、清晰和条理化 2. 编译程序的效率会改进编译程序的效率会改进 3增强编译程序的可移植性增强编译程序的可移植性从教学角度考虑：浅显易懂，各章节内容相对独立从教学角度考虑：浅显易懂，各章节内容相对独立三、将词法分析工作分离的考虑三、将词法分析工作分离的考虑一、正规文法一、正规文法正规文法正规文法( (3型文法型文法) )：产生（接受）语言为正则集：产生（接受）语言为正则集产生式形式是：产生式形式是：A aB 或或 A a 其中：其中： A、B VN , a VT程序设计语言中的几

6、类单词可用下述规则描述：程序设计语言中的几类单词可用下述规则描述： l | l l | d | l | d d | d + | - | * | / | = | | = ，| ；| ( | ) | 注意：基本字集是标识符集合的子集。注意：基本字集是标识符集合的子集。其中：最复杂的一类单词为无符号实数了，如其中：最复杂的一类单词为无符号实数了，如25.55e+5、 2.1、4.3e2, 它们可以由如下规则描述。它们可以由如下规则描述。例例4.1 G d |. |e d |. |e | d e |d | d | + |- d d | 4 4 . 4 .3 4 .3e 4 .3e 2 4 .3e 2

7、二、正规式（正则表达式）二、正规式（正则表达式）正规式和它所表示的正规集的递归定义：正规式和它所表示的正规集的递归定义：设字母表为设字母表为，辅助字母表，辅助字母表=,* *,|,(,),|,(,) 1和和都是都是上的正规式，上的正规式，L()=， L()= ; 2任何任何a，a是是上的一个正规式，上的一个正规式， L(a)=a； 3假定假定e1和和e2都是都是上的正规式，它们所表示的正规集上的正规式，它们所表示的正规集分别为分别为L(e1)和和L(e2)，则有，则有 (e1) ， e1|e2，e1 e2， e1* 也都是正规式也都是正规式表示的正规集分别为表示的正规集分别为： L(e1

8、) )=L(e1) L(e1|e2)= L(e1)L(e2) L(e1 e2)= L(e1) L(e2) L(e1*)=(L(e1)*= L(e1)*4仅由有限次使用上述三步骤而定义的表达式才是仅由有限次使用上述三步骤而定义的表达式才是上的正规上的正规式，仅由这些正规式所表示的字集才是式，仅由这些正规式所表示的字集才是上的正规集。上的正规集。例例42 令令=a，b，则有，则有正规式正规式正规集正规集 a a a | b a，b ab ab (a|b)(a|b) aa，ab，ba，bb) a* ，a，aa，=an | n=0 (a | b)* ，a，b，aa，ab所有所有a，b组成的串组成

9、的串 (a|b)*(aa | bb)(a|b)* *上所有含有两个相继的上所有含有两个相继的a或两或两个相继的个相继的b组成的串。组成的串。例例4.3 令令=d，e，+，则，则上的正规式上的正规式: 整数：整数： dd* 仅含小数点的实数：仅含小数点的实数： d*dd* (= dd* | dd*dd*) 指数：指数： e(+| | )dd* (= e +dd* | e dd* | e dd* )无符号数：无符号数：d*(dd* | )(e(+| | )dd*| ) /有问题有问题 d*(dd* | d)(e(+| | )dd*| ) /稍加改动稍加改动 = dd* | d*dd* | dd*

10、 e(+| | )dd* | d*dd* e(+| |)dd*其中：其中：d=0|1|2|9 比如比如2 ，12.59，3.6e2 和和 471.88e l 等等等等正规式的等价性：正规式的等价性：若两个正规式若两个正规式e1和和e2，所表示的正规集相同，即，所表示的正规集相同，即 L(e1)=L(e2)，则说，则说e1和和e2等价，写作等价，写作 e1=e2例如：若例如：若e1=a | b，e2=b | a，则有，则有e1=e2，即，即a | b=b | a 又又 b(ab)*=(ba)*b (a | b) *= (a*b*)*设设r，s，t为正规式，正规式服从的代数规律有：为正规式，正规

11、式服从的代数规律有： 1r | s =s | r “或或”满足交换律。满足交换律。 2r |(s | t) = (r | s)| t “或或”的可结合律。的可结合律。 3(rs)t = r(st) “连接连接”的可结合律的可结合律 4r(s | t) = rs | rt 分配律分配律 (s | t)r = sr | tr 5 r = r 吸收率吸收率 r = r说明：单词集合是正规集说明：单词集合是正规集例比如例比如=字母，数字字母，数字上的正规式：上的正规式： el=字母字母(字母字母|数字数字)*表示的是所有标识符的集合，表示的是所有标识符的集合，或者用或者用l代表字母，代表字母，d代表数

12、字，代表数字，=l，d el=1(1 | d)*三、正规文法到正规式三、正规文法到正规式1正规式正规式正则文法正则文法（1）对任何正规式）对任何正规式r，选择一非终结符，选择一非终结符S，生成产生式：，生成产生式： S r （S设定为设定为G的开始符的开始符) （2）若）若x和和y是正规式，对形如是正规式，对形如A xy产生式，重写成：产生式，重写成： A xB B y （其中：（其中：B是新引进的非终结符）是新引进的非终结符）（3）对形如）对形如A x*y产生式，重写为：产生式，重写为： A xB A y B xB B y （其中：（其中：B为一新非终结符）为一新非终结符）（4）对形

14、 x*y 规则规则3: Axx Ay A x | y例例4.5 GS： S aaA S a A aA A dA A a A d S aaA | aA (a(a | d)A| a | dA (a(a | d)*( a | d)S=a(a(a | d)*( a | d) | a S=a(a(a | d)*( a | d) | a=a(a(a | d)+ | )= a(a(a | d)*一、确定的有穷自动机（一、确定的有穷自动机（ DFA ）DFA：Determinastic Finite Automaton定义：定义：DFA M是一个五元组是一个五元组 M=(K , , f , S, Z) 其中：

15、其中： K-有穷状态集有穷状态集 -有穷字母表有穷字母表 f - K K 的映像（单值映射）的映像（单值映射） S- 初态初态 S K Z - 终态集终态集（也称可接受状态或结束状态）（也称可接受状态或结束状态）Z K令：令：K=k1, k2, , kn =a1, a2, , am(k1,a1)(k1,a2)(ki, aj)(kn,am) k1 k2 klknKK其中：其中：(ki, aj)kl 写成写成 f(ki, aj)=kl 作用：若当前状态为作用：若当前状态为ki，输入符为，输入符为aj时，将转换到时，将转换到下一个下一个状态状态kl例例4.6 DFA M=(S,U,V,Q , a

16、,b , f , S, Q) f(S, a)=U f(V, a)=U f(S, b)=V f(V, b)=Q f(U, a)=Q f(Q, a)=Q f(U, b)=V f(Q, b)=Q DFA的表达形式的表达形式集合法：上述定义形势集合法：上述定义形势矩阵法：状态矩阵矩阵法：状态矩阵/状态转换矩阵状态转换矩阵图法：状态图图法：状态图/状态转换图状态转换图 f(S, a)=U f(S, b)=V f(U, a)=Q f(U, b)=V f(V, a)=U f(V, b)=Q f(Q, a)=Q f(Q, b)=Q状态图状态图SUVaa,bbabQbaabUQUQSUVQVVQQ K状态矩阵状

17、态矩阵+0001 定义：设定义：设DFA M =(K , , f , S, Z)，若有，若有 t*， f(S, t)=P，PZ 则称则称t可为可为M所接受（识别）所接受（识别）令：令：t=a1a2an , ai （i=1,2,n）则存在状态序列（路）：则存在状态序列（路）：S ，k1，k2 ，kn-1 ，P 使使 f(S, a1)=k1 ， f(k1, a2)=k2 ，， f(kn-1 , an )=P f扩充定义：设扩充定义：设 QK1. f(Q, )=Q （输入字符是空串，状态不变）（输入字符是空串，状态不变）2. 设输入串设输入串 t=t1tx ，t1， tx* 则定义：则定义： f

18、(Q, t1tx )= f(f(Q, t1 ) , tx )例如，验证例如，验证baab可为可为例例4.6 DFA M所接受。所接受。SUVaa,bbabQba因为：因为：f(S, baab)=f(f(S,b), aab)=f(V , aab )= f(f(V,a), ab) =f(U , ab ) = f(f(U,a), b)=f(Q, b)=QQ Z,得证。得证。上述过程等价于：上述过程等价于： f(S, baab) = f(V , aab ) = f(U , ab ) = f(Q, b)=Q 亦等价于：亦等价于： f(S, b)=V ，f(V, a)=U ，f(U, a)=Q ，f(Q

19、, b )=Q 结论：结论：V *是正则式，当且仅当存在是正则式，当且仅当存在上上DFA M，使，使 L(V)=L(M) L(M)=(a(ba)*(bb|a)|b(ab)*(aa|b)(a|b)*说明：如果初态说明：如果初态S，同时又为终态，则，同时又为终态，则 L(M)二、非确定的有穷自动机（二、非确定的有穷自动机（ NFA ）定义：定义：NFA M是一个五元组是一个五元组 M=(K , , f , S, Z) 其中：其中： K-有穷状态集有穷状态集 -有穷字母表有穷字母表 f - K K 子集的映像（非单值映射）子集的映像（非单值映射） S- 初态集初态集 S K Z - 终态集终态集（

20、也称可接受状态或结束状态）（也称可接受状态或结束状态）Z K(k1,a1)(k1,a2)(ki, aj)(kn,am) k1 k2 klknKK例例4.6 DFA M=(0, 1, 2, 3, 4 , a, b , f , 0, 2, 4) f(0, a)=0, 3 f(2, b)=2 f(0, b)=0, 1 f(3, b)=4 f(1, b)=2 f(4, a)=4 f(2, a)=2 f(4, b)=431a,bba2b04a,ba,ba三、三、NFADAF的转换的转换定理：对于每个定理：对于每个NFA M，存在一个，存在一个DAF M，使得，使得 L(M)=L(M)设有状态集合设有状态

21、集合I S，则基于，则基于 I 的两个有关运算的两个有关运算:1. I的的Closure (I) （ I的的闭包集）：闭包集）： Closure(I)=I中的任何状态中的任何状态S经任意条经任意条弧而能到达状态弧而能到达状态的集合的集合其中：其中：I Closure(I)2. I的的Move(I, a) （ I关于关于a弧转换集）：弧转换集）： Move(I, a)= I中的某一状态经过一条中的某一状态经过一条a弧而到达状态的弧而到达状态的全体全体设：设：I= s1，s2，sj ，a，则有，则有 Move(I, a)=f(s1, a)f(s2, a)f(sj, a) 16bab0104

22、325879ab例：设有例：设有NFA N:令：令：I=0，则，则 Closure(I)= Closure(0)=0, 1, 2, 4, 7 A= 0, 1, 2, 4, 7 ，则，则 Move(A, a) =3, 8 Move(A, b) =5 I=3, 8 Closure(3, 8)=1, 2, 3, 4, 6, 7, 8 NFA N=(K , , f , K0, Kt) DFA M=(S , , D , S0, St) 使使L(N)=L(M)的算法如下：的算法如下：1. M的状态集的状态集S由由K的子集构成，令的子集构成，令 C=(T0, T1 , Tn ) /T为为K的子集的子集 S=

23、S0, S1 , Sn =T0, T1, Tn求求C（也即求（也即求S）的算法如下：）的算法如下：(1) 令令T0=Closure(K0)为为C中唯一成员中唯一成员, 且是未被标记的且是未被标记的(2) While (C中存在尚未被标记的子集中存在尚未被标记的子集T) 标记标记T; for a do U:= Closure(Move(T, a) ); if U不在不在C中中 then 将作为未被标记的子集加在将作为未被标记的子集加在C中中 2. M和和N的字母表都为的字母表都为； 3. DFA的转换函数的转换函数D定义如下：定义如下： D(S, a) = S S=T=K1, K2 , Kj

24、S=T=R1, R2 , Ri 其中：其中：Closure ( Move(K1, K2 , Kj , a) )=R1, R2 , Ri ; 4. S0=T0= Closure(K0); 5. St=K1, K2 , Ke, 其中其中K1, K2 , KeS 且且 K1, K2 , KeKt 16bab0104325879ab 例例4.8 对上述对上述DFA N构造子集，步骤如下：构造子集，步骤如下： 1. 令令T0= Closure(0)=0, 1, 2, 4, 7，且未被标记，且未被标记 2. 标记标记T0; 令令T1=Closure( Move(T0, a) )= 1, 2, 3 , 4,

25、 6, 7, 8 T2=Closure( Move(T0, b) )= 1, 2, 4, 5, 6, 7 将将T1、T2加入加入C中，中，未被标记。未被标记。3. 标记标记T1; T1=1, 2, 3 ,4, 6, 7, 8 计算计算 Closure ( Move(T1, a) )=1, 2, 3 ,4, 6, 7, 8= T1 令令 T3=Closure ( Move(T1, b) )= 1, 2, 4, 5, 6, 7, 9 将将T3加入加入C中，中，未被标记。未被标记。4. 标记标记T2; T2=1, 2, 4, 5, 6, 7 计算计算 Closure ( Move(T2, a) )=

26、1, 2, 3 ,4, 6, 7, 8= T1 计算计算 Closure ( Move(T2, b) )= 1, 2, 4, 5, 6, 7=T216bab0104325879ab5. 标记标记T3; T3=1, 2, 4, 5, 6, 7, 9 计算计算 Closure ( Move(T3, a) )=1, 2, 3 ,4, 6, 7, 8= T1 令令 T4=Closure ( Move(T3, b) )= 1, 2, 4, 5, 6, 7, 10 将将T4加入加入C中，中，未被标记。未被标记。6. 标记标记T4; 计算计算 Closure ( Move(T4, a) )=1, 2, 3

27、,4, 6, 7, 8= T1 计算计算 Closure ( Move(T4, b) )= 1, 2, 4, 5, 6, 7=T216bab0104325879ab得：得：C=(T0, T1, T2, T3, T4 T0= 0, 1, 2, 4, 7 T3=1, 2, 4, 5, 6, 7, 9 T1=1, 2, 3 ,4, 6, 7, 8 T4=1, 2, 4, 5, 6, 7, 10 T2=1, 2, 4, 5, 6, 7且有：且有： Closure(Move(T0, a)=T1 Closure(Move(T0, b)=T2 Closure(Move(T1, a)=T1 Closure(M

28、ove(T1, b)=T3 Closure(Move(T2, a)=T1 Closure(Move(T2, b)=T2 Closure(Move(T3, a)=T1 Closure(Move(T3, b)=T4 Closure(Move(T4, a)=T1 Closure(Move(T4, b)=T2NFA N构造的构造的DAF M为：为： 1. S=T0, T1, T2, T3, T4 2. =a, b 3. D(T0, a)=T1 /Closure(Move(T0, a)=T1 D(T0, b)=T2 /Closure(Move(T0, b)=T2 D(T1, a)=T1 /Closure

29、(Move(T1, a)=T1 D(T1, b)=T3 /Closure(Move(T1, b)=T3 D(T2, a)=T1 /Closure(Move(T2, a)=T1 D(T2, b)=T2 /Closure(Move(T2, b)=T2 D(T3, a)=T1 /Closure(Move(T3, a)=T1 D(T3, b)=T4 /Closure(Move(T3, b)=T4 D(T4, a)=T1 /Closure(Move(T4, a)=T1 D(T4, a)=T2 /Closure(Move(T4, b)=T2 4. S0= T0 5. St= T4 可将可将T0、T1、T2

30、、T3、T4 重新命名为：重新命名为：0、1、2、3、4 则则DFA M状态转换图如下：状态转换图如下： a104a32bbabaaabD(0, a)=1 D(0, b)=2D(1, a)=1D(1, b)=3D(2, a)=1D(2, b)=2D(3, a)=1D(3, b)=4D(4, a)=1D(4, a)=2S0=0St=4S0=0,1, 2,4,7S1=1,2,3,4,6,7,8S2=1,2,4,5,6,7S3=1,2,4,5,6,7,9S4=1,2,4,5,6,7,10 a b1,2,3,4,6,7,81,2,4,5,6,71,2,3,4,6,7,81,2,4,5,6,7,91,2

31、,3,4,6,7,81,2,4,5,6,71,2,3,4,6,7,81,2,3,4,6,7,81,2,4,5,6,7,101,2,4,5,6,7_+16bab0104325879ab四、四、DAF的化简的化简DAF的化简指：没有多余状态和等价状态。的化简指：没有多余状态和等价状态。多余状态：指从开始状态出发不能够达到的状态。多余状态：指从开始状态出发不能够达到的状态。 0 1S0 S1 S5 0S1 S2 S7 1 S2 S2 S5 1S3 S5 S7 0S4 S5 S6 0S5 S3 S1 0S6 S8 S0 1S7 S0 S1 1S8 S3 S6 0 0 1S0 S1 S5 0S1 S2

32、S7 1 S2 S2 S5 1S3 S5 S7 0S5 S3 S1 0S6 S8 S0 1S7 S0 S1 1S8 S3 S6 0 0 1S0 S1 S5 0S1 S2 S7 1 S2 S2 S5 1S3 S5 S7 0S5 S3 S1 0S7 S0 S1 1其中：右部的其中：右部的0表示非终止状态，表示非终止状态，1表示终止状态。表示终止状态。14800001611S013510011001107211S0135100110011072等价状态：指从两个状态出发产生的（子）串集相同。等价状态：指从两个状态出发产生的（子）串集相同。31a,bba2b04a,ba,ba其中状态其中状态2和和4等

33、价。等价。31a,bba24b0a,ba例例: 0和和4是可区分的，是可区分的， 0是非终态，是非终态，4是终态。是终态。2和和4是可区分的，是可区分的， 2是非终态，是非终态，4是终态。是终态。2和和3是可区分的，是可区分的，f(2,b)=2 , f(3,b)=4 两个状态两个状态s和和t等价的条件：等价的条件：1. 一致性条件：一致性条件： s和和t同时为终态或非终态同时为终态或非终态即：终态和非终态一定不等价即：终态和非终态一定不等价原因：终态产生原因：终态产生串，而非终态则不能串，而非终态则不能2. 蔓延性条件：对于所有输入符号，蔓延性条件：对于所有输入符号， s和和t必须转到等价必须

34、转到等价的状态里。的状态里。说明：如果说明：如果s和和t不等价，则称不等价，则称s和和t是是a104a32bbabaaab分割法分割法: 1. 利用一致性和蔓延性两个条件，将状态集利用一致性和蔓延性两个条件，将状态集K分割成一些分割成一些不相交的子集，如：不相交的子集，如： K1 , Ki , Kj , , Kn 使任意两个状态子集使任意两个状态子集Ki 和和Kj 中的状态都是可分的，而中的状态都是可分的，而同一子集同一子集Ki中的任意两个状态都是等价的。中的任意两个状态都是等价的。2. 用用Ki 做最小化做最小化DFA的状态，且采用如下方法构造的状态，且采用如下方法构造 F： F(Ki

35、 , a) = Kj 存在状态存在状态sKi 和和 tKj 有有 f(s,a)=t 亦可以选取亦可以选取Ki中的一个状态代替中的一个状态代替Ki 。3. 设设s0是原是原DFA的初态，若的初态，若s0Ki 则令则令Ki为最小化为最小化DFA的的初态；初态；令均由原令均由原DFA的终态构成的子集为最小化的终态构成的子集为最小化DFA 的终态。的终态。例例4 . 9 DFA = 最小化最小化DFA2361574abaabaaabbbbab1. 利用一致性分割条件将状态集利用一致性分割条件将状态集 K=1, 2, 3, 4, 5, 6, 7分割分割成两个子集：成两个子集： P0= 1, 2,

36、3, 4 , 5, 6, 7 2. 利用蔓延性分割条件继续分割。利用蔓延性分割条件继续分割。 f(1, a)=6 f(2, a)=7 f(3, a)=1 f(4, a)=4说明说明 1, 2关于关于a不可分，不可分， 3, 4关于关于a不可分不可分 1, 2同同3, 4关于关于a是可分的，即得：是可分的，即得： P1= 1, 2 , 3, 4 , 5, 6, 7 继续分割继续分割 P1= 1, 2 , 3, 4 , 5, 6, 7 关于集合关于集合1, 2 有：有： f(1,a)=6 f(2,a)=7 f(1,b)=3 f(2,b)=3 说明说明1，2关于关于b也不可分，也不可分， 1，2 暂

37、时是不可分的。暂时是不可分的。关于集合关于集合3, 4 有：有： f(3,a)=1 f(4,a)=4 f(3,b)=5 f(4,b)=6 说明说明3，4关于关于a是可分的。是可分的。 P2= 1, 2 , 3 , 4 , 5, 6, 7 2361574abaabaaabbbbab 继续分割继续分割 P2= 1, 2 , 3 , 4 , 5, 6, 7 关于集合关于集合5, 6, 7有：有： f(5,a)=7 f(6,a)=4 f(7,a)=4 说明说明5同同6，7 是可分的。是可分的。 P3= 1, 2 , 3 , 4 , 5 , 6, 7 又又f(6,a)=4 f(7,a)=4 f(6,b

38、)=1 f(7,b)=2 说明说明6，7关于关于a, b都是不可分的，是等价的。都是不可分的，是等价的。显然显然1，2也是等价的。也是等价的。2361574abaabaaabbbbab a b -1 6 3 3 1 5 4 4 6 +5 6 3 +6 4 136154baababbbaa a b-1,2 6,7 3 3 1,2 5 4 4 6,7 +5 6,7 3+6,7 4 1,2 2361574abaabaaabbbbab正则式和有穷自动机的等价性由以下两点说明：正则式和有穷自动机的等价性由以下两点说明：1. 对于对于上的上的NFA M =正则式正则式R，使，使L(M)=L(R)2. 对

39、于对于上的正则式上的正则式R= NFA M，使，使L(R)=L(M)NFA M=(K , , f , S, Z)=正则式正则式R第一步：在第一步：在M的状态图上增加两个新状态的状态图上增加两个新状态: x和和y 令令 f(x, )=S，f(Z, )=y 形成与形成与M等价的等价的M, M= (Kx,y, , f, x, y)第二步：利用如下规则消除第二步：利用如下规则消除K中所有状态。得到：中所有状态。得到： Ryx12R13R21 R1 R231.1 R1|R2212R1R22. R212R13R3*1 R1R2R333.a,bbb40a,b2a,b31aa0a,ba,b42a,bbb31

40、aaxy例例4.10 求例求例4.6 NFA M的正则式的正则式R第一步，加新状态第一步，加新状态 x和和y0a|bbbaaxa|b42a|byaa(a|b)*0a|bxybb(a|b)*0a|bxy(aa|bb)(a|b)*xy(a|b)*(aa|bb)(a|b)*第二步，逐步消去状态，得正则式第二步，逐步消去状态，得正则式R最后得正则式：最后得正则式：R= (a|b)*(aa|bb)(a|b)*正则式正则式R= NFA M第一步：令：第一步：令：Ryx第二步：利用如下规则分解第二步：利用如下规则分解R： ikR1jR2i R1 R2j1.i R1|R2jijR1R22. R2ik j *i

41、 R2j3.说明：书中给出的转换方法带有概念性的特点，可不看。说明：书中给出的转换方法带有概念性的特点，可不看。例例4.11 为为R=(a|b)*abb 构造构造NFA N第一步：第一步：(a|b)*abb(a|b)*abbabba|b50b1a,b24b3a第二步：第二步：3型文法型文法=NFA设设3型文法型文法: G =（VN，VT，P，S）构造的构造的NFA：A=( VNZ ,VT , f , S , Z)其中：其中：AtB G = f(A , t)=B /t VT At G = f(A , t)=Z例例4.12 GS=NFA M S aaA S bbB S A aB A bA B a

42、S B bA B abSAaZBbabFA = 3型文法型文法设设DFA M =( S , , f , S0 , F )构造的构造的3型文法型文法: G=(S , ，P，S0)其中：其中： f(A , t)=B = AtB Z F = Z例例4.12 DFA M= GAABaDbCabbab A aaB A bbD B bC C aaA C bD C D aaB D bD D设计词法分析程序目前存在两种途径：设计词法分析程序目前存在两种途径：1. 用用DFA人工构造词法分析程序；人工构造词法分析程序；2. 使用词法分析程序的自动生成器构造词法分析程序。使用词法分析程序的自动生成器构造词法分析程

43、序。用用DFA人工构造词法分析器有两种方法：人工构造词法分析器有两种方法： 1.1.利用利用DFA的状态转换表；的状态转换表； 2.2.利用状态转换图手工编制词法分析程序。利用状态转换图手工编制词法分析程序。 l,d;+3dd724:=598l空白空白106 l d + ; : = 0 0 1 2 3 4 5 err 1 6 1 1 6 6 6 6 6 2 7 7 2 7 7 7 7 7 3 4 5 9 9 9 9 9 9 8 9 6 7 8 9 状态状态转换图及转换图及状态状态转换表：转换表：l,d;+3dd24:=56l空白空白01 l d + ; : = 0 0 1 2 3 4 5 e

44、rr 1 1 1 2 2 3 4 5 6 6 改进的状态改进的状态转换图及转换图及状态状态转换表转换表(1)(1) 若用若用T T代表状态代表状态转换表转换表，则利用状态，则利用状态转换表转换表的实现程序的实现程序可构造如下：可构造如下： State=InitStateState=InitState；/取开始状态取开始状态 String=“”; /把存放单词的变量清空把存放单词的变量清空 getc(ch)getc(ch)； /循环读单词的第一个非空白符循环读单词的第一个非空白符号号 while(T(State,ch)while(T(State,ch)error&cherror&chEOF) E

45、OF) String=String ch; /组合单词组合单词 State=T(State,ch)State=T(State,ch)； /进行状态转换进行状态转换 getc(ch)getc(ch)； /读后续符号读后续符号 if (Stateif (StateFinalStatesSet) Ok(putc(ch) else ErrorFinalStatesSet) Ok(putc(ch) else Error；其中：其中：errorerror包含正常结束和非正常结束两层含义包含正常结束和非正常结束两层含义 EOFEOF表示文件结束表示文件结束 putc(ch):putc(ch):表示源程序文

46、件指表示源程序文件指针针向后退一个字符位置向后退一个字符位置使用状态转换图实现使用状态转换图实现DFA的思想是，把状态转换图直接的思想是，把状态转换图直接视为识别算法，每个状态对应带标号的视为识别算法，每个状态对应带标号的if语句，有向边对语句，有向边对应于应于goto转向。如果用状态名直接代表标号名，其实现方转向。如果用状态名直接代表标号名，其实现方法如下：法如下： Si： getc(ch)； if(ch=a) goto Sj； else if(ch=b) goto Sk； else Error()； kaijbSi：getc(ch)； if(ch=a) goto Sj； else if(

47、ch=b) goto Sk； else OK；ikajb其中：其中：Error表示非正常其他符号表示非正常其他符号4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具l,d;+3dd724:=598l空白空白106S0: getc(ch)；/循环读一非空白符循环读一非空白符 if(ch=字母字母) goto S1； else if(ch=数字数字) goto S2； else if(ch=+) goto S3； else if(ch=;) goto S4； else if(ch=:) goto S5； else Error()； S1: getc(ch)； if(ch=字母字母|数字数

48、字) goto S1； else goto S6；S2: getc(ch)； if(ch=数字数字) goto S2； else goto S6；S3: /输出输出“+”的的TOKENS4: /输出输出“;” 的的TOKENS5: getc(ch)； if(ch=) goto S8； else goto S9；S6: /输出输出“保留字保留字”/“标识符标识符”的的TOKENS7: /输出输出“常数常数” 的的TOKENS8: /输出输出“:=”的的TOKENS9: /输出输出“:” 的的TOKENl,d;+8dd729:=51112l空白空白1061043改进的状态改进的状态转换图转换图(2)(2)：使用词法分析程序的自动生成器使用词法分析程序的自动生成器LEX构造词法分析程序构造词法分析程序:LEX编译系统编译系统 LEX 源程序源程序 Lex.1Lex.yy.ca.outC编译程序编译程序Lex.yy.ctokena.out输入串输入串P72：1(3)、2、3、4(a)、5P73：7（不需要做最小化）、8

文档来源：https://www.renrendoc.com/paper/212469640.html

文档标签：第4章词法分析2013 词法分析 2013

第4章词法分析2013

下载地址

文档大全热门下载