编译原理 第03章 词法分析与有穷自动机.ppt

第三章 词法分析与有穷自动机 词法分析程序功能 词法分析程序的编写方法 正规文法与有穷自动机 正规式与有穷自动机正规式与有穷自动机 语言单词符号的两种定义方式 单词符号及输出单词的形式 回顾回顾：词法分析的任务字符串表示的源程序词法分析器字符单词符号取下一个单词符号语法分析器 3.1 词法分析程序的功能 3.2 单词符号及输出单词的形式 关键字 也称基本字，例如，C语言中 的if，else，while,do等。标识符 表示各种名字，如变量名、常 量名、数组名和函数名等。语言的单词符号是指语言中具有独立语言的单词符号是指语言中具有独立 意义的最小语法单位意义的最小语法单位。3.2 单词符号及输出单词的形式 常数 整型常数125、实型常数0.718、布尔型常数TRUE等。运算符 如、*、/、等。分界符 如，、；、（、）、：等。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|lT Tl|d|lT|dT 以标识符为例:l(l|d)*正规文法设有字母表=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)e1.e2 也是上的一个正规式，它所表示的正规集为L(e1.e2)=L(e1)L(e2)(3)(e1)*也是上的一个正规式，它所表示的正规集为L(e1)*)=(L(e1)*3.3.1 正规式和正规集 3.3.1 正规式和正规集 运算符的优先级：闭包“*”连接“”或“|”。连结符“”一般可省略不写。运算符均是左结合的。3.3.1 正规式和正规集 例1 设有字母表=a,b，有：1.a 和 b是正规式，相应正规集为2.a|b 是正规式，相应正规集为3.ab 是正规式，相应正规集为L(a)=a,L(b)=b L(a|b)=L(a)L(b)=a,bL(ab)=L(a)L(b)=ab=ab 3.3.1 正规式和正规集4.(a|b)*是正规式，相应正规集为 需要指出的是，a,b*的任一子集不一定是正规集。如：a,b*的子集 an bn|n1 L(a|b)*)=(L(a|b)*=a,b*=,a,b,aa,ab,ba,bb,5.ba a*是正规式，相应的正规集为L(ba a*)=L(b)L(a a*)=b,ba,baa,baaa,6.(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 正规式和正规集 3.3.1 正规式和正规集 例2 设=a,b,c,则 aa*bb*cc*是上的一个正规式,它所表示的正规集：L=abc,aabc,abbc,abcc,aaabc,=ambnck|m,n,k1a+b+c+3.3.1 正规式和正规集 例3 设程序语言字母表是键盘字符集合，则程序语言部分单词符号可用如下正规式定义：关键字 if|else|while|do标识符 l(l|d)*l代表az中任一字母整常数 dd*d代表09中任一数字关系运算符 =3.3.1 正规式和正规集 注意:正规式与正规文法之间的区 别和联系：标识符 I=l(l|d)*l代表az中任一字母 d代表09中任一数字Il|Il|Id 3.3.1 正规式和正规集如果正规式 R1 和 R2 描述的正规集相同,则我们称正规式R1与R2等价。记为 R1R2。例如，(a|b)*=(a*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 (分配律)6 A|A=A7 A*=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)Z 0AA 0A|0BB 1A|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 X=X+,则解为 X=*3.3.2 正规文法与正规式 例2 设有正规文法G：A aB|bBB aC|a|bC aB 试给出该文法生成语言的正规式。正规式方程组如下：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)X=X+,则解为 X=*3.3.2 正规文法与正规式 例3 设有正规文法G：相应的正规式方程组为Z U0|V1 U Z1|1 V Z0|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)*X=X+,则解为 X=*3.3.2 正规文法与正规式2.正规式到正规文法的转换(1)令 VT=。(2)对任何正规式R选择一个非终结符Z生 成规则ZR并令SZ。(3)若a和b都是正规式，对形如 Aab 的 规则转换成 AaB 和 Bb 两规则，其中B是新增的非终结符。3.3.2 正规文法与正规式(4)对已转换的文法中,形如A a*b 的规 则，进一步转换 成 A aA|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)BB (aa)*(a|b)3.3.2 正规文法与正规式对B根据规则(4)变换为 根据规则(3)变换为即前面例2中的文法。A aB|bBB aaB|a|bA aB|bBB aC|a|bC aB A a*bA aA|b转换成B (aa)*(a|b)3.3.2 正规文法与正规式 例2 将描述标识符的正规式 R=l(l|d)*转换成相应的正规文法令I为文法的开始符号，根据规则(2)有 根据规则(3)变换为 根据规则(4)变换为 I l(l|d)*I lT T (l|d)*I lT T (l|d)T|3.3.2 正规文法与正规式进一步变换为 去掉 规则即前面描述标识符的右线性文法。I lT T lT|dT|I l|lT T l|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,qj Q,a )3.4.1 确定有穷自动机 单值函数是指 f(q i,a)唯一地确定了下一个要转移的状态。S1S2S3S4abc 3.4.1 确定有穷自动机SQ，是唯一的一个初态。ZQ，是一个终态集。3.4.1 确定有穷自动机M=(Q,f,S,Z)例 设DFA M=(q0,q1,q2,a,b,f,q0,q2)其中 状态转换矩阵f(q0,a)=q1 f(q0,b)=q2 f(q1,a)=q1 f(q1,b)=q1 f(q2,a)=q2 f(q2,b)=q1 状态 字符 a q0 b q1 q2 q1 q1 q1 q2 q1 q2 3.4.1 确定有穷自动机 一个 DFA也可以表示成一张状态转换图。例中DFA M=(q0,q1,q2,a,b,f,q0,q2)的状态转换图如下图所示。f(q0,a)=q1 f(q0,b)=q2 f(q1,a)=q1 f(q1,b)=q1 f(q2,a)=q2 f(q2,b)=q1 q0q1q2bbbaaa 3.4.1 确定有穷自动机 对符号串，若存在一条从初态结点到终态结点的道路,在这条路上所有弧的标记连结成的符号串等于,则称为DFA M所识别(或接受)。M所识别的符号串的全体记为L(M)，称为DFA M所识别的语言。例中的DFA M所识别的语言为L(M)=ba*。q0q1q2bbbaaa 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)S Q，是非空初态集。是非空初态集。S1S2S3S4aaca 3.4.2 非确定有穷自动机其中 例 设有NFA M=(1,2,3,a,b,f,1,3,2)例中 NFA M对应的状态转换矩如下表所示。f(1,a)=3 f(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 例中 NFA M 对应的状态转换图如下图所示。1abb23bb 3.4.2 非确定有穷自动机其中 例 设有NFA M=(1,2,3,a,b,f,1,3,2)f(1,a)=3 f(1,b)=1,2 f(2,a)=f(2,b)=3 f(3,a)=f(3,b)=2 例中NFA M 所识 别的语言为 L(M)=b*(b|ab)(bb)*1abb23bb 3.4.2 非确定有穷自动机 例中 NFA M,对符号串=bbb可由3条路来识别。由NFA的定义可知，同一个符号串 可由多 条路来识别。第二条路：状态1状态1状态2；第一条路：状态1状态2状态3状态2；第三条路：状态3状态2状态3状态2；bb1ab23b 3.4.2 非确定有穷自动机 DFA是NFA 的特例,即对于每个NFA M 存在 DFA M,使 L(M)=L(M)。因此，利用有穷自动机构造词法分析程序的方法:从单词的描述中构造出NFA;再将非确定的有穷自动机转化为确定的有穷自动机;将其化简为状态最小化的DFA;对DFA的每一个状态构造一小段程序将其转化为识别语言单词的词法分析程序。3.4.2 非确定有穷自动机 3.4.3 由正规式R构造NFA 输入：字母表上的正规式R 输出：识别(接受)语言L(R)的NFA M 1.引进初始结点X和终止结点Y，把R2.表示成拓广转换图2.用如下规则对R进行分裂和加进新结点,直至每个边上只留下一个符号或 为止方法：XYR对于代换为ABr1r2ACBr1r2对于ABr1|r2代换为对于代换为ABr1*ABr1r2ACBr1 3.4.3 由正规式R构造NFA 3.分裂过程中,所有新结点均采用不同的名字，保留X，Y为全图唯一初态结点和终态结点。3.4.3 由正规式R构造NFA 例1 试构造识别标识符的NFA，描述标识符的正 规式R=l(l|d)*首先将R表示成如下拓广转换图 XYl(l|d)*从左到右分裂RX2Y1lld 3.4.3 由正规式构造NFA 例2 试构造识别语言R=(a|b)*abb 的NFA M,使 L(N)=L(R)。首先将R表示成拓广转换图 XY(a|b)*abb从左到右分裂RX12Y(a|b)*3bbaX12Y3bba0ba 3.4.3 由正规式R构造NFA 例3 试构造正规式 R=0(l*)*|01 的NFA。首先将R表示成如下拓广转换图 XY01*从左到右分裂RX2Y101首先利用正规式的等价性化简正规式(l*)*=1*R=01*|01=0(1*|1)=01*(A*)*=A*A|A*=A*3.4.3 由正规式构造NFA 3.4.4 NFA确定化为DFA的方法 对于一个NFA，由于状态转换函数 f 是一个 多值函数，因此，对于它们有基本思想:f(q,a)=q1,q2,q3,qn也就是说，DFA的每一个状态代表NFA状态 集合的某个子集，称此构造方法为子集法。即是NFA状态集合的一个子集，为了将NFA 转换为DFA，把状态集合q1,q2,q3,qn看作 一个状态A。输入：一个NFA M 输出：一个接受（识别）相同语言的DFA M 方法：利用构造闭包的方法将NFA确定化 为DFA。1.状态集合 I 的闭包的概念：设I是NFA M的一个状态子集,closure(I)定义 如下：(1)若sI,则 s closure(I)(2)若s closure(I),那么从s出发经过任意条弧能到达的任何状态 s，都属于 closure(I)3.4.4 NFA确定化为DFA的方法 即 closure(I)表示所有那些从I中的状态出发经过道路所能到达的NFA的状态所组成的集合,I中任何状态也在其中，因为它们是通过通路到达自身的。该集合对DFA来说是一个状态。3.4.4 NFA确定化为DFA的方法 closure(0)=0,1,2,3例：这个状态集合实际就是要求的DFA的初态。0123456789bb 3.4.4 NFA确定化为DFA的方法 若令A=0,1,2,3,则令B=closure(4,7)=4,5,6,7,8,9B即是DFA在状态A下遇到输入符号b，转移到的后继状态。J=f(A,b)=f(0,b)f(1,b)f(2,b)f(3,b)=4,70123456789bb 3.4.4 NFA确定化为DFA的方法 2.从 NFA M 构造 DFA M 的算法 已知 NFA M=(Q,f,x,y)求 DFA M=(I,f,初态,终态集)开始令I=3.4.4 NFA确定化为DFA的方法 3.4.4 NFA确定化为DFA的方法 步骤一：由NFA构造一张表：(1)表的列数由中的字符数确定：列数=字符数+1。第一列为I,第二列、第三列为Ia,Ib,其中a,b为中的字符。(2)第一列第一行元素为:_CLOSURE(X),X为NFA的开始状态。(3)由(2)中的状态出发,求Ia,Ib,其中Ia=_CLOSURE(J),J 表示(2)中的状态在读入a时转换成的状态集;Ib=_CLOSURE(J),J 表示(2)中的状态在读入b时转换成的状态集;。3.4.4 NFA确定化为DFA的方法 (4)检查Ia,Ib 是否在第一列出现过，把凡是未出现过的都填入空行的第一列，并求出相应的Ia,Ib,直到所有Ia,Ib都在第一列出现为止。步骤二：由上表构造DFA：表中第一列第一行元素为DFA开始状态，含有原NFA终态的集合为DFA的终止状态。求DFA M的初态CLOSURE(x),并置为无标记送入I;while(I中存在一个无标记的状态 T=s1,s2,s3,sn)标记T;for (每个输入符号a)J=f(s1,s2,s3,sn,a)U=CLOSURE(J);if(U不在I中&U不为空)置U为无标记并送入I;if(U不为空)置MT,a=U;if(U中至少有一个是N的终态)U为M的终态;/*求 f(T,a)=U*/=f(s1,a)f(s2,a)f(sn,a);3.4.4 NFA确定化为DFA的方法 例1 将下图所示的NFA N确定化。DFA的开始状态为:A=CLOSURE(X)=X,0,1Ib X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A(1)f(A,a)=CLOSURE(f(X,0,1,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=Af(A,b)=CLOSURE(f(X,0,1,b)=CLOSURE(0)=0,1=Cf(A,a)=CLOSURE(f(X,0,1,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,Cf(A,b)=CLOSURE(f(X,0,1,b)=CLOSURE(0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BCf(B,a)=CLOSURE(f(0,1,2,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,Cf(B,b)=CLOSURE(f(0,1,2,b)=CLOSURE(0,3)=0,1,3=D 0,1,2 0,1 0,1,2 0,1 BC(2)在I中取Bf(B,a)=CLOSURE(f(0,1,2,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,Df(B,b)=CLOSURE(f(0,1,2,b)=CLOSURE(0,3)=0,1,3=D 0,1,2 0,1 0,1,2 0,1 BC 0,1,2 0,1,3 0,1,3 Df(C,a)=CLOSURE(f(0,1,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,Df(C,b)=CLOSURE(f(0,1,b)=CLOSURE(0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC 0,1,2 0,1,3 0,1,3 Df(C,a)=CLOSURE(f(0,1,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,Df(C,b)=CLOSURE(f(0,1,b)=CLOSURE(0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC(3)在I中取C 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 f(D,a)=CLOSURE(f(0,1,3,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,Df(D,b)=CLOSURE(f(0,1,3,b)=CLOSURE(0,Y)=0,1,Y=E 0,1,2 0,1 0,1,2 0,1 BC 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 f(D,a)=CLOSURE(f(0,1,3,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,D,Ef(D,b)=CLOSURE(f(0,1,3,b)=CLOSURE(0,Y)=0,1,Y=E 0,1,2 0,1 0,1,2 0,1 BC 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 0,1,Y E 0,1,2 0,1,Y f(E,a)=CLOSURE(f(0,1,Y,a)=CLOSURE(0,2)=0,1,2=BIb X,0,1 IaAIaX12Y3bba0b 3.4.4 NFA确定化为DFA的方法 I=A,B,C,D,Ef(E,b)=CLOSURE(f(0,1,Y,b)=CLOSURE(0)=0,1=C 0,1,2 0,1 0,1,2 0,1 BC 0,1,2 0,1,3 0,1,3 D 0,1,2 0,1 0,1,Y E 0,1,2 0,1,Y 未增加新的状态,且已无其它状态可处理 0,1,2 0,1 例2 将下面的NFA N确定化。首先确定其初态,命名为0状态 IIdIlX1,2,Y1,2,Y2,Y2,Y2,Y2,Y2,Y0210=CLOSURE(X)=XX2Y1lld 3.4.4 NFA确定化为DFA的方法 d02l1lld1ABCDEaaaaabbbbbIb X,0,1 0,1,Y 0,1,3 0,1 0,1,2 Ia 0,1,2 0,1,2 0,1 0,1,2 0,1 0,1,Y 0,1 EDCBAI 0,1,3 0,1,2 0,1,2 3.4.4 NFA确定化为DFA的方法 例3 将下面的NFA N确定化。首先确定其初态,命名为0状态 I10X1,2,Y1,2,Y2,Y2,Y2,Y0210=CLOSURE(X)=XX2Y101 3.4.4 NFA确定化为DFA的方法 010121 3.4.5 DFA的化简 1.DFA的化简 所谓一个DFA M 的化简是指寻找一个状态数比 M 少的 DFA M，使得 L(M)=L(M)。(1)没有多余状态。化简了的DFA满足两个条件:(2)它的状态集中没有两个状态是 互相等价的。所谓有穷自动机的多余状态是指从该自动机的开始状态出发，任何输入串不能到达的状态。3.4.5 DFA的化简 2.多余状态3.等价状态 设 DFA M(Q,f,S0,Z),s,t Q，若对任何 *,f(s,)Z 当且仅当f(t,)Z，则称状态 s 和 t 是等价的。例如，终态与非终态是可区别的。因为终态有一条到达自身的道路，而非终态没有到达终态的道路。3.4.5 DFA的化简 如果 s 和 t 不等价,则称 s 和 t 是可区别的。无多余状态下把M的状态集 Q划分成一些不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的。化简方法:然后在每个子集中任取一个状态作“代表”,而删去子集中其余状态,并把指向其余状态的箭弧都改作指向作“代表”的状态中。3.4.5 DFA的化简 A,F,GI,L,MW,ZE,H,KO,R,T,XAMWHT下面给出化简算法的具体执行步骤:1.将DFA M的状态集Q分成两个子集：终态集F和非终态集F，形成初始划分。2.对使用如下方法建立新划分NEW：(1)把G划分成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于的同一子集。对的每个状态子集G:3.4.5 DFA的化简(2)用G划分出的所有新子集替换G,形(3)成新的划分NEW；3.如果NEW，则执行第4步；否则令 NEW，重复第2步。4.划分结束后，对划分中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把指向其它状态的箭弧改为指向这个作为代表的状态。3.4.5 DFA的化简 例1.将右面的DFA M最小化 1,2l=2=(1,20)分析 由图可知，给定的DFA无多余状态。初始分划=(1,20)1,2d=2 ld02lld1d01ll 3.4.5 DFA的化简 例2.将右面的DFA最小化 初始分划=(A,B,C,DE)A,B,C,Da=B分析 由图可知，给定的DFA中无多余状态。A,B,C,Db=C,D,E=(A,B,CDE)A,B,Ca=BA,B,Cb=C,D=(A,CBDE)A,Ca=BA,Cb=C=(A,CBDE)aABCDEaaaabbbbbEDBAaaaabbbb 3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 1.在 M 的转换图上添加两个结点：X 结和Y结。从X结点用连线连结到M的所有初态结点，从 M 的所有终态结点用连线连结到 Y 结。3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 2.逐步消去M中的其它结点，直至只剩下X，Y结点。在消除结点过程中，逐步用正规式来标记相应的箭弧。3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 对于代换为ABr1r2ACBr1r2对于ABr1|r2代换为代换为ABr1r2*r3ABr1r2对于ACBr1r3r2 3.4.6 有穷自动机到正规式的转换有穷自动机到正规式的转换 例1.给出如下有穷自动机的正规式R=(10|01)(10|01)*3.5 正规文法与有穷自动机正规文法与有穷自动机p前面提到程序设计语言的单词符号可用乔母斯基3型文法正规文法来描述p对于正规文法所描述的语言可用一种有穷自动机来识别 3.5 正规文法与有穷自动机正规文法与有穷自动机 右线性正规文法到有穷自动机的转换方法右线性正规文法到有穷自动机的转换方法 则相应的有穷自穷自动机 M=(Q,f,q0,Z)1.令 Q=VND (D VN)Z=D =VT q0=S2.对G中每一形如 AaB(A,BVN,aVT)的产生式,令 f(A,a)=B设给定了一个右线性正规文法 G=(VN,VT,P,S)/a=AB令f(A,)=B AaBAa3.5.1 右线性正规文法到有穷自动右线性正规文法到有穷自动 机的转换方法机的转换方法3.对G中每一形如Aa(AVN,aVT)的产生式,令 f(A,a)=D4.对G中每一形如A(AVN)的产生 式,令A为接受状态或令 f(A,)=D例1 构造下述文法GZ的有穷自动机。Z0AA0A|0BB1A|M=(Q,f,q0,Z)G=(VN,VT,P,S)M=(VN D,VT ,f,Z,D)M=(Z,A,B,D,0,1),f,Z,D)f=?根据规则来确定f(Z,0)=A f(Z,1)=f(z,)=f(A,0)=A,B f(A,1)=f(A,)=f(B,0)=f(B,1)=A f(B,)=DZ0AA0A|0BB1A|AaB(A,BVN,aVT),令 f(A,a)=BAa(AVN,aVT),令 f(A,a)=DA(AVN),令A为接受状态 或令 f(A,)=DAZ0010DB3.5.2 左线性正规文法到有穷自动左线性正规文法到有穷自动 机的转换方法机的转换方法则相应的有穷自穷自动机 M=(Q,f,q0,Z)1.令 Q=VNq0 (q0 VN)Z=S =VT 2.对G中每一形如 ABa(A,BVN,aVT)的产生式,令 f(B,a)=A设给定了一个左线性正规文法 G=(VN,VT,P,S)/a=AB令f(B,)=A ABaAa 3.5.2 左线性正规文法到有穷自动左线性正规文法到有穷自动 机的转换方法机的转换方法3.对G中每一形如 Aa(AVN,aVT)的产生式,令 f(q0,a)=A例1.构造下述文法GA的自动机。其状态图如下图所示。显然,该自动机是确定的。它识别的语言就是文法GA所描述的语言。即 L(GA)=L(M)=00*11*BB0|0AA1|B1ABS0101 3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换设给定有穷自动机M=(Q,f,q0,Z)则相应的正规文法 G=(VN,VT,P,S)1.令 VN=Q VT=S=q0 2.若f(A,a)=B 且B 时，则将产生式 AaB 加到P中。Z /3.若f(A,a)=B 且BZ时，则将产生式 AaB|a 或将产生式AaB、B 加到P中。3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换4.若文法的开始符号S是一个终态，则 将产生式 S 加到P中。例1 设有穷自动机 M=(S,A,a,b,0,1,f,S,A)M的状态转换图如图所示。根据上述转换规则,与M等价的正规文法G为:其中P:自动机M所识别的语言L(M)=L(G)=(a|b)(0|1|a|b)*。f(S,a)=A f(S,b)=Af(A,a)=A f(A,b)=Af(A,0)=A f(A,1)=A其中G=(S,A,a,b,0,1,P,S)SaA|bA|a|bAaA|bA|0A|1A|a|b|0|1例3 设DFA M=(A,B,C,D,0,1,A,B)该自动机相应的状态转换图如下图所示。构造一个右线性文法G,使得L(G)=L(M)。(A,0)=B (A,1)=D(B,0)=D (B,1)=C(C,0)=B (C,1)=D(D,0)=D (D,1)=DBCA001D0110,1其中：从状态转换图可以看出,状态D是多余的,可以去掉,于是得到与M等价的DFA M的状态转换图如图所示。3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换BCA001BCA001D0110,13.5.3 3.5.3 有穷自动机到正规文法的转换有穷自动机到正规文法的转换G=(A,B,C,0,1,P,A)其中P为或 该自动机所识别的语言为 0(10)*。A0B|0B1CC0B|0根据转换规则所求右线性文法为A0BB1C|C0B BCA001 3.6 词法分析程序的编写方法词法分析程序的编写方法 第二种方法是利用词法分析程序的自动生成工具LEX自动生成词法分析程序第一种方法是用手工方式，即根据识别语言单词的状态转换图，使用某种高级语言，例如C语言直接编写词法分析程序。例如，下表列出了某个简单语言的所有单词符号，以及它们的种别编码和单词值。单词符号 种别编码单词值1234567101113141516171819212223内部字符串二进制数值表示beginendifthenelsewhiledo标识符整常数+-*/=:=;右图是一张识别前表的单词符号的状态转换图。图中,状态0为初态,凡带双圈者均为终态;状态17是识别不出单词符号的出错情况。l 代表任一字母，d 代表任一数字。根据这张转换图，我们用C语言直接编写出识别该语言所有单词的词法分析程序。3.6 词法分析程序的编写方法词法分析程序的编写方法 关键字作为一类特殊的标识符来处理，不再专设对应的转换图。但需把它们预先安排在一个表格中，此表叫关键字表。当利用状态转换图识别出一个标识符时，就去查关键字表，以确定它是否是一个关键字。其次规定，若关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔，即此时的空白符是有意义的。根据状态转换图构造出词法分析程序最简单的办法是让每个状态对应一小段程序。1.ch 字符变量，存放当前读进的源程序字符。2.token 字符数组,存放构成单词符号的字符串。3.getch()读字符函数，每调用一次从输入缓冲区中读进源程序的下一个字符放在ch中，并把读字符指针指向下一个字符。4.getbc()函数，每次调用时，检查ch中的字符是否为空白字符，若是空白字符，则反复调用getbc()，直至ch中进入一个非空白字符为止。所用的全局变量和需调用的函数如下：3.6 词法分析程序的编写方法词法分析程序的编写方法 6.letter(ch)和 degit(ch)布尔函数，它们分别判定 ch 中的字符是否为字母和数字，从而给出true 或 false。7.reserve()整型函数，对token中的字符串查关键字表，若它是一个关键字,则回送它的编码，否则回送标识符的种别码10。5.concat()函数，每次调用把当前ch中的字符与token中的字符串联接。例如，假定token字符数组中原有值为“ab”,ch中存放着“c”,经调用concat()后，token数组中的值变为“abc”。3.6 词法分析程序的编写方法词法分析程序的编写方法 8.retract()函数，读字符指针回退一个字符。9.return()函数，收集并携带必要的信息返回调用程序，即返回语法分析程序。10.dtb()进制转换函数,它将token中的数字串转换成二进制数值表示,并以此作为函数值返回。根据该语言的状态转换图用C语言编写出词法分析程序如下:Scaner()token=NULL;getch();getbc();if (letter(ch)while(letter(ch)|digit(ch)concat();getch();retract();c=reserve();if(c!=10)return(c,token);else return(10,token);相对于状态转换图用C语言编写出词法分析程序如下:else if(digit(ch)while(digit(ch)concat();getch();retract();return(11,dtb();else switch(ch)case+:return(13,);break;case-:return(14,);break;case*:return(15,);break;case/:return(16,);break;case)return(18,);retract();return(19,);break;case:getch();if(ch=)return(22,);retract();return(21,);break;case;:return(23,);break;default:error();break;由此可知,只要构造出识别语言单词符号的有穷自动机,就很容易构造出识别语言单词符号的词法