第三章词法分析四四 正则式正则式四四 正则式（正规式）正则式（正规式）n 这一节介绍表示正则语言的一个更为简洁的方法正则式。这是一种表示语言的代数方法。n利用正则式来描述单词的结构，可以更容易地构造词法分析器和词法分析器的自动生成程序。1. 正则式（正则式（Regular Expression）的形式定义）的形式定义n设设 是一个字母表，并设是一个字母表，并设 = , ,+, ,*,(,) , 上的正规式是上的正规式是 上的一个串，其递归定义如下：上的一个串，其递归定义如下： （1） 和和 及及 中的元素都是正则式，对应正规集：中的元素都是正则式，对应正规集： 、 、a, a （2） 若若和和是是 上的正则式，分别表示语言上的正则式，分别表示语言A和和B，则，则 () 、| ( 也写成也写成+)、(也写成也写成) 及及 * 也是也是 上的上的正规式正规式，分别表示的语言为，分别表示的语言为 A、A B、AB、A* （3）有限次应用）有限次应用步骤步骤（1）、（）、（2）生成的表达式仍是）生成的表达式仍是 上上 的正则表达式。的正则表达式。 2. 运算符及优先级运算符及优先级n（ | ） + 表示“或”运算，（也称“和”运算、选择运算）。n n表示“连接”运算（也称“乘积”运算、并置运算）。 n*表示“闭包”运算（也称自重复连接运算）。 31 231 1 2 22. 运算符及优先级运算符及优先级n优先级：由高到低分别是闭包、乘积、加。n结合律：加、乘、闭包运算均执行左结合规则。n一般不写n*等价于如下的正则式： | | | | n例：=a, b,求上的正则式及正则集。n解： 正规式 正规集 a a a|b a,b ab ab a* ,a,aa, (a|b)(a|b) aa,ab,ba,bb (a|b)* a,b上的任意串 (a|b)*(aa|bbb)(a|b)* *上所有含有两个相继的a 或三个连续的b的a、b串 (a|b)*abb 以abb结尾的a、b串正则式的值正则式的值n| + |=| | |=x| x| |或x| |n| |= | | | |=xy| x| |且y| |n|*|=|*=x| x |i |0 = i=0例：例：用正则式描述程序设计语言的词法结构用正则式描述程序设计语言的词法结构.解：解：令令 =a z,0 9,正则式正则式 =a|b|z正则式正则式 =0|1|9描述标识符的正则式：描述标识符的正则式： ( | )*描述无符号整数的正则式：描述无符号整数的正则式： *例：例：用正则式描述程序设计语言的词法结构用正则式描述程序设计语言的词法结构.解：解：令令 =a z,0 9,正则式正则式 =a|b|z正则式正则式 =0|1|9描述无符号实常数的正则式：描述无符号实常数的正则式： *. *. * *. *(E|e)(+|-| ) *. *(E|e)(+|-| ) * *(E|e)(+|-| ) *结合上述各式，则无符号实常数的正则式为：结合上述各式，则无符号实常数的正则式为： *. *|. *|( *. *|. *| *)(E|e)(+|-| ) *3. 正则式的性质正则式的性质n1.交换律 + = + n2.结合律 + ( +)= (+ ) + ()= ()n3.分配律 ( +)= + (+ )= +n4.恒等元素 = =同一正则语言的正则式表示不唯一同一正则语言的正则式表示不唯一n注：注：正则式表示的语言又称为正则集。正则表达式 表示的语言也记为L()。n语言的正则式表示不是唯一的。例如， L(1*1*)=L(1*)*) L(a*(baa)*)*)=L(a+baa)*)(ba)*b=b(ab)* (a|b)*=(a*b*)*4. 正则式与正则文法的等价性正则式与正则文法的等价性（1）正则语言可以由正则式定义，也可以由正则文 法定义。（2）对任一正则文法，存在一个定义同一个语言的正则式。（3）对每个正则式，存在一个生成同一语言的正则文法。4. 正则式与正则文法的等价性正则式与正则文法的等价性正则文法 正则式 AxB By A=xy AxA | y A=x*y Ax Ay A=x | y 正则文法构造正则式正则文法构造正则式4. 正则式与正则文法的等价性正则式与正则文法的等价性首先对任意给定的正则式，生成产生式S （S是文法的开始符号）。 若有规则形式为 重写为 A xy AxB By A x*y AxA | y A x | y Ax Ay n不断利用上述规则做变换，直到每个产生式右部最多包含有一个终极符为止。正则式构造正则文法正则式构造正则文法4. 正则式与正则文法的等价性正则式与正则文法的等价性n例：例： 文法G： S aS | aB BbC CaC | a 求正则式。解：由得 C=a*a 代入得 B=ba*a 代入： SaS|aba*a所以 S=a*aba*a所以 S=aibaj| i, j =14. 正则式与正则文法的等价性正则式与正则文法的等价性n例：例：将R=a(a|b)*转换为正规文法 解： Sa(a|b)* 进一步转换： 即得到正规文法GS: SaA AaA|bA| 4. 正则式与正则文法的等价性正则式与正则文法的等价性nEx:写出一个生成与下面正则式相同的语言的文法： (a|c|ba|bc)*(b| )解：令=a|c|ba|bc 则 GS: SS|b| 即 SaS|cS|baS|bcS|b| 5. 正则式与正则式与FA的等价性的等价性n两个定理：两个定理：（1）对于上的NFA M，可构造一个上的正则式r，使L(r)=L(M)； （2）对于上的每个正则式r，可构造上的NFA M，使L(M)=L(r)。5.1 NFA M构造等价的正则式构造等价的正则式R（1）新增两个状态x，y。x为新的初态结点，用弧连向原来所有的初态结点。y为新的终态结点，将原来所有的终态结点用弧连向y。形成与M等价的M。（2）对NFA M中的结点按下页图示的规则合并弧和去状态。（3）反复使用这些规则，直到NFA M中只剩下结点 x，y。其弧上的标记即为所求的正则式R。 （结果不唯一）（结果不唯一）5.1 NFA M构造等价的正则式构造等价的正则式RNFA M 到正则式的转换规则到正则式的转换规则12 | 12123 13123 *13若有若有若有代之为：代之为：代之为：n例：例： 已知FA，求正则式 n解：所求正则式r=(a | b | c (a | b)*d )*，具体步骤见下图(a)(c) 图 上例的FA Mcda2b1ab图 例中由FA求正则式的步骤cda | b2xa | b1y(a)xa | b1y(b)c (a | b)*dxy(c)(a | b | c (a | b)*d)*cda2b1abn例：例：已知FA，求正则式。1图 FA M的状态图S A 0B 00解：利用规则删去一个状态时，必须注意到一切与之有关的支路。所求的正则式 r= ( 00*1)*00*0。求解步骤见图 (a)(c)。图 例中由FA求正则式的步骤S A10y 00xB(a)S y x(b) 00*000*1y x(c)(00*1)*00*0图 上例的FA MS A0B 0015.2 正则式正则式R构造等价的构造等价的NFA M（1）引进两个状态x和y，x是NFA M的开始状态，y是终止状态，x引向y的弧上标记为正则式R，即把正则式表示成拓广转换图。 （2）运用如下的三条转换规则不断加入新结点进行分解，直到每个弧的标记只是VT中的一个字符或为止，所得的NFA M即为所求。正则式R到NFA M的转换规则12| 12132 12132*12若有若有若有代之为：代之为：代之为：例：例：已知正则式r=b*(d|ad)(b|ad)+，构造等价的NFA M。n解： 因为R+=RR*原来正则式改造为：b*(d|ad)(b|ad)(b|ad)*构造NFA M 的步骤见图(a)(c)。正则式构造NFA M(c)xy b*(d|ad)(b|ad)(b|ad)*x y b*12 d | ad3 b | ad (b | ad)*(a)(b)x d ad4 b2 5 1 da3 6 da8 7 by bdn例：例：已知正则式r= 1 (01)*(0* | 1* ) 0 ，构造等价的NFA M。 n解：根据正则式定义语言的特征，可以使NFA M的状态图更简化。 NFA MS 1DE 01A0B1C00第三模块词法分析五五 DFA的化简的化简 (DFA的最小化）的最小化）五五 DFA的化简的化简 (DFA(DFA的最小化）的最小化）n在编译程序中，扫描器的效率是很重要的，如果可能的话，应该使构造的DFA最小（即状态数最少）。n实际上，对于任何给定的DFA，都有与之等价且具有最小状态数的DFA存在，并且是唯一的. DFA的最小化的例子的最小化的例子A aBbbaa SBS aba最小化的最小化的DFA一一. 定义定义1.化简的FA：是指没有多余状态且状态中没有两个是互相等价的。2.多余状态：从DFA的开始状态出发，任何输入串也不能到达的那个状态。 3.在DFA中，状态s和t状态等价的条件是：q（1）一致性条件s和t必须同时为可接受态或不可接受态。 q（2）蔓延性条件对于所有输入符号， s和t必须转换到等价的状态集里。如果DFA的状态s和t不等价，则称s和t是可区分的。二. 分割法将分割法将DFA最小化最小化nDFA的最小化采用分割法，即将M的状态集分割成一些不相交的子集，使得任何不同子集的状态都是可区分的，而同一子集中的任何状态都是等价的。二. 分割法将分割法将DFA最小化最小化 具体方法：具体方法：（1 1）把）把DFADFA的终态和非终态分开，形成具有两个子集的基本的终态和非终态分开，形成具有两个子集的基本划分。划分。（2 2）对当前已划分出的子集）对当前已划分出的子集I I(1) (1) ,I(2),I(2), ,I I(n(n) )，看每一个，看每一个I I(i(i) )是否能进一步分割是否能进一步分割; ; 例如：例如： 如果如果s s和和t t I I(i(i) ) ，若，若f(s,af(s,a) )和和f(t,af(t,a) )属于不同子集，属于不同子集，则则I I(i(i) )应进一步细分，使应进一步细分，使s s和和t t属于属于I I(i(i) )的不同子集的不同子集; ; 若若s s有定义，而有定义，而t t无定义，则无定义，则s s和和t t也是可区分的也是可区分的，应划分在，应划分在I I(i(i) )的不同子集中。的不同子集中。二. 分割法将分割法将DFA最小化最小化具体方法：具体方法：（3 3） 重复进行（重复进行（2 2）步中的划分，直到每个子集无法再分）步中的划分，直到每个子集无法再分割。割。（4 4） 对每个子集，选一个状态为代表，删去其余等价状态。对每个子集，选一个状态为代表，删去其余等价状态。 例如，例如， I I(i(i) )=S=S1 1,S,S2 2,S,S3 3,删去删去S S2 2和和S S3 3。原原DFA MDFA M中有指向中有指向S S2 2和和S S3 3的有的有向边，均改为指向向边，均改为指向S S1 1, ,所有所有S S2 2和和S S3 3引出的弧，均已由引出的弧，均已由S S1 1引出。引出。 （5 5） 若子集中有初态，则该状态为新的初态；若子集中有若子集中有初态，则该状态为新的初态；若子集中有终态，则该状态为新的终态。终态，则该状态为新的终态。n例：例：将下图所示的DFA M最小化。n解：首先将M的状态分成两个子集 P0=(1,2,3,4, 5,6,7) DFA Ma61bbababb75aaaba423b在P0中寻找一个子集和一个输入符号，使该子集中的状态可区分。考察：1,2,3,4 因为 1,2a=6,7 5,6,7 3,4a=1,4 1,2,3,4在P1中寻找一个子集和一个输入符号，使该子集的状态可区别。对于3,4中： 由于 3a=1 4a=4 所以 P2=1,2,3,4,5,6,7在P2中考察5,6,7 ，由于 5a=7, 6,7a=4 所以 P2=1,2,3,4,5,6,7 经观察，不能再划分了。 DFA Ma61bbababb75aaaba423bn令1代表1,2，6代表6,7，消去2和7。把原来指向2和7的弧，指向1和6。最小化的DFA 如下图n比起原来的DFA，化简的DFA具有较少的状态，因而在计算机上实现起来更简洁。 最小化的DFA Ma61bbbab5aaba43练习. 把图确定化和最小化DFAabF0121114213332405554 02354 1bbbbbaaaaaab练习：把右图确定化和最小化解：已知是DFA，做最小化 P0 = （0, 1,2,3,4,5） 因为 4a=0 , 1,2,3,5a=1,3,5所以 P1 = (0, 1,2,3,5,4) 因为1,5b=4, 2,3b=2,3 所以 P2 = (0, 1,5, 2,3, 4) P3 = (0, 1,5, 2, 3, 4) 1,5等价，用1代替5 02354 1bbbbbaaaaaab 0234 1bbbaaaaabbDFAAbF0121114213332405554三. 定理n定理：对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下是唯一的。（不考虑状态命名）n可通过构造最小DFA，证明正则式的等价性 如：(a|b)*=(a*|b*)*=(|a)b*)* (a|baa)*=(a*(baa)*)*通过构造下列正则式的最小DFA，证明它们是等价的。 (1) (a | b)* (2) (a* | b*)* (3) ( | a)b*)*解：(1)YXABCab(2)(1)-(3)对应的最小DFA为：XYab(3) ab XAYabab 根据正则文法，求正则式。根据正则文法，求正则式。 （比较特殊案例）（比较特殊案例） 例:GS: SbS|aA AaA|bB BaA|bC CbS|aA | , 求正则式解：由、 ，C S | 所以 BaA|bS|b B=S+b 所以 A=aA+b(S+b)=aA+bS+bb, A=S+bb S=bS+a(S+bb)=(a+b)S+abb 因此 S=(a+b)*abb即：以abb结尾的a、b串本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。 本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷自动机。词法分析概述词法分析器的手工构造词法分析器的手工构造所谓词法分析器的手工构造，是将状态转换图识别单词的所谓词法分析器的手工构造，是将状态转换图识别单词的过程，转化为程序。过程，转化为程序。具体方法是：具体方法是：（1 1）根据正则表达式（或正则文法）描述的单词结构，构造识别）根据正则表达式（或正则文法）描述的单词结构，构造识别 单词的状态转换图。单词的状态转换图。（2 2）根据状态转换图，画出词法分析程序流程图。）根据状态转换图，画出词法分析程序流程图。状态转换图对应程序流程图的方法状态转换图对应程序流程图的方法状态转换图中状态的变迁，可通过程序中控制流程的改变来实现。具体步骤是：（1）初始状态对应程序的开始；（2）结束状态对应程序的结束；（3）状态转移对应条件语句或多分支转移语句；（4）状态图中的环对应程序中循环语句；（5）终态返回时，应满足最长匹配原则。关于最长匹配原则，是指识别出的单词有混淆时，按长度关于最长匹配原则，是指识别出的单词有混淆时，按长度最长来确定，以避免回溯问题。例如程序段最长来确定，以避免回溯问题。例如程序段“x+yx+y”中，中，识别单词单词的顺序是识别单词单词的顺序是 x x、+、+ +、y y。词法分析概述 词法分析器的自动生成模型词法分析器的自动生成模型词法分析器的自动生成是指能够自动构造分析表，它是关于状态转换图的矩阵形式。这种词法分析程序的总控制程序是根据分析表的内容进行操作，实现状态的变迁和单词的识别。 输入某语言的单词描述（正则式描述单词）分析表的自动生成程序图 分析表的自动构造分析表输入字符序列分析表总控制程序图操作分析表的词法分析器模型自动构造词法分析器的难点在于构造分析表，对于实际的程序设计语言来说，需要借助词法分析器的自动生成工具LEX来实现 词法分析器的自动生成模型词法分析器的自动生成模型词法分析程序的自动生成器词法分析程序的自动生成器LEX LEX 使用LEX的流程如图所示: LEX源程序 LEX YYLEX.C YYLEX.CC编译器 YYLEX.EXE 字符串源程序 YYLEX.EXE符号串源程序图 LEX使用流程 LEXLEX源程序是使用源程序是使用LEXLEX语言编写的词法规则说明，经过语言编写的词法规则说明，经过LEXLEX编编译后形成目标文件译后形成目标文件YYLEX.CYYLEX.C，再用再用C C编译器对编译器对YYLEX.CYYLEX.C进行编进行编译，生成目标程序译，生成目标程序YYLEX.EXEYYLEX.EXE，它就是词法分析程序它就是词法分析程序。用。用YYLEX.EXEYYLEX.EXE就可以将字符串源程序转换成符号串源程序。就可以将字符串源程序转换成符号串源程序。 词法分析程序的自动生成器词法分析程序的自动生成器LEX LEX LEX使用步骤：1、编写LEX源程序，如“Cffx.l”，将“Cffx.l”与FLEX.EXE保存在同一文件夹下。2、进入DOS环境FLEX.EXE所在文件夹，运行FLEX.EXE程序。FLEX cffx.l3、运行FLEX后，产生“LEXYY.C”程序4、用VC打开“LEXYY.C”程序，编译后产生“LEXYY.EXE”程序。5、编写TEST语言源程序，保存为AAA.TEST，并与“LEXYY.EXE”保存在同一文件夹下。6、进入DOS环境“LEXYY.EXE”所在文件夹，运行“LEXYY.EXE”程序。LEXYY.EXE AAA.TEST BBB.TXT7、打开“BBB.TXT”，看词法分析的结果。n词法分析程序的设计技术可应用于其他领域，比如查询语言以及信息检索系统等。这种应用领域的程序设计特点是：通过字符串模式的匹配来引发动作。n说明词法分析程序的语言，可以看成是一个模式-动作语言。n词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。词法分析后记1 解释下面每个有限自动机识别的语言是什么？(1)12345aaaaa作业：正则式：正则式：a(aaaaa)*(2)0120001112 给出接受下列在字母表0，1上的语言的DFA，并给出正规式描述: (1) 所有以00结束的串的集合； (0|1)*00 (2) 所有具有三个0的串的集合；1*01*0 1*01* （3）每个0后面至少紧随两个1的0、1串。 1*|1*011(011|1)* 或者 （1|1*011）* (两个终止状态分别讨论) 0(2) (0|1(01*0)*1)*3设有正规文法GS，GS：SaAAaA|bS|a（1）试构造一确定的有穷自动机 M，使L（M）=L（G）； （2）求一正规式，恰好是该文法所定义的语言。 （正则式：a(a|ba）*a )4 . 考虑字母表=a上的语言，该语言包含的所有串的长度要么是2的倍数，要么是3的倍数，其中包括了空串。（提示：串长只能是2、3的倍数，如：aaaaa不满足要求）（1）试写出该语言的正则表达式。（aa）*|（aaa）*（2）画出识别该语言的不确定有限自动机（NFA）；你可直接画NFA，不必运用机械算法从正则表达式得到。（3）画出识别该语言的确定有限自动机（DFA）；你可直接画DFA，不必运用机械算法从上一小题的NFA确定化得到。其中第一列是单词属性，第二列是单词值。其中第一列是单词属性，第二列是单词值。 intintIDa;IDa=NUM10;# # int a;a=10;#一个简单的词法分析器的设计与实现（课后作业）一个简单的词法分析器的设计与实现（课后作业）1样本样本S语言的定义语言的定义 int ID; | int ID;if () then else | if () then | while () do | ID=| ; | 一个简单的词法分析器的设计与实现一个简单的词法分析器的设计与实现 and | or | ID relop ID | ID + | - | * | / | () | ID | NUM根据样本S语言的定义， 一个合法的程序如下：n n int a; int b;n a=10;n if (a0) then b=an 一个简单的词法分析器的设计与实现2样本样本S语言的单词类别及内部表示语言的单词类别及内部表示 文法中的终极符是语言的单词，单词的类别以助记符的形式在文法中表现出来。文法的非终极符是语法单位名称，如语句、算术表达式等。保留字：int、if、then、else、while、do。标识符：用助记符(或称为单词记号） ID 表示。常数： 用助记符NUM表示。算术运算符：+、- 、*、/。逻辑运算符：and、or。关系运算符：、=、!= 、= =用助记符用助记符relop表示。表示。分隔符：、 ；、（、；、（、 ）、）、=。 一个简单的词法分析器的设计与实现3样本样本S语言的单词识别的状态转换图语言的单词识别的状态转换图 每个单词的识别都从初始状态开始，如果把状态转换图看成一个函数，则每次调用只能识别出一个单词。 对于保留字这类单词，并不专设对应的状态转换图，而是事先存在保留字表中。每识别出一个标识符，就去查保留字表，若匹配成功，则该标识符是一个保留字，否则就是一个标识符。 （ID，标识符名）或（保留字，标识符名）或（保留字，_ ）返回（返回（NUM，常数值），常数值）（+，_）或（）或（- ，_）或（）或（*，_）或（）或（/，_）或（）或（and，_）或（）或（or，_）或（，或（，_）或（）或（ ），），_）或（或（，_）或（）或（，_）或（；，）或（；，_）（relop，=）或）或（relop，!=）（relop，）或）或“ ! 是非法字符是非法字符” 返回（relop，= =）， 返回（=，_）返回 “非法字符”