词法分析(6学时)调整版.ppt

《词法分析(6学时)调整版.ppt》由会员分享，可在线阅读，更多相关《词法分析(6学时)调整版.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 词法分析词法分析正规式正规式NFANFA正规文法正规文法DFADFA最小化最小化DFADFA子集法子集法语言语言消除多余状态消除多余状态合并等价状态合并等价状态n有穷自动机有穷自动机 FAFA：是一个识别装置，用于识别是一个识别装置，用于识别“所有句子所有句子”。n引入引入FAFA的目的：的目的：为词法分析程序的自动构造寻找特殊的方法和工具为词法分析程序的自动构造寻找特殊的方法和工具n类型：类型：确定的有穷自动机确定的有穷自动机 DFADFA不确定的有穷自动机不确定的有穷自动机 NFANFA返回返回4.1 有穷自动机（有穷自动机（FA，Finite Automata）nFA(Fi

2、nite AutoMata)FA(Finite AutoMata)：是一个识别装置，用于识别是一个识别装置，用于识别“所有句子所有句子”。n引入引入FAFA的目的：的目的：为词法分析程序的自动构造寻找特殊的方法和工具为词法分析程序的自动构造寻找特殊的方法和工具n类型：类型：确定的确定的有穷自动机有穷自动机 DFADFA不确定的有穷自动机不确定的有穷自动机 NFANFAnNFA NFA DFA DFA（子集法）子集法）nDFADFA的化简的化简（最小化最小化 DFADFA）下一节下一节确定的有穷自动机确定的有穷自动机(DFA)DFA)1.1.定义：定义：一个一个DFADFA是一个五元组是一个五元

3、组 M=(K,M=(K,f,S,Z ,f,S,Z)K K：有穷的状态集有穷的状态集 ：有穷的字母表（即输入字符的集合）有穷的字母表（即输入字符的集合）f f：转换函数转换函数 K K K K 上的映像上的映像 S S：初态（初态唯一）初态（初态唯一）Z Z：终态终态集集（终态不唯一）（终态不唯一）例：例：DFA M=(S,U,V,Q,a,b,f,S,Q)DFA M=(S,U,V,Q,a,b,f,S,Q)f f：f(S,a)=Uf(S,a)=Uf(S,b)=Vf(S,b)=Vf(U,a)=Qf(U,a)=Qf(U,b)=Vf(U,b)=Vf(V,a)=Uf(V,a)=Uf(V,b)=Qf(V,b

4、)=Qf(Q,a)=Qf(Q,a)=Qf(Q,b)=Qf(Q,b)=Q确定的有穷自动机确定的有穷自动机(DFA)DFA)2.2.DFADFA的的“直观直观”表示：表示：1)1)状态图（状态转换图）状态图（状态转换图）每个状态用结点表示每个状态用结点表示若若f(f(KiKi,a)=,a)=KjKj，则则初态用初态用“=”“=”或或“-”“-”标出标出终态用双圈终态用双圈 或或“+”“+”标出标出2)2)矩阵矩阵列标题：输出符号（列标题：输出符号（VTVT）行标题：状态行标题：状态若若f(f(KiKi,a)=,a)=KjKj，则则KiKi和和a a的交汇处是的交汇处是 KjKj初态用初态用“=”“

5、=”标出标出 或或 默认第一行（表格左端）默认第一行（表格左端）终态用终态用“1”“1”标出（表格右端）标出（表格右端）非终态用非终态用“0”“0”标出（表格右端）标出（表格右端）KiKja例：参见上例的例：参见上例的DFADFA，分别用状态图和矩阵表示。分别用状态图和矩阵表示。确定的有穷自动机确定的有穷自动机(DFA)DFA)3.3.DFADFA可以接受的可以接受的句子句子句子句子（符号串符号串符号串符号串）：）：若若tt*，且存在且存在f(S,t)=Pf(S,t)=P，P P终态集，终态集，则则t t为该为该DFADFA可以接受的句子。可以接受的句子。即：从初态即：从初态S S到某终态结点

6、到某终态结点P P的道路上，所有弧上的的道路上，所有弧上的标记符连接而成字符串标记符连接而成字符串t t，t t为该为该DFADFA可以接受的可以接受的句子。句子。例：参见上例的例：参见上例的DFADFA状态图，判断下列句子能否被接受：状态图，判断下列句子能否被接受：abbaabbabaabbaababbabbaaaaa aDFA M DFA M 能够接受的句子的全体记为能够接受的句子的全体记为 L(M)!L(M)!确定的有穷自动机确定的有穷自动机(DFA)DFA)4.4.DFADFA的确定性：的确定性：f:f:K K K K 是一个单值函数是一个单值函数即即 对任何状态对任何状态K K，当输

7、入字符当输入字符a a时，下一状态唯一。时，下一状态唯一。上例的有穷状态机就是上例的有穷状态机就是DFADFADFA M=DFA M=（K K，f f，S S，Z Z）的行为模拟程序：的行为模拟程序：K:=SK:=S；c:=getchar;c:=getchar;while(ceof)while(ceof)K:=f(K,c);K:=f(K,c);c:=getchar;c:=getchar;if(K in Z)if(K in Z)return(yes);return(yes);elseelse return(no);return(no);DFADFA的行为模拟程序的行为模拟程序返回示例：一个识别标

8、识符的确定的有穷状态机12字母其它字母数字字母3其它数字数字或其它n最小化DFA没有多余状态(死状态)没有两个状态是互相等价DFADFA的化简（最小化的化简（最小化DFADFA）（1）多余状态：）多余状态：从开始状态出发，任何输入串也不能到达的状态从开始状态出发，任何输入串也不能到达的状态处理：处理：消除多余状态消除多余状态消除多余状态消除多余状态（2）两个状态）两个状态s和和t等价：满足等价：满足一致性一致性同是终态同是终态 或或 同是非终态同是非终态蔓延性蔓延性从从s s出发读入某个出发读入某个a a a a和从和从 t t 出出发发读入某个读入某个a a到达的状态等价。到达的状态等价。处

9、理：处理：合并等价状态合并等价状态合并等价状态合并等价状态（使用（使用“分割法分割法”）s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7DFADFA的化简（最小化的化简（最小化DFADFA）举例：消除多余状态举例：消除多余状态解：解：步骤一：消除多余状态步骤一：消除多余状态步骤二：使用分割法，合并等价状态。步骤二：使用分割法，合并等价状态。b02134abaaaabbbDFA M举例：求最小化

10、举例：求最小化DFADFADFADFA的化简（最小化的化简（最小化DFADFA）1,2,3,4,5,6,7Ia：6,7,1,4,7,4,4Ib：3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb13546aaaaabbbbb举例：求最小化DFA返回P70 P70 例例2 2课后题：课后题：4(4(b)9b)9不确定的有穷自动机不确定的有穷自动机(NFA)NFA)1.1.定义：定义：一个一个NFANFA是一个五元组是一个五元组 M=(K,M=(K,f,S,Z ,f,S,Z)K K：有穷的状态集有穷的状

11、态集 ：有穷的字母表（即输入字符的集合）有穷的字母表（即输入字符的集合）f f：转换函数转换函数 K K*K K+上的映像上的映像（K K+表示表示K K的子集的子集）S S：初态集初态集（初态不唯一初态不唯一）Z Z：终态集终态集例：例：NFA M=(NFA M=(0,1,2,3,40,1,2,3,4,a,ba,b,f,f,0 0,2,42,4)f f：f(0,a)=0,3f(0,a)=0,3f(0,b)=0,1f(0,b)=0,1f(1,b)=2f(1,b)=2f(2,a)=2f(2,a)=2f(2,b)=2f(2,b)=2f(3,a)=4f(3,a)=4f(4,a)=4f(4,a)=4f

12、(4,b)=4f(4,b)=42.2.NFANFA的的“直观直观”表示：表示：1)1)状态图（状态转换图）状态图（状态转换图）每个状态用结点表示每个状态用结点表示若若f(f(KiKi,a)=,a)=KjKj，则则初态用初态用“=”“=”或或“-”“-”标出标出终态用双圈终态用双圈 或或“+”“+”标出标出2)2)矩阵矩阵列标题：输出符号（列标题：输出符号（VTVT）行标题：状态行标题：状态若若f(f(KiKi,a)=,a)=KjKj，则则KiKi和和a a的交汇处是的交汇处是 KjKj初态用初态用“=”“=”标出标出 或或 默认第一行（表格左端默认第一行（表格左端）终态用终态用“1”“1”标出

13、（表格右端）标出（表格右端）非终态用非终态用“0”“0”标出（表格右端）标出（表格右端）KiKja举例：参见上例的举例：参见上例的NFANFA，分别用状态图和矩阵表示。分别用状态图和矩阵表示。不确定的有穷自动机不确定的有穷自动机(NFA)NFA)3.3.NFANFA可以接受的可以接受的句子句子句子句子（符号串符号串符号串符号串）：）：(同同DFA)DFA)若若tt*，且存在且存在f(S,t)=Pf(S,t)=P，P P终态集，终态集，则则t t为该为该NFANFA可以接受的句子。可以接受的句子。例：参见上例的例：参见上例的NFANFA状态图，判断下列句子能否被接受：状态图，判断下列句子能否被接

14、受：aaaaaabaabbaababbabba aabaabababbabNFA M NFA M 能够接受的句子的全体记为能够接受的句子的全体记为 L(M)L(M)对于每个对于每个NFA M NFA M 存在一个存在一个DFA MDFA M，使得使得L(M)=L(M)L(M)=L(M)!不确定的有穷自动机不确定的有穷自动机(NFA)NFA)可以被可以被 NFA M NFA M 能够接受的两种情况：能够接受的两种情况：MM的某结点既是初态，又是终态的某结点既是初态，又是终态 存在一条从初态到终态的存在一条从初态到终态的 道路道路4.4.NFANFA的不确定性：的不确定性：对于状态对于状态K K，

15、当输入字符当输入字符a a时，下一状态不一定唯一。时，下一状态不一定唯一。5.NFA5.NFA的确定化：的确定化：对每个对每个NFA M NFA M 一定存在一定存在一个一个DFA MDFA M，使得，使得L(M)=L(M)L(M)=L(M)即：对每个即：对每个NFA MNFA M存在着与之存在着与之等价等价的的DFA M DFA M。注：与某一注：与某一NFANFA等价的等价的DFADFA不唯一。不唯一。不确定的有穷自动机不确定的有穷自动机(NFA)NFA)返回NFANFADFADFA（子集法）（子集法）（一）基本运算：（一）基本运算：n n状态集合状态集合状态集合状态集合I I I I的的

16、的的 闭包闭包闭包闭包：表示为：表示为 -closure(I)closure(I)closure(I)closure(I)状态集状态集I I中的任何状态中的任何状态S S经任意条经任意条 弧而能到达的弧而能到达的状态状态状态状态的集合的集合的集合的集合。注：状态集注：状态集I I的任何状态的任何状态S S都属于都属于-closure(I)closure(I)n n状态集合状态集合状态集合状态集合I I I I的的的的a a a a弧转换弧转换弧转换弧转换：表示为：表示为move(I,a)move(I,a)move(I,a)move(I,a)定义为状态集合定义为状态集合J J，其中其中J J是所

17、有那些可从是所有那些可从I I的某一状的某一状态经过一条态经过一条a a弧而到达的状态的全体。弧而到达的状态的全体。定义定义 Ia=Ia=-closure(J)closure(J)举例：参见举例：参见P58 P58 图图4.44.4，求：，求：-closure(0)closure(0)closure(0)closure(0)move(0,a)move(0,a)move(0,a)move(0,a)move(0,b)move(0,b)move(0,b)move(0,b)-closure(1)closure(1)closure(1)closure(1)move(2,a)move(2,a)move(2

18、,a)move(2,a)move(2,b)move(2,b)move(2,b)move(2,b)move(0,1,2,4,7,a)move(0,1,2,4,7,a)move(0,1,2,4,7,a)move(0,1,2,4,7,a)-closure(1,3)closure(1,3)closure(1,3)closure(1,3)move(0,1,2,4,7,b)move(0,1,2,4,7,b)move(0,1,2,4,7,b)move(0,1,2,4,7,b)NFANFADFADFA（子集法）（子集法）（二（二）转换的主要思想：转换的主要思想：DFADFADFADFA的的的的一个一个一个一个

19、状态可能对应状态可能对应状态可能对应状态可能对应NFANFANFANFA的的的的一个或一组一个或一组一个或一组一个或一组状态状态状态状态 DFADFADFADFA同样同样同样同样记录记录记录记录在在在在NFANFANFANFA上上上上读入某个读入某个读入某个读入某个VTVTVTVT后可能到达的所后可能到达的所后可能到达的所后可能到达的所有状态有状态有状态有状态（三）子集法（三）子集法NFA NFA NFA NFA N N N N=(K,=(K,=(K,=(K,f,K,f,K,f,K,f,K0 0 0 0,K,K,K,Kt t t t)构造构造构造构造 DFA DFA DFA DFA M M M

20、 M=(S,=(S,=(S,=(S,d,S,d,S,d,S,d,S0 0 0 0,S,S,S,St t t t)，使得使得使得使得 L(M)=L(N)L(M)=L(N)L(M)=L(N)L(M)=L(N)：1.1.1.1.M M M M的状态集的状态集的状态集的状态集S S S S由由由由K K K K的一些子集组成的一些子集组成的一些子集组成的一些子集组成2.2.2.2.M M M M和和和和N N N N的的的的输入字母表相同输入字母表相同输入字母表相同输入字母表相同3.3.3.3.转换函数转换函数转换函数转换函数d d d d是这样定义的：是这样定义的：是这样定义的：是这样定义的：4.4

21、.4.4.d(d(d(d(S S S S1 1 1 1,.,.,.,.,S S S Sj j j j,a)=a)=a)=a)=-closure(moveclosure(moveclosure(moveclosure(move(S S S S1 1 1 1,.,.,.,.,S S S Sj j j j,a)a)a)a)4.4.4.4.S S S S0 0 0 0=-closure(Kclosure(Kclosure(Kclosure(K0 0 0 0)为为为为M M M M的开始状态的开始状态的开始状态的开始状态5.5.5.5.S S S St t t t=S S S Si i i i,S S

22、S Sk k k k ,.,S,.,S,.,S,.,Se e e e ，其中，其中，其中，其中 S S S Si i i i,S S S Sk k k k ,.,S,.,S,.,S,.,Se e e e S S S S6.6.6.6.且且且且 S S S Si i i i,S S S Sk k k k,.,.,.,.S S S Se e e e K K K Kt t t t NFANFADFADFA（子集法）（子集法）构造构造构造构造 NFA N NFA N NFA N NFA N 的状态的状态的状态的状态 K K K K 的子集的算法的子集的算法的子集的算法的子集的算法：假定所构造的子集族为

23、假定所构造的子集族为 C=(TC=(T1 1,T,T2,2,.,.T Ti i)，其中其中T T1 1,T,T2,2,.,.T Ti i为状态为状态 K K 的子集。的子集。1 1）开始，令）开始，令-closure(Kclosure(K0 0)为为C C中唯一成员，并且它是未中唯一成员，并且它是未被标记的。被标记的。2 2）While(CWhile(C中存在尚未被标记的子集中存在尚未被标记的子集T)doT)do 标记标记T T；for(for(每个输入字母每个输入字母a)doa)do U:=U:=-closure(move(T,a)closure(move(T,a)；ifif（U U不在不在

24、C C中）中）thenthen 将将U U作为未标记的子集加在作为未标记的子集加在C C中；中；举例：参见举例：参见举例：参见举例：参见P58 P58 P58 P58 图图图图4.4 4.4 4.4 4.4 构造构造构造构造NFANFANFANFA对应的子集对应的子集对应的子集对应的子集NFANFADFADFA（子集法）（子集法）-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,7 T1=1,2,3,4,6,7,8 T2=1,2,4,5,6,7 T1=1,2,3,4,6,7,8 T1=1,2,3,4,6,7,8 T3=1,

25、2,4,5,6,7,9T2=1,2,4,5,6,7 T1=1,2,3,4,6,7,8 T2=1,2,4,5,6,7T3=1,2,4,5,6,7,9 T1=1,2,3,4,6,7,8 T4=1,2,4,5,7,10T4=1,2,4,5,7,10 T1=1,2,3,4,6,7,8 T2=1,2,4,5,6,7b02134abaaaabbb初态初态终态终态DFA M：课后习题：课后习题：2 2，3 3，4(4(a)a)返回4.4.2 2 词法分析程序的设计词法分析程序的设计 词法分析（词法分析（词法分析（词法分析（lexical analysislexical analysislexical ana

26、lysislexical analysis）功能：功能：功能：功能：逐个读入逐个读入逐个读入逐个读入源程序源程序源程序源程序字符字符字符字符，输出，输出，输出，输出“单词符号单词符号单词符号单词符号”，供语，供语，供语，供语法分析使用。法分析使用。法分析使用。法分析使用。主要任务：主要任务：主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务：其他任务：其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序追踪换行标志，复制出错源程

27、序追踪换行标志，复制出错源程序追踪换行标志，复制出错源程序宏展开，宏展开，宏展开，宏展开，单词符号单词符号n n一般可分为下列五种：一般可分为下列五种：一般可分为下列五种：一般可分为下列五种：基本字基本字基本字基本字（关键字关键字关键字关键字）：）：）：）：begin,end,if,whilebegin,end,if,whilebegin,end,if,whilebegin,end,if,while 标识符标识符标识符标识符：各种名称，如常量名、变量名、过程名：各种名称，如常量名、变量名、过程名：各种名称，如常量名、变量名、过程名：各种名称，如常量名、变量名、过程名 常数常数常数常数（量）：（

28、量）：（量）：（量）：25,3.1415,25,3.1415,25,3.1415,25,3.1415,TRUE,“ABC”TRUE,“ABC”TRUE,“ABC”TRUE,“ABC”等等等等 运算符运算符运算符运算符：如：如：如：如+-*/=+-*/=+-*/=+-*/=等等等等 界符界符界符界符：逗号，分号，括号等：逗号，分号，括号等：逗号，分号，括号等：逗号，分号，括号等词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式 方式一（常用）：方式一（常用）：词法分析程序（扫描整个待编译的源程序）词法分

29、析程序（扫描整个待编译的源程序）词法分析程序（扫描整个待编译的源程序）词法分析程序（扫描整个待编译的源程序）中间文件中间文件中间文件中间文件输出输出输出输出语法分析程序语法分析程序语法分析程序语法分析程序输入输入输入输入：二元式（单词种类，值）二元式（单词种类，值）优点：优点：（1 1）整个编译结构简洁、清晰、条理化）整个编译结构简洁、清晰、条理化（2 2）可移植性好）可移植性好词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式词法分析程序与语法分析程序的接口方式 方式二（方式二（PL/0采用）：采用）：语法分析程序语法分析程序语法分析

30、程序语法分析程序词法分析程序词法分析程序词法分析程序词法分析程序调用调用调用调用返回一个返回一个返回一个返回一个单词单词单词单词4.4.3 3 单词的描述工具单词的描述工具单词的描述工具和识别工具：单词的描述工具和识别工具：正规文法正规文法（正则文法、（正则文法、3 3型文法）型文法）正规式正规式（正则式）（正则式）有穷自动机有穷自动机（NFANFA、DFADFA）三者之间可以相互转换三者之间可以相互转换下一节下一节正规文法正规文法文法的文法的每个产生式的形式都为：每个产生式的形式都为：AaBAaB 或或 AaAa 右线性右线性ABaABa 或或 AaAa 左线性左线性其中其中 A A，BVB

31、VN N ，aVaVT T*例如：例如：例如：例如：n n标识符标识符标识符标识符的正规文法的正规文法的正规文法的正规文法：（若：（若i i表示任一字母，表示任一字母，d d表示任一数字）表示任一数字）标识符标识符i|ii|i字母数字字母数字字母数字字母数字i|d|ii|d|i字母数字字母数字|d d字母数字字母数字n n无符号整数无符号整数无符号整数无符号整数的正规文法的正规文法的正规文法的正规文法：无符号整数无符号整数 d|dd|d无符号整数无符号整数n n运算符运算符运算符运算符的正规文法的正规文法的正规文法的正规文法：运算符运算符+|-|*|/|=|-|*|/|=|等号等号等号等号=n

32、 n界符界符界符界符的正规文法的正规文法的正规文法的正规文法：界符界符,|;|(|)|,|;|(|)|返回返回正规式正规式(regular expression)regular expression)n正规式：正规式：是描述单词符号串规则的工具是描述单词符号串规则的工具设字母表设字母表=a,z,A,Z,0,9 a,z,A,Z,0,9 辅助字母表辅助字母表=，“”表示表示“闭包闭包”，即任意有限次的自重复连，即任意有限次的自重复连接接“”表示表示“连接连接”，有时可以省略，有时可以省略“”表示表示“或或”优先顺序为优先顺序为“()”“()”、“”、“”、“”“”、“”和和“”都是左结合的都是左结

33、合的正规式为正规式为 ，(e)e)，e e1 1|e|e2 2 ，e e1 1 e e2 2 ，e e*中的符号。中的符号。（其中（其中e e表示任一正规式）表示任一正规式）例例例例1 1 1 1：令：令：令：令 =0 0 0 0，1111，上正规式和相应正规集的例子有：上正规式和相应正规集的例子有：上正规式和相应正规集的例子有：上正规式和相应正规集的例子有：正规式正规式正规式正规式正规集正规集正规集正规集0 0000 0 1 10,10,10101 0101(0(0 1)(01)(0 1)1)(中间省略连接号)00,01,10,1100,01,10,110 0 ,0,0,0,0,任意个任意个

34、0 0的串的串(0 0 1)1),0,1,00,01 ,0,1,00,01 所有由所有由0 0 和和1 1组成的串组成的串(0 0 1)1)(00(00 11)(011)(0 1)1)上所有含有两个相继上所有含有两个相继 的的0 0或两个相继的或两个相继的1 1组成组成 的串的串 正规式举例正规式举例两个正规式两个正规式等价等价n若两个正规式若两个正规式 e e1 1 和和 e e2 2 所表示的所表示的正规集相同正规集相同正规集相同正规集相同,则说则说 e e1 1 和和 e e2 2 等价。等价。记作记作 e e1 1=e e2 2例如：例如：0 1=1 01(01)=(10)1(0 1)

35、=(0 1)正规式的代数运算正规式的代数运算n n设设设设r,s,tr,s,tr,s,tr,s,t为正规式，则有：为正规式，则有：为正规式，则有：为正规式，则有：r r r r s=ss=ss=ss=s r r r r“或或或或”的交换律的交换律的交换律的交换律 r r r r (s s s s t)=(t)=(t)=(t)=(r r r r s s s s)t t t t“或或或或”的结合律的结合律的结合律的结合律 (rs)trs)trs)trs)t=r(str(str(str(st)“连接连接连接连接”的可结合律的可结合律的可结合律的可结合律 r(s r(s r(s r(s t)=t)=t

36、)=t)=rsrsrsrs rtrtrtrt(s(s(s(s t)r=t)r=t)r=t)r=srsrsrsr trtrtrtr分配律分配律分配律分配律 r=r r=r r=r r=r r r r r =r=r=r=r 是是是是“连接连接连接连接”的恒的恒的恒的恒等元素等元素等元素等元素n n程序中的程序中的程序中的程序中的单词符号单词符号单词符号单词符号都能用正规式表示：都能用正规式表示：都能用正规式表示：都能用正规式表示：e=e=e=e=(|)*返回返回正规式正规式NFANFA正规文法正规文法DFADFA最小化最小化DFADFA子集法子集法语言语言消除多余状态消除多余状态合并等价状态合并等

37、价状态转换转换正规文法正规文法正规式正规式 等价转换的规则等价转换的规则 不不断断用用上上述述规规则则进进行行变变换换，直直到到最最后后只只剩剩一一个个开开始始符符号为止。号为止。正规文法正规文法正规式正规式AxBByAxyAxAAyAx*yAxAyAx|y正规文法正规文法正规式正规式 举例举例例：正规文法例：正规文法GS:GS:S SaA aA，将正规式将正规式正规文法。正规文法。S Sa aA AaAaAA AdAdAA Aa aA Ad dSaASaAaAAdAAaAdSaA|aAaA|dAAa|dSa(A|)A(a|d)AAa|dSa(A|)A(a|d)*(a|d)Sa(a|d)*(a

38、|d)|)Sa(a|d)*课后习题：课后习题：8 8正规式正规式正规文法正规文法 任何正规式任何正规式 r r：定义定义S S为开始符号为开始符号 S Sr r 转换规则转换规则 不不断断用用上上述述规规则则进进行行变变换换，直直到到每每个个产产生生式式的的右右部部只只含一个含一个V VT T为止。为止。正规式正规式正规文法正规文法Axy AxBBy Ax*y AxB 或或 AxAAy AyBxBByAx|y AxAy正规式正规式正规文法正规文法 举例举例例：正规式例：正规式 r=0(0|1)r=0(0|1)*，将正规式将正规式正规文法。正规文法。S0(0|1)*S0A S(0|1)*S0AA

39、(0|1)A A S0AA0A|1AA S0AA0AA1AA 练习：练习：R=R=(01|10)(01|10)*(0|1)(0|1)，将正规式将正规式正规文法正规文法返回返回4.4 4.4 正规式和有穷自动机的等价性正规式和有穷自动机的等价性正规式正规式NFANFA正规文法正规文法DFADFA最小化最小化DFADFA子集法子集法语言语言消除多余状态消除多余状态合并等价状态合并等价状态转换转换n对于对于上的上的 NFA MNFA M，可以构造一个，可以构造一个上的正规式上的正规式 R R，使得使得 L(R)=L(M)L(R)=L(M)。n对于对于上的正规式上的正规式R R，可以构造一个，可以构造

40、一个上的上的 NFA MNFA M，使，使得得 L L(M)=L(R)M)=L(R)。1.1.在在FA MFA M的状态图上的状态图上加两个状态结点加两个状态结点加两个状态结点加两个状态结点x x x x和和和和y y y y。从从x x结点出发，用结点出发，用弧连接弧连接 x x结点结点 到到 所有初态结点所有初态结点所有初态结点所有初态结点从从M M的的 所有终态结点所有终态结点所有终态结点所有终态结点 用用弧连接到弧连接到 y y结点结点此时，此时，x x x x为初态为初态为初态为初态和和y y y y为终态为终态为终态为终态。2.2.利用消结规则，逐步消去利用消结规则，逐步消去MM中

41、的所有结点，直至只剩下中的所有结点，直至只剩下x x和和y y。3.3.最后最后x x和和y y结点间的弧上的标记则为所求的正规式结点间的弧上的标记则为所求的正规式R R。FA FA 正规式正规式123R1R213R1R213R1R213R1|R2123R1R3R213R1 R2*R3举例：求举例：求FAFA所对应的正规式所对应的正规式R R03124a,baaa,ba,bbb解：解：0 03 31 12 24 4a,ba,ba aa aa,ba,ba,ba,bb bb bx xy yFA FA 正规式正规式0 02 24 4a|ba|baaaaa|ba|ba|ba|bbbbbx xy y0

42、0a|ba|baa(a|b)*aa(a|b)*bb(a|b)*bb(a|b)*x xy y则：则：R=R=(a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*0 0a|ba|baa(a|b)aa(a|b)*bb(a|b)bb(a|b)*x xy y0 0a|ba|bx xy y(aa|bb)(a|b)(aa|bb)(a|b)*x xy y(a|b)(a|b)*(aa|bb)(a|b)(aa|bb)(a|b)*课后习题：课后习题：9 91.1.将正规式分解成一系列将正规式分解成一系列 子表达式子表达式。2.2.对于每个子表达式，用如下规则构造对于每个子表达式，用如下规则构造

43、FAFA：正规式正规式FAFA正规式正规式FARR1R2 121212R R正规式正规式FAR1|R2R*13R1R2123R注意：由于分解的方法和顺序不同，注意：由于分解的方法和顺序不同，构造的构造的NFANFA可能不同，但最小化的可能不同，但最小化的DFADFA一定相同一定相同 ！13R R1 1 R R2 22举例：为举例：为 R=R=R=R=(a|b)(a|b)(a|b)(a|b)*abbabbabbabb 构造构造NFA NNFA N，使得使得L(N)=L(R)L(N)=L(R)。136b2ab45ab解：对应的解：对应的NFANFA为为NFANFADFADFA最小化最小化DFADF

44、AP68 P68 例例1 1课后习题：课后习题：1(3)(4)111(3)(4)11正规式正规式FAFA4.5 4.5 正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性正规式正规式NFANFA正规文法正规文法DFADFA最小化最小化DFADFA子集法子集法语言语言消除多余状态消除多余状态合并等价状态合并等价状态转换转换1.1.输入字符集与正规文法的输入字符集与正规文法的 V VT T 相同相同2.2.状态集与正规文法中的状态集与正规文法中的 V VN N 相同相同3.3.左线性左线性正规文法的转换规则：正规文法的转换规则：增加一个初态结点增加一个初态结点，开始符号对应的结点作为终态，开

45、始符号对应的结点作为终态 对对形形如如 AtAt 的的规规则则，引引一一条条从从初初始始状状态态到到A A的的弧弧，标记为标记为t t 对形如对形如 ABtABt 的规则，引一条从的规则，引一条从B B到到A A的弧，标记为的弧，标记为t t4.4.右线性右线性正规文法的转换规则：正规文法的转换规则：增加一个终态结点增加一个终态结点，开始符号对应的结点作为初态，开始符号对应的结点作为初态 对对形形如如 AtAt 的的规规则则，引引一一条条从从A A到到终终态态结结点点的的弧弧，标记为标记为t t 对形如对形如 AtBAtB 的规则，引一条从的规则，引一条从A A到到B B的弧，标记为的弧，标记

46、为t t注：注：t t 为为 V VT T 或或正规文法正规文法FAFA举例：求与文法举例：求与文法GSGS等价的等价的 NFA MNFA MGSGS：SaASaASbBSbBSSAaBAaBAbAAbABaSBaSBbABbABBS SA AB BZ Za aa ab bb ba ab b正规文法正规文法FA FA 举例举例 课后习题：课后习题：7 7举例：求与文法举例：求与文法GSGS等价的等价的 DFADFA，并给出该文法的语并给出该文法的语言的正规式。言的正规式。GSGS：SAaSAaSSAAaAAaASbASbAaAa正规文法正规文法FA FA 举例举例x xA AS Sb ba a

47、a aa aNFA:NFA:0 01 12 2a ab ba aa aDFA:DFA:0 01 12 2a ababaa aa aDFADFA可变换为可变换为:则：正规式为则：正规式为 R=R=aa(ba|a)aa(ba|a)*课后习题：课后习题：10101.1.与与f(A,a)=B f(A,a)=B 对应的产生式为：对应的产生式为：AaBAaB2.2.对终态结点对终态结点Z Z，增加产生式：增加产生式：ZZ3.3.NFANFA的初态对应文法的开始符号的初态对应文法的开始符号4.4.NFANFA的输入字符集对应文法的的输入字符集对应文法的 V VT TFAFA正规文法正规文法GSGS：AaBA

48、aBAbDAbDBbCBbCCaACaACbDCbDCCDaBDaBDbDDbDDD课后习题：5举例：求与举例：求与NFA MNFA M等价的文法等价的文法GSGSABDababbbaC4.6 4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具把正规式把正规式转换转换（编译编译）为一个为一个NFANFA，进而转换为相应的进而转换为相应的DFADFA，由此构造出词法分析程序。由此构造出词法分析程序。LEXLEX编译系统作用：从正规式产生识别单词的词法分析程序。编译系统作用：从正规式产生识别单词的词法分析程序。“lexlex”命令：命令：UNIXUNIX使用使用“lexlex”命令，可以

49、构造各种语言命令，可以构造各种语言的词法分析程序。的词法分析程序。“lexlex”即：即：LEXLEX编译系统。编译系统。LEXLEX编译系统：编译系统：应用：应用：词法分析程序的设计技术，还用于信息检索、查询。词法分析程序的设计技术，还用于信息检索、查询。词法分析程序的自动构造工具：用于生成一个程序，还用于词法分析程序的自动构造工具：用于生成一个程序，还用于识别印刷电路板中的缺陷、用于文本编辑的自动生成。识别印刷电路板中的缺陷、用于文本编辑的自动生成。LEXLEX源程序源程序lex.llex.lLEXLEXLEXLEX编译系统编译系统编译系统编译系统词法分析程序词法分析程序lex.yy.clex.yy.cC C编译器编译器a.outa.out输入字符串输入字符串单词符号串单词符号串