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

第四章 词法分析正规式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：转换函数 K×K 上的映像§ 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: K×K 是一个单值函数即 对任何状态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)返回NFADFA（子集法）（一）基本运算：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)NFADFA（子集法）（二）转换的主要思想：§ § 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} }NFADFA（子集法）构造构造 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对应的子集对应的子集NFADFA（子集法）-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,2,4,5,6,7,9}T2= {1,2,4,5,6,7} T1 = {1,2,3,4,6,7,8} T2 = {1,2,4,5,6,7}T3= {1,2,4,5,6,7,9} T1 = {1,2,3,4,6,7,8} T4 = {1,2,4,5,7,10}T4= {1,2,4,5,7,10} T1 = {1,2,3,4,6,7,8} T2 = {1,2,4,5,6,7}b02134abaaaa 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，，1}1}，，  上正规式和相应正规集的例子有上正规式和相应正规集的例子有 ：： 正规式正规式正规集正规集 0{0} 01{0,1} 01 {01} (01)(01)(中间省略连接号){00,01,10,11} 0 { ,0,0, ……任意个 0的串} (01){ ,0,1,00,01 ……所有由0和1组成的串} (01)(0011)(01){上所有含有两个相继的0或两个相继的1组成的串}正规式举例正规式举例两个正规式两个正规式等价等价n若两个正规式 e1 和 e2 所表示的正规集相同正规集相同,则说 e1 和 e2 等价记作 e1 = e2例如： 01 = 10 1(01) = (10)1 (01) = (01)正规式的代数运算n n设设r,s,tr,s,t为正规式，则有：为正规式，则有： § § r r s=ss=s r r““或或””的交换律的交换律 § § r r ( (s s t)=(t)=(r r s 。