编译原理(第二版)第4章词法分析.ppt

第四章 词法分析,教学要求：本章介绍编译程序的第一个阶段词法分析的设计原理，要求掌握正则文法、DFA、NFA、正规式和正规集的基本概念和词法分析器的设计原理。 教学重点：词法分析器的任务与设计，状态转换图。,4.1 词法分析程序的设计,回顾： 1、词法分析的任务：逐个读入源程序字符并按照构词规则切分成一系列单词。 2、词法分析程序：实现词法分析的程序。 一.词法与语法分析程序的接口方式 1、作为独立的一遍 2、语法分析结合在一起作为一遍,单词符号,单词符号一般可分为下列五种： 基本字（关键字）：begin, end, if, while等 标识符：各种名称，如常量名、变量名、过程名等 常数（量）：25, 3.1415, TRUE, “ABC”等 运算符：如 + - * / =等 界符：逗号，分号，括号等,二、输出表示：（单词种别，单词自身的值） A:=B+2 (id,指向A的符号表的入口指针） (id,指向B的符号表的入口指针) (num, 2) 三、词法分析工作独立的原因： 1、简化设计 2、改进编译效率 3、增加编译系统的可移植性,4.2 单词的描述工具,一、正规文法： 文法G=（VN，VT，P，S），P中每一产生式的形式都为：AaB或Aa，其中AVN ，BVN ，aVT,几类单词的描述,标识符： 标识符l | l字母数字 字母数字l | d | l字母数字| d字母数字 无符号整数： 无符号整数d | d无符号整数 运算符： 运算符 + | - | * | / | = | = 界符： 界符 , | ; | ( | ) |,二、正规式(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、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。,正规式中的符号说明： “”读为“或”（也有使用“+”代替 “” 的） “ ”读为“连接”； “”读为“闭包”（即，任意有限次的自重复连接）。 在不致混淆时，括号可省去，但规定算符的优先顺序为：“”、“ ”、“” 。 连接符“ ”一般可省略不写。 “”、“ ”和“” 都是左结合的。 正规集是正规语言的另一种表示。 如：字母(数字|字母) 表示标识符。,例令=a，b， 上的正规式和相应的正规集的例子有： 正规式 正规集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,aa, 任意个a的串 (ab) ,a,b,aa,ab 所有由a 和b组成的串 (ab)(aabb)(ab) 上所有含有两个相继 的a或两个相继的b组成 的串,例 =l，d，r=l(ld)定义的正规集: l,ll,ld,ldd,（标识符） 其中：l代表字母,d代表数字,正规式即是 字母(字母|数字) 它表示的正规集是“字母打头的字母数字串”。 例4.3 =d，.，e，+，-,则上的正规式 ： d(.dd )(e(+-)dd) 表示的是无符号数的集合。其中：d为0-9的数字。,（二）两个正规式等价,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (ab)， e2 = ba 又如： b(ab) = (ba)b (ab) = (ab),（三）正规式的运算律,设r,s,t为正规式，正规式服从的代数规律有： 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 “或”的抽取律,三、正规文法到正规式,1. 将正规式转换成正规文法 VT= , SVN ， （1）对正规式r，生成正规产生式 Sr （2）若x和y都是正规式 对形如Axy的正规产生式： AxB，By，BVN 对形如Axy的正规产生式： AxB，Ay，BxB，By，BVN 对形如Axy的正规产生式: Ax，Ay 不断应用上述规则做变换，直到每个产生式右端只含一个VT,对上的正规式r ,存在一个G=(VN,VT,P,S)使得L(G)=L(r) ， 反之亦然。,例 r = a(ad) VT=a,d Sa(ad) SaA A(ad) A(ad)B A B(ad)B B,Gs: SaA A VT=a,d AaB VN=S,A,B AdB BaB BdB B,2. 将正规文法转换成正规式 使用如下规则，最后只剩下一个开始符号定义的产生式，并且右部不含非终结符。 规则1 ：A-xB,B-y = A=xy 规则2： A-xA|y = A=x*y 规则3： A-x, A-y = A=x|y,例如：文法GS为： S-aA, S-a, A-aA, A-dA, A-a, A-d,S=aA|a A=(aA|dA)|(a|d) A=(a|d)A|(a|d) A=(a|d)*(a|d)=(a|d)+ A代入S得：S=a(a|d)+|a S=a(a|d)+|） S=a(a|d)* 所以，对应正规式为：a(a|d)*,4.3 有穷自动机,有穷自动机(也称有限自动机)是识别正规集的装置。,一、确定的有穷自动机（DFA） 1、定义: 一个确定的有穷自动机（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.SK是唯一的一个初态； 5.ZK是一个终态集，终态也称可接受状态或结束状态。,例：,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,（1）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,b,S,U,V,a,a,a,b,a，b,b,（2）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,a,b,S,U,V,U,Q,V,V,U,Q,Q,Q,Q,字符,状态,0,1,0,0,终态行在表的右端标以1，非终态标以0。,2、*上的符号串t在M上运行 一个输入符号串t，（我们将它表示成Tt1的形， 其中T，t1*）在DFA M上运行的定义为： f（Q，Tt1）=f（f（Q，T），t1） 其中QK。 扩充转换函数f，是K*K上的映射，且： f（Q，）=Q,3、*上的符号串t被M接受 t*，f(S，t)=P，其中S为DFA M的开始状态， PZ，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（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),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,定义 N=K，f，S，Z，其中K为状态的有穷非空集， 为有穷输入字母表，f为K* 到K的子集的映射，SK是初始状态集，ZK为终止状态集。,例,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，（我们将它表示成Tt1的形式，其中T，t1*）在NFA M上运行的定义为：f（Q， Tt1）=f（f（Q，T），t1），其中QK. *上的符号串t被NFA N接受（读出、识别） 若t*，f(S0，t)=P，其中S0S，PZ，则称t为NFA M所接受（识别）,具有转移的不确定的有穷自动机NFA f为 K（）到K的子集的映射. 对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。,状态集合I的有关运算：,1、状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合(状态集合I的任何状态S都属于-closure(I)。 2、状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。,三、NFA到DFA的转换,例 I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； -closure(5,3,4)=2,3,4,5,6,7,8； move(1,2,a)=5,3,4,NFADFA的算法：,假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)： 1. M的状态集S由K的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。 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 ,. ,SeS且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,-closure(move(Ti,a),-closure(move(Ti,b),T0= -closure(0) =0,1,2,4,7,1,2,3,4,6,7,8=T1,1,2,4,5,6,7=T2,T1= 1,2,3,4,6,7,8,T1,1,2,4,5,6,7,9 =T3,T2= 1,2,4,5,6,7,T1,T2,T3= 1,2,4,5,6,7,9,T1,T4,T4= 1,2,4,5,7,10,T1,T2,b,0,2,1,3,a,b,a,a,a,a,b,b,b,DFA M,四、DFA的最小化（化简）,最小状态DFA 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 多余状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,消除多余状态,两个状态s和t等价,满足: 一致性同是终态或同是非终态 蔓延性从s出发读入某个a(a)和从 t出发读入某个a到达的状态等价。,状态2和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). DFA的最小化算法的核心： 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.,将下图中的DFA M最小化,1,2,3,4 5,6,7,1,2 3,4,1,2,5,6,7,3 4,5,6,7,4.4 正规式和有穷自动机的等价性,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。,例：,求正规式R,0,3,1,a,b,a,a,a,b,a,b,b,b,x,0,a|b,aa,a