ct1312.2.ppt

第二章词法分析,词法分析概述正则表达式自动机理论词法分析器的设计与实现,3有限自动机,确定有限自动机DFA非确定有限自动机NFANFA到DFA的转换DFA的化简,2,3,4,5,待机,待选择,冲调,待取,不足,投币,投币,选择恰当/金额充足,付咖啡/找零钱,取咖啡/取零钱,金额不足,超时,退款,退款,超时,3.1确定有限自动机,定义1：一个确定有限自动机DFA为一个五元组(,S,f,s0,Z)，其中：是有穷字母表，每个元素称为一个输入字符；S是一个有穷集，它的每个元素称为一个状态；f是在SS上的单值转换函数；s0S是唯一的一个初始状态；ZS，是终止状态集，又称为接受状态集。,6,7,0,1,2,3,4,c,c,e,f,g,d,b,a,a,b,0,3.1.1DFA实例1,3.1.1DFA实例2,DFAM=(a,b,S,U,V,Q,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,8,3.1.2DFA的两种表示方式,状态转换图结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。状态转换矩阵可用二维数组描述。标识出初始状态和终止状态。若DFA中有f(SI,a)=SJ，则：Trans(SI，a)SJ,9,3.1.3DFA接受的字符串,定义2：对于*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t为DFAM所接受（识别）的字符串。DFAM所能接受的字符串的全体记为L(M)称为M所能接受（识别）的语言。,10,思考,试用自动机描述银行ATM机的状态转换。确定有限自动机名字中的“确定”二字含义、用途、局限？,11,3.1.4DFA的确定性,初始状态唯一。转换函数f:SS是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(s,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。没有空边，即不接受任何输入就进行状态转换（没有输入为，有时用表示的边）。,12,3.1.5DFA的局限,13,3.2非确定有限自动机,定义3：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,f,S0,TS).其中是字母表SS是状态集f是转换函数f:SS()2SSS0是初始状态集TS是终止状态集,14,3.2.1NFA接受的字符串,定义4：设A是一个NFA，A=(,SS,f,S0,TS)则定义L(A)为从任意初始状态到任意终止状态所接受的字符串集合。L(A)=|s0s,s0S0sTS一个NFA的例子,S,P,Z,0,0,1,1,1,1,15,3.2.2等价和NFA的确定化转换,自动机等价设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2)，则称A1和A2等价。NFA到DFA的转换（确定化）定理：对于每一个非确定自动机A，存在一个确定自动机A，使得L(A)=L(A)。,16,3.2.2.1NFA的一种确定性方法,子集法已知NFA:A=(,S,f,S0,Z)构造DFA:A=(,S,f,S0,Z)令A的初始状态为S0=S1,S2,Sk,其中S1Sk是A的全部初始状态。若X=S1,Sm是A的一个状态，a则定义f(X,a)=f(S1,a)f(S2,a)f(Sm,a)=Q，将Q加入S，重复该过程，直到S收敛。若Y=S1,Sn是A的一个状态,且存在一个Si是A的终止状态，则令Y为A的终止状态。,17,NFA确定化实例,18,1,3,2,5,6,4,带“空”边的自动机,19,0,1,2,space,D,+,-,.,D,4,D,3,闭包？！,在数学中，一个集合被称为在某个运算下闭合，如果在这个集合的成员上的运算生成这个集合的成员。如自然数之与减法。当一个集合S不闭合在某个运算下的时候，我们通常可以找到包含S的最小的闭合集合。这个最小闭合集合被称为S的(关于这个运算的)闭包。如在自然数集的减法下的闭包，是整数集。,20,3.2.2.2带空边的NFA的确定化,定义5：设I是NFA的状态集的子集，则I的闭包为：_CLOSURE(I)=Iq|f(p,)=q,p_CLOSURE(I)定义6：设I是NFA状态集的子集，则Ia=_CLOSURE(J)，J=q|f(p,a)=q,pI,21,修改后的子集法已知A：NFA,构造A:DFA令A的初始状态为I0=_CLOSURE(S1,S2,Sk),其中S1Sk是A的全部初始状态。若I=S1,Sm是A的一个状态，a则定义f(I,a)=Ia将Ia加入S，重复该过程，直到S收敛。若I=S1,Sn是A的一个状态,且存在一个Si是A的终止状态，则令I为A的终止状态。,22,带空边的NFA确定化的例子,23,I0=1,2I1=I0a=2,4,5,6,7I2=I0b=3,8I3=I1a=I4=I1b=3,8,9I5=I2a=9I6=I2b=I7=I4a=9=I5I8=I4b=,24,DFAM=(,I0,I1,I2,I4,I5,f(I0,a)=I1,f(I0,b)=I2,f(I1,b)=I4,f(I2,a)=I5,f(I4,a)=I5,I0,I1,I4,I5),3.3DFA化简（极小化）,状态等价：对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。无关状态：从有限自动机的开始状态开始，任何输入序列都不能到达的状态。最小DFA：如果DFA中没有无关状态，也没有彼此等价的状态，则称该自动机是最小的。,25,3.3.1状态分离法,将DFA的所有状态K按终态和非终态划分成两个子集Z与K-Z，构成初始化分，记作：=Z,K-Z。设当前的划分中已经含有m个子集:=I1,I2,Im对于每一个子集Ii=Si1,Si2,Sin及每一个a，设Iin=f(Ii,a)=f(Si1,a)f(Si2,a)f(Sin,a)若Iin中的状态分别落在中p个不同的子集，则根据转移状态相同与否将Ii分为p个子集得到新的划分new。若new,则将new作为重复2，直到不能划分。将最后所得到的划分中的每个子集看成一个状态，对边作相应修改，确定开始状态和结束状态。,26,3.3.2DFA化简例1,27,思考：将如下DFA化简,28,29,S,B,A,C,D,E,F,b,a,b,b,a,a,a,b,C,D,E,F,3.4正则表达式与FA等价,定理：对任一确定有限自动机A，存在一正则表达式e,使得L(A)=L(e),反之亦然。关系图：,30,DFA,正则表达式,NFA,X,W,3.4.1正则表达式到DFA的转换,31,3.4.2DFA到正则表达式的转换,1,2,3,a,b,1,2,a,b,1,2,3,1,3,ab,1,2,a|b,1,3,ab*c,a,b,c,32,思考1,设计DFA以识别能够被4整除的二进制数。,33,思考2,设计DFA以识别所有能被3整除的无符号十进制数。,34,0,1,2,3,6,9,3,6,9,1,4,7,0,2,5,8,2,5,8,1,4,7,2,5,8,3,6,9,1,4,7,思考3,设计识别C语言实型常数的自动机。,35,4词法分析器的设计与实现,设计：单词分类、正则表达式法、自动机法实现：转换矩阵法、转换图法、几个细节问题、构造步骤,36,4.1单词分类,标识符：标识符一般是由字母开头，字母、数字或其它符号的任意组合构成的。常量：用来表示各种常量。主要包括整数常数实数常数、字符串常量等。特殊符号：包括保留字、运算符和界限符。保留字一般是由语言系统自身定义的通常是由字母组成的字符串。运算符表示序中算术运算、逻辑运算、字符运算、赋值运算的确定的字符或字符串。界限符包括各种括号，命令结束符号等。格式符包括EOF，回车等符号。,37,4.1.1正则表达式描述,标识符：L(L|D)*其中L=a-z,A-Z,D=0-9整数：D1D*|0,其中D1=1-9特殊符号：+|；|：|:=|=|保留字：if|else|,38,4.1.2有限自动机描述,按类构造出相应的状态转换图。合并各类单词的状态转换图，构成一个能识别语言所有单词的状态转换图。将各类单词的状态转换图的初始状态合并为一个唯一的初始状态；化简调整状态冲突和对冲突状态重新编号；如果有必要，增加出错状态。,39,自动机设计实例,40,抽象后的DFA,41,0,1,6,7,2,3,4,5,I,D,I,D,D,D,_,D,D,D,D,+,-,.,.,.,_,space,4.2.1状态转换矩阵法,把自动机看作一种数据结构（状态转换矩阵），由控制程序控制字符在其上运行，从而完成词法分析。State=InitState;Read(CurrentChar);While(T(State,CurrentChar)error特点程序短小，但占用存储空间多。,42,4.2.2状态转换图法,每个状态对应一个带标号的case语句转向边对应goto语句特点：程序长，但占用存储空间少,43,a,b,Li:caseCurrentCharofa:gotoLjb:gotoLkother:Error(),i,j,k,4.3特殊处理,保留字识别符合单词、数控制字符、注释语义信息存储,44,4.3.1保留字识别,统一识别事先构造好保留字表。在进行词法分析时，把保留字也当作一般标识符来识别，然后查保留字表，若有，则把它作为保留字来处理；若没有，则按一般标识符来处理。单独识别在自动机中加入识别各个保留字的状态，即把保留字和一般标识符分开来识别而不统一识别。,45,4.3.2符合单词、数,复合单词的识别在程序设计语言中，有一类单词是由两个或者两个以上的符号组成的，这类单词的前缀部分也可以是一个独立的单词。在处理这类单词时要特别加以注意。有时候需要向前看若干个字符才能判断。数的转换词法分析程序应该把字符串转换成数，如“123”应该转换成123。,46,4.3.3控制字符、注释,控制字符的处理无用的空格符和制表符要删掉；字符串内的空格不能删；换行符不能直接删除，而需用于错误定位。注释的处理源程序中的注释没有任何语法和语义上的意义，因此在进行词法分析时可以直接将注释删除，而不必生成其TOKEN。,47,4.3.4语义信息存储,直接在语义信息部分存储语义信息的长度有限制时，可直接将标识符或常