第04章、词法分析

第4章词法分析S.PO.P表格管理程序错误处理程序

本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。4.1词法分析程序4.2正规表达式与正规集（正规语言）4.3有限自动机4.4正规文法和有限自动机的转换4.5正规式和有限自动机的等价性2本章重点单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正规表达式，识别机制是有穷状态自动机。34.1词法分析程序实现词法分析（lexicalanalysis）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括关键字(保留字)、标识符、常数、运算符、界符等。词法分析是编译过程中的一个阶段，在语法分析前进行，也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。4词法分析的任务：主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符删除注释进行词法检查，报告所发现的错误建立符号表5单词的分类（1）关键字：或称为保留字，是特定的字母序列，在相应的程序设计语言中表示特殊含义。（2）标识符：由用户定义的串，在程序中常用做常量名、变量名、过程名等。（3）常数：各种类型的常数，包括整型、实型、布尔型、文字型等，如100，10.12，TRUE，“ABC”等。（4）运算符：包括算术运算符和逻辑运算符号，如+、*、<等。（5）界符：如逗号、分号等。6词法分析程序的输出词法分析程序所输出的单词符号，常采用以下二元式表示：

（单词种类，单词自身值）其中，单词种类是语法分析所需要的信息，而单词自身值则是编译的其他阶段需要的信息。单词种类，可以用整数编码表示，例如：1-标识符，2-常数，3-关键字，4-运算符，5-界符语句例：if(a>0)b=b+1;

(1)关键字if(3,’if’)(2)左括号((4,’(’)(3)标识符a(1,指向a的符号表入口)(4)运算符>(4,’>’)(5)常数0(2,’0’)……(12)界符;(5,’;’)7不同分类方法的例子：

下述C++代码段：while(i>=j)i--;经词法分析器处理以后，它将被转换为如下的单词符号串。(while,_)((,_)(id,指向i的符号表指针)(>=,_)(id,指向j的符号表指针)(),_)(id,指向i的符号表指针)(--,_)(;,_)8词法分析程序的实现方式词法分析单独作为一遍优点：结构简单、各遍功能单一缺点：效率低9源程序词法分析程序语法分析程序Tokengettoken….词法分析程序作为单独的子程序优点：无须在外存中保留整个源程序的内码形式。10将词法分析工作分离的原因简化设计改进编译效率增加编译系统的可移植性114.2正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分,单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。12正规式正规式也称正则表达式，正规表达式（regularexpression），是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。13定义（正规式和它所表示的正规集）：设字母表为，辅助字母表’={，，，，，，}。1.和都是上的正规式，它们所表示的正规集分别为{}和{}；2.任何a，a是上的一个正规式，它所表示的正规集为{a}；143.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式，它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。15

正规式中的符号

其中的“”读为“或”（也有使用“+”代替“”的）；“

”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。16例令={a，b}，上的正规式和相应的正规集的例子有：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意个a的串}17

正规式 正规集

(ab) {,a,b,aa,ab……所有由a 和b组成的串}(ab)(aabb)(ab){上所有含有两个相继 的a或两个相继的b组成的串}18

讨论下面两个例子例4.1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式即是字母(字母|数字)

,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则.例4.2={d，，e，+，-},则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合，其中d为09的数字。比如2、21.59、3.6e2、471.88e-1等都是该正规集中的元素。

程序设计语言的单词都能用正规式来定义19正规式的等价若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)b

e1=(ab),e2

=(ab)20正规式服从的代数规律设r,s,t为正规式，正规式服从的代数规律有：1.rs=sr “或”服从交换律2.r(st)=(rs)t “或”的可结合律3.(rs)t=r(st) “连接”的可结合律4.r(st)=rsrt (st)r=srtr 分配律5.r=r,r=r 是“连接”的恒等元素 零一律6.rr=r r=rrr… “或”的抽取律

214.3有限自动机

有限自动机(也称有穷自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有限自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。

有限自动机分为两类：确定的有限自动机(DeterministicFiniteAutomata)不确定的有限自动机(NondeterministicFiniteAutomata)22关于有限自动机我们将讨论如下题目确定的有限自动机DFA不确定的有限自动机NFANFA的确定化DFA的最小化23确定的有限自动机DFADFA定义：一个确定的有限自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；24DFA定义(续）3.f是转换函数，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S∈K是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态或结束状态。25一个DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q26DFA可以表示成一个状态图一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=>”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；27

DFA的状态图表示bSUVQaaaba，bb28DFA还可以用一个矩阵表示一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=>”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。29DFA的矩阵表示字符状态0001以后我们用*表示终态书上：用0表示非终态用1表示终态30

为了说明DFA如何作为一种识别机制，我们还要理解下面的定义

∑*上的符号串t在DFA

M上运行一个输入符号串t，（将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM=（K，Σ，f，S，Z）上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K扩充转换函数f为K×Σ*→K上的映射，且：

f（ki，）=ki31∑*上的符号串t被DFA

M接受M=（K，Σ，f，S，Z）若t∑*，f(S，t)=P，其中S为

M的开始状态，PZ，Z为终态集。则称t为DFAM所接受（识别）.32例：证明t=baab被下图的DFA所接受。bSUVQabba,baaf（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属于终态。得证。33

DFAM所能接受的符号串的全体记为L(M)，对于任何两个有限自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的。

结论：

上一个符号串集V是正规的，当且仅当存在一个上的确定有限自动机M，使得V=L(M)。34DFA的确定性表现在：转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。35例：DFAM=({0,1,2,3},{a,b},f,0,{3})其中：f（0,a)=1;f（0,b)=2f（1,a)=3;f（1,b)=2f（2,a)=1;f（2,b)=3f（3,a)=3;f（3,b)=3问：有几个状态,几个输入字符？并画出其转换图。该自动机可识别符号串abaab和abab吗？36解：有0，1，2，3共四个状态。输入字符为a,b两个。其状态转换图如下：012abababa,b3对于符号串abaab，可被识别。对于符号串abab，不能被识别。37不确定的有限自动机NFA定义NFAM=K，，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2K）的一种映射（即K×*2k），SK是非空初始状态集，ZK为终止状态集.显然，NFA也可以表示成一张状态转换图。假定NFA含有m个状态、n个输入字符，那么，这张图含有m个状态结点，每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用*上的一个字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含有一个初态和若干个（可以是0个）终态结点。某些结点既可以是初态也可以是终态结点。38例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}），其中：

f（S，0）={P}f（Z，0）={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}SPZ00111139矩阵表示01S{P}{S,Z}P{}{Z}*Z{P}{P}40f为K*到K的子集（2K）的一种映射具有转移的不确定的有限自动机

123abc41有如下定理:对任何一个具有转移的不确定的有限自动机NFAN，一定存在一个不具有转移的不确定的有限自动机NFAＭ，使得L(M)=L(N)。

与上例等价的一个NFA:2acbb31acacbb123abc42类似DFA,对NFAM=K，，f，S，Z也有如下定义:∑*上的符号串t在NFA

M上运行一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFAM上运行的定义为：f(Q，Tt1)=f(f(Q，T)，t1)其中Q∈K，∑*上的符号串t被NFA

M接受若t∑*，f(S0，t)=P，其中S0∈S，P∈

Z，则称t为NFAM所接受（识别）43

∑*上的符号串t被NFA

M接受也可以这样理解

对于Σ﹡中的任何一个串t，若存在一条从某一初态结点到某一终态结点的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFAM所识别(读出或接受)。若M的某些结既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的道路，其上所有弧的标记均为ε，那么空字可为M所接受。44举例0001111010001110000001不能识别：000110045

NFAM所能接受的符号串的全体记为L(M)结论：

上一个符号串集V是正规的，当且仅当存在一个上的不确定的有限自动机M，使得V=L(M)。46例：(0|1)*(000|111)(0|1)*47定理：DFA是NFA的特例，对每个NFAN一定存在一个DFAＭ，使得L(M)=L(N)。对每个NFAN存在着与之等价的DFAM。有一种算法，将NFA转换成接受同样语言的DFA，这种算法称为子集法。

与某一NFA等价的DFA不唯一。48从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFA的每一个状态对应NFA的一组状态.DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。49定义对状态集合I的几个有关运算：1.状态集合I的ε-闭包：表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。状态集合I的任何状态S都属于ε-closure(I)。2.Ia：从I中的状态经过一条a弧(前后可跳过任意条ε弧)而到达的状态的全体。50状态集合I的有关运算的例子若I={1},则

-closure(I)={1,2}；若I={5},则

-closure(I)={5,6,2}；若I={1,2},则Ia={2,3,4,5,6,7,8}；(备注：不需要掌握书上讲的move集合)12534678aaa51NFA转换为DFA的思想：将从状态S出发经过任意条弧所能到达的状态作为DFA的初态S'；从S'出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态；如此重复，直到不再有新的状态出现为止。52

NFA确定化算法:

假设NFAN=(K,,f,K0,Kt)，按如下办法构造一个DFAM=(S,,d,S0,St)，使得L(M)=L(N)：531.M的状态集S由K的一些子集组成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的状态。并且约定，状态S1,S2,,...

Sj是按某种规则排列的，即对于子集{S1,S2}={S2,S1,}来说，S的状态就是[S1S2]；

2.M和N的输入字母表是相同的，即是；3.

转换函数是这样定义的：d([S1S2,...

Sj],a)=[R1R2...

Rt]

其中{R1,R2,...,Rt}

=

{S1,S2,,...

Sj}a4.

S0=-closure(K0)为M的开始状态；5.St={[SiSk...

Se]，其中[Si

Sk...

Se]S且{Si

,Sk,,...

Se}Kt}54

NFA的确定化例子47356210aaaabbbb55若要将上图的NFA转换为DFA，步骤如下：（1）构造一张表，它共有｜Σ｜+1列；（2）第一行第一列为-closure({0})；（3）求Ia、Ib并检查，未在第一列出现过者，填入下行首列；（4）重复步骤（3）；（5）将状态子集重新命名。5647356210aaaabbbb-closure(0)I

S

A

B

A

C

B

B

A

D

*C

C

E

*D

F

D

*E

F

D

*F

C

E

57等价的DFAaCDBAEFSbaaaaabbbbbabF58确定有限自动机的化简说一个有限自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有限自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有限自动机。所谓有限自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。59

DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价，满足：(或可区别：不满足）一致性(或兼容性)——同是终态或同是非终态；蔓延性(或传播性)——从s出发读入某个aa和从 t出发读入某个a到达的状态等价。60

例：C和F是等价的。因为C和F同是终态,C和F读入a都到达C,读入b都到达E，所以C和F等价。aCDBAEFSbaaaaabbbbbabF61最小状态DFA对于一个DFAM=（K,∑,f,

k0,kt)，存在一个最小状态DFAM’=（K’,∑,f’,

k0’,,kt’)，使L(M’)=L(M).62“分割法”DFA的最小化算法的核心把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。结论：终态和非终态是可区别的（不等价），因为从终态可以识别到达终态，而从非终态则不能识别到达终态。

63

DFA的最小化算法

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

1.构造状态的一初始划分：终态kt和非终态K-kt两组(group)

2.对∏根据最小化原则，构造新划分∏new

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

4.

为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r，M’的开始状态是含有S0的那组的代表，M’的终态是含有F的那组的代表5.去掉M’中的死状态.64DFA最小化算法的核心——分割法。步骤如下：（1）将所有状态分成两个子集：终态集和非终态集；（2）把等价的状态构成一个子集，若不等价继续划分；（3）结束后，重新标号或从每个子集中选一个状态做代表。65IIaIbSABACBBAD*CCE*DFD*EFD*FCEDFA的最小化—例子M={S,A,B}∪{C,D,E,F}∵{S,A,B}a={A,C}不包含于第1次划分出的任意集合∴{S,A,B}不等价，继续得到第2次划分为：{S,B}∪{A}∵{S,B}b={B,D}不包含于第2次划分出的任意集合∴{S,B}不等价，继续得到第3次划分为：{S}∪{A}∪{B}∵{C,D,E,F}a={C,F}{C,D,E,F}b={D,E}∴{C,D,E,F}等价故最后结果为：M={S}∪{A}∪{B}{C,D,E,F}aCDBAEFSbaaaaabbbbbabF66IIaIbSABACBBAC*CCCDFA的最小化—例子(续)因{C,D,E,F}等价，故从{C,D,E,F}中选C作为代表，出现D,E,F的地方一律用C代替，如下：aCDBAEFSbaaaaabbbbbabF最小化后DFA的为：CBASaaabbbba67例子画出能够识别C语言注释/**/的DFA状态1：注释开始状态。状态2：进入注释体前的中间状态。状态3：表明目前正在注释体中的状态。状态4：离开注释前的中间状态。状态5：注释结束状态，即接受状态。1/2534/**othersothers有限自动机的一些应用用于某些重要软件的设计和构造设计和检查数字电路行为的软件;扫描如网页族等大规模文本以发现字、词或其它结构的出现频率的软件;验证所有只有有限多个不同状态的系统的软件，这类系统包括通信协议和信息安全交换协议。文献举例：基于协议分析状态机的入侵检测系统有限自动机在BBS信息监测系统中的运用定理：

由任意正规文法G定义的语言必然能被一个NFAM所接受。即L（G）＝L（M）

4.4正规文法和有限自动机的转换70定理：由任意正规文法G定义的语言必然能被一个NFAM所接受。即L（G）＝L（M）构造方法：

设正规文法G＝（VN，VT，P，S），构造一个与G等价的有限自动机NFA

M＝（K，∑，f，S，Z），其中：(1)K＝VNU{Z}，Z为一个新增加的终态；(2)∑=VT(即字母表与G的终结符集相同)；(3)开始符号S作为开始状态S；f的定义为：当AaBP，则构造：f（A，a）=B当AaP,则构造：f（A，a）=Z当A

P,则构造：f（A，）=Z一、正规文法＝>有限自动机71正规文法＝>有限自动机（例）例：设有正规文法G=({S,A},{a,b},P,S)，其中 P：SaAAaA|bS|a

试构造与G等价的有限自动机M。解：

设NFAM=(K,∑,f,S,Z)K={S,A,Z}∑={a,b}S

=SZ={Z}转换函数：对于产生式SaA，有f(S,a)={A}对于产生式AaA，有f(A,a)={A}对于产生式AbS，有f(A,b)={S}对于产生式Aa，有f(A,a)={Z}SAZ开始aaab72课堂练习

设正规文法G＝({S，A，B}，{a，b}，P，S)P： S

aA|bB|a AaA|aS|bB BbB|b|a 构造相应的NFAM。73二、有限自动机＝>正规文法定理：设有限自动机M接受的语言为L(M)则存在正规文法G，它产生的语言L(G)＝L(M)。证明思路：构造一个正规文法G，使它接受由NFAM定义的语言。构造方法：

设M＝（K，∑，f，S，Z），构造一个正规文法G＝（VN，VT，P，S），其中VN＝K，S＝SP定义为：若f（A，a）＝B，则AaB在P中

对终态Z，增加一产生式：

Z

74有限自动机＝>正规文法（例）例：设有DFAM=({A,B,C,D},{a,b},f,A,{D})

其中转换函数如图所示，

试构造与之等价的正规文法G。解：构造正规文法G=(VN,VT,P,S)VN={A,B,C,D}VT={a,b}S=A产生式集合Pf(A,a)=B，AaBf(A,b)=C，AbCf(B,a)=D，BaDf(B,b)=B，BbBf(C,a)=C，CaCf(C,b)=D，CbDDZ，DABCDaaabbb开始构造的文法G:G[A]:AaB|bCBaD|bBCaC|bDD75课堂练习构造同NFAM等价的正规文法G。解：bAaBbCDabbaG[A]：A→aB|bDB→bCC→aA|bD|εD→aB|bD|ε764.5正规式和有限自动机的等价性

词法分析程序的自动构造方法，基于有限自动机和正规表达式的等价性，即：1.对于∑上的一个NFAM，可以构造一个∑上的正规式R,使得L(R)=L(M)。2.对于∑上的一个正规式R，可以构造一个∑上的NFAM，使的L(M)=L(R)。771、在M上加两个结点S、Z，从S结点用ε弧到M的所有初态，从M的所有终态用ε到Z结成与M等价的M’，M’只有一个初态S和一个终态Z。03214a,ba,ba,bbbaaS03412Zεεεaa,ba,ba,babb一、自动机＝>正规式（状态消去法）2、逐步消去M’中的所有结点，直至剩下S和Z结点，在消去过程中，逐步用正规式来标记弧，消去规则如下：R1R2123R1R21312R1R2R1|R2121R1R323R2R1R2*R313继续消去S03412Zεεεaa,ba,ba,babbS042Zεεεaaa|b