第4章 词法分析ppt课件.ppt

《第4章 词法分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章 词法分析ppt课件.ppt（68页珍藏版）》请在三一办公上搜索。

1、第4章 词法分析,本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。,本章重点,单词的描述工具,单词的识别系统,设计和实现词法分析程序,首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。,描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。,词法分析程序,实现词法分析（lexical analysis）的程序称为词法分析程序（或扫描器）。,对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再

2、把它们转换成长度统一的标准形式属性字（TOKEN）。,词法分析程序的主要任务：,词法分析是编译过程中的第一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,源程序,词法分析程序,语法分析程序,Token,get token,.,词法分析程序和语法分析程序的关系,词法分析工作从语法分析工作独立出来的原因：,简化设计,改进编译效率,增加编译系统的可移植性,4.1 对于词法分析器的要求,4.1.1 词法分析器的功能和输出形式,功能：输入源程序，输出单词符号。,单词符号是一个程序语言的基本语法符号。,单词的分类（五类）：,(1)

3、关键字：由程序语言定义的具有固定意义的标识 符。也称为保留字或基本字。,(2)标识符：用来表示程序中各种名字的字符串。,(3)常 数：常数的类型一般有整型、实型、布尔型、文字型。,(4)运算符：如+、*、/等。,(5)界限符：如逗号、分号、括号等。,一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。,词法分析器所输出的单词符号常常表示成如下的二元式：,（单词种别，单词符号的属性值）,单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则直按类型（整、

4、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。,如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。,单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。,在教材中

5、，我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。,考虑下述C十代码段：while（ij）i；,经词法分析器处理后，它将被转换为如下的单词符号序列：,while，,（，,id，指向i的符号表项的指针,，,id，指向j的符号表项的指针,），,id，指向i的符号表项的指针,，,；，,4.1.2词法分析器的设计,我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。,一、输入、预处理,词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词

6、符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。,某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。,注解部分仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。,空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。,我们可以构造一个预处理子程序，它能够完成上面所述的任务。,预处理的主要工作：,二、单词符号的识别：超前搜索,词法分析器的结构如图4.1所示。,图4.1 词法分析器,三、状态转换图,状态转换图是一张有限方

7、向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。例如，图4.2（a）表示：在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为Y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。,1,2,3,X,Y,图4.2（a）转换图示例,一个状态转换图可用于识别（或接受)一定的字符串。,例如，识别标识符的转换图如图4.2（b）所示。,图4.2（b）识别标识符的转换图,图4.2（c）识别整数的转换图,图4

8、.2（d）识别FORTRAN实型常数的转换图,4.2 正规表达式与正规集（正规语言）,程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。,正规表达式是典型的词法规则描述工具。,正规式,定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，,正规式也称正则表达式。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。,和都是上的正规式，它们所表示的正规集分别为和；对任何a

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

10、“”、“”和“”都是左结合的。,“”读为“或”；,例子,令=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组成 的串,讨论下面两个例子,例4.2 有=d，.，e，+，-,则上的正规式 d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为09的数字。,结论：程序设计语言的单词都能用正规式来定义。,例4.1 令=l，d，则上的正规式 r=l(ld

11、)定 义的正规集为:l,l l,l d,l d d,其中l代表字母,d代表数字,正规式 即是 字母(字母数字),它表示的正规集中的每个元素的模式是“以字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则。,正规式的等价性,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。,例如：e1=(ab)，e2=ba，e1=e2,又如：e1=b(ab),e2=(ba)b，e1=e2,e1=(ab),e2=(ab)，e1=e2,设U,V,W为正规式，正规式服从的代数规律有：,1.UV=VU“或”服从交换律,2.U(VW)=(UV)W“或”的可结合律,

12、3.(UV)W=U(VW)“连接”的可结合律,U(VW)=UVUW(VW)U=VUWU分配律,5.U=U,U=U 是“连接”的恒等元 素零一律,6.UU=UU=UUU“或”的抽取律,4.3 有穷自动机,有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)。,关于有穷自动机讨论

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

14、态。,4.s0 K是唯一的一个初态；,二、一个DFA 的例子：,DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q,显然，一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，即k行a列的 矩阵元素表示f（k，a）的值。这个矩阵称为状态转换矩阵。,对于上例，有如下状态转换矩阵,注意：在状态矩阵中 初态结点的旁边标以；终态结点旁边标。,f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，

15、b）=Vf（Q，b）=Q,一个DFA也可表示成一张（确定的）状态转换图。,注意：初态结点的旁边标以；终态结点则用双圈表示。,假定DFA M含有 m个状态和 n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。,S,U,Q,V,a,a,b,b,b,a,a,b,对于*中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字符串等于，则称可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）D

16、FA M所能识别的字的全体记为L(M)。,如有=abb，显然可为上例的DFA M所识别。,如果一个DFA M的输入字母表为，则我们也称M是的一个DFA。,换言之：,若t*，f(S，t)=P，其中S为DFA M的初态，PZ，Z为终态集。则称t 可为DFA M所接受（识别）。,结论：上的一个字集V*是正规的，当且仅当存在上的DFA M，使得VL（M）。,*上的符号串t 在DFA M上运行:,一个输入符号串t，（将它表示成T t1的形式，其中T，t1*）在DFA M=（K，f，S，Z）上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）,其中QK;扩充转换函数f 为 K*K上的映射，且：f（k

17、i，）=ki,例：证明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属于终态。得证。,三、DFA的确定性表现两个方面：,1.映射f：KK是一个单值函数。也就是说，对任何状态sK和输入符号a，f（s，a）唯一地确定了下一状态。从转换图的角度来看，假定字母表含有n个输入字符，那么，任何一个状态结最多只有n条弧射出，而且每条弧以一个不同的输入字符标记。,2.DFA有且仅有唯一的一个初态s0K。,4.3.2 非确定的有穷自动机NFA,1.K是一个有穷集，它的每个元

18、素称为一个状态；,2.是一个有穷字母表，它的每个元素称为一个输入符 号，所以也称为输入符号表；,3.f 是状态转换函数，是在K*K的子集的映射，即，f:K*2K；表明在某状态下对于某输入符号可能有多个后继状态；,5.Z K是一个终态集（可空）。,4.S K是一个非空初态集；,一、NFA定义：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，f，S，Z）,其中:,二、一个NFA 的例子：,NFA M=（S，P，Z，0，1，f，S，P，Z）其中：f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z,矩阵表示,具有转移的不确定的有穷自动机,对任何一个具有转移的

19、不确定的有穷自动机NFAN，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。,定理：,与上例等价的一个NFA：,c,类似DFA,对NFA M=K，f，S，Z也有如下定义：,*上的符号串t在NFA M上运行：一个输入符号串 t，（我们将它表示成T t1的形式，其中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，若存在一条从某一初态结到

20、某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。,结论：,NFA M所能接受的符号串的全体记为 L(M)。,上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。,4.3.3 NFA与DFA的等价性：,显然，DFA是NFA的特例。,对于每个NFA M，存在一个DFA M，使得L(M)=L(M)。对每个NFA M存在着与之等价的DFA M。,即：对于任何两个有穷

21、自动机M和M，如果L(M)=L(M)，则称M与M是等价的。,有一种算法，将NFA转换成接受同样语言的DFA。这种算法称为子集法。与某一NFA等价的DFA不唯一。,从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态。,DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.,一、NFA确定化算法（NFADFA的转换）:,假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：,1.M的状态集S由K的一些

22、子集组成。用S1 S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1 S2；,2 M和N的输入字母表是相同的，即是；,转换函数是这样定义的：d(S1 S2,.Sj,a)=R1R2.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,二、定义对状态集合I的几个有关运算：,1.状态集合I的-闭包，表示为-closure(

23、I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。,状态集合I的任何状态S都属于-closure(I)。,2.状态集合I的a弧转换，定义状态集合J表示为 J=move(I,a)，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。,Ia=-closure(J)=-closure(move(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,3,4,5,6,7,8；,三、构造NFA N的状态K的子集的算法：,假定所构

24、造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。,开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。,2.while（C中存在尚未被标记的子集T）do 标记T；for 每个输入字母a do U:=-closure(move(T,a)；if U不在C中 then 将 U作为未标记的子集Ti加在C中,例子,a,a,等价的DFA,a,4.3.4确定有穷自动机的化简,说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。即用一个状

25、态代替所有与其等价的状态。,所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,DFA的最小化就是寻求最小状态DFA,1.没有多余状态(死状态)；2.没有两个状态是互相等价（不可区别）。,两个状态s和t可区别：不满足兼容性同是终态或同是非终态；传播性从s出发读入某个aa和从 t 出发读入某个a到达的状态等价。,一、最小状态DFA的含义：,两个状态s和t等价：如果由 s 出发能导出的所有串的集合与 t 出发能导出的所有串的集合相等，我们称状态 s 与状态 t 是等价的。,例子,C和D同是终态，读入a到达C和F，C和F

26、同是终态，C和F读入a都到达C，读入b都到达E。C和D等价。,a,二、“分割法”（逐步分组试探法）,DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。算法假定每个状态射出的弧都是完全的,否则，引入一个新状态，叫死状态，该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己。,三、DFA的最小化算法,设有DFA M=（K,f,k0,kz）,最小状态DFA M1.因为不难证明，如果si是非终结状态，而sj是终结状态，那么si和sj一定互不等价（根据等价的定义可知，它们导出的符号

27、串集不同）。所以开始可以把K中的终态和非终态分开，分成两个子集，形成一个基本划分：P2I1，I2（I1I2K，I1I2）2.若此两个子集还可以进行划分，则作进一步的划分，形成Pm,假定到某个时候Pm已经含有m个子集，记为：PmI1，I2，Im，设s和s是Ii中的任意两个状态，如果对某个a,存在Ij，使 f(s,a),f(s,a)Ij，则称s和s关于a是拟等价的。如果存在s，sIi，使得对字母表中的某个符号a,s和s不为拟等价，则我们说Ii是可分的。换句话说，令Ii s1，s2,，sn，如果对某个a，使得Iai f(s1,a)，f(s2,a)，f(sn,a)不全落在现行Pm的某一个子集Ij之中；

28、即Iai这个集合中的元素分别属于I1，I2，Im中的几个不同集合，则Ii可分为几个集合（至少可一分为二）。,3转2,上述过程务必一再重复，直到P中的每个集合均是不可再分时为止。此时，P所含的集合数不再增加，即P中的每个集合中的状态互相等价，而不同集合间的状态互不等价。4.为P中的每一组选一代表，这些代表构成M的状态。把原来导入非代表状态的弧均导入其代表即可，即若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r，M的开始状态是含有S0的那组的代表，M的终态是含有F的那组的代表。5.去掉M中的死状态。,例：有DFA M见右图，求其极小化后的DFA M。,4.4 正规式

29、与有穷自动机的等价性,一、定理：对于上的NFA M，可以构造一个上的正规式R，使得L（R）=L（M）。对于上的任一个正规式R，可以构造一个上的NFA M，使得L（M）=L（R）。,二、把上的NFA M转换为一个上的正规式R,转换方法：我们把状态转换图的概念拓广，令每条弧可用一个正规式标记。1.在M的状态图上加进两个结点x、y。从x结点用弧 连接到M的所有初态结点，从M的所有终态结点弧 连接到y结点。形成一个与M等价的M，M只有一个初态和一个终态。,2.逐步消去M中的所有结点，直至只剩下x结点和y结点。在消结过程中，逐步用正规式来标记弧，其消结规则如下：,最后x结点和y结点之间的弧上的标记就是所

30、求的正规式R。,例：有NFA M如图，求其等价的正规式R。,三、从上的正规式R 构造一个上的NFA M，使得L(M)=L(R),首先，对正规式R构造如下拓广转换图：,然后通过对R进行分裂和加进新结点的办法，逐步把这个图转变为：每条弧标记为中的一个字母或，其转换规则如下：,在整个分裂过程中，所有新结点均采用不同的名字，保留x和y为全图的唯一初态结点和终态结点，至此我们就可以得到一个与R 等价的NFA M。,4.5 正规文法与有穷自动机的等价性,一、定理：对于给定的正规文法GR，可以直接构造一个NFA M，使得L（M）=L（R）。对于上的任一个NFA M，可以直接构造正规文法GR，使得L（R）=L

31、（M）。,二、把给定的正规文法GR转换为一个上的NFA M构造规则:,设GR=（VN，VT，P，R），NFA M=（K，f，S，Z）,1.令=VT；2.K=VN，S=R；即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态；3.增加一个新状态Z，作为NFA M 的终态，ZK；4.对G中的形如AtB（其中t为终结符或；A和B为非终结符）的产生式，构造M的一个转换函数f（A，t）=B；5.对G中的形如At（其中t为终结符或；A和B为非终结符）的产生式，构造M的一个转换函数f（A，t）=Z；,三、把给定的上的NFA M转换为一个正规文法GR的构造规则:,设NFA M=（K

32、，f，S，Z），GR=（VN，VT，P，R），,1.令 VT=；2.令VN=K即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态；3.令R=S（如果M有多个初态，应先拓广自动机，引入新初态x）；4.对M 的终态Z增加一个产生式：Z；5.对M的每一个转换函数f（A，t）=B可写G的一个产生式AtB（其中t为终结符或；A和B为非终结符）；,4.6 词法分析程序的自动构造,词法分析总控程序见图4.15。,界限符,运算符,字母,数字,结束符“#”,开始,Char是什么？,初始化,标识符和关键字词法分析子程序,无符号数词法分析子程序,运算符词法分析子程序,界限符词法分析子程

33、序,结束,图4.15 词法分析总控程序,若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图4.16，构造自动机见图4.17。,图4.17 无符号数的自动机,开始,0N，P，j;1e,数字d;N*10+dN,是数字？,Y,N,Y,N,整型量标记C1,是吗？,是e吗？,是吗？,1e,Y,N,Y,N,是数字？,Y,数字d;N*10+dN；j+1j,是数字？,Y,ERROR,N,N,实型量标记C1,是数字？,Y,数字d;P*10+dP,Y,ERROR,N,N,实型量标记C1,N*10e*P-j t,结束,Y,N,整数部分,小数部分,是吗？,是数字？,指数部分,N,图4.18 无符号数词法分析流程图,最后可得到无符号数分析算法流图见图4.18。,实验题目：单词的词法分析程序设计 作业72页练习：2题，4题,