《编译原理课件第3章.pptx》由会员分享，可在线阅读，更多相关《编译原理课件第3章.pptx（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、内容简介：内容简介：3.1 对于词法分析器的要求对于词法分析器的要求 一功能和输出形式一功能和输出形式 二接口设计二接口设计3.2 词法分析器的设计词法分析器的设计 一输入和预处理一输入和预处理 二单词符号的识别二单词符号的识别 三状态转换图及其实现三状态转换图及其实现3.3 正规表达式与有限自动机正规表达式与有限自动机 一单词符号的描述一单词符号的描述 1.正规式与正规集正规式与正规集 2.正规文法正规文法 二有限自动机二有限自动机 1.3.NFA与与DFA的等价的等价 4.DFA的化简的化简 三正规式与有限自动机的等价性三正规式与有限自动机的等价性 四正规文法与有限自动机的等价性四正规文法
2、与有限自动机的等价性3.4 词法分析器的自动产生（）词法分析器的自动产生（）略略第1页/共91页.对于词法分析器的要求对于词法分析器的要求一、功能和输出形式、功能：输入源程序，输出单词符号、单词符号的分类（）关键字:由程序语言定义的具有固定意义的标识符，也 称为保留字或基本字。例如：Pascal 语言中 begin end if while 等。（）标识符：用来表示各种名字。如变量名、数组名、过程名等。（）常数：整型、实型、布尔型、文字型等例：100 3.14159 true sample（）运算符：+、-、*、/（）界符：，；（）等第2页/共91页、输出的单词符号形式二元式：（单词种别，单词
3、符号的属性值）.对于词法分析器的要求对于词法分析器的要求单词符号的编码：标识符：一般统归为一种常数：常按整型、实型、布尔型等分类关键字：全体视为一种一字一种运算符：一符一种界符：一符一种通常用“整数编码”“单词符号的特征或特性”第3页/共91页例：例：考虑下述+代码段：while(i=j)i-;.对于词法分析器的要求对于词法分析器的要求经词法分析器处理后，它将被转换为如下的单词经词法分析器处理后，它将被转换为如下的单词符号序列：符号序列：=,-第4页/共91页.对于词法分析器的要求对于词法分析器的要求二、接口设计、词法分析器作为独立的一遍、词法分析器作为一个独立的子程序，但并不一定作为独立的一
4、遍语法分析器词法分析器调用（取下一个单词）单词优点：优点：使整个编译程序的结构更简洁、清晰和条理化.词法分析字符流单词序列（源程序）（输出在一个中间文件上）第5页/共91页、预处理：剔掉空白符、跳格符、回车符、换行符、注解部分等.一、输入、预处理.词法分析器的设计词法分析器的设计 原因：原因：编辑性字符除了出现在文字常数中之外，在别编辑性字符除了出现在文字常数中之外，在别处的任何出现都无意义处的任何出现都无意义.注解部分不是程序的必要组成部分，它的作用注解部分不是程序的必要组成部分，它的作用仅在于改善程序的易读性和易理解性仅在于改善程序的易读性和易理解性.第6页/共91页 每当词法分析器调用时
5、，就处理出一串确定长度（如120个字符）的输入字符，并将其装进词法分析器所确定的扫描缓冲区中。、预处理子程序：.词法分析器的设计词法分析器的设计第7页/共91页 起点指示器搜索指示器扫描缓冲区的两个指示器：扫描缓冲区的两个指示器：一个指向当前正在识别的单词的开始位置（即新单词的首字符）起点指示器一个用于向当前搜索以寻找单词的终点搜索指示器图 _ 源程序输入缓冲区的对半互补结构.词法分析器的设计词法分析器的设计第8页/共91页二.单词符号的识别超前搜索 1关键字的识别 2标识符的识别 3常数的识别 4算符和界符的识别.词法分析器的设计词法分析器的设计第9页/共91页三、状态转换图及其实现1 1、
6、状态转换图及其示例、状态转换图及其示例 .词法分析器的设计词法分析器的设计例例:012 数字数字 其它 *012 字母或数字字母 其它 *第10页/共91页例例:(课本课本4242页表页表3.1;433.1;43页图页图3.3)3.3).词法分析器的设计词法分析器的设计第11页/共91页2 2、状态转换图的实现、状态转换图的实现 实现方法实现方法:用程序实现用程序实现,让每个状态结点对应一小段程序。让每个状态结点对应一小段程序。A、变量和过程说明、变量和过程说明ch字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。strToken 字符数组，存放构成单词符号的字符串。字符
7、数组，存放构成单词符号的字符串。GetChar 子程序过程，将下一输入字符读到子程序过程，将下一输入字符读到ch中，搜索指中，搜索指 示器前移一字符位置。示器前移一字符位置。GetBC子程序过程，检查子程序过程，检查ch中的字符是否为空白。若是，中的字符是否为空白。若是，则调用则调用GetChar直至直至ch中进入一个非空白字符。中进入一个非空白字符。Concat子程序过程，将子程序过程，将ch中的字符连接到中的字符连接到strToken之后之后.词法分析器的设计词法分析器的设计第12页/共91页IsLetter和和IsDigit 布尔函数过程，它们分别判断布尔函数过程，它们分别判断ch中的中
8、的字符是否为字母和数字。字符是否为字母和数字。Reserve整型函数过程，对整型函数过程，对strToken中的字符串查找中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返保留字表，若它是一个保留字则返回它的编码，否则返回回0值（假定值（假定0不是保留字的编码）。不是保留字的编码）。Retract 子程序过程，将搜索指示器回调一个字符位置，子程序过程，将搜索指示器回调一个字符位置，将将ch置为空白字符。置为空白字符。InsertId整型函数过程，将整型函数过程，将strToken中的标识符插入中的标识符插入符号表，返回符号表指针。符号表，返回符号表指针。InsertConst 整型
9、函数过程，将整型函数过程，将strToken中的常数插入中的常数插入常数表，返回常数表指针。常数表，返回常数表指针。.词法分析器的设计词法分析器的设计第13页/共91页B、示例图中结点i所对应的程序段可表示为：GetChar（）;if(IsLetter()状态j的对应程序段；else if(IsDigit()状态k的对应程序段；else if(ch=/)状态l的对应程序段；else 错误处理;图中结点i所对应的程序段可表示为：GetChar（）;while(IsLetter()or IsDigit()GetChar();状态j的对应程序段lkji字母数字/ji字母或数字 其它.词法分析器的设计
10、词法分析器的设计第14页/共91页C、例课本43页图3.3；45-46页.词法分析器的设计词法分析器的设计第15页/共91页.正规表达式与有限自动机正规表达式与有限自动机一、正规式，正规集，正规文法二、确定有限自动机（DFA)三、非确定有限自动机(NFA)四、NFA=DFA=化简五、正规式有限自动机六、左线性正规文法有限自动机 左线性正规文法有限自动机第16页/共91页.正规表达式与有限自动机正规表达式与有限自动机一、正规式与正规集、递归定义正规式，a(a）若若U U，V V是正规式是正规式 U U.V,U|V,UV,U|V,U*正规集，a L(U)L(U)，L(V)L(V)L(U)L(V),
11、L(U)L(V),(L(U)L(U)L(V),L(U)L(V),(L(U)*第17页/共91页.正规表达式与有限自动机正规表达式与有限自动机例题：、令，下面是上的正规式和相应的正规集正规式正规式ba*a(a|b)*(a|b)*(aa|bb)(a|b)*正规集正规集上所有以b为首后跟任意多个a的字上所有以a为首的字上所有含有两个相继的a或两个相继的b的字第18页/共91页.正规表达式与有限自动机正规表达式与有限自动机正规式正规式 (A|B)(A|B|0|1)*(0|1)(0|1)*、令，则：一个正规式的正规集与之完全等价，只是表达形式不同正规集正规集上的“标识符”的全体上的“数”的全体第19页/
12、共91页.正规表达式与有限自动机正规表达式与有限自动机、运算“”（或）：表示从各选择对象中选择“”（连接积）：表示“连接”起来（）（闭包）：任意有限次的自重复连接注：S*=Sn=S SS L(r*)=L(r)*优先级：*”|”n=0第20页/共91页.正规表达式与有限自动机正规表达式与有限自动机例题：、L(r|s)L(rs)L(a|b)c)B、L(a|b)*)=,a,b,aa,ab,ba,bb,L(a|(b*)=,a,b,bb,bbb,C、a|bc*a|(b(c*)ab|c*d (ab)|(c*)d)=L(r)L(s)=r s=r,s=L(r)L(s)=r s=rs=L(a|b)L(c)=a,
13、bc=ac,bc第21页/共91页3、等价：若两个正规式所表示的正规集相同，则认为二者等价两个等价的正规式和，记为.正规表达式与有限自动机正规表达式与有限自动机例：b(ab)*=(ba)*b(a|b)*=(a*b*)*(a*b*)*=(a|b)*L(a*b*)*=(L(a)*(L(b)*=,a,b,aa,bb,.*=,a,b,ab,.L(a|b)*=a,b*=,a,b,ab,第22页/共91页、令、均为正规式，则：（交换律）（）（）（结合律）（）（）（结合律）U（V|W）=UV|UW（分配律）（V|W）U=VU|WU U=U =U U*=（U|）*(U*)*=U*.正规表达式与有限自动机正规表
14、达式与有限自动机第23页/共91页例题：、已知字母表=a，b，c，试求在该字母表上的仅包括一个b的所有串的集合相对应的正规式.正规表达式与有限自动机正规表达式与有限自动机B、已知字母表=a，b，c，若集合是包括了最多一个b的所有串，求其相应的正规式(a|c)*b(a|c)*(a|c)*(b|)(a|c)*第24页/共91页.正规表达式与有限自动机正规表达式与有限自动机补充：正规文法补充：正规文法单词符号单词符号1、正规文法的形式左线性文法:任何产生式为AB或A,其中 VT*,A、B VN右线性文法:任何产生式为AB或A,其中 VT*,A、B VN2、描述能力、描述能力（1）正规文法所描述的是）
15、正规文法所描述的是(VNVT)上的正规集。上的正规集。（2）多数程序设计语言的单词的词法都能用正规文法来描述。）多数程序设计语言的单词的词法都能用正规文法来描述。第25页/共91页.正规表达式与有限自动机正规表达式与有限自动机3、例题例.程序设计语言中的几类单词可用下述规则描述:标识符 字母数字字母数字字母数字字母数字无符号整数无符号整数运算符=|=|=|=|界符，；（）中的任一英文字母；中的任一数字第26页/共91页.正规表达式与有限自动机正规表达式与有限自动机二、确定有限自动机DFA（Deterministic Finite Aufomofa）1、DFA M是一个五元式M=（S，S0，F）
16、其中：其中：S S有限集，其中的每个元素称为一个状态有限集，其中的每个元素称为一个状态有穷字母表，其中的每个元素称为一个输入字符有穷字母表，其中的每个元素称为一个输入字符：SSS S（即（即 状态状态SSSS，aa，（S S，a a）唯一的确定下一状态）唯一的确定下一状态）（s s，a a）=s=s:当现行状态为当现行状态为s s，输入字符为，输入字符为a a时，将转换到下一状态时，将转换到下一状态s ss s0 0SS，唯一的初态，唯一的初态F F S S，是一个终态集（可空），是一个终态集（可空）s s的一个后继状态的一个后继状态第27页/共91页.正规表达式与有限自动机正规表达式与有限自
17、动机2、DFA的两种表达方式（1）状态转换矩阵例：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第28页/共91页则其状态转换矩阵为：状态状态ab012132213333.正规表达式与有限自动机正规表达式与有限自动机（0，a）=1 （0，b）=2（1，a）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=3第29页/共91页（2）状态转换图.正规表达式与有限自动机正规表达式与有限自动机DFA M:m个状态：图中有 个状态结点;n个输入符号：每个结点
18、顶多有 条箭弧射出;每条箭弧用中的一个 （相同/不同)输入字符作标记;整张图含有 个初态结点和若干个 （可为0）终态结点.0132 a a a a b a a b a a，b b b b第30页/共91页.正规表达式与有限自动机正规表达式与有限自动机3、识别（读出/接受）对于任何*中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于。则成可为DFA M所识别（接受/读出）。若若MM的初态结点同时又是终态结点，则空字的初态结点同时又是终态结点，则空字 可为可为MM所识别所识别/接受。接受。DFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L
19、 L（MM）。）。若一个若一个DFA MDFA M的输入字母表为的输入字母表为，则称，则称MM是是上的一个上的一个DFADFA。第31页/共91页0132 a a a a b a a b a a，b b b b第32页/共91页.正规表达式与有限自动机正规表达式与有限自动机4、定理上的一个字集V*是正规的，当且仅当存在上的DFA M，使得V=L（M）第33页/共91页.正规表达式与有限自动机正规表达式与有限自动机三、非确定有限自动机（NFA）1、一个NFA是一个五元式M=（S，S0，F）其中：其中：S S有限集，其中每个元素称为一个状态有限集，其中每个元素称为一个状态有穷字母表，其中的每个元素
20、称为一个输入字符有穷字母表，其中的每个元素称为一个输入字符：SS*2 2S S S S的子集的子集的子集的子集 字字字字S S0 0 S S，是一个非空初态集，是一个非空初态集F F S S，是一个终态集（可空），是一个终态集（可空）第34页/共91页.正规表达式与有限自动机正规表达式与有限自动机三、非确定有限自动机（NFA）DFANFAS初态终态F有限状态集字母表SS初态唯一可为空 同左同左S*2S初态不一定唯一同左第35页/共91页.正规表达式与有限自动机正规表达式与有限自动机2、状态转换图注：（1）每条弧用 的作为输入字,箭弧上的标记 （允许/不允许）相同。（2）整张图至少含有一个初态结
21、点以及若干个（可为0个）终态结点（3）某些结点既可为初态结点也可为终态结点*中一个字（可以是空字）允许第36页/共91页例：q0q111000DFA?NFA?第37页/共91页.正规表达式与有限自动机正规表达式与有限自动机3、识别（读出/接受）对于*中的任何一个，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为的弧）等于，则称可为NFA M所识别（读出/接受）。若若MM的某些结点既是初态结点又是终态结点，或者存在的某些结点既是初态结点又是终态结点，或者存在 一条从某个初态结点到某个终态结点的一条从某个初态结点到某个终态结点的通路，则空字通路
22、，则空字 可为可为MM所接受。所接受。第38页/共91页.正规表达式与有限自动机正规表达式与有限自动机四、NFA=DFA(确定化）=化简（最少化）第39页/共91页1、_CLOSURE（I）：(a)I中的每个状态；(b)若s _CLOSURE（I），则状态s经过任意条标记为的弧到达的状态s _CLOSURE（I）。_CLOSURE（x）=x,5,1第40页/共91页2、Ia=_CLOSURE（J）若sIs经过1条标记为a的弧到达的状态s JI=x,5,1Ia=x,5,1a=_CLOSURE（5,3)=5,3,1Ib=x,5,1b=_CLOSURE（5,4)=5,4,1第41页/共91页IIaI
23、bX,5,1_CLOSURE(初态）（一）NFA=DFA5,3,15,4,15,3,15,4,15,2,3,1,6,Y5,4,15,2,3,1,6,Y5,3,15,2,4,1,6,Y5,2,4,1,6,Y5,2,3,6,1,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,6,1,Y5,3,6,1,Y5,6,3,1,Y5,2,6,4,1,Y5,2,6,3,1,Y5,6,4,1,Y第42页/共91页.正规表达式与有限自动机正规表达式与有限自动机解：（1）构造DFA的状态转换矩阵(2)构造重新命名后的状态转换矩阵DFA M L(M)=L(M)=L(M)Sab01213221433
24、5464564635第43页/共91页第44页/共91页（二）DFA的化简状态s和t等价：s和t到达终态能够识别相同的字。第45页/共91页1、首先分为非终态集和终态集0，1，2和3，4，5，62、分别对每个集合进行试探：（1）0，1，2a=1,3,1 把集合分为0，2和1 0，2b=2,5 把集合划分为0和2 把集合0，1，2划分为0、1和2第46页/共91页2、（1）0、1、2、3，4，5，6 （2）3，4，5，6a=3，6，6，3 3，4，5，6b=4，5，5，4 集合3，4，5，6不可再划分。3、最终形成的划分0123，4，5，6第47页/共91页0123，4，5，6用一个状态代表一个
25、状态子集。0132abababa,b第48页/共91页.正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机关系定理定理：上的NFA M所能识别的语言L(M)可以用上的正规式来表示。即：对上的NFA M，可构造一个正规式，使得L()=L(M)定理：上任何正规式，存在DFA M使得L(M)=L()。即：由 正规式可以构造一个DFA M，使得L(M)L()第49页/共91页.正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机1 1、有限自动机有限自动机=正规式正规式1)1)把状态转换图的概念拓广把状态转换图的概念拓广，令每条弧上都可以用一个，令每条弧上都可以用一个正规式作
26、标记。正规式作标记。2)2)在在MM的转换图上加两个结点：的转换图上加两个结点：x,yx,y。从从 x x用用 弧连接到弧连接到MM的所有初态结点；从的所有初态结点；从MM的终态结点用的终态结点用 弧连接到弧连接到y y。这。这个新的个新的NFANFA为为MM，且，且L(M)=L(M)L(M)=L(M)3)3)通过引入的通过引入的3 3条有限自动机替换规则条有限自动机替换规则逐步消去逐步消去MM中的中的所有结点，直到只剩下所有结点，直到只剩下x x和和y y为止。为止。这样，在这样，在x x至至y y的弧的弧线上的标记就是线上的标记就是 上的正规式，也就是上的正规式，也就是MM接受的正规式。接
27、受的正规式。第50页/共91页.正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机1 1、有限自动机有限自动机=正规式正规式替换规则替换规则:jiABAB jiA|BA|B jiA A*A A B Bjkijki A A代之以代之以代之以jiA AB B第51页/共91页例：将下面的DFA M 所接受的语言表示为正规式xy111113200 00 0 x0 310|0101|1000|1100|11y第52页/共91页x0 310|0101|1000|1100|11y x 0 y00|11(10|01)(00|11)*(01|10)x y (10|01)(00|11)*(01|1
28、0)|(00|11)*第53页/共91页练习1：第54页/共91页练习1：第55页/共91页练习2：第56页/共91页练习2：第57页/共91页.正规表达式与有限自动机正规表达式与有限自动机五、正规式有限自动机2 2、正规式、正规式=有限自动机有限自动机第58页/共91页证明过程证明过程如下：（1）若正规式有零个运算符时：正规式，构造NFA为：对应正规式，构造NFA为：对应正规式a，构造NFA为：（2）假设正规式有k(k=1)个运算符时结论成立。（3）则正规式有k+1(k=1)个运算符时：xyxyxya第59页/共91页 R=stR=s*xyN(s)N(s)N(t)xyN(s)N(t)R=s|
29、t第60页/共91页书上例子P56第61页/共91页转换规则：1)由正规式 构造一个如下仅有两个结点x,y的状态图。2)按所引入的3条正规式分裂规则分裂。3)重复步骤2直到每个弧上的标记是上的一个字符或为止。4)将所得的NFA M(因为包含弧)进行确定化就得到DFA。x y 第62页/共91页正规式分裂规则 12|1 22 1 123 1 12*23第63页/共91页例：根据正规式(a|b)*(aa|bb)(a|b)*,构造DFA M，使之等价.x y (a|b)*(aa|bb)(a|b)*1y(a|b)*(a|b)*2 x(aa|bb)1y 2 xaa 5 bba|b 6 a|b 1y 2
30、xa 5 ba 6 abb34ab第64页/共91页练习练习1：L(R)=(a|b)*abb，构造，构造NFA使使L(N)=L(R)练习练习2：L(R)=a*b*abb，构造，构造NFA使使L(N)=L(R)第65页/共91页练习1：L(R)=(a|b)*abb，构造NFA使L(N)=L(R)解：xy(a|b)*abbxyabbabxyabba,bxyababbxy(a|b)*abb第66页/共91页练习2：L(R)=a*b*abb，构造NFA使L(N)=L(R)解：xybab abxa*b*abby第67页/共91页1、右线性正规文法GR-有限自动机2、左线性正规文法GL-有限自动机3、有限
31、自动机-右线性正规文法GR4、有限自动机-左线性正规文法GL.正规表达式与有限自动机六、正规文法有限自动机第68页/共91页1、右线性正规文法GR-有限自动机.正规表达式与有限自动机六、正规文法有限自动机引例：GR:S aA A bB B cSABfabc（S，a）=A（A，b）=B（B，c）=f第69页/共91页1、右线性正规文法GR-有限自动机.正规表达式与有限自动机六、正规文法有限自动机GR(VT,VN,S,P)P:A aBBbFA(,S,S0,F)字母表:VT状态集S:VN fS0：开始符号S对应的状态F：f:（A，a）=B（B，b）=f第70页/共91页 GR:A 0|0B|1D B
32、 0D|1C C 0|0B|1D D0D|1D第71页/共91页2、左线性正规文法GL-有限自动机.正规表达式与有限自动机六、正规文法有限自动机引例：GL:S Ac A Bb B aSABfcba（A，c）=S（B，b）=A（q0，a）=Bq0S第72页/共91页2、左线性正规文法GL-有限自动机.正规表达式与有限自动机六、正规文法有限自动机GL(VT,VN,S,P)P:A BaBbFA(,S,S0,F)字母表:VT状态集S:VN q0S0：q0F：开始符号S对应的状态:（B，a）=A（q0，b)=B第73页/共91页 GL:A 0|C0 B 0|C0 C B1 D1|C1|D0|D1|B0第
33、74页/共91页3、有限自动机-右线性正规文法GR.正规表达式与有限自动机六、正规文法有限自动机引例1：SABCabc引例2：SABCabcd第75页/共91页3、有限自动机-右线性正规文法GR.正规表达式与有限自动机六、正规文法有限自动机引例1：SABCabc GR:S aA A bB B cC C 第76页/共91页3、有限自动机-右线性正规文法GR.正规表达式与有限自动机六、正规文法有限自动机 GR:S aA A bB B cC C dB|引例2：SABCabcd第77页/共91页规则：3、有限自动机-右线性正规文法GRFA(,S,s0,F)（A，a）=BGR(VT,VN,S,P)VT:
34、VN:状态集S对应的符号集S：初态s0对应的符号P：A aB当C是终态时，增加：C 第78页/共91页ABDabaabbbC GR:AaB|bD B bC C aA|bD D aB|bD|第79页/共91页4、有限自动机-左线性正规文法GL.正规表达式与有限自动机六、正规文法有限自动机引例1：SABCabc引例2：SABCabcd第80页/共91页4、有限自动机-左线性正规文法GL.正规表达式与有限自动机六、正规文法有限自动机引例1：SABCabc GL:CBc B Ab A Sa S 第81页/共91页4、有限自动机-左线性正规文法GL.正规表达式与有限自动机六、正规文法有限自动机 GL:C
35、Bc B Ab A Sa S Ad|引例2：SABCabcd第82页/共91页规则：4、有限自动机-左线性正规文法GLFA(,S,s0,F)（A，a）=BGR(VT,VN,f,P)VT:VN:状态集S对应的符号集S：终态f对应的符号P：B Aa当C是初态时，增加：C 第83页/共91页ABDabaabbbC GL:D Ab|Db|Cb B Aa|Da C Bb ACa|第84页/共91页.正规表达式与有限自动机正规表达式与有限自动机六、正规文法六、正规文法正规式正规式注：注：a)一个正规语言可以由正规文法定义，也可以由正一个正规语言可以由正规文法定义，也可以由正规式定义。规式定义。b)对任一个
36、正规文法，存在一个定义同一个语言的对任一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。一语言的正规文法。c)有些正规语言很容易用文法定义，有些更容易用有些正规语言很容易用文法定义，有些更容易用正规式定义。正规式定义。第85页/共91页.正规表达式与有限自动机正规表达式与有限自动机、正规式、正规式正规文法正规文法、规则、规则:将将上的一个正规式转换成文法上的一个正规式转换成文法G=(VN,VT,S,P)(1)令令VT=(2)确定产生式和确定产生式和VN的元素用如下办法的元素用如下办法对任何正规式对任何正规
37、式r,选择选择SVN,生成产生式生成产生式S，且，且定为开始符号定为开始符号若，均为正规式，则：若，均为正规式，则：对形如对形如的产生式，重写成的产生式，重写成，对形如对形如*的产生式，重写成的产生式，重写成A，对形如对形如的产生式，重写成的产生式，重写成，A第86页/共91页.正规表达式与有限自动机正规表达式与有限自动机、例题：已知正规式（）*，将其转换成相应的正规文法。（）S（）*（）（）*（）（）（）（）即 第87页/共91页.正规表达式与有限自动机正规表达式与有限自动机、正规文法正规式、转换规则如下:（），（）*（），不断利用上述规则变换，最后只剩下一个开始符号定义的产生式，且该产生式的右部不含非终结符。第88页/共91页.正规表达式与有限自动机正规表达式与有限自动机、例题：已知文法：，求其对应的正规式？分析：分析：（）（）（）（）（）（）（）+（）+（）+（）第89页/共91页.正规表达式与有限自动机正规表达式与有限自动机正规式最小正规文法：从开始结点出发，探索一切到终点的路径即可。、当有循环时，即用（.）*解决、当有两条可选路径时，用“”解决如此就可顺利写出正规式了第90页/共91页感谢您的观看。第91页/共91页