编译原理课件.ppt

课时分配：6学时,教学目的：理解词法分析器功能及形式；熟练掌握词法分析器设计的原理，单词的描述工具，掌握正规文法、正规式、有穷自动机的相关概念及相互转换;掌握运用状态转换图进行词法分析器设计。,教学重、难点：正规文法、正规式、有穷自动机,第四章 词法分析（lexical analysis）,本章知识点(内容),词法分析程序的设计,单词的描述工具,有穷自动机,正规式和有穷自动机的等价性,正规文法和有穷自动机的等价性,词法分析程序的自动构造,编译程序首先是在单词级别上来分析和翻译源程序的。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器,词法分析程序亦称为扫描器。,词法分析程序的设计,首页,结束,一、词法分析器功能和输出形式功能：输入源程序，输出单词符号。程序语言的单词符号一般分为五种：(1)关键字（保留字或基本字）(2)标识符(3)常数（整型、实型、布尔型、文字型等）(4)运算符。(5)界符(逗号、分号、括号、*，*等)。,词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）,单词种别通常用整数编码。1、标识符一般统归为一种2、常数则宜按类型（整、实、布尔等）分种3、关键字可视其全体为一种，也可以一字一种。4、运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。5、界符一般一符一种的分法。,如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那麽，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。【例如】对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。,作为例子考虑下述C+代码段：while(i=j)i-;经词法分析器处理后，它将转换为如下的单词符号序列：=的编码,-,【例如】单词符号 类别编号 标识符 1 常数 2 if3 then 4 else5 program 6 begin7 end 8+9-10*11,单词符号 类别编号/12(13)14 15=16 19:=20;21.22,23,单词种别编码,可使整个编译程序的结构更简沽、清晰和条理化。也可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输人串中识别出一个单词符号，把它交给语法分析器。,词法分析器作为独立子程序,二、词法分析器的设计 1、输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。我们可以设想构造一个预处理子程序，他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。,扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。,图1词法分析器,2、单词符号的识别词法分析器的结构图如图1所示。,当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。,单词的描述工具-正规表达式 单词的识别系统-有穷自动机,首页,结束,单词是程序设计语言中的基本语法符号，正规式给出了字符串的简洁结构表示，因此通常用正规式来描述字符串的词法结构，再利用正规式与有穷自动机之间的等价性，构造出能识别符合词法结构的字符串的有穷自动机，这便是词法分析器的形式化构造方法。,3型文法，又称右线性文法或正规文法(Regular Grammars),其表达式形如：AaB或Aa。绝大部份程序设计语言的单词都能用正规文法来描述。,单词的描述工具,1、正规文法,首页,结束,所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式，用于描述给定3型语言的所有句子。,2、正规式,正规表达式与正规集,正规式和正规集的递归定义：（1）和都是上的正规式，它们所表示的正规集分别为和(2)任何a，a是上的一个正规式，它所表示的正规集为a；(3)假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别为L(U)UL(V),L(U)L（V）（连接积）和（L（U）*（闭包）。仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集。,1、正规式的运算符，|读为“或”，“”读为“连接”，“*”读为“闭包”（即，任意有限次的自重复连接）。2、规定算符的优先顺序为：先“*”，次“”最后”|”。连接符 一般可省略不写。,【说明】,【例】设=0，1，则有,设r,s,t为正规式，则正规式服从如下的代数规则：r|s=s|r(或满足交换律)r|(s|t)=(r|s)|t(或满足结合律)r(st)=(rs)t(连接满足结合律)r(s|t)=rs|rt(分配律)r=r=r(是连接的恒等元素)注意：rssr r|(st)rs|rt,【例】令=a,b其正规式和正规集如下：正规式 正规集 ba*a(a|b)*(a|b)*(aa|bb)(a|b)*,正规集是 所有两个相继的a或相继的b 的字,上所有以a为首的字。,上所有以b为首后跟着任意多个a 的字,【例】令=A,B,0,1,则：正规式 正规集(A|B)(A|B|0|1)*(0|1)(0|1)*,上的“标识符”的全体,上“数”的全体,【说明】若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如：b(ab)*=(ba)*b等价。,正规式和正规文法之间的转换,将上的正规式r 转换成正规文法G=(VN,VT,P,S)方法规则：,(1)令Sr,(2)对形如Axy的产生式，可分解成AxB,By,(3)对形如Ax*y的产生式，可分解成为AxA,Ay,(4)对形如Ax|y 的产生式，可分解为 Ax,Ay,反复利用上述规则，直至所有产生式都符合正规文法的形式。,正规文法到正规式的转换规则,例：将正规文法 GS:SdA|eB AaA|b BbB|c换成正规式。解：步骤如下：(1)由AaA|b，将A转换成a*b；由BbB|c，将 B转换成b*c；(2)由 SdA|eB，将S可转换成(da*b)|(eb*c)故所求正规式为R=(da*b)|(eb*c),有穷自动机,文法是语言的生成系统，而自动机是语言的识别系统，有限自动机理论是描述词法规则的基本理论；一条词法规则表示为一个正规表达式（简称正规式），而一个正规式又可以化为一个确定的有限自动机，这个有限自动机就可以用来识别该词法规则定义的所有单词符号。把程序设计语言的所有词法规则都构造出相应的有限自动机，就得到了一个词法分析器。,有穷自动机(Finite Automata):可准确的识别正规集。分类:(1)确定的有穷自动机(Deterministic Finite Automata,简称DFA)(2)不确定的有穷自动机(Nondeterministic Finite Automata,简称NFA),一、有穷（有限）自动机的定义,1、确定的有限自动机（DFA）是一个五元组 M=(,S,s0,F,)其中：,(1)是一个有穷字母集，它的每个元素称为一个输入字符。(2)S是一个有限集，它的每个元素称为一个状态。（3）是一个从S x 至S的单值部分映射。(s,a）=S。意味着：当现行状态为s、输入字符为a时，将转换到下一个状态S。我们称S为s的后继状态。4）S0S，是唯一的初态。5）FS，是一个终态集（可空）,DFA可以用矩阵表示,DFA也可以表示成一张（确定的）状态转换图。使用状态转换图是设计和实现词法分析程序的一种有效工具，是有限自动机的直观图示。在转换图中，结点代表状态，用园圈表示;状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。,DFA的状态图表示 假设DFA M有m个状态,n个输入字符,则：1、状态图有m个状态结点,每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用上的一个不同字符作标记;2、整张图有唯一的一个初态结点,前面冠以“=”或“-”标记；3、有若干终态结点，用双圆圈或“+”标记；,DFA的矩阵表示 1、行表示状态；2、列表示输入字符；3、矩阵元素表示相应状态行和输入字符后的新状态，即第k行a列为f(k,a)的值；4、用“=”标记行或第一行表示初态；5、终态行右端标以1，非终态行右端标以0。,例如，有DFA M=(0,1,2,3，a,b，0，3)其中为(0,a)1(0,b)2(1,a)3(1,b)=2(2,a)l(2,b）=3(3,a)3(3,b）=3它所对应的状态转换矩阵如表,状态转换矩阵,一个DFA也可表示成一张（确定的）状态转换图,问：有几个状态？几个输入字符？并画出其转换图，L(M)=?。,解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如下图:,这个NFA所能识别的是所有含有相继两个a或相继两个b的字。,【例】右图表示：在状态1下，若输入字符为X，则读进X，并转换到状态2。若输入字符为y，则读进Y，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。,对于*中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于，则称可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则为空字，可以为M所识别。DFA M所能识别的字的全体记为L(M)。,接受(识别),【例】试证串abbc可被图示DFA识别。,证明：f(S,abbc)=f(f(S,a),bbc)=f(f(A,b),bc)=f(f(A,b),c)=f(A,c)=B B为终态，得证。,说明,上的一个字符串集V*是正规集，当且仅当存在着一个上的确定有穷自动机M，使得V=L(M)。,DFA的确定性表现在状态转换函数是一个单值函数，即f(k,a)唯一确定一个后继状态。,2、非确定有限自动机(NFA)一个非确定有限自动机（NFA)是一个五元式 M=(S,S0,F)其中:(1)是一个有穷字母集，它的每个元素称为一个输入字符。（2）S是一个有限集，它的每个元素称为一个状态。（3）是一个从S x*到S的子集的映射，即：S x*2s(4)S0S,是一个非空的初态集；（5）F S，是一个终态集（可空）,一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用*中的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点。某些结点既可以是初态结点也可以是终态结点。,对于*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为的弧）等于,则称可为NFA M所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的通路，那么，空字可为M所接受。,说明,【例】试证串abc可被图示NFA识别,证：f(S,abc)=f(A,bc)=f(A,c)f(C,c)=B 又因为B 终态集B，得证。,DFA与NFA的等价,显然,DFA是NFA的特例。但是，对于每个NFA M存在一个DFA M,使L(M)=L(M）。证明过程如下：(1)假定NFA MS,s0,F，对M的状态转换图进行以下改造：引进新的初态结点X和终态结点Y，X，YS,从X到s0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。对M的状态转换图进一步施行图1 所示的替换其中k是新引入的状态。重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为，或为中的单个字母。将最终得到的NFA记为M，显然L(M）=L(M）。,图1,(2)将M进一步变换为DFA，方法如下：假定I是M 的状态集的子集，定义I的闭包=CLOSURE(I)为:(a)若qI,则qCLOSURE(I)；(b)若q I,那么从q出发经任意条弧而能到达的任何状态q 都属于_CLOSURE（I)；假定I是M 的状态集的子集，a，定义 Ia_CLOSURE(J)其中，J是那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。,假定a1，ak。我们构造一张表，此表的每一行含有k十1列。置该表的首行首列为_CLOSURE(X)。一般而言，如果某一行的第一列的状态子集已经确定，例如记为I，那么，置该行的i十1列为Iai（i1，k)。然后，检查该行上的所有状态子集，看它们是否已在表的第一列中出现将未曾出现者填入到后面空行的第一列。重复上述过程，直至出现在第i1列（i1，.k)上的所有状态子集均已在第一列上出现。因为M 的状态子集的个数是有限的，所以上述过程必定在有限步内终止。,正规式到有限自动机的变换过程是：首先根据正则式构造出非确定的有限自动机，然后用子集法将其确定化，再进行最小化，最后得到一个状态最小的确定的有限自动机。1、将正则式转换成非确定的有限自动机（1）首先把正则式V表示为下图所示,（2）通过对V进行分裂和加进新节点的办法，逐步把这个图转换成每条弧都标记有的一个字符或的图，规则如下图：,正规式和有限自动机的等价性,【例】正规式：R=(a*b)*ba(a|b)*可以画为：,【例】正规式(a|b)*(aa|bb)(a|b)*对应的NFA,2、用子集法将NFA确定为DFA,_,_CLOSURE（I）；,其中，J是所有那些可以从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。,【例】子集法构造出的状态转换矩阵,对上表所有状态子集重新命名得到以下状态转换矩阵,【例】将下图确定化,等价的DFA,a,a,b,对于一DFA来说,其状态数可能并不是最小的.原因是DFA中有些状态是“等价”的.为得到效率高的DFA,需将这些“等价”状态合并,这就是DFA的最小化（或化简）.一个确定有限自动机M的化简是指：寻找一个状态数比M少的 DFA M,使得L(M)=L（M）。在一DFA中,等价状态可合并.,3、确定有穷自动机的化简,最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态等价的条件是：一致性同是终态或同是非终态 传播性从s出发和从t出发读入所有输入符号aa转换到达的状态等价。,C和D同是终态,读入a到达C和F,C和F同是终态,C和D读入b都到达E,D读入b都到达D.因此 C和D等价。,a,a,b,化简方法（分割法）,(1)将S划分为终态集和非终态集，得S=Z,S-Z。(2)递归地分割S中的子集，使得任何两个不同子集的状态都是可区分的，而同一个子集中的状态都是等价的。(3)S中的每个子集合并为一个状态。(4)含原初态的状态为初态；含原终态的状态为终态。,【例】设有DFA M如右图所示：划分状态集为4和 0,1,2,3对于0,1,2,3和输入字符a和b:f(0,a)=1 f(1,a)=1f(2,a)=1 f(3,a)=1f(0,b)=2 f(1,b)=3f(2,b)=2 f(3,b)=4只有状态3在输入为b时映像不在后继状态0,1,2,3中，因此该状态集划分为3和0,1,2对于0,1,2：状态1在输入为b时的后继状态不在0,1,2中，因此划分为1和0,2对于0,2:对于相同输入字符，该子集中每一状态映像得到的后继状态都相同，因此不再可划分,b,对于划分结果4,3,1,0,2，把0,2合并为一个状态，分别标记为新状态3,2,1,0，其状态转换图如图,最后划分为：4 3 1 0,2,【例】化简下图,使其最小化,1、首先划分状态集为S,A,B，C,D,E,F,f(S,a)=A f(A,a)=Cf(B,a)=A,2、将S,A,B分解为S,A,B,【例】构造正规表达式0*(0|10)*0*1、首先构造NFA为,2、用子集法确定化,DFA,（1）终态组为1,2,4，非终态组为3，1,2,4，（2）因为1,2,4为等价状态，可合并。（3）最终的状态集的划分1，3,3、化简（最小化）,b,化简后的DFA：,【例】将图示NFA确定化,重新命名新状态,正规文法与有限自动机的等价性,对于正规文法G和有限自动机M,如果L(G)=L(M),则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：(1)对每一个右线性正规文法G或左线性正规文法M，都存在一个有限自动机(FA)M，使得L(M）=L(G）。(2）对每一个FA M,都存在一个右线性文法Gr和左线性正规文法Gl，使得L(M)=L(Gr)=L(Gl),3G（右线性文法）FA：(1)字母表与G的终结符集相同（VT）；对每个非终结符画一个结点，开始符S为开始结点；(2)增设一个终止结点Z;(3)对形如Ua的规则，画一条从U到Z的a弧;(4)对形如UaW的规则，画一条从U到W的a弧;,正规文法和有穷自动机的等价性,采用下面的规则从正规文法G直接构造一个有穷自动机NFA N，使得L(N)=L(G)：,3G（左线性文法）FA：(1)字母表与G的终结符集相同（VT）;对每个非终结符画一个结点，开始符S为终止结点；(2)增设一个开始结点Z;(3)对形如Ua的规则，画一条从Z到U的a弧;(4)对形如UWa的规则，画一条从W到U的a弧;对左线性文法，则把上述算法中的“开始结点”与“终止结点”互换，且将各弧反向。,【例】对无符号整数文法GN:N:=dN|d可构造状态图：【例】对标识符文法GN:N:=Nd|d可构造状态图：,【练习】构造正则表达式(a|b)*|(bb)*的DFA。,1、词法分析程序的手工设计（1）画框图,（2）由状态图写出词法分析程序将状态图看成通常的程序框图，按如下方法写出相应的词法分析程序。对于状态图中的每一状态（代表一个非终结符）构造一段代码，代码的功能为：1、从输入串中读一个字符2、判明读入的字符与由此状态出发的哪条弧上的标记相匹配，然后转至相匹配的那条弧所指的状态3、均不匹配时便失败,词法分析程序的设计,状态转换图的实现,(1)ch 字符变量，存放最新读进的源程序字符。(2)strToken 字符数组，存放构成单词符号的字符串。(3)GetChar 子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。(4)GetBC 子程序讨程检杳ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符(5)Concat 子程序过程，将ch中的字符连接到strToken之后。6)IsLetter和IsDigit 布尔函数过程，它们分别判断ch中的字符是否为字母和数字。,(7)Reserve 整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）。(8)Retract 子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。(9)InsertId 整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。(10）InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。,状态转换图的实现,对于不含回路的分叉结点来说，可让它对应一个switch语句或一组if.then.else语句。例如，下图状态结点i所对应的程序段可表示为：GetChar(）；if（IsLetter（）状态J的对应程序段；else if（IsDigit（）状态k的对应程序段；else if（ch）状态I的对应程序段；else 错误处理；,对于含回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段。例如，下图的状态结点i所对应的程序段可为：CetChar(）；while（IsLetter(）or IsDigit(）CetChar（）；状态j的对应程序段,2、词法分析程序的自动生成,由专门的构造程序对正则式组成的程序设计语言的符号说明书进行处理，生成一些表（这些表描述了不同语言中单词符号的构成规则），有一个通用扫描算法使用这些表就能实现某特定语言的词法分析程序的功能。,一个 Lex 程序分为三个段：说明部分/*C 和 Lex 的全局声明*/%/*间隔符*/转换规则/*包括模式C 代码*/%辅助过程/*补充的 C 函数*/,Lex 是一种生成扫描器的工具。扫描器是一种识别文本中的词汇模式的程序。,一种匹配的常规表达式可能会包含相关的动作。这一动作可能还包括返回一个标记。当 Lex 接收到文件或文本形式的输入时，它试图将文本与常规表达式进行匹配。它一次读入一个输入字符，直到找到一个匹配的模式。如果能够找到一个匹配的模式，Lex 就执行相关的动作（可能包括返回一个标记）。另一方面，如果没有可以匹配的常规表达式，将会停止进一步的处理，Lex 将显示一个错误消息。Lex 和 C 是强耦合的。一个.lex 文件（Lex 文件具有.lex 的扩展名）通过 lex 公用程序来传递，并生成 C 的输出文件。这些文件被编译为词法分析器的可执行版本。,用 Lex 定义常规表达式,常规表达式举例,标记声明举例,词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。,小 结,作 业,P72 练 习 1（4）、4、7、8、9,