《第4部分词法分析.ppt》由会员分享,可在线阅读,更多相关《第4部分词法分析.ppt(68页珍藏版)》请在三一文库上搜索。
1、第4章 词法分析,词法分析程序的设计 单词的描述工具 有限自动机 正规式和有穷自动机的等价性 正规文法和有穷自动机间的转换 词法分析程序的自动构造工具,返回目录,逐个读入源程序字符并按照构词规则切分成一系列单词。,4.1 词法分析程序的设计,词法分析(lexical analysis),单词是语言中具有独立意义的最小单位,包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段,在语法分析前进行。也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序,源程序,词法分析程序,语法分析程序,Token,get token
2、,.,主要任务:,读源程序,产生单词符号。,滤掉空格,跳过注释、换行符。 追踪换行标志,复制出错源程序。 宏展开,,其他任务:,单词符号,单词符号一般可分为下列五种: 基本字(关键字):begin, end, if, while, var等。 标识符:各种名称,如常量名、变量名、过程名等。 常数(量):25, 3.1415, TRUE, “ABC”等 运算符:如 + - * / =等。 界符:逗号,分号,括号等。,输出表示(单词种别,单词自身的值)。,单词的种别可以用整数编码表示,假如标识符编码为1,常数为2,保留字为3,运算符为4,界符为5。,如:程序段 if i=5 then x=y;在经
3、词法分析器扫描后输出的单词符号和它们的表示如下:,程序段 if i=5 then x=y - 保留字if(3,if) - 标识符i(1,指向i的符号表入口) - 等号=(4,=) - 常数5(2,5) - 保留字then(3,then) - 标识符x(1,指向x的符号表入口) - 赋值号=(4,=) - 标识符 y(1,指向y的符号表入口) - 分号;(5,;),词法分析工作独立的原因:,简化设计,改进编译效率,增加编译系统的可移植性,单词的描述工具,文法G=(VN,VT,P,S),P中每一产生式的形式都为:AaB或Aa,其中AVN ,BVN ,aVT。,几类单词的描述,标识符: 标识符l |
4、 l字母数字 字母数字l | d | l字母数字| d 字母数字,4.2 正则表达式和正规集,正规文法,无符号整数: 无符号整数d | d无符号整数 运算符: 运算符 + | - | * | / | = | 等号 等号 = 界符: 界符 , | ; | ( | ) |,无符号实数: 无符号实数 d 余留无符号数| . 十进小数| e指数部分 余留无符号数 d 余留无符号数| . 十进小数| e指数部分| 十进小数 d 余留十进小数 余留十进小数 e指数部分| d 余留十进小数| 指数部分 d 余留整指数| s整指数 整指数 d 余留整指数 余留整指数 d 余留整指数 | 其中s表示正或负号。
5、如 25.55e+5 和 2.1,正规式(regular expression),正规式和它所表示的正规集 设字母标为,辅助字母表=,。,1。 和都是上的正规式,它们所表示的正规集分别为和;,2。任何a ,a是上的一个正规式,它所表示的正规集为a;,3。假定e1和e2都是上的正规式,它们所表示的正规集分别为L(e1)和L(e2),那么,(e1), e1e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。,4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式,仅由这些正规式所表示的字集才是上的正规集。,说明:
6、 其中的“”读为“或”(也有使用“+”代替 “” 的);“ ”读为“连接”;“”读为“闭包”(即,任意有限次的自重复连接)。在不致混淆时,括号可省去,但规定算符的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。,例4.2 令=a,b, 上的正规式和相应的正规集的例子有: 正规式 正规集 a a ab a,b ab ab,(ab)(ab),aa,ab,ba,bb,a , ,a,a, 任意个a的串,(ab), ,a,b,aa,ab 所有由a和b组成的串,(ab)(aabb)(ab),上所有含有两个相继的a或两个相继的b组成的串,例 =l,d,r=l(l
7、 d) 定义的正规集: l,ll,ld,ldd,,其中l代表字母,d代表数字,正规式,即是字母(字母|数字)*,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则。 例4.3 =d,.,e,+,-,则上的正规式 d(.dd )(e(+- )dd )表示的是无符号数的集合,其中d为09的数字。,两个正规式等价,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。,例如: e1= (ab), e2 = ba,又如: b(ab) = (ba)b (ab) = (ab),正规式的运算律,设r,s,t为正规式,
8、正规式服从的代数规律有: 1。rs=sr “或”服从交换律 2。r(st)=(rs)t “或”的可结合律 3。(rs)t=r(st) “连接”的可结合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r 是“连接”的恒等元素 6。 rr=r r=rrr “或”的抽取律,对于上的正规式r ,存在一个G=(VN,VT,P,S) 使得L(G)=L(r) ,反之亦然。,1. 将正规式转换成正规文法 VT= ,S VN ,生成正规产生式 Sr,正规文法到正规式,(1) 对形如 Axy的正规产生式: AxB By BVN,(2)对形如Axy的正规产生式:AxB Ay BxB
9、By BVN,(3)对形如Axy的正规产生式: A x A y,不断应用上述规则做变换,直到每个产生式右端只含一个VN。,例 r = a(ad) VT=a,d Sa(ad),Gs: SaA A VT=a,d AaB VN=S,A,B AdB BaB BdB B,SaA A(ad),A(ad)B A B(ad)B B,规则一,规则二,2. 将正规文法转换成正规式, S=aAa,例Gs:SaA AaA AdA Sa Aa Ad, A =aAdA a d =(ad)A(ad) =(ad)(ad), S=a(ad)(ad)a =a(ad)(ad) =a(ad), R=a(ad),(1)AxB, By
10、A=xy,(2)AxAy A=xy,(3)Axy A=xy,文法产生式 正规式,4.3有穷自动机,确定的有穷自动机(DFA) 不确定的有穷自动机(NFA) NFA DFA 的转换 DFA的化简,DFA定义: 一个确定的有穷自动机(DFA)M是一个五元组:M=(K,f,S,Z)其中 1。K是一个有穷集,它的每个元素称为一个状态; 2。是一个有穷字母表,它的每个元素称为一个输入符号,所以也称为输入符号字母表; 3。f是转换函数,是在KK上的映射,即,如 f(ki,a)=kj,(kiK,kjK)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态; 4。S
11、K是唯一的一个初态; 5。Z K是一个终态集,终态也称可接受状态或结束状态。,DFA 例:,DFA M=(S,U,V,Q, a,b, f, S, Q) 其中 f 定义为: 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(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(V,a)=U f(S,b)=V f(v,b)=Q f(U,a)=Q f(Q,
12、a)=Q f(U,b)=V f(Q,b)=Q,0,1,0,0,DFA的确定性表现在: 转换函数f:KK是一个单值函数,也就是说,对任何状态kK,和输入符号a,f(k,a)唯一地确定了下一个状态。 从状态转换图来看,若字母表含有n个输入字符,那末任何一个状态结点最多有n条弧射出,而且每条弧以一个不同的输入字符标记。,*上的符号串t在M上运行 一个输入符号串t,(我们将它表示成Tt1的形式,其中T,t1 *)在DFA M上运行的定义为: f(Q, Tt1)=f(f(Q,T),t1) 其中QK 扩充转换函数f,是K*K上的映射, 且: f(Q,)= Q,*上的符号串 t 被 M 接受,对于*中的任何
13、字符串t,若存在一条从初态结到某一终态结的道路,且这条路上所有弧的的标记符连接成的字符串等于t,则称t可为DFA M所接受,若M的初态结同时又是终态结,则空字可为M所接受(识别)。 若t *,f(S,t)=P,其中S为DFA M的开始状态,P Z,Z为终态集。 则称t为DFA M所接受(识别)。,例:证明t=baab被如下的DFA所接受。,DFA M=(S,U,V,Q, a,b, f, S, Q)其中 f 定义为: 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,证明: f(S,baab) =f(f
14、(S,b),aab) =f(V,aab) =f(f(V,a),ab) =f(U,ab) =f(f(U,a),b) =f(Q,b) =Q Q属于终态。得证。,DFA M所能接受的符号串的全体记为L(M) 结论: 上一个字符串集V是正规的,当且仅当存在一个上的确定有穷自动机M,使得V=L(M)。,不确定的有穷自动机NFA,定义 N=K,f,S,Z,其中K为状态的有穷非空集, 为有穷输入字母表,f为K * 到K的子集的映像,SK是初始状态集,Z K为终止状态集。,由此定义可看出:DFA是NFA的特例,DFA与NFA的区别: DFA的初态唯一,NFA的初态不唯一。 DFA的转换函数是单值, NFA的转
15、换函数是多值。,例子,NFA N=(S,P,Z,0,1,f,S,P,Z) 其中 f(S,0)=P f(S,1)=S,Z f(P,1)=Z f(Z,0)=P f(Z,1)=P,状态图表示,矩阵表示,NFA N=(S,P,Z,0,1,f,S,P,Z) 其中 f(S,0)=P f(S,1)=S,Z f(P,1)=Z f(Z,0)=P f(Z,1)=P,*上的符号串t在NFA N上运行 *上的符号串t被NFA N接受(读出、识别) 具有转移的不确定的有穷自动机NFA f为 K ( )到K的子集的映像 对任何一个具有转移的不确定的有穷自动机NFA N,一定存在一个不具有转移的不确定的有穷自动机NFA ,
16、使得L(M)=L(N)。,DFA M=(K,f,S,Z)的行为的模拟程序 K:=S; c:=getchar; while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no),NFA的确定化,DFA是NFA的特例.对每个NFA M一定存在一个DFA ,使得 L(M)=L(M )。 对每个NFA M存在着与之等价的DFA M 。与某一NFA等价的DFA不唯一。,定义对状态集合I的几个有关运算:,1 状态集合I的-闭包,表示为-closure(I),定义为一状态集,是状态集I中的任何状态S经
17、任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。 2 状态集合I的a弧转换,表示为move(I,a)定义为状态集合J,其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。 定义Ia = -closure(J),例 I=1, -closure(I)=1,2; I=5, -closure(I)=5,6,2; move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8;,NFADFA,假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St),使得L(M)=L(N): 1. M的
18、状态集S由K的一些子集组成。用S1 S2. Sj表示S的元素,其中S1, S2,. Sj是K的状态。并且约定,状态S1, S2,. Sj是按某种规则排列的,即对于子集S1, S2= S2, S1,来说,S的状态就是S1 S2;,2. M和N的输入字母表是相同的,即是; 3. 转换函数是这样定义的: D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt,其中 R1 , R2 ,. , Rt = -closure(move(S1 ,S2 ,. , Sj,a) 4. S0=-closure(K0)为M的开始状态; 5. St=Si ,Sk ,.,Se,其中Si ,Sk ,. ,S
19、eS且Si , Sk,. SeKt,构造NFA N的状态K的子集的算法:,假定所构造的子集族为C,即C= (T1, T2,. TI),其中T1, T2,. TI为状态K的子集。 1. 开始,令-closure(K0)为C中唯一成员,并且它是未被标记的。,2. while (C中存在尚未被标记的子集T)do 标记T; for 每个输入字母a do U:= -closure(move(T,a); if U不在C中 then 将U作为未标记的子集加在C中 ,例4.8 将下图的NFA N转换成DFA M,NFA N,初态,终态,DFA M,DFA的最小化(化简),最小状态DFA 没有多余状态(死状态)
20、 没有两个状态是互相等价(不可区别) 两个状态s和t等价:满足 一致性同是终态或同是非终态 蔓延性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。,消除多余状态,s1 s5 s2 s7 s2 s5 s5 s7 s5 s6 s3 s1 s8 s0 s0 s1 s3 s6,0 1,0 1 1 0 0 0 1 1 0,s0 s1 s2 s3 s4 s5 s6 s7 s8,s1 s5 s2 s7 s2 s5 s5 s7 s5 s6 s3 s1 s8 s0 s0 s1 s3 s6,0 1,0 1 1 0 0 0 1 1 0,s0 s1 s2 s3 s4 s5 s6 s7 s8,s1 s5 s2
21、 s7 s2 s5 s5 s7 s3 s1 s0 s1,0 1,0 1 1 0 0 1,s0 s1 s2 s3 s5 s7,如图,状态0和4是可区别的。 状态2和3是可区别的,因为读入b后分别到达2和4,而2和4不是等价的。,DFA M,对于一个DFA M =(K,f, k0,kt),存在一个最小状态DFA M =(K,f,k0,kt),使L(M)=L(M). 算法的核心: 把M的状态集K分成不相交的子集。使得任何不同两子集中的状态都是可区别的,而同一子集中的任何两状态是等价的。 结论 接受L的最小状态有穷自动机不计同构是 唯一的。,将下图中的DFA M最小化,去处多余状态,合并等价状态,正规
22、式和有穷自动机的等价性,1. 对于上的NFA M,可以构造一个上的正规式R,使得L(R)=L(M)。 2.对于上的一个正规式R,可以构造一个上的NFA M,使得L(M)=L(R)。,1. 对于上的NFA M,可以构造一个上的正规式R,使得L(R)=L(M)。 第一步:在M的状态转换图上加进两个结,一个为x结点,一个为y结点。从x结点用弧连接到M的所有初态结点,从M的所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态x和一个终态y。 第二步:逐步消去M中的所有结点,直至只剩下x和y。(消去规则见下页) 最后x和y结点间的弧上的标记则为所求的正规式R。,1,2,3,R1,R2,1,
23、3,R1 R2,1,3,R1,R2,1,3,R1| R2,1,2,3,R1,R3,R2,1,3,R1 R2* R3,消为,消为,消为,例:,求正规式R,a,b,0,3,1,a,b,a,a,a,b,b,b,x,a|b,0,a|b,x,aa(a|b)* |bb(a|b)*,x,(a|b)* (aa |bb)(a|b)*,(aa |bb)(a|b)*,R=(a|b)* (aa |bb)(a|b)*,2.对于上的一个正规式R,可以构造一个上的NFA M,使得L(M)=L(R)。 由正规表达式构造等价的NFA M的方法如下: (1) 将正规表达式R表示成如图所示的拓广转换图。 (2) 对正规表达式采用下
24、图所示的三条转换规则来构造NFA M。,对于给定的正规表达式R,首先将其表示成拓广转换图,其中X为初始状态,Y为终止状态;然后逐步将这个拓广转换图运用三条转换规则不断加入新结点进行分解,直至每条有向边上仅标识有的一个字母或为止,则NFA M构造完成。 注: 采用本办法比教材讲授的办法简单,并且得到的NFA的状态要少。,例:为R=(a|b)*abb构造NFA N,使得L(N)=L(R)。 解一:采用教材讲授的方法。,2,3,5,4,a,b,R=(a|b)*abb,R=(a|b)*abb,2,3,5,4,a,b,1,6,R=(a|b)*abb,继续加上abb即可得到结果。,一共11个状态,解二:,
25、第一步:构造拓广转换图,第二步:不断应用三个规则增加结点和弧,直至每条有向边 上仅标识有的一个字母或为止。,一共6个状态,正规文法和有穷自动机间的转换,采用下面的规则从正规文法G直接构造一个有穷自动机NFA M,使得L(M)=L(G): 字母表与G的终结符集相同; 为G中的每个非终结符生成M的一个状态,(不妨取称相同的名字)G的开始符号是开始状态S; 增加一个新状态Z,作为NFA的状态; 对G中的形如AtB的产生式(其中t为终结符或,A和B为非终结符),构造M的一个转换函数f(A,t)=B; 对G中形如At的产生式,构造M的一个转换函数f(A,t)=Z。,例:与文法GS等价的NFA M,GS:SaA SbB S AaB AbA BaS BbA B,S,A,B,Z,a,a,b,b,a,b,4.4 词法分析程序的自动构造工具,把正规式转换为一个NFA进而转换为相应的DFA,由此构造出词法分析程序。 LEX编译系统,
链接地址:https://www.31doc.com/p-2566754.html