第4章词法分析编译原理

第四章词法分析正规式NFA正规文法DFA最小化DFA子集法语言消除多余状态合并等价状态4.1词法分析程序的设计词法分析（lexicalanalysis）功能：逐个读入源程序字符，输出“单词符号”，供语法分析使用。主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序宏展开，……单词符号一般可分为下列五种：基本字（关键字）：begin,end,if,while标识符：各种名称，如常量名、变量名、过程名常数（量）：25,3.1415,TRUE,“ABC”等运算符：如+-*/<<=等界符：逗号，分号，括号等词法分析程序与语法分析程序的接口方式方式一（常用）：词法分析程序（扫描整个待编译的源程序）中间文件输出语法分析程序输入：二元式（单词种类，值）优点：（1）整个编译结构简洁、清晰、条理化（2）可移植性好=80;eniLLine=80;==;;输入031字母字母数字数字数字=；4562001字母1字母1字母1字母200=52000=53数字3数字3数字3数字44；6输出1字母1字母id,Line=,num,80;,有限控制器分析结束词法分析程序与语法分析程序的接口方式方式二（PL/0采用）：语法分析程序词法分析程序调用返回一个单词4.2单词的描述工具单词的描述工具和识别工具：正规文法（正则文法、3型文法）正规式（正则式）有穷自动机（NFA、DFA）三者之间可以相互转换下一节正规文法文法的每个产生式的形式都为：A→aB

或

A→a——右线性A→Ba

或

A→a——左线性其中A，B∈VN，a∈VT*例如：标识符的正规文法：（若i表示任一字母，d表示任一数字）

〈标识符〉→i|i〈字母数字〉

〈字母数字〉→i|d|i〈字母数字〉|d〈字母数字〉无符号整数的正规文法：

〈无符号整数〉→d|d〈无符号整数〉运算符的正规文法：

〈运算符〉→+|-|*|/|=|<〈等号〉|>〈等号〉……

〈等号〉→=界符的正规文法：

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

e2，e*

中的符号。（其中e表示任一正规式）例1：令={0，1}，上正规式和相应正规集的例子有：

正规式 正规集

0 {0} 01 {0,1} 01 {01} (01)(01)(中间省略连接号) {00,01,10,11} 0 {,0,00,……任意个0的串}

(01) {,0,1,00,01……所有由0 和1组成的串}

(01)(0011)(01) {上所有含有两个相继 的0或两个相继的1组成 的串}正规式举例两个正规式等价若两个正规式e1和e2所表示的正规集相同, 则说e1和e2等价。 记作e1=e2例如：

01=10 1(01)=(10)1 (01)=(01)正规式的代数运算设r,s,t为正规式，则有：rs=sr “或”的交换律r(st)=(rs)t “或”的结合律(rs)t=r(st) “连接”的可结合律r(st)=rsrt

(st)r=srtr

分配律r=r r=r

是“连接”的恒等元素程序中的单词符号都能用正规式表示：

e=<字母>(<字母>|<数字>)*返回有穷自动机(FA，FiniteAutomata)有穷自动机FA： 是一个识别装置，用于识别“所有句子”。引入FA的目的： 为词法分析程序的自动构造寻找特殊的方法和工具类型：确定的有穷自动机DFA不确定的有穷自动机NFA返回如果我们能构造一个DFAM，使得L(M)是编译器处理的程序语言中的单词，那么模拟DFAM的程序将可以用作词法分析器的控制程序。正规式NFA正规文法DFA最小化DFA子集法语言消除多余状态合并等价状态转换正规文法正规式①等价转换的规则②不断用上述规则进行变换，直到最后只剩一个开始符号为止。正规文法正规式AxBByAxyAxAAyAx*yAxAyAx|y正规文法正规式举例例：正规文法G[S]: SaA，将正规文法正规式。 Sa AaA AdA Aa AdSaASaAaAAdAAaAdSaA|aAaA|dAAa|dSa(A|ε)A(a|d)AAa|dSa(A|ε)A(a|d)*(a|d)Sa((a|d)*(a|d)|ε)Sa(a|d)*正规式正规文法①任何正规式r：定义S为开始符号Sr②转换规则③不断用上述规则进行变换，直到每个产生式的右部只含一个VT为止。正规式正规文法AxyAxBByAx*yAxB或AxAAyAyBxBByAx|yAxAy正规式正规文法举例例：正规式r=0(0|1)*，将正规式正规文法。S0

(0|1)*

S0AA(0|1)*

S0AA(0|1)AAεS0AA0A|1AAε

S0AA0AA1AAε

返回4.3有穷自动机（FA）FA(FiniteAutoMata)：

是一个识别装置，用于识别“所有句子”。引入FA的目的：

为词法分析程序的自动构造寻找特殊的方法和工具类型：确定的有穷自动机

DFA不确定的有穷自动机

NFANFADFA（子集法）DFA的化简（最小化DFA）下一节确定的有穷自动机(DFA)1.定义：一个DFA是一个五元组M=(K,,f,S,Z)K：有穷的状态集：有穷的字母表（即输入字符的集合）f：转换函数K×K上的映像S：初态（初态唯一）Z：终态集（终态不唯一）例：DFAM=({S,U,V,Q},{a,b},f,S,{Q}) f： f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q确定的有穷自动机(DFA)2.DFA的“直观”表示：状态图（状态转换图）每个状态用结点表示若f(Ki,a)=Kj，则初态用“=>”或“-”标出 终态用双圈或“+”标出矩阵列标题：输出符号（VT） 行标题：状态若f(Ki,a)=Kj，则Ki和a的交汇处是Kj初态用“=>”标出或默认第一行（表格左端） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端）KiKja例：参见上例的DFA，分别用状态图和矩阵表示。字符状态0001矩阵表示如下：1.用转换函数例

设ＤＦＡＭ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，f）其中f:f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３DFA的三种表示:2.转移矩阵转移矩阵易存储0132aaaabbbb3状态转换图3.状态转换图确定的有穷自动机(DFA)3.DFA可以接受的句子（符号串）：若t∈*，且存在f(S,t)=…=P，P∈终态集，则t为该DFA可以接受的句子。即：从初态S到某终态结点P的道路上，所有弧上的标记符连接而成字符串t，t为该DFA可以接受的句子。例：参见上例的DFA状态图，判断下列句子能否被接受： abba baab abb aa aDFAM能够接受的句子的全体记为L(M)!!例：证明t=baab被下图的DFA所接受。f（S，baab）=f（f（S，b），aab）

=f（V，aab）=f（f（V，a），ab）

=f（U，ab）=f（f（U，a），b）

=f（Q，b）=QQ属于终态。得证。bSUVQabba,baaSUVZ111000例：从下图结点S出发，最终到达结点Z，请判断01101或1001可否被接受？问题：

设有DFAM=（{0，1，2，3}，{a，b}，f，0，3），其中：f(0,a)=1,f(0,b)=2,f(1,a)=3,f(1,b)=2,f(2,a)=1,f(2,b)=3,f(3,a)=3,f(3,b)=3

（1）画出状态图和矩阵（2）abb是否为M所接受？例：DFA，接受

0和1的个数都是偶数的字符串312011110000开始偶0偶1奇0奇1奇0偶1偶0奇1确定的有穷自动机(DFA)4.DFA的确定性：f:K×K

是一个单值函数即对任何状态K，当输入字符a时，下一状态唯一。上例的有穷状态机就是DFADFAM=（K，Σ，f，S，Z）的行为模拟程序：K:=S；c:=getchar;while(c<>eof){ K:=f(K,c); c:=getchar;}if(KinZ){ return(‘yes’); }else{ return(‘no’); }DFA的行为模拟程序返回例：识别={0,1}上能被能5整除的二进制数0123开始40DFA应用的一个实例0123开始410DFA应用的一个实例（续）0123开始4100DFA应用的一个实例（续）0123开始41001DFA应用的一个实例（续）0123开始410010DFA应用的一个实例（续）0123开始4100101DFA应用的一个实例（续）0123开始41001010DFA应用的一个实例（续）0123开始410010101DFA应用的一个实例（续）0123开始4100101010DFA应用的一个实例（续）0123开始41001010101DFA应用的一个实例（续）0123开始4100101010110102=10101112=710DFA应用的一个实例（续）不确定的有穷自动机(NFA)1.定义：一个NFA是一个五元组M=(K,,f,S,Z)K：有穷的状态集：有穷的字母表（即输入字符的集合）f：转换函数K×*K+

上的映像 （K+表示K的子集）S：初态集（初态不唯一）Z：终态集例：NFAM’=({0,1,2,3,4},{a,b},f,{0},{2,4})

f： f(0,a)={0,3} f(0,b)={0,1} f(1,b)={2} f(2,a)={2} f(2,b)={2} f(3,a)={4} f(4,a)={4} f(4,b)={4}2.NFA的“直观”表示：状态图（状态转换图）每个状态用结点表示若f(Ki,a)=Kj，则初态用“=>”或“-”标出 终态用双圈或“+”标出矩阵列标题：输出符号（VT） 行标题：状态若f(Ki,a)=Kj，则Ki和a的交汇处是Kj初态用“=>”标出或默认第一行（表格左端） 终态用“1”标出（表格右端） 非终态用“0”标出（表格右端）KiKja举例：参见上例的NFA，分别用状态图和矩阵表示。不确定的有穷自动机(NFA)例子NFAM=（{S，P，Z}，{0，1}，f，{S}，{Z}）其中：

f（S，0）={P}

f（Z，0）={P}

f（P，1）={Z}

f（Z，1）={P}

f（S，1）={S，Z}

SPZ00,11113.NFA可以接受的句子（符号串）：(同DFA)若t∈*，且存在f(S,t)=…=P，P∈终态集，则t为该NFA可以接受的句子。例：参见上例的NFA状态图，判断下列句子能否被接受： aaa baab abb a aba babNFAM’能够接受的句子的全体记为L(M’)对于每个NFAM’存在一个DFAM，使得L(M’)=L(M)

!!不确定的有穷自动机(NFA)

可以被NFAM’能够接受的两种情况：

M’的某结点既是初态，又是终态存在一条从初态到终态的道路4.NFA的不确定性：对于状态K，当输入字符a时，下一状态不一定唯一。5.NFA的确定化：

对每个NFAM’一定存在一个DFAM，使得L(M')=L(M) 即：对每个NFAM存在着与之等价的DFAM'。 注：与某一NFA等价的DFA不唯一。证明思想：用M的一个状态对应M的一个状态集合，用这种方法，能从一个NFAM构造一个DFAM，称作子集构造法。不确定的有穷自动机(NFA)返回NFADFA（子集法）（一）基本运算：状态集合I的闭包：表示为-closure(I) 状态集I中的任何状态S经任意条弧而能到达的状态的集合。注：状态集I的任何状态S都属于-closure(I)状态集合I的a弧转换：表示为move(I,a) 定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。举例：参见P58图4.4，求：-closure(0) move(0,a) move(0,b)-closure(1) move(2,a) move(2,b)… move({0,1,2,4,7},a)-closure({1,3}) move({0,1,2,4,7},b)注：1.状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。状态集合I的任何状态S都属于ε-closure(I)。注：2.状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；move({1,2},a)={5,6,2,4,7,3,8}move({5,6,2},a)={3,8}；12534687aaaNFADFA（子集法）（二）转换的主要思想：DFA的一个状态可能对应NFA的一个或一组状态DFA同样记录在NFA上读入某个VT后可能到达的所有状态01426578910bbb例从具体例子的讨论,提炼出从NFA构造DFA的算法。3aa012470,1,2,4,73861243,8,6,1,2,4,7a75614275,6,1,2,4,7b（三）子集法

NFAN=(K,,f,K0,Kt)构造DFAM=(S,,d,S0,St)，使得L(M)=L(N)

：M的状态集S由K的一些子集组成M和N的输入字母表相同转换函数d是这样定义的： d([S1,...,Sj],a)=-closure(move([S1,...,Sj],a))S0=-closure(K0)为M的开始状态St={[Si,Sk

,...,Se]，其中[Si,Sk

,...,Se]S

且{Si,Sk,,...

Se}Kt}NFADFA（子集法）构造NFAN的状态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图4.4构造NFA对应的子集NFADFA（子集法）-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}b02134abaaaabbb初态终态DFAM：课后习题：2，3，4(a)返回01436578910abbb2a3,8,6,1,2,4,70,1,2,4,725,6,1,2,4,7325,9,6,1,2,4,742325,10,6,1,2,4,752319开始0abab6782345输入符号ab状态

NFA到DFA的转换的实例19开始0abab6782345输入符号abA状态

A={0,1,2,4,7}

NFA到DFA的转换的实例19开始0abab6782345输入符号abAB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

NFA到DFA的转换的实例19开始0abab6782345输入符号abABB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}NFA到DFA的转换的实例19开始0abab6782345输入符号abABCB状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBBDC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBBDCD状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBBDCBCD状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的转换的实例19开始0abab6782345输入符号abABCBBDCBCDBC状态

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

NFA到DFA的转换的实例BD开始aAabbabCba19开始0abab6782345输入符号abABCBBDCBCDBC状态NFA到DFA的转换的实例NFA到DFA的转换的实例二4f35621iaaaabbbbNFA到DFA的转换的实例二（续）CDBAEFSbaaaaabbbbb4f35621iaaaabbbb最小化DFA没有多余状态(死状态)没有两个状态是互相等价DFA的化简（最小化DFA）（1）多余状态：

从开始状态出发，任何输入串也不能到达的状态 处理：消除多余状态（2）两个状态s和t等价：满足一致性——同是终态或同是非终态蔓延性——从s出发读入某个aa和从t出发读入某个a到达的状态等价。处理：合并等价状态（使用“分割法”）BD开始aAabbaa,bCbaEb多余状态例子BD开始aAabbabCba左图无死状态，右图加入死状态E。BD开始aAabbabCba等价状态例子A和Ｃ是等价的状态A和Ｂ是不等价的状态CDBAEFSbaaaaabbbbbabaC和D同是终态，读入a到达C和F，C和F同是终态，C和F读入a都到达C，读入b都到达E，C和D等价。DFA的最小化DFA的最小化的唯一性对于一个DFAM=（K,∑,f,k0,,kt)，存在一个最小状态DFAM’=（K’,∑,f’,

k0’,,kt’)，使L(M’)=L(M).结论接受L的最小状态有穷自动机不计同构是唯一的。即，接受L的最小状态有穷自动机不计拓扑结构相同而形式不同的差别，则这种最小状态有穷自动机是唯一的。DFA的最小化算法的过程:把一个DFA的状态分成一些不相交的子集，使得同一子集中的任何两个状态都是等价的.DFA的最小化DFA的最小化算法:

DFAM=（K,∑,f,k0,,kt),最小状态DFAM’

1.构造状态的一初始划分:终态kt

和非终态K-kt两组(group)2.对∏构造新划分∏new

3.如∏new=∏,则令∏final=∏并继续步骤4，否则∏:=∏new重复2.

4.合并等价状态

有穷自动机DFA的最小化算法的核心：把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的，最后每个子集中选出一个代表，同时消除其他等价状态。DFA的最小化例子CDBAEFSbaaaaabbbbbaba１．将Ｍ的状态分为两个子集一个由终态｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态｛Ｓ，Ａ，Ｂ｝组成：２．考察｛Ｓ，Ａ，Ｂ｝是否可分．

S输入a到达A，A输入a到达C，B输入a到达A

因为Ａ属｛Ｓ，Ａ，Ｂ｝而Ｃ属｛Ｃ，Ｄ，Ｅ，Ｆ｝，S和B是两个等价状态，而和A是不等价状态，所以可分为｛Ａ｝和｛Ｓ，Ｂ｝两个集合．３．考察｛Ｓ，Ｂ｝是否可再分：

S输入b到达B，B输入b到达D

因为Ｂ属｛Ｓ，Ｂ｝，Ｄ属｛Ｃ，Ｄ，Ｅ，Ｆ｝所以，可再分为｛Ｓ｝和｛Ｂ｝两个集合．４．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：因为Ｃ，Ｄ，Ｅ，Ｆ输入a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝所以：５．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝来代替则最小化的ＤＦＡ如下图：DFA的最小化例子aaBD开始aAabbabCba12开始a0abbabDFA的最小化算法实例DFA的最小化划分{A,C,B},{D}move({A,C},a}={B}move({A,C},b}={C}合并补充剩余弧解：

步骤一：消除多余状态 步骤二：使用分割法，合并等价状态。b02134abaaaabbbDFAM举例：求最小化DFADFA的化简（最小化DFA）

1,2,3,4,5,6,7Ia：6,7,1,4,7,4,4Ib：3,3,5,6,3,1,2{1,2,3,4}{5,6,7}{1,2}{3,4}{5}{6,7}{1,2}{3}{4}{5}{6,7}1352746aaaaaaabbbbbbb13546aaaaabbbbb举例：求最小化DFA返回P70例2课后题：4(b)94.4正规式和有穷自动机的等价性正规式NFA正规文法DFA最小化DFA子集法语言消除多余状态合并等价状态转换对于∑上的

NFAM，可以构造一个∑上的正规式R，使得

L(R)=L(M)。对于∑上的正规式R，可以构造一个∑上的

NFAM，使得

L(M)=L(R)。在FAM的状态图上加两个状态结点x和y。从x结点出发，用ε弧连接x结点到所有初态结点从M的所有终态结点用ε弧连接到y结点 此时，

x为初态和y为终态。利用消结规则，逐步消去M’中的所有结点，直至只剩下x和y。最后x和y结点间的弧上的标记则为所求的正规式R。FA正规式123R1R213R1R213R1R213R1|

R2123R1R3R213R1R2*

R3举例：求FA所对应的正规式R03124a,baaa,ba,bbb解：03124a,baaa,ba,bbbxyεεεFA正规式024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε则：R=(a|b)*(aa|bb)(a|b)*0a|baa(a|b)*bb(a|b)*xyε0a|bxyε(aa|bb)(a|b)*xy(a|b)*(aa|bb)(a|b)*课后习题：9将正规式分解成一系列子表达式。对于每个子表达式，用如下规则构造FA：正规式FA正规式FAФεRR1R2

1212ε12R正规式FAR1|

R2R*13R1R2123εεR注意：由于分解的方法和顺序不同，构造的NFA可能不同，但最小化的DFA一定相同！！13R1R22从正规式到有限自动机首先构造识别和字母表中一个符号的NFAi开始识别正规式的NFAafif开始识别正规式a的NFA构造识别主算符为选择的正规式的NFA

fi开始识别正规式s|t的NFAN(s)N(t)从正规式到有限自动机iN(s)f开始识别正规式st的NFAN(t)构造识别主算符为连接的正规式的NFA

从正规式到有限自动机构造识别主算符为闭包的正规式的NFA

N(s)f开始识别正规式s*的NFAi从正规式到有限自动机对于加括号的正规式(s)，使用N(s)本身作为它的NFA。19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正规式到有限自动机19开始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解从正规式到有限自动机19开始0abab6782345r9r7r8r4r