第四章 词法分析正规式NFA正规文法DFA最小化DFA子集法语言消除多余状态 合并等价状态n有穷自动机 FA：是一个识别装置，用于识别“所有句子”。n引入FA的目的：为词法分析程序的自动构造寻找特殊的方法和工 具n类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFA返回4.1 有穷自动机（FA ，Finite Automata）nFA ( Finite AutoMata ) ：是一个识别装置，用于识别“所有句子”。n引入FA的目的：为词法分析程序的自动构造寻找特殊的方法和工 具n类型： 确定的有穷自动机 DFA 不确定的有穷自动机 NFAnNFA DFA（子集法）nDFA的化简（最小化 DFA）下一节确定的有穷自动机确定的有穷自动机( (DFA)DFA)1. 定义：一个DFA是一个五元组 M=(K , ,f ,S ,Z ) K：有穷的状态集 ：有穷的字母表（即输入字符的集合 ） f：转换函数 KK 上的映像 S：初态（初态唯一） Z：终态集（终态不唯一） 例：DFA M =(S,U,V,Q , a,b , f , S , Q) f：f(S,a)=Uf(S,b)=V f(U,a)=Qf(U,b)=V f(V,a)=Uf(V,b)=Q f(Q,a)=Qf(Q,b)=Q确定的有穷自动机确定的有穷自动机( (DFA)DFA)2. DFA的“直观”表示：状态图（状态转换图）每个状态用结点表示若f( Ki , a ) = Kj，则初态用“=” 或 “-”标出终态用双圈 或 “+”标出矩阵列标题：输出符号（VT） 行标题：状态若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj初态用“=” 标出 或 默认第一行（表格左端 ）终态用“1”标出（表格右端）非终态用“0”标出（表格右端）KiKja例：参见上例的DFA，分别用状态图和矩阵表示。确定的有穷自动机确定的有穷自动机( (DFA)DFA)3. DFA可以接受的句子句子（符号串符号串）：若t*，且存在f(S,t)= = P，P终态集，则t为该DFA可以接受的句子。即：从初态S到某终态结点P的道路上，所有弧上的 标记符连接而成字符串t，t为该DFA可以接受的 句子。例：参见上例的DFA状态图，判断下列句子能否被接受：abbabaababbaaaDFA M 能够接受的句子的全体记为 L(M) !确定的有穷自动机确定的有穷自动机( (DFA)DFA)4. DFA的确定性：f: KK 是一个单值函数即 对任何状态K，当输入字符a时，下一状态唯一 。上例的有穷状态机就是DFADFA M=（K，f，S，Z）的行为模拟程序：K:=S； c:=getchar; while (c” 或 “-”标出终态用双圈 或 “+”标出矩阵列标题：输出符号（VT） 行标题：状态若f( Ki , a ) = Kj，则Ki和a的交汇处是 Kj初态用“=” 标出 或 默认第一行（表格左端 ）终态用“1”标出（表格右端）非终态用“0”标出（表格右端）KiKja举例：参见上例的NFA，分别用状态图和矩阵表示。不确定的有穷自动机不确定的有穷自动机( (NFA)NFA)3. NFA可以接受的句子句子（符号串符号串）：(同DFA)若t*，且存在f(S,t)= = P，P终态集，则t为该NFA可以接受的句子。例：参见上例的NFA状态图，判断下列句子能否被接受： aaabaababb aabababNFA M 能够接受的句子的全体记为 L(M)对于每个NFA M 存在一个DFA M，使得L(M)= L(M)!不确定的有穷自动机不确定的有穷自动机( (NFA)NFA) 可以被 NFA M 能够接受的两种情况： M的某结点既是初态，又是终态 存在一条从初态到终态的道路4. NFA的不确定性：对于状态K，当输入字符a时，下一状态不一定唯一 。5. NFA的确定化：对每个NFA M 一定存在一个DFA M，使得 L(M)=L(M)即：对每个NFA M存在着与之等价的DFA M 。注：与某一NFA等价的DFA不唯一。不确定的有穷自动机不确定的有穷自动机( (NFA)NFA)返回NFADFA（子集法）（一）基本运算：n n状态集合状态集合I I的的 闭包闭包：表示为 - -closure(I)closure(I) 状态集I中的任何状态S经任意条弧而能到达的状态状态 的集合的集合。注：状态集I的任何状态S都属于-closure(I)n n状态集合状态集合I I的的a a弧转换弧转换：表示为move(I,a)move(I,a) 定义为状态集合J，其中J是所有那些可从I的某一状 态经过一条a弧而到达的状态的全体。 定义 Ia = -closure(J)举例：参见P58 图4.4，求： - -closure(0)closure(0)move(0,a)move(0,a)move(0,b)move(0,b) - -closure(1)closure(1)move(2,a)move(2,a)move(2,b)move(2,b) move(0,1,2,4,7,a)move(0,1,2,4,7,a) - -closure(1,3)closure(1,3)move(0,1,2,4,7,b)move(0,1,2,4,7,b)NFADFA（子集法）（二）转换的主要思想： DFADFA的的一个一个状态可能对应状态可能对应NFANFA的的一个或一组一个或一组状态状态 DFADFA同样同样记录记录在在NFANFA上上读入某个读入某个VTVT后可能到达的所后可能到达的所有状态有状态（三）子集法NFA NFA N N=(K, =(K, ,f,K,f,K0 0,K,Kt t) )构造构造 DFA DFA M M=(S, =(S, ,d,S,d,S0 0,S,St t) )， 使得使得 L(M)=L(N)L(M)=L(N) ：M M的状态集的状态集S S由由K K的一些子集组成的一些子集组成M M和和N N的的输入字母表相同输入字母表相同转换函数转换函数d d是这样定义的：是这样定义的：d(d( S S1 1 ,.,.,S Sj j,a) = a) = - -closure(moveclosure(move( ( S S1 1 ,.,.,S Sj j,a)a)S S0 0= = - -closure(Kclosure(K0 0) )为为M M的开始状态的开始状态S St t=S Si i , ,S Sk k ,.,S,.,Se e ，其中，其中 S Si i , ,S Sk k ,.,S,.,Se e S S且且 S Si i , ,S Sk k, ,.,.S Se e K Kt t NFADFA（子集法）构造构造 NFA N NFA N 的状态的状态 K K 的子集的算法的子集的算法：假定所构造的子集族为 C = (T1, T2,. Ti)， 其中T1, T2,. Ti为状态 K 的子集。 1）开始，令-closure(K0)为C中唯一成员，并且它是 未被标记的。 2）While(C中存在尚未被标记的子集T) do 标记T； for(每个输入字母a) do U:= -closure(move(T,a) ； if（U不在C中） then 将U作为未标记的子集 加在C中； 举例：参见举例：参见P58 P58 图图4.4 4.4 构造构造NFANFA对应的子集对应的子集NFADFA（子集法）-closure(move(Ti,a)-closure(move(Ti,b)T0= -closure(0)=0,1,2,4,7T1 = 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,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,7b02134abaaaa bbb初态终态DFA M：课后习题：2，3，4(a)返回4.4.2 2 词法分析程序的设计词法分析程序的设计 词法分析（词法分析（lexical analysislexical analysis）功能：功能： 逐个读入逐个读入源程序源程序字符字符，输出，输出“单词符号单词符号” ” ，供，供 语法分析使用。语法分析使用。 主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序追踪换行标志，复制出错源程序宏展开，宏展开，单词符号单词符号n n一般可分为下列五种：一般可分为下列五种： 基本字基本字（关键字关键字）：）：begin, end, if, whilebegin, end, if, while 标识符标识符：各种名称，如常量名、变量名、过程：各种名称，如常量名、变量名、过程 名名 常数常数（量）：（量）：25, 3.1415, 25, 3.1415, TRUE, “ABC”TRUE, “ABC”等等 运算符运算符：如：如 + - * / 等号 等号 =n n界符界符的正规文法的正规文法： 界符 , | ; | ( | ) |返回正规式正规式( (regular expression)regular expression)n正规式：是描述单词符号串规则的工具设字母表=a,z, A,Z, 0,9 辅助字母表=， ，“”表示“闭包”，即任意有限次的自 重复连接“”表示“连接”，有时可以省略“”表示“或” 优先顺序为“( )”、“”、“”、 “”“”、“”和“” 都是左结合的正规式为 ， ， ，(e) ，e1|e2 ，e1 e2 ， e* 中的符号。 （其中e表示任一正规式）例例1 1：令：令 =0 0，11， 上正规式和相应正规集的例子有上正规式和相应正规集的例子有 ： 正规式正规式正规集正规集 00 010,1 01 01 (01)(01)(中间省略连接号)00,01,10,11 0 ,0,0, 任意个 0的串 (01) ,0,1,00,01 所有由0和1组成的串 (01)(0011)(01)上所有含有两个相继的0或两个相继的1组成的串正规式举例正规式举例两个正规式两个正规式等价等价n若两个正规式 e1 和 e2 所表示的正规集相同正规集相同,则说 e1 和 e2 等价。记作 e1 = e2例如： 01 = 10 1(01) = (10)1 (01) = (01)正规式的代数运算n n设设r,s,tr,s,t为正规式，则有：为正规式，则有： r r s=ss=s r r“或或”的交换律的交换律 r r ( (s s t)=(t)=(r r s