编译原理之词法分析.ppt

《编译原理之词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理之词法分析.ppt（96页珍藏版）》请在三一办公上搜索。

1、第4章 词法分析,本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。4.1 词法分析程序的设计4.2 单词的描述工具（正规式和正规文法）4.3 有穷自动机(单词的识别机制)4.4 正规式和有穷自动机的等价性4.5 正规文法和有穷自动机间的转换4.6 词法分析程序的自动构造,本章重点,单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。,回顾 什么是词法分析程序,实现词法分析（lexical analysis

2、）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序的功能,词法分析程序的功能是读入源程序，输出单词符号。源程序 单词符号“词法”“分析程序”“的”“功能”假如你没有中文分词的概念，你会明白中文句子的含义吗？,词法分析器,词法分析程序的功能,While ij do if ij then i:i-j else j:=jI while，i，j，do，if

3、，i，j,then,i,:=,i,-,j,else,j,:=,j,-,i,词法分析器,4.1.1 词法分析程序与语法分析程序的接口方式,4.1 词法分析程序的设计,源程序,词法分析程序,语法分析程序,Token,get token,4.1.2 词法分析程序的输出,程序语言单词的分类：1关键字(保留字或基本字)：begin,end 2标识符：用来表示各种名字 3字面常数：256，3.14，true,abc 4 运算符：如，、*、/等等 5分界符：如逗号，分号，冒号等,4.1.2 词法分析程序的输出,词法分析程序所输出的单词符号常常用以下二元式表示：（单词种别，单词自身的值）单词的种别是语法分析需

4、要的信息，而单词的值则是编译其它阶段需要的信息。例如：在PASCAL的语句const i=25;yes=1;中的单词25和1的种别是常数，常数的值是25和1。,4.1.3 将词法分析工作分离的考虑,简化设计改进编译效率增加编译系统的可移植性,4.2 单词的描述工具,程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描 述。基于描述工具，实现词法分析程序的自动构造。,4.2.1 正规文法,多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。程序设计语言中的几类单词可用下述规则来描述：L|L L|d|L,d|d|+|-|*|/|=|=|,|;|(|)|.其中L表示az中

5、的任何一英文字母，d表示09中的任一数字。,例4.1 无符号数的正规文法,d|.|ed|.|e|d e|d|d|s d d|其中s表示正或负号+，-。,4.2.2 正规式,正规式也称正则表达式,正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。,正规式和它所表示的正规集,定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，。1.和都是上的正规式，它们所表示的正规集分别为和；2.任何a，a是上的一个正规式，它所表示的正规集为a；,正规式和它

6、所表示的正规集,3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。,正规式和它所表示的正规集,其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都

7、是左结合的。,例4.2,令=a，b，上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab)aa,ab,ba,bba,a,a,任意个a的串,正规式 正规集(ab),a,b,aa,ab 所有由a 和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串,例4.3=d，.，e，+，-,则上的正规式 d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0-9的数字。,例:令=l，d，则上的正规式r=l(ld)定义的正规集为:l,ll,ld,ldd,其中l代表字母,d代表数字,正规式即是字母(字母|数字),它表示的正规集中的每个

8、元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则。含义：上所有由字母开头的串。字母打头的后跟字母和数字任意组合的串,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)b e1=(ab),e2=(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是“连接”的恒等元

9、素零一律6.rr=r r=rrr“或”的抽取律,4.2.3 正规文法和正规式的等价性,一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文法。,一、将上的一个正规式转换成正规文法,将上的一个正规式r转换成文法G=（VN，VT，S，P）。令其中的VT=，确定产生式和VN用如下办法：对任何正规式r，选择一个非终结符S生成产生式Sr，并将S定为G的识别符号。若x和y都是正规式，对形如Axy的产生式，重写成：A xB,B y两产生式，其中B是新选择的非终结符，即BVN,对已转换的文法中的形如A x*y

10、的产生式，重写为：A xBA yB xBB y其中B为一新非终结符。对形如A x|y的产生式，重写为：A xA y不断利用上述规则做变换，直到每个产生式最多含有一个终结符为止。,例4.4 将R=a(a|d)*转换成相应的正规文法。S a(a|d)*S aA A(a|d)*A(a|d)B，A，B(a|d)B，B A aB A dBB aB B dB,二、将正规文法转换成正规式,基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。,例4.5 文法GS，求该文法对应的正规式,S aAS aA aAA dAA aA d,S=aA|aA=(aA|dA)|(a|d

11、)A=(a|d)A|(a|d)A=(a|d)*(a|d)A=(a|d)+S=a(a|d)+|)S=a(a|d)*,4.3 有穷自动机,有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)-DFA不确定的有穷自动机(Nondeterministic Finite Automata)-NFA,关于有穷自动机我们将讨论如下题目,确定的有穷自动机DFA不确定的有穷自动机

12、NFANFA的确定化DFA的最小化,4.3.1 确定的有穷自动机DFA,DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；（状态集）2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；,DFA定义,3.f是转换函数，是在KK上的映射，即，如f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.Z K是一个终态集，终态也称可接受状态或结束状态。,一个DFA 的例子：,例4.6DFA

13、M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q,一个DFA可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“”或标以“-”，终态结点用双圈表示或标以“+”，若 f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；,DFA 的状态图表示,b,f（S，a）=Uf（S，b）=V f（U，a）=Q f（

14、U，b）=V f（V，a）=U f（V，b）=Q f（Q，a）=Q f（Q，b）=Q,一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。,DFA 的矩阵表示,0001,为了说明DFA如何作为一种识别机制,我们还要理解下面的定义,*上的符号串t在DFA M上运行一个输入符号串t，（将它表示成Tt1的形式，其中T，t1*）在DFA M=（K，f，S，Z）上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK 扩

15、充转换函数f为 K*K上的映射，且：f（ki，）=ki,*上的符号串t被DFA M接受M=（K，f，S，Z）若t*，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集。则称t为DFA M所接受（识别）.,例：证明t=baab被下图的DFA所接受。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属于终态。得证。,b,DFA M所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.结论：上一个符号串集V是正规的，当且仅当存在一个上的

16、确定有穷自动机M，使得V=L(M)。,DFA的确定性表现在转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。,4.3.2 不确定的有穷自动机NFA,定义NFA M=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2 K）的一种映射，SK是初始状态集，Z K为终止状态集.,例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1

17、）=Pf（S，1）=S，Z,状态图表示,状态图表示,矩阵表示,矩阵表示,类似DFA,对NFA M=K，f，S，Z也有如下定义,*上的符号串t在NFA M上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在NFA M上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK.*上的符号串t被NFA M接受若t*，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M所接受（识别）,*上的符号串t被NFA M接受也可以这样理解,对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，

18、则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。,4.3.3 NFADFA的转换,从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.,DFA是NFA的特例.对每个NFA N一定存在一个DFA，使得L(M)=L(N)。对每个NFA N存在着与之等价的DFA M有一种算法，将NFA转换成接受同

19、样语言的DFA.这种算法称为子集法.与某一NFA等价的DFA不唯一.,定义对状态集合I的几个有关运算：,1.状态集合I的-闭包 表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合I的a弧转换 表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。,状态集合I的有关运算的例子,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,

20、3,4,5,6,7,8；,NFA DFA（确定化）算法:,假设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的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1 S2,2 M和N的输入字母表是相同的，即是；3 转换函数是这样定义的：d(S1 S2,.Sj,a)=R1R2.Rt 其中 R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4 S0=-clo

21、sure(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 对图4.4的NFA N确定化。,NFA确定化为DFA的过程如下所示,Ia=-closur

22、e(move(I,a)Ib=-closure(move(I,b),DFA M 如图4.6所示,4.3.4 确定有穷自动机的化简,1 什么是多余状态？所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,4.3.4 确定有穷自动机的化简,2 什么是等价状态？两个状态s和t等价：满足兼容性(一致性条件)同是终态或同是非终态传播性（蔓延性条件）对于所有输入符号，状态s和t必须转换到等价的状态里。,一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。说一个有穷自动机是化简了的，即它没有多余

23、状态并且它的状态中没有两个是互相等价的。,DFA的最小化就是寻求最小状态DFA,最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）,C和D同是终态,读入a到达C和F,C和F同是终态,C和F读入a都到达C,读入b都到达E.C和D等价,最小状态DFA,对于一个DFA M=（K,f,k0,kt)，存在一个最小状态DFA M=（K,f,k0,kt)，,使L(M)=L(M).,“分割法”,DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.算法假定每个状态射出的弧都是完全的,否则,引入

24、一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.,例4.9 将图4.8中的DFA M最小化,Step 1:P0=(1,2,3,4,5,6,7),Step 2:P1=(1,2,3,4,5,6,7),Step 3:P2=(1,2,3,4,5,6,7),Step 4:P3=(1,2,3,4,5,6,7),Step 5:令1代表1,2消去2,令6代表6,7消去7.得到图4.8(b)DFA M,4.4 正规式和有穷自动机DFA的等价性,1有穷自动机和正规表达式的等价性 对于上的一个NFA M，可以构造 一个上的正规式R,使得L(R)=L(M)。对

25、于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。,2有穷自动机 NFA正规式,为M添加两个结点的X,Y，X用连接到M的所有初态，Y用连接到M的所有终态。利用下面三条规则：反复三条规则，最后X,Y间的标记就是所求的正规式R。,3.正规式有穷自动机 NFA,(1).“语法制导”方法，即按正规式的语法结构构造。r为正规式，规则如下：r=,构造任一具有空终态集的NFA M,(b)r=,(c)r=a,(2).对于正规式r,r=r1|r2构造的NFA,(3).对于正规式r,r=r1r2构造的NFA,4.对于正规式r,r=r1*构造的NFA,例4.10 以例4.7的NFA M为例，M

26、的状态图如 图4.3所示，求正规式r，使L(r)=L(M).,Step 1.加入x,y结点，分别用弧连接到初态和终态.如图4.9(a)所示M,Step 2.逐步消去M中的结点,消去1,3之后如图4.9(b).,Step 3.逐步消去M中的结点,消去2,4之后如图4.9(c).,Step 4.逐步消去M中的结点,消去0之后如图4.9(d).,Step 5.r=(a|b)*(aa|bb)(a|b)*即为所求.,例4.11 为r=(a|b)*abb构造NFA N,使得L(N)=L(r).,4.5 正规文法和有穷自动机的等价性,(一)正规文法NFA M，L(M)=L(G).M的字母表与G的终结符集相同

27、,=VT为G中的每个非终结符生成一个同名状态，G的开始符号S是开始状态.增加一个新状态Z作为NFA的终态.对G中的形如A tB的规则(其中t为终结符或,A,B为非终结符的产生式)，构造M的一个转换函数f(A,t)=B.对G中形如A t的产生式，构造M的一个转换函数f(A,t)=Z.,例4.12 与文法GS等价的NFA M如图4.11.,GS:S aAS bBS A aBA bAB aSB bAB,G=(A,B,C,D,a,b,P,A),其中P为：A aBA bDB bCC aAC bDC D aBD bDD,(二)NFA M正规文法，L(G)=L(M).对转换函数f(A,t)=B,可写成一产生

28、式：AtB.对可接受状态Z，增加一产生式：Z.,4.6 词法分析程序的自动构造,正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序,词法分析程序的自动构造工具LEX简介,一.原理 单词的结构用正规式描述 正规式 NFA DFA min DFA二.用LEX建立词法分析程序的过程,三.lex源程序 lex源程序由三部分组成声明%翻译规则%辅助过程,声明包括变量，显明常量和正规定义式。翻译规则的形式为：p1 动作1 p2 动作2 p n 动作n,每个pi是正规定义式的名子，每个动作i是正规定义式pi识别某类单词时，词法分析器应执行动作的程序段。用C书写。辅助过程是动作需要的，这些过程用C书写，可以分别编译。词法分析器返回给语法分析器一个单词,把单词的属性值存放于全程变量yylval中。,作业：P72,1.（1）5,本章小结,词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷自动机。在此基础上给出了词法分析程序自动构造工具，如LEX的原理。,