第三章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 3.1 对于词法分析程序的要求 第三章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 3.1 对于词法分析程序的要求 3.2 词法分析器的设计 3.3 正则表达式与有限自动机 3.4 词法分析器的自动产生

本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 —首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。 —描述程序设计语言的词法的机制是正则表达式，识别机制是有限状态自动机。

什么是词法分析程序 实现词法分析（lexical analysis）的程序称为词法分析程序（或扫描器）。 词法分析程序的主要任务： 对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一的标准形式—属性字（TOKEN）。

词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 词法分析程序和语法分析程序的关系 Token 源程序 词法分析程序 语法分析程序 …. get token

词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性

功能：输入源程序，输出单词符号。 § 3.1 对于词法分析器的要求 单词符号是一个程序语言的基本语法符号。 单词的分类（五类）： § 3.1 对于词法分析器的要求 3.1.1 词法分析器的功能和输出形式 功能：输入源程序，输出单词符号。 单词符号是一个程序语言的基本语法符号。 单词的分类（五类）： 1. 关键字：由程序语言定义的具有固定意义的标识 符。也称为保留字或基本字。 2. 标识符：用来表示程序中各种名字的字符串。 3. 常 数：常数的类型一般有整型、实型、布尔型、 文字型。 4. 运算符：如+、－ 、*、/ 等。 5. 界限符：如逗号、分号、括号等。

一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。 词法分析器所输出的单词符号常常表示成如下的二元式： （单词种别，单词符号的属性值） 单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则直按类型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。

如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。 单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。

考虑下述C＋十代码段： while（i＞＝j）i－－； 经词法分析器处理后，它将被转换为如下的单词符号序列： 在教材中，我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。 考虑下述C＋十代码段： while（i＞＝j）i－－； 经词法分析器处理后，它将被转换为如下的单词符号序列： ＜while，－＞ ＜（，－＞ ＜id，指向i的符号表项的指针＞ ＜＞＝，－＞ ＜id，指向j的符号表项的指针＞ ＜），－＞ ＜id，指向i的符号表项的指针＞ ＜－－，－＞ ＜；，－＞

我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。 3.2词法分析器的设计 我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。 一、 输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。

预处理的主要工作： 某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。 注解部分—仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。 空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。 我们可以构造一个预处理子程序，它能够完成上面所述的任务。

二、 单词符号的识别：超前搜索 词法分析器的结构如图3.1所示。当词法分析器调用预处理子程序处理出一串输入字符放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。 图3.1 词法分析器

为什么要采用超前搜索 在程序中有一些单词的识别经常需要多读入一些字符才能知道哪些字符组成一个单词。如： 这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以基本字开头的，语句3和4是赋值句，它们都是以用户自定义标识符开头的。 1 DO99K＝l,10 2 IF（5.EQ.M） I＝10 3 DO99K＝1.10 4 IF（5）＝55 又如C中： a=a++; a=a+1;

1 2 3 三、 状态转换图 状态转换图是一张有限方向图，是设计词法分析器的有效工具。 图3.2（a）转换图示例 X Y 图3.2（a）转换图示例 一个状态转换图可用于识别（或接受)一定的字符串。

正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。 §3.3 正规表达式与有限自动机 1 正规式与正规集 正规式也称正则表达式。 正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。 定义（正规式和它所表示的正规集）： 设字母表为，辅助字母表`={ ，，，，，， }，1. 和都是上的正规式，它们所表示的正规集分别为{}和{ }；

2. 对任何a ，a是上的一个正规式，它所表示的正规集为{a}； 3. 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1))。 4. 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。

注意: “”读为“或” ； 2. “ ”读为“连接”； 3. “”读为“闭包”（即，任意有限次的自重复连接）。 其中“”、 “ ”、 “”均为正规式运算符： “”读为“或” ； 2. “ ”读为“连接”； 3. “”读为“闭包”（即，任意有限次的自重复连接）。 在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“ ”、“” 。连接符“ ”一般可省略不写。“”、“ ”和“” 都是左结合的。

令={a，b}， 上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb} a  { ,a,a, ……任意个a的串}

正规式 正规集 (ab) { ,a,b,aa,ab ……所有由a 和b组成的串} (ab)(aabb)(ab) {上所有含有两个相继 的a或两个相继的b组成 的串}

若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 正规式的等价性 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (ab)， e2 = ba， e1= e2 又如： e1= b(ab) , e2 =(ba)b， e1= e2 e1= (ab) , e2 =(ab)， e1= e2

设U,V,W为正规式，正规式服从的代数规律有： 1. UV=VU “或”服从交换律 2. U(VW)=(UV)W “或”的可结合律 3. (UV)W=U(VW) “连接”的可结合律 U(VW)=UVUW (VW)U=VUWU 分配律 5. U=U, U=U 是“连接”的恒等元 素零一律 6. UU=U U=UUU…

2 有限自动机 有限自动机(也称有穷自动机) 能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有限自动机(Deterministic Finite Automata)和不确定的有限自动机(Nondeterministic Finite Automata) 。

关于有限自动机我们将讨论如下题目 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化

一、DFA定义： 一个确定的有穷自动机（DFA）M是一个五元组： M=（S，Σ，δ，s0 ，F）,其中: 1. S是一个有穷集，它的每个元素称为一个状态； 2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表； 3. δ是转换函数，是在S×Σ→S上的单值部分映射，即，如果 δ（s，a）=s’，（s∈S，s’∈S）就意味着，当前状态为s，输入符为a时，将转换为下一个状态s’，s’称作s的一个后继状态； 4. s0 ∈S是唯一的一个初态； 5. F S是一个终态集（可空），终态也称可接受状态或结束状态。

DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，即s行a列的 矩阵元素表示δ （s，a）的值。这个矩阵称为状态转换矩阵。

一个DFA也可表示成一张（确定的）状态转换图。 假定DFA M含有 m个状态和 n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用Σ中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。 注意：初态结点的旁边标以 ； 终态结点则用双圈表示。

状态 a b S U V Q a U a,b a b a Q  S V b b 对于Σ*中的任何字α，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字符串等于α，则称α可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字ε可为M所识别（或接受）DFA M所能识别的字的全体记为L(M) 。 如有α =abb，显然α可为上例的DFA M所识别。

例：证明t=baab被下图的DFA所接受。 S U V Q a b,a  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）=Q Q属于终态。得证。

三、DFA的确定性 1. 映射δ ：SΣ→S是一个单值函数。也就是说，对任何状态s∈S和输入符号a∈Σ，f（s，a）唯一地确定了下一状态。从转换图的角度来看，假定字母表Σ含有n个输入字符，那么，任何一个状态结最多只有n条弧射出，而且每条弧以一个不同的输入字符标记。

3非确定的有穷自动机NFA 一、NFA定义： 一个非确定的有穷自动机（NFA）M是一个五元组： M=（S，Σ， δ ，S0 ，F）,其中: 2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表； 3. δ是状态转换函数，是在S×Σ*→S的子集的映射，即， δ : S×Σ*→2S ；表明在某状态下对于某输入符号可能有多个后继状态； 4. S0 S是一个非空初态集； 5. F S是一个终态集（可空）。

δ （Z，0）={P} δ （P，1）={Z} δ （Z，1）={P} δ （S，1）={S，Z} 二、一个NFA 的例子： NFA M=（{S，P，Z}，{0，1}， δ ，{S}，{Z}） 其中 ： δ （S，0）={P} δ （Z，0）={P} δ （P，1）={Z} δ （Z，1）={P} δ （S，1）={S，Z} 状态图表示 S P Z 0,1 1

∑*上的符号串t被NFA M接受也可以这样理解: 对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为ε，那么空字可为M所接受。

NFA M所能接受的符号串的全体记为 L(M)。 结论： 上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。

4.NFA与DFA的等价性： 显然， DFA是NFA的特例。 对于每个NFA M，存在一个DFA M’ ，使得L( M ) =L( M’ )。对每个NFA M存在着与之等价的DFA M’。 即：对于任何两个有穷自动机M和M’，如果L( M )=L( M’ )，则称M与M’是等价的。 有一种算法，将NFA转换成接受同样语言的DFA。这种算法称为子集法。 与某一NFA等价的DFA不唯一。

从NFA的矩阵表示中，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： DFA的每一个状态对应NFA的一组状态。

一、NFA确定化算法（NFA→DFA的转换）: 假设NFA N=(K, , f,K0,Kt)按如下办法构造一个DFA M=(S, , δ,S0,St)，使得L(M)=L(N)： 1. M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]； 2 M和N的输入字母表是相同的，即是； 转换函数是这样定义的： δ([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = -closure(move({S1, S2,,... Sj},a)) 4 S0=-closure(K0)为M的开始状态； 5 St={[Si Sk... Se]， 其中 [Si Sk... Se]S且{Si , Sk,,... Se}Kt}

二、定义对状态集合I的几个有关运算： 1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。 2. 状态集合I的a弧转换，定义状态集合J表示为 J=move(I,a) ，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。 Ia=ε-closure(J ) =ε-closure(move(I,a) )

状态集合I的有关运算的例子 I={1}, -closure(I)={1,2}； I={5}, -closure(I)={5,6,2}； 3 4 6 8 7 a  I={1}, -closure(I)={1,2}； I={5}, -closure(I)={5,6,2}； move({1,2},a)={5,3,4} -closure({5,3,4})={2,3,4,5,6,7,8}；

假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 三、构造NFA N的状态K的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。 2.while （C中存在尚未被标记的子集T）do { 标记T； for 每个输入字母a do { U:= -closure(move(T,a))； if U不在C中 then 将 U作为未标记的子集Ti加在C中 }

Ia Ib I 例子 {i,1,2} {1,2,3} {1,2,4} {1,2,3,5,6,f} {1,2,4,5,6,f}  a b Ia Ib {i,1,2} {1,2,3} {1,2,4} {1,2,3,5,6,f} {1,2,4,5,6,f} {1,2,4,6,f} {1,2,3,6,f} I

等价的DFA C D B A E F S b a JFLAP加载Figure3.6.jff 演示一次

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

1.没有多余状态(死状态)； 两个状态s和t等价： 两个状态s和t等价： 一、最小状态DFA的含义： 2.没有两个状态是互相等价（不可区别）。 两个状态s和t等价： 兼容性——同是终态或同是非终态； 传播性——对于所有输入符号，状态s和状态t必须转换到等价的状态里。 两个状态s和t等价： 如果由 s 出发能导出的所有串的集合与 t 出发能导出的所有串的集合相等，我们称状态 s 与状态 t 是等价的。

C和D同是终态，读入a到达C和F，C和F同是终态， C和F读入a都到达C，读入b都到达E。 C和D等价。 例子 C D B A E F S b a C和D同是终态，读入a到达C和F，C和F同是终态， C和F读入a都到达C，读入b都到达E。 C和D等价。

二、“分割法”（逐步分组试探法） DFA的最小化算法的核心思想 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。 算法假定每个状态射出的弧都是完全的,否则，引入一个新状态，叫死状态，该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己。

三、 DFA的最小化算法 设有DFA M =（K,∑,f,k0 ,kz）,最小状态DFA M 1.  因为不难证明，如果si是非终结状态，而sj是终结状态，那么si和sj一定互不等价（根据等价的定义可知，它们导出的符号串集不同）。所以开始可以把K中的终态和非终态分开，分成两个子集，形成一个基本划分： P2＝{I1，I2} （I1∪I2＝K，I1∩I2＝Φ） 2. 若此两个子集还可以进行划分，则作进一步的划分，形成Pm ,假定到某个时候Pm已经含有m个子集，记为：Pm＝{I1，I2，…，Im}，设s和s是Ii中的任意两个状态，如果对某个a∈Σ,存在Ij ，使 f(s,a), f(s,a)∈Ij ，则称s和s关于a是拟等价的。 如果存在s，s∈Ii，使得对字母表Σ中的某个符号a, s和s不为拟等价，则我们说Ii是可分的。 换句话说，令Ii ＝{s1，s2, …，sn} ，如果对某个a∈Σ，使得Iai＝{ f(s1,a)，f(s2,a)，…，f(sn,a)}不全落在现行Pm的某一个子集Ij之中；即Iai这个集合中的元素分别属于I1，I2，…，Im中的几个不同集合，则Ii可分为几个集合（至少可一分为二）。

2 3 6 4 1 b a 5 7 b 3．转2,上述过程务必一再重复，直到P中的每个集合均是不可再分时为止。 此时，P所含的集合数不再增加，即P中的每个集合中的状态互相等价，而不同集合间的状态互不等价。 4.为P中的每一组选一代表，这些代表构成M的状态。把原来导入非代表状态的弧均导入其代表即可，即若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r，M的开始状态是含有S0的那组的代表，M的终态是含有F的那组的代表。 5.去掉M中的死状态。 2 3 6 4 1 b a 5 7 例：有DFA M见右图，求其极小化后的DFA M 。 b

6 正规式与有穷自动机的等价性 定理： 对于上的NFA M，可以构造一个上的正规式R，使得L（R）=L（M）。 对于上的任一个正规式R ，可以构造一个上的NFA M ，使得L（M）=L（R）。

把上的NFA M转换为一个上的正规式R 转换方法：我们把状态转换图的概念拓广，令每条弧可用一个正规式标记。 1. 在M的状态图上加进两个结点x、y。从x结点用ε弧 连接到M的所有初态结点，从M的所有终态结点ε弧 连接到y结点。形成一个与M等价的M， M只有一个初态和一个终态。 2. 逐步消去M中的所有结点，直至只剩下x结点和y结点。在消结过程中，逐步用正规式来标记弧，其消结规则如下： 对于 1 2 3 R1 R2 代之为： R1 R2 R1 | R2 R1R2* R3 R3 最后x结点和y结点之间的弧上的标记就是所求的正规式R。

例：有NFA M如图，求其等价的正规式R。 1 2 3 4 b a a，b  x y (a| b)*(aa| (bb(a| b) *)) 

三、从上的正规式R 构造一个上的NFA M，使得L(M)=L(R) x y R  然后通过对R进行分裂和加进新结点的办法，逐步把这个图转变为：每条弧标记为中的一个字母或ε ，其转换规则如下： 对于 i k j α β 代之为： αβ 1 2 α | β β * ε 在整个分裂过程中，所有新结点均采用不同的名字，保留x和y为全图的唯一初态结点和终态结点，至此我们就可以得到一个与R 等价的NFA M。

7 正规文法与有穷自动机的等价性 定理： 对于给定的正规文法G[R]，可以直接构造一个NFA M，使得L（M）=L（G）。 对于上的任一个NFA M ，可以直接构造正规文法G[R] ，使得L（ R ）=L（ M ）。

把给定的正规文法G[R]转换为一个上的NFA M构造规则: 设G[R]=（VN，VT，P，R）， NFA M=（ K，Σ，f，S，Z） 1.令 Σ= VT； 2. K = VN，S = R；即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态； 3.增加一个新状态Z，作为NFA M 的终态，Z∈K； 4.对G中的形如AtB（其中t为终结符或ε；A和B为非终结符）的产生式， 构造M的一个转换函数f（A，t）=B； 5.对G中的形如At（其中t为终结符或ε；A和B为非终结符）的产生式， 构造M的一个转换函数f（A，t）=Z；

把给定的上的NFA M转换为一个正规文法G[R]的构造规则: 设NFA M=（ K，Σ，f，S，Z），G[R]=（VN，VT，P，R）， 1.令 VT = Σ ； 2.令VN = K即对M的每一个状态生成G中的非终结符（不妨取相同的名字，G的开始符号是M的初态； 3.令S=R（如果M有多个初态，应先拓广自动机，引入新初态x）； 4.对M 的终态Z增加一个产生式： Zε； 5.对M的每一个转换函数f（A，t）=B可写G的一个产生式AtB（其中t为终结符或ε；A和B为非终结符）；

3.4 词法分析程序的自动构造 若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。 读tiger.lex 说明lex的思想 作业： 6，7，8，9，12，14