《第三章 词法分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章 词法分析精选文档.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 词法分析1本讲稿第一页，共八十四页3.1 对于词法分析器的要求 词法分析器的功能 输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号分类 关键字(for while)标识符(x1 xname)运算符(+*)界符 (;)常数 (23 “abcdf”)功能和输出形式2本讲稿第二页，共八十四页单词符号 一个程序语言的关键字、运算符和界符都是确定的。但对于标识符和常数的使用是灵活的。词法分析器所输出的单词符号形式：（单词种别，属性值）单词种别通常用整数编码。属性值是反映单词符号特性或特征的值。本书假定 关键字、运算符和界符都是一符一种；标识符为一种；常数按类型分
2、种。3本讲稿第三页，共八十四页例如：C的代码段while (x=y)x-;=,-经词法分析器处理后，输出如下序列：4本讲稿第四页，共八十四页词法分析器作为一个独立子程序 好处 使整个编译程序的结构更简单、清晰和条理化。因为词法分析比语法分析要简单得多，可用更有效的特殊方法和工具进行处理。讨论 是否可以把词法分析器作为独立一遍呢？5本讲稿第五页，共八十四页3.2 词法分析器的设计 常常按词法分析的任务和作为一个独立子程序来考虑它的设计。3.2.13.2.1 输入、预处理 词法分析器的第一步工作是输入源程序文本到一个输入缓冲区中。这样，词法分析的工作可以直接在这个缓冲区中进行。在许多情况下，常常把
3、输入串预处理一下，目的是为了方便单词符号的识别。预处理的工作是将源程序中多余的空白符、跳格符、回车符、换行符等编辑性字符以及注释部分剔除掉，并将结果存入扫描缓冲区中。6本讲稿第六页，共八十四页词法分析器 预处理子程序词法分析器单词符号输入缓冲区扫描缓冲区源程序7本讲稿第七页，共八十四页扫描缓冲区 词法分析器对扫描缓冲区进行扫描时，一般用两个指示器(P1,P2)：一个指向当前正在识别的单词的开始位置，另一个用于向前搜索以寻找单词的终点。P1 P2 120个字符120个字符|标识符|=120个字符|常数|=120个字符 while(x100)8本讲稿第八页，共八十四页单词符号的识别-超前搜索关键字
4、的识别（Fortran）例如：(1)do99k=1,10 do 99 k=1,10 (2)do99k=1.10 do99k是变量标识符的识别常数的识别 例如：(1)5.E-8 5-8 (2)5.EQ.M 5=M算符和界符的识别例如：+,+=,=9本讲稿第九页，共八十四页 状态转换图 状态转换图是设计词法分析程序的一个好途径。转换图是一张有限的有向图。结点代表状态，用圆圈表示，状态之间用箭弧连接。箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类。一张转换图只能含有有限个状态，其中一个被认为是初态，可以有一个或多个终态（双圈）。10本讲稿第十页，共八十四页例如 字母字母数字 数字数字其它
5、 其它（a）识别标识符的状态图 （b）识别整数的状态图*一个状态转换图可用于识别（或接受）一定的字符串。3311本讲稿第十一页，共八十四页 大多数程序语言的单词符号都可以用转换图予以识别。作为一个综合例子，我们来构造一个识别某个简单语言的所有单词符号的转换图。P42表3.1中列出了这个小语言所有单词以及它们的种别和内部值。单词符号的识别12本讲稿第十二页，共八十四页单词单词符号符号种别种别编码编码内码值内码值beginbeginendendififthenthenelseelsewhilewhiledodo标识符标识符整常数整常数1 12 23 34 45 56 67 710101111-内部
6、字符串内部字符串二进制形式二进制形式单词单词符号符号种别种别编码编码内码值内码值+-*/=:=:=;1313141415151616171718181919212122222323-小语言单词符号及内部表示小语言单词符号及内部表示13本讲稿第十三页，共八十四页词法分析的状态转换图*非字母或数字 字母 数字 非数字空白 数字*非*其它103*字母或数字 13 见P43 7*14本讲稿第十四页，共八十四页3.2.4 状态转换图的实现 状态转换图很容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。假设已有一组全局变量和过程，将它们作为实现转换图的基本部分。这些变量和过程见P44。词法分析器
7、算法见P45。15本讲稿第十五页，共八十四页 ch=GetChar();GetBC();if(IsLetter(ch)/*进入关键字或标识符识别状态*/while(IsLetter(ch)|IsDigit(ch)Concat();ch=Getchar();Retract();/*回退一个字符位置*/code=Reserve();/*查找保留字表 */if(!code)return(code,-);else value=InsertId(strToken);return($ID,value);else /*进入其它单词符号的判断状态 */16本讲稿第十六页，共八十四页状态转换图的实现状态转换图的
8、实现 状态转换图容易用程序实现。最简单的办法是让状态转换图容易用程序实现。最简单的办法是让每个状态结点每个状态结点对应一小段程序对应一小段程序。下面引进一组。下面引进一组全局变量和过程全局变量和过程，将它们作为实现，将它们作为实现转换图的基本部分。这些变量和过程是：转换图的基本部分。这些变量和过程是：(1)(1)chch字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。(2)(2)strTokenstrToken字符数组，存放构成单词符号的字符串。字符数组，存放构成单词符号的字符串。(3)(3)GetCharGetChar读字符函数，从输入缓冲区中读进源程序的读字符函数，
9、从输入缓冲区中读进源程序的下一个字符到下一个字符到 chch，并把读字符指针指向下一，并把读字符指针指向下一个字符。个字符。(4)(4)GetBCGetBC函数，检查函数，检查 ch ch 中的字符是否为空白字符，中的字符是否为空白字符，若是空白字符，则反复调用若是空白字符，则反复调用 GetChar()GetChar()，直，直到到 ch ch 中读入一个非空白字符为止。中读入一个非空白字符为止。17本讲稿第十七页，共八十四页(5)(5)ConcatConcat函数，将函数，将 ch ch 中的字符与中的字符与 token token 中的字符中的字符串连接。串连接。(6)(6)IsLett
10、erIsLetterIsDigitIsDigit布尔函数，分别判断布尔函数，分别判断 ch ch 中的字符是否为字中的字符是否为字符或数字。符或数字。(7)(7)ReserveReserve整数函数，对整数函数，对 token token 中的字符串查找关键中的字符串查找关键字表，若它是一个关键字则返回它的编码，字表，若它是一个关键字则返回它的编码，否则返回标识符的种别码否则返回标识符的种别码 1010。(8)(8)RetractRetract函数，读字符指针回调一个字符位置。函数，读字符指针回调一个字符位置。(9)(9)ReturnReturn函数，收集并携带必要的信息返回调用程序，函数，收
11、集并携带必要的信息返回调用程序，即返回语法分析程序。即返回语法分析程序。(10)(10)dtbdtb十进制转换函数，将十进制转换函数，将 token token 中的数字串转中的数字串转换成二进制数值表示，并以此作为函数值返换成二进制数值表示，并以此作为函数值返回。回。18本讲稿第十八页，共八十四页思考题：1.令=a,b,画出接受上含有偶数个 a 的字符串的状态转换图。2.2.画出状态转换图，它接受=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。aabb120010012119本讲稿第十九页，共八十四页3.3 正规表达式与有限自动机 词法分析器的自动生成可依据正规表达式和有限自动
12、机的理论。实际上，状态转换图与正规表达式和有限自动机在描述语言能力方面是等价的。3.3.1 正规式与正规集 对于字母表，我们感兴趣的是它的一些特殊字集，即正规集。我们将使用正规式这个概念来表示正规集。下面是正规式和正规集的递归定义：1）和都是上的正规式，它们所表示的正规集分别为和；2）任何a,a是上的一个正规式，它所表示的正规集为a；20本讲稿第二十页，共八十四页正规式和正规集的递归定义（续）3）假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(UV)和(U)*也都是正规式。它们所表示的正规集分别为L(U)L(V)、L(U)L(V)（连接积）和(L(U
13、)*（闭包）。仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集正规集。算符的优先顺序：先“*”，次“”，后“|”。21本讲稿第二十一页，共八十四页例3.1 令=a,b，下面是上的正规式和相应的正规集。正规式 正规集 ba*上所有以b为首，后跟任 意多个a的字。a(a|b)*上所有以a为首的字。(a|b)*(aa|bb)(a|b)*上所有含有两个相继的a 或两个相继的b的字。22本讲稿第二十二页，共八十四页例3.2 令=a，b，0，1，则：正规式 正规集(a|b)(a|b|0|1)(a|b)(a|b|0|1)*上的“标识符”的全体 (0|1)(0|1
14、)(0|1)(0|1)*上的“数”的全体23本讲稿第二十三页，共八十四页正规式的等价性若两个正规式所表示的正规集相同，则称两者等价。例如 b(ab)*=(ba)*b (a|b)*=(a*|b*)*令U、V和W均为正规式，则下列关系成立：1)U|V=V|U 交换律2)U(V|W)=(U|V)|W 结合律3)U(VW)=(UV)W 结合律4)U(V|W)=UV|UW 分配律 (V|W)U=VU|WU 5)U=U=U注意:UVVU24本讲稿第二十四页，共八十四页思考题：写出下面正规式1.令=a,b,含有偶数个a的上的字符串。2.2.每个1都有0直接跟在右边的二进制串。(b*|ab*a)*(0|10)
15、*aabb1200125本讲稿第二十五页，共八十四页确定的有限自动机一个确定有限自动机(DFA)M 是一个五元式：M=(S,sM=(S,s0 0 ,F),F)其中：1)S是一个有限集，它的每个元素称为一个状态。2)是一个有穷字母表，它的每个元素称为一个输入字符。3)是一个从S至 S的单值部分映射。(s,a)=s 意味着：当现行状态为s、输入字符为a时，将转换到下下一状态一状态s。我们称s为s的一个后继。4)s0S，是唯一唯一的初态。5)F S 是一个终态集（可空）。26本讲稿第二十六页，共八十四页状态转换矩阵一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示(s,a)
16、的值。这个矩阵称为状态转换矩阵。例3.2 有DFADFA M M=(=(S S,s s0 0 ,F F)其中：S S=0,1,2,3,=0,1,2,3,=a,b,=a,b,s s0 0 =0,=0,F F=3,=3,(0,a)=1(0,a)=1 (0,b)=2(0,b)=2 (1,a)=3(1,a)=3 (1,b)=2(1,b)=2 (2,a)=1(2,a)=1 (2,b)=3(2,b)=3 (3,a)=3(3,a)=3 (3,b)=3(3,b)=327本讲稿第二十七页，共八十四页状态转换矩阵 状态转换图 字符状态ab 0 1 2 1 3 2 2 1 3 3 3 30 aaabbba,b 28
17、本讲稿第二十八页，共八十四页DFA M 接受的语言 对于*中的任何字，若存在一条从初态到某一终态结点的通路，且这条通路上的所有弧的标记符连接成的字等于，则称可为DFA MDFA M所识别(或接受)。DFA M 所能识别的字的全体，称为DFA M所接受的语言，记为L(M)L(M)。注意：若 M 的初态结点又是终态结点，则空字可被M所识别。29本讲稿第二十九页，共八十四页例如：有DFA MDFA M 如下：0 aaabbba,b M可接收的字：aa bb aaa aab babb abaa baaa abbbM接收的语言为：含有两个相继a或b的a,b字符串。30本讲稿第三十页，共八十四页非确定的有
18、限自动机一个非确定有限自动机(NFANFA)M 是一个五元式：M=(S,SM=(S,S0 0 ,F),F)其中：1)S是一个有限集，它的每个元素称为一个状态。2)是一个有穷字母表，它的每个元素称为一个输入字符。3)是一个从S*至 S的幂集的映射,即:S:S*2S4)S0 S，是一个非空初态集。5)F S 是一个终态集（可空）。31本讲稿第三十一页，共八十四页同样,一个 NFA MNFA M 也可表示成状态转换图。NFA状态转换图与DFA状态转换图的主要区别：（1）箭弧上的标记可以不同。DFA的标记是 上的单个字符，而NFA的标记是*上的字（可以是字）；（2）映射函数的定义不同，DFA的是单值函
19、数，而NFA的是多值函数。0DFA00NFA32本讲稿第三十二页，共八十四页 对于*中的任何字，若存在一条从某个初态到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略字）等于，则称可为NFA M 所识别(或接受)。NFA M 所能识别的字的全体，称为NFA M所接受的语言，记为L(M)L(M)。NFA M 接受的语言33本讲稿第三十三页，共八十四页例如：下图就是一个NFA M 它所能识别的是含有两个相继 a a 或两个相继 b b 的字符串。x y aaaabbbb 34本讲稿第三十四页，共八十四页NFA 与 DFA 等价 显然，DFA 是 NFA 的特例。但是可以证明对于每
20、个NFA M，都存在一个DFA M”，使 L(M)=L(M”)证明：（构造性证明）（1）假定NFA M=，对M 的状态转换图进行以下改造：引进新的初态结点X X和终态结点Y Y，并且X、Y S，从X到S0的任意状态结点连一条箭弧，从F中任意状 态结点连一条箭弧到Y。35本讲稿第三十五页，共八十四页对M的状态转换图进行如下替换：代之以 k k 代之以 代之以 k k 重复这种分裂过程直至状态转换图中的每条箭弧上的标记或为，或为 中的单个字母。将最终得到的NFA记为M。显然,L(M)=L(M)ABA|BABBAA*A36本讲稿第三十六页，共八十四页（2）将 NFA M 进一步变换成等价的DFA M
21、”方法如下：假定 I 是M的状态集的子集，定义I的闭包_CLOSURE(I)为：若qI，则 q_CLOSURE(I)；若qI，那么从q出发经过任意条弧而能达到的任何状态q 都_CLOSURE(I)假定 I 是M的状态子集，a，定义Ia=_CLOSURE(J)_CLOSURE(J)其中，J J是那些可以从I I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。37本讲稿第三十七页，共八十四页 假定=a1,ak。构造一张含有k+1列的表 置该表的首行首列为_CLOSURE(X)。若某行第一列状态子集I已确定，求出其它列Iai i (i=1,2,k)，然后检查该行上的所有状态子集，将其未出现在
22、第一列的状态子集填入后面空行的第一列。重复上述过程，直至所有状态子集均在该表的第一列出现过。因为M的状态子集的个数是有限的，所以上述过程必定在有限步内终止。38本讲稿第三十八页，共八十四页（3）将所构造出的表视为状态转换矩阵 将其中每个状态子集视为一个新的状态。显然，该表唯一刻划了一个DFA M”。它的初态就是该表中的首行首列的那个状态子集，终态是那些含有原终态Y的状态子集对应的新状态。显然,L(M)=L(M)=L(M”)L(M)=L(M)=L(M”)。上述把 NFA 确定化为 DFA 的方法称为子集法。39本讲稿第三十九页，共八十四页例如：正规式(a|b)*(aa|bb)(a|b)*求对应的
23、NFA M，并转换出等价的DFA M。NFA (2)NFA (1)解答：a|ba|b aa|bbaaaabbbb x y 40本讲稿第四十页，共八十四页利用子集法求状态转换表：aaaabbbb x y IIaIb x,5,1 5,3,1 5,4,1 5,3,1 5,2,3,1,6,y 5,4,1 5,4,1 5,3,1 5,2,4,1,6,y 41本讲稿第四十一页，共八十四页继续求新的子集：I、Ia、Ib b，得出下表：得出下表：I Ia Ib0X,5,15,3,15,4,115,3,15,3,1,2,6,Y5,4,125,4,15,3,15,4,1,2,6,Y35,3,1,2,6,Y5,3,
24、1,2,6,Y5,4,1,6,Y45,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y55,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y65,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y0 1 2 1 3 22 1 5 3 3 44 6 55 6 5 6 3 4 42本讲稿第四十二页，共八十四页对所有的状态子集重新命名，由此而得：0aaaaaaabbbbbb等价的DFADFA（未化简）如下：43本讲稿第四十三页，共八十四页例题1（1 1）画）画 NFANFA（2 2）加）加 X X，Y Y 构造一个DFA，它接受 a,b 上含有偶数个a的字符串。bbaabbbaa
25、b x y44本讲稿第四十四页，共八十四页(3)用子集法求状态转换矩阵 I Ia Ib 0 X,1 2 1 1 1 2 1 2 2 3,1,y 2 3 3,1,Y 2 3,1,Y bbaab x y45本讲稿第四十五页，共八十四页(4)重新命名得 DFA I Ia Ib 0 X,1 2 1 1 1 2 1 2 2 3,1,y 2 3 3,1,Y 2 3,1,Y0 2 1 1 2 1 2 3 2 3 2 3 bbaab 0 aba46本讲稿第四十六页，共八十四页例题2（1）DFA （2）正规文法 G(S):构造一个DFA，它接受 a,b 上含有偶数个a的字符串。然后写出其等价的正规文法。bbaa
26、ba S aA|bSA aB|bA|aB aA|bB|b47本讲稿第四十七页，共八十四页正规文法与有限自动机的等价性 对于正规文法 G G 和有限自动机 M M，如果：L(L(G G)=L()=L(M M)则称 G G 和 M M 是等价的。结论：（1）对每一个右（或左）线性文法G，都存在一个有限自动机(FA)M，使得：L(M)=L(G)L(M)=L(G)（2）对于每一个FA M，都存在一个右线性文法GR和左线性文法GL，使得：L(M)=L(GL(M)=L(GR R)=L(G)=L(GL L)48本讲稿第四十八页，共八十四页证明(1)对每一个右线性文法G，都存在一个FA M，使得:L(M)=L
27、(G)L(M)=L(G)证明：(构造性证明)设右线性文法G=V,S,P，将V VN N的每个非终结符视为状态符号，并增加一个终态状态符fVfVN N。令：FA M=其中定义如下：对 AV VN N 及及 a aV VT T ，若有 A Aa a，则令(A,a)=f(A,a)=f 对 AV VN N 及及 a aV VT T ，若有 A AaAaA1 1|aA|aA2 2|aA|aAk k，则 令(A,a)=(A,a)=A A1 1，A A2 2，A Ak k 显然，上述构造的 M 是一个NFA NFA。可以证明：L(G)L(G)当且仅当当且仅当 L(G)L(G)49本讲稿第四十九页，共八十四页
28、 显然显然 A Aa a A f A f A AaB aB A B A Baa令 =a1 a2 ak 其中 aiVVT T若 L(G)L(G)即 S 则 S a1B1 a1a2B2 a1a2ak-1Bk-1 a1a2ak 因此，存在一条从初态S到终态 f 的通路，其箭弧上的标记依次连接起来恰好为a1 a2 ak ，故 L(M)L(M)*a1a2ak-1akS B1 B2 Bk-1 f50本讲稿第五十页，共八十四页例题3已知正规文法 G G 如下，构造其等价的FA FA M M 。G:S aA|bS A bA|a|aB B aA|bB|b NFA解：S A B fabbaabab51本讲稿第五十
29、一页，共八十四页证明(2)对于每一个DFA M，都存在一个右线性文法G，使得：L(M)=L(G)L(M)=L(G)证明：设 DFA M=F(1)若 s s0 0 F F，令 G=其中 P 定义如下：对任意 a a及 A，BS，若有 (A,a)=B，则 若BF时，令 AaB 若BF时，令 Aa|aB可以推出：L(M)L(M)当且仅当当且仅当 L(G)L(G)(2)若 S S0 0 F F，即(S S0 0，)=S S0 0，但是，L(G)L(G)。此时增加一个S S0 0S S，且令 S S0 0|S S0 0，并为开始符号。显然，对G修改后的G，有 L(G)=L(M)L(G)=L(M)考虑出弧
30、！52本讲稿第五十二页，共八十四页例题4设 DFA M 如下，构造等价的正规文法。bbaaba S aA|bS A a|aB|bA B aA|b|bBaba b S S|S aA|bS|b A a|aS|bA53本讲稿第五十三页，共八十四页例题5bbaa 解：S aA|bS A bA|a|aB 注意:若终态无出弧，则去掉该非终结符54本讲稿第五十四页，共八十四页证明(1)对每一个左线性文法G，都存在一个FA M，使得：L(M)=L(G)L(M)=L(G)证明：设左线性文法G=V,S,P，将V VN N的每个非终结符视为状态符号，并增加一个初态符q0 0 V VN N。令：FA M=其中定义如下
31、：对AVVN N 及及 aVaVT T，若有：A Aa a，则令(q q0 0,a)=A,a)=A 对AVVN N 及及 aVaVT T，若有：A A1 1Aa Aa，A A2 2Aa Aa，A Ak kAaAa，则令 (A,a)=(A,a)=A A1 1，A A2 2，A Ak k 显然，上述构造的 M 是一个NFA NFA。可以证明：W WL(G)L(G)当且仅当当且仅当 W WL(M)L(M)55本讲稿第五十五页，共八十四页 显然显然 A Aa a q q0 0 A A A ABa Ba B A B Aaa令 =a1 a2 ak 其中 aiVVT T若 L(G)L(G)即 S 则 S B
32、k-1 ak B Bk-2a ak-1 ak B1a2ak a1a2ak 因此，存在一条从初态q q0 0 到终态 S的通路，其箭弧上的标记依次连接起来恰好为a1 a2 ak ，故 L(M)L(M)*akak-1a2a1S Bk-1 Bk-2 B1 q q0 056本讲稿第五十六页，共八十四页证明(2)对于每一个DFA M，都存在一个左线性文法G，使得：L(M)=L(G)L(M)=L(G)证明：设 DFA M M=f 令 G=其中 P 定义如下：若 (S S0 0,a)=A，则 Aa|S S0 0a 若 (A,a)=B B，则 BAa （其中AS S0 0）可以证明：L(M)L(M)当且仅当当
33、且仅当 L(G)L(G)考虑入弧！57本讲稿第五十七页，共八十四页例3.4(1)1）已知 DFA M 求 GR ABCD0100110,1解：右线性文法GR(A):A 0|0B|1D B 0D|1C C 0|0B|1D D 0D|1D58本讲稿第五十八页，共八十四页例3.4(2)2）已知 GR 求 FA M 右线性文法GR(A):A 0|0B|1D B 0D|1C C 0|0B|1D D 0D|1DABCD0100110,1f0059本讲稿第五十九页，共八十四页例3.4(3)2）已知FA M 求 GL ABCD0100110,1f00解：左线性文法GL(f):f 0|A0|C0 D 1|A1|
34、B0|C1|D0|D1 C B1 B0|A0|C0A 无入弧！60本讲稿第六十页，共八十四页正规式与有限自动机的等价性可以证明：（1）对任何 FA MFA M，都存在一个正规式r,r,使得：L(L(r r)=L(M)=L(M)（2）对任何正规式r r，都存在一个 FA MFA M，使得 L(M)=L(L(M)=L(r r)结论：正规文法、正规式、NFA NFA、DFADFA在接受语言能力上是等价的。61本讲稿第六十一页，共八十四页证明 对任何 FA MFA M，都存在一个正规式r,r,使得：L(L(r r)=L(M)=L(M)证明：(1)引进新的初态结点 X X 和终态结点 Y Y，并且 X、
35、Y S，从X到S0的任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。62本讲稿第六十二页，共八十四页 （2 2）逐步消除中间状态结点，使之只剩下X，Y为止。在消除结点的过程中，逐步用正规式来标记箭弧，方法如下：代之为 V1V2V1 V2 代之为 V1|V2V1V2 代之为 V1V2V1 V2*V3V3r最后得到:x y63本讲稿第六十三页，共八十四页证明:对任何正规式r r，都存在一个 FA MFA M，使得 L(M)=L(L(M)=L(r r)证明：（采用归纳证明法）（1）若 r 具有0个运算符，则 r=或 r=或 r=a此时，对应的FA 分别为：q0q0q0qa64本讲稿第六十四
36、页，共八十四页（2）假设结论对少于k(k0)个运算符的 r 成立。（3）当 r 具有k个运算符时，有三种情形：r=rr=r1 1|r|r2 2 q0q1fM1f1q2M2f2 65本讲稿第六十五页，共八十四页 r=rr=r1 1.r.r2 2q1M1f1q2M2f2 r=rr=r1 1*q q1M1f1f 66本讲稿第六十六页，共八十四页例题6 1.写出a,ba,b上不以a开头，以aa结尾的正规式和 DFA DFA。解:正规式：b(a|b)b(a|b)*aaaaabab a I Ia Ib 1 2 2 2,3 2 2,3 2,3,4 2 2,3,4 2,3,4 2 NFA：DFA：bbaa a
37、bb67本讲稿第六十七页，共八十四页例题7 写出下面 NFA FA 对应的正规式（1）baa b解：令 r=abr=ab*(a|b)(a|b)正规式:R=r(ar)R=r(ar)*即：abab*(a|b)(aab(a|b)(aab*(a|b)(a|b)*解：ab*(a|b)a（2）aa bb68本讲稿第六十八页，共八十四页确定有限自动机的化简一个确定有限机 M 的化简：即寻找一个状态数比 M 少的DFA M，使得：L(M)=L(M)L(M)=L(M)什么是等价状态？如果从状态 s s 出发能读出某个字 而停止于终态，从状态 t t 出发也能读出相同的字 而停止于终态；反之亦然，则称状态 s 和
38、 t 是等价的。两个状态是可区别的？如果 DFA M 的两个状态 s s 和 t t 不等价；则称状态 s s 和 t t 是可区别的。69本讲稿第六十九页，共八十四页例题8 状态 2 与3是等价的。状态 2 与1是可区别的。DFA：bbba aab70本讲稿第七十页，共八十四页 DFA M 的状态最少化过程 将 M 的状态集分割成一些不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。I1197352846I4I3I271本讲稿第七十一页，共八十四页将DFA最小化的方法 (1)先把DFA M 的
39、终态与非终态分开，分成两个不同的子集；(2)对每个子集I中的状态分别考察它们是否是可区别的，设 I=qI=q1,1,q qk k 若存在一个输入字符 a 使得IaIa不全在现行划分的同一子集I中，就将I 分为两个子集I1，I2：I I1 1=s|s s|s是是经a弧到达同一子集的状态 I I2 2=I-I=I-I1 1 (3)重复（2）过程，直到每个状态子集中的状态都是等价的。72本讲稿第七十二页，共八十四页 设 I=q q1,1,q qk k ，选 q q1 1 为代表，在原来的DFA中，凡导入到q q2,2,q qk k的弧，都改成导入到q q1 1 ，然后删除q q2,2,q qk k。
40、若I I中含有原来的初态，则q q1 1是新初态；若I I中含有原来的终态，则q q1 1是新终态。可以证明：如此化简之后得到的DFA M和原来的M 是等价的，即：L(M)=L(M)L(M)=L(M)(5)若从M中再删除所有无用状态(从初态开始不可达的状态)，则M就是含有最少状态的DFA。(4)在每个子集I I中选取一个状态代表其它状态73本讲稿第七十三页，共八十四页例题9将DFA 最小化 I1=1,2,3 I2=4 bbba aab I11=1 I12=2,3 I2=4 最小化DFA baabb74本讲稿第七十四页，共八十四页例题3.6设 DFA M 如下，将其最少化。0aaaaaaabbb
41、bbb (1)(1)I I1 1=0,1,2=0,1,2 I I2 2=3,4,5,6=3,4,5,6(2)(2)0,1,2 0,1,2 分为分为 0,2 1 0,2 1(3)(3)0,2 0,2 分为：分为：0 1 0 1(4)(4)3,4,5,6 3,4,5,6 不可分(5)(5)故故 0 1 20 1 2 3,4,5,6 3,4,5,6 b75本讲稿第七十五页，共八十四页例题3.6设 DFA M 如下，将其最少化。最少化的 DFA DFA：0aaaaaaabbbbbb (5)(5)故故 0 1 20 1 2 3,4,5,6 3,4,5,6 0aabb abab3b76本讲稿第七十六页，共
42、八十四页3.4 词法分析器 L 的自动产生LEX编译程序词法分析器LLEX源程序(.l)词法分析器 (lexyy.c)输入串 单词符号串77本讲稿第七十七页，共八十四页LEX语言：是专门描述词法分析器的语言。一个LEX源程序主要包括两部分：正规定义式和识别规则。（1）上的正规定义式为：d d1 1 r r1 1 d di i r ri i 其中 d di i 表示不同的名字，r ri i 是 dd1 1,d,di-1i-1 上的正规式。78本讲稿第七十八页，共八十四页（2）识别规则是如下一串LEX语句：P P1 1 A A1 1 P Pm m A Am m 其中 P Pi i 是一个正规式，称
43、为词形，A Ai i 是一小段程序代码。分析器L只能识别具有词形P P1,1,P Pm m的单词符号，它指明在识别出词型为Pi的单词后，词法分析器应采取动作Ai。分析器L一般是返回Pi的种别编码和属性值。79本讲稿第七十九页，共八十四页作业 P647.8.9.10*.（选做）12.14.15.20.80本讲稿第八十页，共八十四页补充题1.1.构造a,ba,b上的含有偶数个a的文法。2.2.构造a,ba,b上的含有奇数个a的文法。3.3.构造a,ba,b上的含有偶数个a，且偶数个b的文法。4.4.构造a,ba,b上的含有奇数个a，且奇数个b的文法。5.5.构造a,ba,b上的含有偶数个a，且奇数
44、个b的文法。81本讲稿第八十一页，共八十四页补：正规文法与正规式的等价性 正规文法正规式82本讲稿第八十二页，共八十四页 思路：思路：让正则文法对应于非终极符的联立方程组，解此联让正则文法对应于非终极符的联立方程组，解此联立方程组，以求得关于识别符号（开始符）的正则表达式。立方程组，以求得关于识别符号（开始符）的正则表达式。例：文法例：文法G1 SG1 SScSc BcBc B BB bB b AbAb A AAaAa a a 建立方程组：建立方程组：S SSc+Bc .(1)Sc+Bc .(1)B BB b+Ab.(2)B b+Ab.(2)A AAa+a.(3)Aa+a.(3)由（由（3 3）得：）得：A=aa.(4)A=aa.(4)依次代入（依次代入（3)3)（2 2）（）（1 1）得：）得：S=aabbcc S=aabbcc 即语言即语言 aai ib bj jc ck k i,j,k i,j,k 1183本讲稿第八十三页，共八十四页例：文法G2 ZZ0T1 1 0.(1)TZ00.(2)建立方程组：ZZ0+T1+1+0.(1)TZ0+0.(2)(2)代入（1）得：Z=Z（0 01）+（01 1 0）=（01 1 0）0 0184本讲稿第八十四页，共八十四页