词法分析与有穷自动机.ppt

第3章词法分析与有穷自动机,有穷自动机是构造词法分析程序的理论基础。本章主要介绍词法分析程序的设计原理和构造方法，重点介绍有穷自动机的基本概念以及正规文法、正规表达式与有穷自动机之间的相互关系。,第3章词法分析与有穷自动机,词法分析程序功能,词法分析程序的编写方法,正规文法与有穷自动机,正规式与有穷自动机,语言单词符号的两种定义方式,单词符号及输出单词的形式,词法分析的任务是对字符串表示的源程序从左到右地进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。,3.1词法分析程序的功能,字符串表示的源程序,词法分析器,单词符号,取下一个单词符号,语法分析器,3.2单词符号及输出单词的形式,关键字也称基本字，例如，C语言中的if，else，while,do等,这些字在语言中具有固定的意义，一般不作为标识符使用。,标识符表示各种名字，如变量名、常量名、数组名和函数名等。,语言的单词符号是指语言中具有独立意义的最小语法单位。,3.2单词符号及输出单词的形式,常数各种类型的常数，如整型常数125、实型常数0.718、布尔型常数TRUE等。,运算符如、*、/、等。,分界符如，、；、（、）、：等。,3.2单词符号及输出单词的形式,词法分析程序输出单词的形式,词法分析程序所输出的单词符号通常表示成如下的二元式：,（单词种别，单词自身的值）,3.2单词符号及输出单词的形式,单词种别,单词种别表示单词的种类，它是语法分析需要的信息。,为处理方便通常让每种单词对应一个整数码。,3.2单词符号及输出单词的形式,常数:可统归为一种，也可按类型（整型、实型、布尔型等）分种。,基本字:可将其全体视为一种，也可以一字一种。,标识符:一般统归为一种。,运算符和界符:可采用一符一种的分法，也可以统归为一种。,3.2单词符号及输出单词的形式,单词自身的值,一个种别只含一个单词符号,一个种别含有多个单词符号,(1)对于标识符其自身值是标识符自身的字符串；,(2)常数自身值是常数本身的二进制数值。,值是种别编码,3.2单词符号及输出单词的形式,(3)用指向某类表格一个特定项目指针值来区分同类中不同的单词。,例如,对于标识符用它在符号表的入口指针作为它自身值;常数用它在常数表的入口指针作为它自身的值。,3.2单词符号及输出单词的形式,常数自身的值用常数本身的值(转变成标准二进制形式)表示；,对例子:if(a1)b=100；,假定:,基本字、运算符和界符都是一符一种；,标识符自身的值用自身的字符串表示；,3.2单词符号及输出单词的形式,假设:标识符的种别编码为整数10；常数的种别编码为整数11；基本字if种别编码为2；赋值号的种别编码为17；大于号的种别编码为23；分号的种别编码为26；左括号的种别编码为29；右括号的种别编码为30；则程序段：,3.2单词符号及输出单词的形式,if(a1)b=100；在经词法分析程序扫描后，它所输出的单词符号串是：,（2,）基本字if,（29,）左括号(,（10,a）标识符a,（23,）大于号,（11,1）常数1,（30，）右括号),（10，b）标识符b,（17，）赋值号=,（11，100）常数100,（26,）分号；,3.3单词符号的两种定义方式,正规式,以标识符为例:Il|Il|Id或Il|lTTl|d|lT|dT,以标识符为例:l(l|d)*,正规文法,3.3.1正规式和正规集,设有字母表=a1,a2,an，在字母表上的正规式和它所表示的正规集可用如下规则来定义：,1.是上的正规式，它所表示的正规集是，即空集。,2.是上的正规式，它所表示的正规集仅含一空符号串，即。,3.ai是上的一个正规式，它所表示的正规集是由单个符号ai所组成，即ai。,3.3.1正规式和正规集,4.如果e1和e2是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，则：,(1)e1|e2是上的一个正规式，它所表示的正规集为L(e1|e2)=L(e1)L(e2),(2)e1e2也是上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2),(3)(e1)*也是上的一个正规式，它所表示的正规集为L(e1)*)=(L(e1)*,3.3.1正规式和正规集,正规式中包含三种运算符：连接“”，或“|”和闭包“*”。其中闭包运算的优先级最高，连接运算次之，或运算最低。连结符“”一般可省略不写。这三种运算符均是左结合的。,3.3.1正规式和正规集,例1设有字母表=a,b，根据正规式与正规集的定义，则有：,a和b是正规式，相应正规集为,2.a|b是正规式，相应正规集为,3.ab是正规式，相应正规集为,L(a)=a,L(b)=b,L(a|b)=L(a)L(b)=a,b,L(ab)=L(a)L(b)=ab=ab,3.3.1正规式和正规集,4.(a|b)*是正规式，相应正规集为,例如，a,b*的子集anbn|n1就不是一个正规集，不能用正规式来描述，也不能用正规文法来描述，只能用上下文无关法来描述。,需要指出的是，对a,b*的任一子集不能认为是一个正规集。,L(a|b)*)=(L(a|b)*=a,b*=,a,b,aa,ab,ba,bb,5.ba*是正规式，相应的正规集为,3.3.1正规式和正规集,L(ba*)=L(b)L(a*)=b,ba,baa,baaa,(a|b)*(aa|bb)(a|b)*是正规式，相应正规集为,即上所有含两个相继a或两个相继b组成的串。,L(a|b)*(aa|bb)(a|b)*)=L(a|b)*)L(aa|bb)L(a|b)*)a,b*aa,bba,b*,3.3.1正规式和正规集,例2设=a,b,c,则aa*bb*cc*是上的一个正规式,它所表示的正规集：,L=abc,aabc,abbc,abcc,aaabc,=ambnck|m,n,k1,a+b+c+,3.3.1正规式和正规集,例3设程序语言字母表是键盘字符集合，则程序语言部分单词符号可用如下正规式定义：,关键字if|else|while|do,标识符l(l|d)*l代表az中任一字母,整常数dd*d代表09中任一数字,关系运算符=,3.3.1正规式和正规集,注意:正规式与正规文法之间的区别和联系：,标识符ID=l(l|d)*l代表az中任一字母d代表09中任一数字,Il|Il|Id,3.3.1正规式和正规集,如果正规式R1和R2描述的正规集相同,则我们称正规式R1与R2等价。记为R1R2。,例如，(a|b)*=(a*b*)*;b(ab)*=(ba)*b,3.3.1正规式和正规集,正规式具有如下性质:,1A|B=B|A(交换律),2A|(B|C)=(A|B)|C(结合律),3A(BC)=(AB)C(结合律),4A(B|C)=AB|AC(分配律),5(A|B)C=AC|BC(分配律),6A|A=A,7A*=AA*|=A|A*=(A|)*,8(A*)*=A*,令A,B和C均为正规式，则,3.3.2正规文法与正规式,1.正规文法到正规式的转换,(1)将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。,(2)依照求解规则：,若x=x|(或x=x+)则解为x=*,若x=x|(或x=x+)则解为x=*,以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解。,3.3.2正规文法与正规式,例1设有正规文法G：,试给出该文法生成语言的正规式。,分析首先给出相应的正规式方程组(方程组中用“”代替正规式中的“|”)如下：,Z=0A(1),A=0A+0B(2),B=1A+(3),Z0A,A0A|0B,B1A|,3.3.2正规文法与正规式,将(3)代入(2)中的B得,A=0A+01A+0(4),对(4)利用分配律得,A=(0+01)A+0(5),即正规文法GZ所生成语言的正规式是,Z=0A(1),A=0A+0B(2),B=1A+(3),对(5)使用求解规则得,A=(0+01)*0(6),将(6)代入(1)式中的A，得,Z=0(0+01)*0,R=0(0|01)*0,3.3.2正规文法与正规式,例2设有正规文法G：,AaB|bB,BaC|a|b,CaB,试给出该文法生成语言的正规式。,分析首先给出相应的正规式方程组(方程组中用“”代替正规式中的“|”)如下：,A=aB+bB(1),B=aC+a+b(2),C=aB(3),3.3.2正规文法与正规式,将(3)代入(2)中的C得,B=aaB+a+b(4),对(4)使用求解规则得,B=(aa)*(a+b)(5),(5)代入(1)中的B得,即正规文法GA所生成语言的正规式是,A=(a+b)(aa)*(a+b),R=(a|b)(aa)*(a|b),A=aB+bB(1),B=aC+a+b(2),C=aB(3),3.3.2正规文法与正规式,例3设有正规文法G：,相应的正规式方程组为,ZU0|V1,UZ1|1,VZ0|0,Z=U0+V1(1),U=Z1+1(2),V=Z0+0(3),3.3.2正规文法与正规式,(2)和(3)代入(1)得,Z=Z10+10+Z01+01(4),对(4)使用求解规则得,即正规文法GZ所生成语言的正规式是,Z=U0+V1(1),U=Z1+1(2),V=Z0+0(3),Z=(10+01)(10+01)*,R=(10|01)(10|01)*,3.3.2正规文法与正规式,例4已知描述“标识符”单词符号的正规文法为,lld,根据前述求解规则,可知该文法所描述语言的正规式是l(l|d)*,3.3.2正规文法与正规式,2.正规式到正规文法的转换,(1)令VT=。,(2)对任何正规式R选择一个非终结符Z生成规则ZR并令SZ。,(3)若a和b都是正规式，对形如Aab的规则转换成AaB和Bb两规则，其中B是新增的非终结符。,3.3.2正规文法与正规式,(4)对已转换的文法中,形如Aa*b的规则，进一步转换成AaA|b。,(5)不断利用规则(3)和(4)进行变换，直到每条规则最多含有一个终结符为止。,3.3.2正规文法与正规式,例1将R=(a|b)(aa)*(a|b)转换成相应的正规文法,令A是文法开始符号，根据规则(2)变换为,根据规则(3)变换为,A(a|b)(aa)*(a|b),A(a|b)B,B(aa)*(a|b),3.3.2正规文法与正规式,对B根据规则(4)变换为,根据规则(3)变换为,即前面例2中的文法。,AaB|bB,BaaB|a|b,AaB|bB,BaC|a|b,CaB,Aa*b,AaA|b,转换成,B(aa)*(a|b),3.3.2正规文法与正规式,例2将描述标识符的正规式R=l(l|d)*转换成相应的正规文法,令I为文法的开始符号，根据规则(2)有,根据规则(3)变换为,根据规则(4)变换为,Il(l|d)*,IlT,T(l|d)*,IlT,T(l|d)T|,3.3.2正规文法与正规式,进一步变换为,去掉规则,即前面描述标识符的右线性文法。,IlT,TlT|dT|,Il|lT,Tl|d|lT|dT,3.4正规式与有穷自动机,有穷自动机是具有离散输入与输出系统的一种抽象数学模型。有穷自动机有“确定的”和“非确定的”两类，确定的有穷自动机和非确定的有穷自动机都能准确地识别正规集。,3.4.1确定有穷自动机,确定有穷自动机（DFA）,一个确定有穷自动机M是一个五元组,Q是一个有穷状态集合，每一个元素称为一个状态。,是一个有穷输入字母表，每个元素称为一个输入字符。,M=(Q,f,S,Z),表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj称为qi的一个后继状态。,f是一个从Q到Q的单值映射：,M=(Q,f,S,Z),f(qi,a)=qj(qi,qjQ,a),3.4.1确定有穷自动机,单值函数是指f(qi,a)唯一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同，见下图。,S1,S2,S3,S4,a,b,c,3.4.1确定有穷自动机,SQ，是唯一的一个初态。,ZQ，是一个终态集。,3.4.1确定有穷自动机,M=(Q,f,S,Z),例设DFAM=(q0,q1,q2,a,b,f,q0,q2),其中,状态转换矩阵,f(q0,a)=q1f(q0,b)=q2,f(q1,a)=q1f(q1,b)=q1,f(q2,a)=q2f(q2,b)=q1,3.4.1确定有穷自动机,一个DFA也可以表示成一张状态转换图。,例中DFAM=(q0,q1,q2,a,b,f,q0,q2)的状态转换图如下图所示。,q0,q1,b,b,b,a,a,a,3.4.1确定有穷自动机,对*中的任何符号串，若存在一条从初态结到终态结的道路,在这条路上所有弧的标记连结成的符号串等于,则称为DFAM所识别(或接受)。M所识别的符号串的全体记为L(M)，称为DFAM所识别的语言。,例中的DFAM所识别的语言为L(M)=ba*。,q0,q1,b,b,b,a,a,a,3.4.1确定有穷自动机,3.4.2非确定有穷自动机,非确定有穷自动机（NFA）,一个非确定有穷自动机M是一个五元组,其中：Q,Z意义同DFA，f和S不同于DFA。,M=(Q,f,S,Z),(1)状态转换函数f不是单值函数,它是一个多值函数：f(qi,a)=某些状态的集合,非确定的有穷自动机还允许f(qi,)=某些状态的集合。,由图可知f(S1,a)=S1,S2,S3,(2)SQ，是非空初态集。,S1,S2,S3,S4,a,a,c,a,3.4.2非确定有穷自动机,其中,例设有NFAM=(1,2,3,a,b,f,1,3,2),例中NFAM对应的状态转换矩阵如下表所示。,f(1,a)=3f(1,b)=1,2,f(2,a)=f(2,b)=3,f(3,a)=f(3,b)=2,3.4.2非确定有穷自动机,状态,字符,a,1,b,2,3,3,1,2,2,3,例中NFAM对应的状态转换图如下图所示。,3.4.2非确定有穷自动机,其中,例设有NFAM=(1,2,3,a,b,f,1,3,2),f(1,a)=3f(1,b)=1,2,f(2,a)=f(2,b)=3,f(3,a)=f(3,b)=2,例中NFAM所识别的语言为,L(M)=b*(b|ab)(bb)*,3.4.2非确定有穷自动机,例中NFAM,对符号串=bbb可由3条路来识别。,由NFA的定义可知，同一个符号串可由多条路来识别。,第二条路：状态1状态1状态1状态2；,第一条路：状态1状态2状态3状态2；,第三条路：状态3状态2状态3状态2；,3.4.2非确定有穷自动机,事实上DFA是NFA的特例,即对于每个NFAM存在DFAM,使L(M)=L(M)。因此，我们利用有穷自动机构造词法分析程序的方法是:1.从语言单词的描述中构造出非确定的有穷自动机，2.再将非确定的有穷自动机转化为确定的有穷自动机，3.并将其化简为状态最少化的DFA,4.然后对DFA的每一个状态构造一小段程序将其转化为识别语言单词的词法分析程序。,3.4.2非确定有穷自动机,3.4.3由正规式R构造NFA,输入：字母表上的正规式R,输出：识别(接受)语言L(R)的NFAN,引进初始结点X和终止结点Y，把R表示成拓广转换图,2.分析R的语法结构，用如下规则对R中的每个基本符号构造NFA。,方法：,(1)R=,构造NFA如图所示。,(2)R=,构造NFA如图所示。,(3)R=a(a),构造NFA如图所示。,3.4.3由正规式R构造NFA,(4)若R是复合正规式，则按下图的转换规则对R进行分裂和加进新结,直至每个边上只留下一个符号或为止。,对于,代换为,对于,代换为,对于,代换为,3.4.3由正规式R构造NFA,3.整个分裂过程中,所有新节点均采用不同的名字，保留X，Y为全图唯一初态结和终态结。,3.4.3由正规式R构造NFA,例1试构造识别语言R=(a|b)*abb的NFAN,使L(N)=L(R)。,首先将R表示成如下拓广转换图,从左到右分裂R,3.4.3由正规式R构造NFA,例2试构造识别标识符的NFA，描述标识符的正规式R=l(l|d)*,首先将R表示成如下拓广转换图,从左到右分裂R,3.4.3由正规式R构造NFA,例3试构造正规式R=0(l*)*|01的NFA。,首先将R表示成如下拓广转换图,从左到右分裂R,首先利用正规式的等价性化简正规式,(l*)*=1*,R=01*|01=0(1*|1)=01*,(A*)*=A*,A|A*=A*,3.4.3由正规式R构造NFA,3.4.4NFA确定化为DFA的方法,对于一个NFA，由于状态转换函数f是一个多值函数，因此，对于它们有,基本思想:,f(q,a)=q1,q2,q3,qn,也就是说，DFA的每一个状态代表NFA状态集合的某个子集，这个DFA使用它的状态去记录在NFA读入输入符号之后可能到达的所有状态的集合,我们称此构造方法为子集法。,该集合是NFA状态集合中的一个子集，为了将NFA转换为DFA，把状态集合q1,q2,q3,qn看作一个状态A。,输入：一个NFAN,输出：一个接受（识别）相同语言的DFAM,方法：利用构造闭包的方法将NFA确定化为DFA。,1.状态集合I的闭包的概念。,设I是NFAN的一个状态子集,closure(I)定义如下：,(1)若sI,则sclosure(I),(2)若sI,那么从s出发经过任意条弧而能到达的任何状态s，都属于closure(I),3.4.4NFA确定化为DFA的方法,由定义可知,closure(I)表示所有那些从I中的元素出发经过道路所能到达的NFA的状态所组成的集合,I中任何状态也在其中，因为它们是通过通路到达自身的。该集合对DFA来说是一个状态。,3.4.4NFA确定化为DFA的方法,closure(0)=0,1,2,3,即0,1,2,3中的任一状态都是从NFA的初态0出发，经任意条道路可到达的状态。,通过下图理解状态集合I的一闭包。,这个状态集合实际就是要求的DFA的初态。,3.4.4NFA确定化为DFA的方法,因为在状态A中只有状态0有b的转移，转移到的状态为4和7。,若令A=0,1,2,3,则