编译原理课件词法分析.ppt

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

1、编译程序的结构,表格管理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出错处理,第三章 词法分析,词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析是编译的基础。执行词法分析的程序称为词法分析器。,3.1 对词法分析器的要求,3.1.1 词法分析器功能和输出形式功能：输入源程序，输出单词符号（单词记号文件）单词符号（token）:具有完整语义的最小的单位，不可分割。输出形式：根据单词符号的不同，构造表示单词符号的机内表示toke

2、n,以二元组形式表示，存放在文件中（形成源程序的内码文件）。二元组形式:(单词种别编码，单词的属性值）,内码文件的形式,for(i=0;i=10,i-)(for,-)(,-)(i，符号表入口)(=,-)(整形常数,常数表入口)(;-).,单词种别编码与单词符号属性值,考虑下述C+代码段：while(i=j)i-;经词法分析器处理后，它将转换为如下的单词符号序列：=,-,3.1.2 词法分析器的构造方式-词法分析器作为独立子程序,词法分析器安排成语法分析的子程序。好处在于：编译器结构清晰。,源程序,词法分析,语法分析,call,read,token,char,3.1.2 词法分析器作为独立子程序

3、,词法分析器作为独立的遍工作方式：不是任何程序的子程序，独立的完成一遍任务。缺点：需要保存单词符号文件，占用内存,源程序,词法分析,单词记号文件,read,token,char,3.2 词法分析器的设计,3.2.1 输入、预处理,预处理空白符，制表符、回车符，注释语句等构造预处理程序,词法分析器的工作,分析器对扫描缓冲区进行扫描一进行单词的识别。扫描时一般使用两个指示器扫描缓冲区最好使用如下一分为二的区域：（循环队列的形式）。,词法分析器的结构,3.2.2 单词符号的识别：超前搜索,超前搜索技术在单词识别的过程中，通过向前多读几个符号的形式，准确的进行单词的识别一旦确定识别到的单词之后，需要进

4、行扫描指针的回退，保证单词识别工作的顺利进行DO99K=1,10 IF(5.EQ.M)I=10 DO99K=1.10 IF(5)=55,关键字的识别,像FORTRAN这样的语言，关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符）借助于超前搜索技术实现。保留字（关键字不能用作标识符）的识别可以借助于保留字i表进行。1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4 IF(5)=55,标识符的识别,标识符的定义：字母开头，字母和数字的组合标识符后通常有界符,常数的识别,算术常数有时需要超前搜索5.EQ.M逻辑常数：.T.,.F.,有界符，容易识别,

5、算符、界符的识别,+，-，*，/，+，-所以需要超前搜索,词法分析器的构造基础小结,构造预处理器，删除非执行代码注释语句，多余的分隔符，等等构造扫描器，对预处理结果进行扫描对常数、标识符、关键字、运算符的识别都要采用超前搜索技术扫描指针要及时地回退到适当的位置,3.2.3 状态转换图,状态转换图：有限、有向图。用来描述单词规则的一种工具。,在转换图中，结点代表状态（单词识别过程中的状态），用园圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。,一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态（用=表示），而且实际上

6、至少要有一个终态（用双圈表示）。,图3.2状态转换图,=,状态图的作用,一个状态转换图可用于识别一定的字符串（描述词法规则）。终态上打个*号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串，如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。可以使用状态图进行词法分析器的开发,=,3.2.4 状态转换图的实现,利用转换图容易编写词法分析器让每个状态结点对应一小段程序。在编制程序的过程中引进一组全局变量和过程。将它们作为实现转换图的基本成分。例如：Key:记录单词识别过程中已识别到的字符串扫描指针回退函数判断读到的符号的类型等等,对不包含回路的节点,状态i对应的代码：i()

7、Ch=Getchar()If(isletter(ch)jElse if(isdigit(ch)kElse if(ch=“/”)lElse 出错处理,i,j,k,l,字母,数字,/,对包含回路的节点,i()ch=getchar();while(isletter(ch)or isdigit(ch)getchar();状态K所对应的程序段；,i,k,其他,字母或数字,对终态节点,K()Return token;,i,k,其他,字母或数字,example:file_operation,标识符,无符号整数,单字符分界符,双字符分界符,S,标,非字母数字,字母,字母、数字,数,非数字,数字,数字,单界,+

8、，（）,出口,星号,*,乘幂,*,其他,出错,其他,读字符,查保留字表,*,3.3 正规表达式与有限自动机,为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将转换图的概念形式化。为此我们引入：正规式，正规集，自动机等概念。,3.3.1 正规式与正规集,和都是 上的正规式，他们所表示的正规集分别为 和；任何a,a是上的一个正规式，它所表示的正规集为a；假定U和V都是上的正规式，他们所表示的正规集分别记为L(U)和L(V),并且，(U|V),UV和（U)*也都是正规式，它们所表示的正规集分别为L(U)L(V),L(U)L(V)(连接积）和（L(U)*（闭包）仅由有限次使

9、用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集。,几个例子,3.1 令=a,b其正规式和正规集如下：正规式 a|b ba*a(a|b)*(a|b)*(aa|bb)(a|b)*,正规集a,bban|n=0,1,2,.以a开头的所有字符串由a、b组成的、包含aa或bb的字符串,3.2 令=A,B,0,1,则：正规式 正规集(A|B)(A|B|0|1)*由A、B、0、1组成的以A、B开头的字符串的全体（0|1）（0|1）*由0、1组成的所有符号串,例 3：令=d,.,e,+,-，则上的无符号数的正则式,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd

10、*|)(e(+|-|)dd*|),dd*,解：,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*.dd*,dd*(.dd*|)e+dd*,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)e-dd*,dd*(.dd*|)edd*,无符号数的组成 整数部分.小数部分 指数部分（e+指数的符号+整数）,正规式的等价性,若两个正规式所表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如：b(ab)*=(ba)*b等,正规式的运算规律,U|V=V|U 或的交换律U

11、|(V|W)=(U|V)|W 或的可结合律U(VW)=(UV)W 连接的可结合律(V|W)U=VU|WU 分配律U=U=U U*=U*,3.3.2 确定有限自动机（DFA),确定有限自动机(DFA)是一个五元式 M=(S,s0,F)1.S是一个有限集，它的每个元素称为一个状态。2.是一个有穷字母集，它的每个元素称为一个输入字符。,3.3.2 确定有限自动机（DFA),确定有限自动机(DFA)是一个五元式 M=(S,s0,F)是一个从S x 至S的单值部分映射。(s,a）=S。意味着：当现行状态为s、输入字符为a时，将转换到下一个状态S。我们称S为s的后继状态。S0S，是唯一的初态。FS，是一个

12、终态集（可空）,DFA实例,M=(0,1,2,3,a,b,0,3)其中：（0,a)=1;（0,b)=2（1,a)=3;（1,b)=2（2,a)=1;（2,b)=3（3,a)=3;（3,b)=3,DFA的矩阵表示,该矩阵的行表示状态，列表示输入字符，矩阵元表示(s,a）的值，该矩阵称为状态转换矩阵。,DFA的（确定的）状态转换图表示,假定DFA M 含有m个状态n个输入字符，那么，这张图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用上的一个不同字符作标记，整张图含有唯一的初态和若干个（可以是0个）终态结点。,DFA对应的状态转换图,M=(0,1,2,3,a,b,0,3)

13、其中：（0,a)=1;（0,b)=2（1,a)=3;（1,b)=2（2,a)=1;（2,b)=3（3,a)=3;（3,b)=3,=,DFA 所识别（读出或接受）的字符串,对于*中的任何一个字符串，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字等于，则称为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则为空字可以为M所识别。DFA M所能识别的字的全体记为L(M).,DFA及其所识别的语言描述,M=(0,1,2,3,a,b,0,3)其中：（0,a)=1;（0,b)=2（1,a)=3;（1,b)=2（2,a)=1;（2,b)=3（3,a)=3;（

14、3,b)=3问：L(M)=?,L(M)为在上所有含相继两个a或相继两个b的字,=,3.3.3 非确定有限自动机(NFA),一个非确定有限自动机（NFA)是一个五元式 M=(S,S0,F)(1)S 同DFA（2）同DFA（3）是一个从S x*到S的子集的映照，即：S x*2s(4)S0S,是一个非空的初态集；（5）F S，是一个终态集（可空）,NFA实例,M=(0,1,2,3,4,a,b,0,2,4)其中：（0,a)=0,3;（0,b)=0,1（1,b)=2;（2,a)=2（2,b)=2;（3,a)=4（4,a)=4;（4,b)=4,NFA的表示,矩阵表示：,NFA的表示,状态转换图表示：假定N

15、FA 含有m个状态n个输入字符，那么，这张图含有m个状态结点，每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用*上的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个的初态和若干个（可以是0个）终态结点。某结点既可以是初态也可以是终态结点。,NFA的状态转换图,=,NFA所识别或接受的字,对于*中的任何一个字（字符串），若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字（忽略那些标记为的弧）等于，则称为NFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，或者存在一条某初态结点到某个终态结点的通路，则为空字可以为M所识

16、别。,=,NFA所识别的语言描述,该NFA识别的语言有什么特点？,L(M)为在上所有含相继两个a或相继两个b的字,=,NFA到DFA的区别：,DFA与NFA的等价性,DFA是NFA的特例。对于每个NFA M存在一个DFA M，使L(M)=L(M)。第一步，引入新的初态X和终态Y(保证初态的唯一性)，并依照下面的函数引入新的弧：（X,)=S（F,)=Y第二步：按照如下替换规则对NFA进行处理,AB,i,j,A,B,i,j,k,A|B,i,j,A*,i,j,A,B,i,j,i,j,k,A,替换规则,NFA允许边出现,子集法,第三步，利用子集法将NFA转化成DFA状态集I的Ia集合：Ia=_CLOS

17、URE(J)J=move(I,a)：所有可以从I中的某一状态经过一条a弧而到达的状态的全体状态集I的_CLOSURE(I)闭包：状态集I中的任何状态经任意条弧而能到达的状态的集合,=,子集法的实现,构造矩阵（包含K+1列,K为字母集的大小），矩阵的列标为Ia1,Ia2；矩阵的首行首列为_CLOSURE(X)如果某行第一列的元素已知，记为I,该行其余各列定义为：Iai(i=1.k)在构造过程中，如果产生新的状态集，则将其写在下面新行的行首重复上述过程，直到没有新的状态集产生将新构造的矩阵视为状态转换表，构造DFA 表中的第一行为DFA的初态，含有原终态的子集为新的终态。,例：有NFA M，求DF

18、A M。,a,1,2,3,4,start,a,b,a,c,c,I Ia Ib Ic,1,4,X,Y 2,3,2,3 2 4,Y 3,4,Y,2 2 4,Y,4,Y,3,4,Y 3,4,Y,X,Y,start,I Ia Ib Ic,1,4,X,Y 2,3,2,3 2 4,Y 3,4,Y,2 2 4,Y,4,Y,3,4,Y 3,4,Y,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,DFA M状态转换矩阵,将求得的状态转换矩阵重新编号,0,1,4,2,3,1,4,X,Y,2,3,4,Y,2,a,c,a,b,b,c,3,4,Y,确定有穷自动机的

19、化简,说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,DFA的最小化就是寻求最小状态DFA,最小状态DFA的含义:1.没有多余状态(死状态)2.没有两个状态是互相等价（不可区别）,所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。两个状态s和t等价：满足一致性条件(兼容性)同是终态或同是非终态蔓延性条件（传播性）从s出发读入某个aa和从t出发读入某个a到达的状态等价。,确定有限自动机的化简

20、,确定有限状态化简：寻找一个状态数比M少的DFA M，使得L(M)=L(M)两个概念：状态s和t等价。状态s和t可区别。一般的，终态和非终态是可区别的。化简过程：对M的状态集进行分割，分割成不相交的子集，使得不同的两个子集中的状态是可区别的，而同一子集中的状态是等价的,状态集划分步骤,第一步，将终态和非终态分开，从而将状态集分成两个子集；假定到某个时候已经将集合划分成m个子集，并且属于不同子集中的状态是可区分的检查每一个子集中的状态是否可以在划分：对于某一个集合I=q1,q2qk,构造该集合的I(a)，如果 I(a)不包含在现行划分中的某一个子集中，则将I一分为二,集合划分方法,如果s1和s2

21、经a弧到达t1和t2，而t1和t2分属于两个子集，则将I分成两部分，其中I(1)=s|s经a弧到达t1所在的子集中的某状态I(2)=I-I(1)重复上述过程，直到没有新的状态子集生成最后，对划分中的每一个子集，选取子集中的一个状态代表其他的状态，并进行相关的处理,例1:最小化,状态集的划分将所有DFA的终态与其它状态划分成两个子集G1,G2;分别从两个子集G1,G2中寻找等价状态进行化简。,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,a,b,例：试求与下图所示NFA等价的化简了的DFA。,化简后的DFA:,有限自动机

22、化简实例,有限自动机化简实例,首先把M的状态分为两组：终态组3，4，5，6，和非终态组0，1，2 其次考察终态组，由于 3，4，5，6a3,4,5,6和 3，4，5，6b3,4,5,6所以不能再划分,再考察0，1，2 由于 0，1，2a1，3，它既不属于0，1，2也不属于3，4，5，6，因此应将其一分为二，由于1态经a弧到达3态，而且状态0，2经a弧到达1态故应把1态分出形成1，0，2。现在划分已经有3个组：3，4，5，6，1，0，2。由于0，2b=2,5未包括在上述分组中，故0，2应一分为二0，2。到此四个分组3，4，5，6，0，1，2。每个组都不可再分。最后，令状态3代表3，4，5，6。把

23、原来到达4，5，6的弧都导入3，并删除4，5，6状态。得到化简的DFA.,正规式与有限自动机的等价性,结论：对于任何FA，都存在一个正规式r，使得L(r)=l(M)对于任何正规式r，都存在一个FA，使得l(M)=L(r),由FA 构造正规式的过程,第一步，引入新的初态X和终态Y，并用标记为的有向弧，将X、Y与原来的初态和终态连接；,由FA 构造正规式的过程,第二步，按照规则消除M上的弧重复第二步，直到状态图中只有XY状态此时，X、Y之间的标注即为正规式,()消除M中的所有结点,a|b,x,0,2,4,y,aa,bb,a|b,a|b,由正规式构造FA,采用关于正规式中运算符数目的归纳方法进行证明

24、。若r 中具有0个运算符，则r=,r=a或r=,由正规式构造FA,2.假设r中有少于k个运算符时时，上述结论成立3.则当r中有k个运算符时：,r的三种情形r=r1|r2,r=r1.r2r=r1*,(a)对于正则式R=s|t,NFA(R),(b)对正则式R=st,NFA(R),N(s),(c)对于正则式R=s*,NFA(R),例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),R=(a|b)*abb,例3：试构造与正则式R=(a*|b*)b(ba)*等价的状态最少的DFA。,NFA确定为DFA:,注：状态从18标注,最小化的DFA:,1,2,例：设计一个最小化的DFA，其输入字母表是

25、0,1，它能接受以0开始，以1结尾的所有序列。,解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换图(NFA)如下：,NFA确定为DFA过程：,得状态转换图(DFA)如下：,在DFA中，所有含有NFA的终态的状态作为DFA的终态,DFA M=(S,A,B,C,0,1,S,C)其中如上（不可省略）,正规文法与有限自动机的等价性,定义：对于正规文法G和有限自动机M,如果L(G)=L(M),则称二者等价结论：对每一个右（左）线性正规文法G，都有一个有限自动机M，使得L(G)=L(M)对每一个有限自动机M，都有一个右（左）线性正规文法G，使得L(G)=L(M),由正规文法构造有限自动机,M中

26、状态转换函数的构造：A-a,a Vt,则（A,a）=fA-aA1|aA2 aAk,a Vt,则（A,a）=A1|A2 Ak,例:求与文法GS等价的NFA GS:SaA|bB|AaB|bA BaS|bA|,G=（A，B，C，D，a，b，P，A）,其中P:A aB A bD|b B bC|b C aA C bD|b D aB D bD|b,二者的等价性证明,对于右线性文法G,在S推导出句子w的过程中，利用A-aB相当于：利用A-a相当于：也就是说：任给w L(G)，都有w L(M)即：L(G)是L(M)的子集；同样，任给w L(M)，都有w L(G)即：L(M)是L(G)的子集；结论：L(M)=L

27、(G)，即M跟G等价,由正规文法构造有限自动机,M中状态转换函数的构造：A-a,a Vt,则（q,a）=AA1-Aa,A2-Aa,Ak-Aa a Vt,则（A,a）=A1,A2 Ak,例:求与文法GS等价的NFA GS:SAa|Bb|ABa|Ab BSa|Ab|,q,B,S,A,b,a,a,a,b,b,由DFA构造正规文法（右线性）,关于文法产生式的定义：对于（A,a）=B的状态转换函数，如果B不属于F，可以定义A-aB形式的产生式；如果B属于F，可以定义A-a|aB形式的产生式;,例:给出如图DFA等价的正则文法G,G=（A，B，C，D，a，b，P，A）,其中P:A aB A bD|b B

28、bC|b C aA C bD|b D aB D bD|b,1.对转换函数(A,t)=B，可写成一个产生式:AtB,3.有限自动机的初态对应于文法的开始符号,有限自动机的字母表为文法的终结符号集。,由DFA构造正规文法（左线性）,关于文法产生式的定义：对每一个S属于F,定义Q-S对于（A,a）=B的状态转换函数，定义B-Aa形式的产生式；如果A为起始符，可以定义B-a,或者定义B-Aa 和A-;如果S0属于F,Q-,已知NFA，构造等价的右线性文法,A-0B|1D|0B-1C|0DC-0B|1D|0D-0D|1D,0,1,有下面的右线性文法，构造NFAA-0B|1D|0B-1C|0DC-0B|1

29、D|0D-0D|1D,A,1,0,1,0,有下面的NFA，构造左线性文法Q-FF-C0|0B-C0|0C-B1D-D0|D1|B0|A1|C1,A,1,0,1,0,3.4词法分析器的自动产生,我们用正规式描述单词符号，并研究如何从正规式产生识别这些单词符号的词法分析程序。首先介绍一个描述词法分析器的语言LEX，讨论LEX的实现，从而，用它来描述和自动产生所需的各种词法分析器。,Lex编译器,C语言编译器,Lex文件(文本文件),可执行的词法分析工具,输入文件,单词符号,3.4词法分析器的自动产生,定义部分规则部分用户子程序部分,3.4.1 LEX的程序结构,定义部分,定义部分%.%,内容Inc

30、lude、声明语句等C语句及正则表达式%#include“stdio.h”#”int lineno%delim tn letter A-Za_z digit 0-9 id letter(letter|digt)*,Lex中的正则表达式规则,转义字符：:表示一个集合，可以结合-表示一个范围，如abc，a-zA-Z?*+:0或1次，任意次，至少一次.:任意一个符号|：二选一（）:分组，括号内的内容被看作一个原子，如（ab）,:标记限定符。例如O2(匹配两个O)，O2，(匹配至少两个O)，O2，5(匹配两个O，至多5个)/向前匹配（超前搜索）。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中

31、“/”前面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。,规则部分,规则部分起始于%，终止于%，其间是词法规则（正则表达式）和相应的动作组成格式P1 A1P2 A2P3 A3其中，Pi是一个正规式（第一部分定义的正规式的名字）Ai是一个程序段C语句,识别规则,%n+num_line;A-Za-z*+num_words.+num_chars%注意：在识别规则中引用正规式的名字时，要用分隔。例如：letter(digit|letter)*超前搜索符号（/）只能在规则段中使用,用户子程序部分,包含用c语言编写的子程序，这些子程序可以用在前面的动作中，这样可以达到简化编程的

32、目的。Lex 编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。注意这一段必须包括 yywrap()函数的定义。,用户子程序的相关问题,Main(int argc,char*argv)-argc;+argv/*跳过对第一个文件，即main 函数多对应的.exe文件*/if(argc0)yyin=fopen(argv0,r);else yyin=stdin yylex();yywrap();/*返回值为零，可对多个文件进行解析*/,一个完整的lex程序,%intwordCount=0;%chars A-za-z.“numbers(0-9)+delimnt whitespace

33、delim+wordschars+%,words wordCount+;whitespace numbers numcount+%,voidmain()yylex();/*starttheanalysis*/printf(Noofwords:%dn,wordCount);intyywrap()return1;,3.4.3 LEX的实现,Lex编译过程：对每条规则构建一个NFA引入新的初态，将这些NFA合并成一个NFA利用子集法将NFA转化为大DFA必要时对DFA进行状态的化简,例题与习题解答,例3.1写能被5整除的十进制整数的文法及正则表达式。解：能被5整除的文法：GZ:ZSAB S+|-B

34、0|5 ANA|N 0|1|2|3|4|5|6|7|8|9|正则表达式：GZ:Z=(+|-)A*(0|5)A=0|1|2|3|4|5|6|7|8|9,例3.2写一个正规式，使其语言是奇数集，且每个奇数不以0开头。解：r1=1|3|5|7|9r2=2|4|6|8r3=r1|r2r4=(0|r3)*R=r1|r3r4r1,例3.3写出能被3整除十进制整数的文法和正则表达式：解：能被3整除的文法：G=(0,1,2,3,4,5,6,7,8,9,S,A,B,S,P,)其中P为：S-(0|3|6|9)S|S-(1|4|7)A|(2|5|8)BA-(0|3|6|9)A|(1|4|7)B|(2|5|8)SB-

35、(0|3|6|9)B|(2|5|8)A|(1|4|7)S,例3.4：已知有限自动机如图,(1)以上状态转换图表示的语言有什么特征？(2)写出其正规式与正规文法.(3)构造识别该语言的有限自动机DFA.,解：（1）L=W|W 0,1,并且W至少有两个连续的1（2）正则式为（0|1)*11(0|1)*正则文法G(Z)为：A0A|1A|1B B 1C|1 C 0C|1C|0|1（3）将图中有限自动机确定化：首先从初态A出发：,I I0 I1(1)A(1)A(2)A,B(2)A,B(1)A(3)A,B,C(3)A,B,C(4)A,C(3)A,B,C(4)A,C(4)A,C(3)A,B,C其相应的DFA

36、如下图：,将这个DFA最小化：首先分终态和非终态两个集K1=1,2 和 K2=3,4 由于状态1输入1到达状态K1集，而状态2输入1到达K2集故将k1分为K11=1,K12=2 由于状态3，和 4 输入1，或0 都到达k2集所以状态3，4等价。则可以分割成三个子集：1，2，3，4,所以将DFA最小化的状态图如下：,例3.5请构造与正则式R=(a*b)*ba(a|b)*等价的状态最少的DFA（确定有限自动机）解：（1）首先构造转换系统图：（2）由系统转换图构造DFA（NFA确定化）设初态为S,A,B,G,F,NFA确定化为DFA的过程：I Ia Ib(1)S,A,B,G,F(2)G,F(3)A,

37、B,C,G,F(2)G,F(2)G,F(4)A,B,G,F(3)A,B,C,G,F(5)D,F,G,E,Z(3)A,B,C,G,F(4)A,B,G,F(2)G,F(3)A,B,C,G,F(5)D,F,G,E,Z(6)G,F,E,Z(7)A,B,E,Z,G,F(6)G,F,E,Z(6)G,F,E,Z(7)A,B,E,Z,G,F(7)A,B,E,Z,G,F(6)G,F,E,Z(8)A,B,C,E,Z,G,F(8)A,B,C,E,Z,G,F(5)D,F,G,E,Z(8)A,B,C,E,Z,G,F DFA 这状态图如下：,确定有限自动机图如下：,（3）将DFA最小化：先将终态和非终态分成两个集:K1=1,2,3,4,K2=5,6,7,8 对于K1中的3态输入a则进入K2集，而1，2，4态输入a仍然在K1中，故K1可一分为二K11=1,2,4和K12=3;考察K11对于1，4态输入b到达3态而2态输入b到达4态。故K11可一分为二K111=1,4;K112=2最后考察K2输入a或b都到达K2集。则DFA化简为1，4，2，3，5，6，7，8四个子集。其状态图如下：,第四章 语法分析自上而下分析（1）,4.1 语法分析器功能 下图表明了语法分析器在编译程序中的地位。,词法分析器,语法分析器,单词符号,取下一个单词符号,编译后续,语法分析树,符号表,