编译原理第四章 词法分析

第四章 词法分析

课前索引

【课前思考】

◇ 词法分析程序的功能是什么？

◇ PL/0词法分析程序识别哪几种单词？ ◇ 画出PL/0词法分析程序的流程图。

◇ C语言，PASCAL语言的标识符和数的表示分别有什么规定？ ◇ 编写一个程序（C的，或PASCAL的）识别C++语言的标识符。 【学习目标】

◇ 明确词法分析在编译过程所处的阶段和作用。 ◇ 掌握词法分析程序的手工实现方法。 ◇ 理解通常的单词分类和构词规则。 ◇ 会使用单词的描述和识别机制。 ◇ 掌握词法分析程序的自动构造原理。 【学习指南】

词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。词法分析也是语法分析的一部分，把词法分析从语法分析中出来是为了使编译程序结构清晰，也是为了便于使用自动构造工具，提高编译效率。

本章首先介绍词法分析程序的功能和设计原则，然后引入正规式和其对单词的描述，接着讲述有穷自动机理论，最后给出词法分析程序的自动构造原理。 【难重点】

◇ 如何设计和实现词法分析程序

◇ 正规式的定义-如何用作单词的描述工具

◇ 有穷自动机的定义和分类-如何用作单词的识别系统

◇ 正规式到有穷自动机的转换算法-词法分析程序的自动构造原理

第4章 词法分析

【知识结构】

第4章 词法分析

词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。

词法分析程序的主要任务： - 读源程序，产生单词符号 词法分析程序的其他任务： - 滤掉空格，跳过注释、换行符 - 追踪换行标志，复制出错源程序， - 宏展开，……

本章要点：

- 告诉你掌握词法分析程序的设计和实现的办法

- 首先需要描述和刻画程序设计语言中的原子单位--单词，其次需要识别单词和执行某些相关的动作。

- 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。

4.1 词法分析程序

首先讨论词法分析程序与语法分析程序的接口方式

词法分析程序完成的是编译第一阶段的工作。词法分析工作可以是的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程。然而，更一般的情况，是将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止。这种设计方案中，词法分析程序和语法分析程序是放在同一遍里，而省掉了中间文件，象第2章介绍的PL/0编译程序那样.也是大多数编译程序采用的方案。 实现词法分析（lexical analysis）的程序

逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 词法分析程序和语法分析程序的关系

f4-1-1.swf

词法分析程序的主要功能是从字符流的源程序中识别单词，它要从左至右逐个字符地扫描源程序，因此它还可完成其它一些任务。比如，滤掉源程序中的注释和空白(由空格，制表或回车换行字符引起的空白)；又比如，为了使编译程序能将发现的错误信息与源程序的出错位置联系起来，词法分析程序负责记录新读入的字符行的行号，以便行号与出错信息相联；再有，在支持宏处理功能的源语言中，可以由词法分析程序完成其预处理等等。

接着讨论词法分析程序的输出

词法分析程序的功能是读入源程序，输出单词符号。单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分成下列5种：

① 保留字，也称关键字，如PASCAL语言中的begin,end,if,while和var等。

第4章 词法分析

② 标识符，用来表示各种名字，如常量名、变量名和过程名等。 ③ 常数，各种类型的常数，如25，3.1415，TRUE和\"ABC\"等。 ④ 运算符，如+，*，<=等。

⑤ 界符，如逗点，分号，括号等。 五种单词符号： - 保留字，关键字 - 标识符 - 常数（量） - 运算符 - 界符

你能举出一些例子吗?

词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单词自身的值)。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1；中的单词 25和1的种别都是常数，常数的值25和1对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式(标识符，指向该标识符所在符号表中位置的指针)，如上述语句中的单词i和yes的表示为：

(标识符，指向i的表项的指针) (标识符，指向yes的表项的指针)

单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段 if i=5 then x∶=y；在经词法分析器扫描后输出的单词符号和它们的表示如下： - 保留字if(3，'if')

- 标识符i(1，指向i的符号表入口) - 等号=(4，'=') - 常数5(2，'5')

- 保留字then(3，'then')

- 标识符x(1，指向x的符号表入口) - 赋值号∶=(4，'∶=')

- 标识符 y(1，指向y的符号表入口) - 分号；(5，'；')

将词法分析工作从语法分析中分离出来的原因

实际上，词法也是语法的一部分，词法描述完全可以归并到语法描述中去，只不过词法规则更简单些。这在后面的章节中可以看到。为什么将词法分析做为一个的阶段？为什么把编译过程的分析工作划分成词法分析和语法分析两个阶段？主要的考虑因素为： ① 使整个编译程序的结构更简洁、清晰和条理化。 ② 编译程序的效率会改进。 ③ 增强编译程序的可移植性。

① 使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；再比如对于FORTRAN和cobol那种受书写格式的语言，需在识别单词时进行特殊处理等等。如果统统合在语法分析时一并考虑，显然会使得分析程序的结构

第4章 词法分析

复杂得多。

② 编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符号分离出来。把词法分析出来，采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。

③ 增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASC II还是EBCDIC字符编码。另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的\"↑\"的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。

第4章 词法分析

4.2 正规表达式与正规集（正规语言）

程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。

为了理解将使用的形式工具，首先表述一些基本术语和概念。

- 符号 一个抽象实体,我们不再形式地定义它(就象几何中的\"点\"一样)。例如字母是符号，数字也是符号。

- 字母表 字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。

- 符号串 由字母表中的符号组成的任何有穷序列称为符号串，例如00 11 10 是字母表Σ={0，1}上的符号串。

不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。 字母表A={a,b,c}上的一些符号串有：a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，例如符号串ab就不同于ba,abca和aabc也不同。可以使用字母表示符号串，如x=STR表示\"x是由符号S、T和R，并按此顺序组成的符号串\"。

如果某符号串x中有m个符号，则称其长度为m，表示为|x|=m，如001110的长度是6。

允许空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即|ε|=0。

下面介绍有关符号串的一些运算。 - 符号串的头尾，固有头和固有尾 - 符号串的连接 - 符号串的方幂 - 符号串集合

符号串的头尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。

举个例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。

当我们对符号z=xy的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：z=x…；

如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串. 由于ε的含义，显然有εx=xε=x。

例如设x=ST，y=abu，则它们的连接xy=STabu，看出|x|=2，|y|=3，|xy|=5。

符号串的方幂：设x是符号串，把x自身连接n次得到符号串z，即z=xx…xx，称为符号串x的n次方幂，写作z=xn，也即把符号串x相继地重复写n次。x0=ε,x1=x,x2=xx,x3=xxx分别对应于n=0,1,2和3 例子；若x=AB 则: x0 = ε x1 = AB x2 = ABAB x3 = ABABAB

第4章 词法分析

xn = xxn-1 = xn-1 x (n>0)

符号串集合：若集合A中的一切元素都是某字母表Σ上的符号串，则称A为字母表Σ上的符号串集合。两个符号串集合A和B的乘积定义如下：AB={xy|x∈A且y∈B}，即AB是满足x属于A，y属于B的所有符号串xy所组成的集合。例如，若A={a,b},B={c,d},则集合AB={ac,ad,bc,bd}。因为对任意符号串x有εx=xε=x，所以有{ε}A=A{ε}=A。 指定字母表Σ之后，使用Σ* 表示Σ上的一切符号串（包括ε）组成的集合。Σ* 称为Σ的闭包。Σ上的除ε外的所有符号串组成的集合记为Σ+。 Σ+ 称为Σ的正闭包。 Σ+ =Σ* -{ε}=ΣΣ* =Σ∪Σ2∪Σ3∪…… Σ* ={ε}∪Σ∪Σ2∪…… 例：Σ={a,b}

Σ* ={ε,a,b,aa,ab,ba,bb,aaa,aab,…} Σ+ ={a,b,aa,ab,ba,bb,aaa,aab,…}

我们用以描述单词符号的工具是正规式。

正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。

正规式也称正则表达式，也是表示正规集的数学工具。下面是正规式和它所表示的正规集的递归定义。

定义（正规式和它所表示的正规集）：

设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，(， }。

① ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{ }； ② 任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；

③ 假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。

④ 仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。

正规式定义中的“|”读为“或”（也有使用“+”代替 “|” 的）；“·”读为“连接”；“*”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“·”、“|” 。连接符“·”一般可省略不写。“*”、“·”和“|” 都是左结合的。 令∑={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= (a|b)， e2 = b|a

又如： e1= b(ab)* ，e2 =(ba)* b 再如： e1= (a|b)* ，e2 =(a* |b* )*

设r,s,t为正规式，正规式服从的代数规律有：

第4章 词法分析

① r|s=s|r \"或\"服从交换律 ② r|(s|t)=(r|s) | t \"或\"的可结合律

③ (rs)t=r(st) \"连接\"的可结合律 ④ r(s|t)=rs|rt

(s|t)r=sr|tr 分配律

⑤ εr=r, rε=r ε是\"连接\"的恒等元素零一律 ⑥ r|r=r

r*=ε|r|rr|… \"或\"的抽取律

程序设计语言的单词都能用正规式来定义。请看下面两个例子：

例4.1

令Σ={l，d}，则Σ上的正规式 r=l(l|d)* 定义的正规集为：{l,ll,ld,ldd,……}，其中l代表字母，d代表数字，正规式，即是字母(字母|数字)*，它表示的正规集中的每个元素的模式是“字母打头的字母数字串”，就是Pascal和多数程序设计语言允许的的标识符的词法规则。

例4.2

Σ={d，·，ε，+，-},则Σ上的正规式d*(·dd* |ε)( ε(+| -ε|)dd* |ε)表示的是无符号数的集合。其中d为0~9的数字。

外文教材中常常遇到的术语 - Token 单词,词标，符号 - lexeme 词素，词位 - pattern 模式，式样

这段话帮你理解外文教材中常常遇到的术语In general，there is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token. The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. 例如：

源程序语句Const pi=3.14159，x1=10；中的pi和x1是token “identifier”的lexeme，其pattern为字母开头，后面跟有字母和/或数字的字符序列。

第4章 词法分析

4.3 有穷自动机

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

有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。

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

4.3.1 确定的有穷自动机DFA

DFA定义：-一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中

① K是一个有穷集，它的每个元素称为一个状态；

② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；

③ f是转换函数，是K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；

④ S ∈ K是唯一的一个初态；

⑤ Z K是一个终态集，终态也称可接受状态或结束状态。 举一个DFA 的例子：

DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=V f（v，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q

一个DFA可以表示成一个状态图(或称状态转换图)。假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头\"=>\"或标以\"-\"，终态结点用双圈表示或标以\"+\"，若 f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧； DFA 的状态图表示

第4章 词法分析

一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头\"=>\"标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。

DFA 的矩阵表示 状态\\字符 S U V Q a U Q U Q b V V Q Q 0 0 0 1

DFA的确定性表现在转换函数f:K×Σ→K是一个单值函数，也就是说，对任何状态k∈K，和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。从状态转换图来看，若字母表Σ含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。

为了说明DFA如何作为一种识别机制,我们还要理解下面的定义。 ∑*上的符号串t在M上运行 - 一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在DFA M上运行的定义为：

- f（Q， Tt1）=f（f（Q，T），t1） 其中Q∈K

- 扩充转换函数f，是K×Σ*→K上的映射，且： f（ki，ε）= ki ∑*上的符号串t被M接受

- 若t∈∑*，f(S，t)=P，其中S为 M的开始状态，P∈Z，Z为终态集。 - 则称t为DFA M所接受（识别）

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

∑上一个符号串集V∑*是正规的，当且仅当存在一个∑上的确定有穷自动机M，使得V=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）

第4章 词法分析

=f（Q，b）=Q Q属于终态。 得证。

4.3.2不确定的有穷自动机NFA

接下来我们讨论不确定的有穷自动机NFA 定义

不确定的有穷自动机NFA N=(K，∑，f，S，Z) 其中：

K为状态的有穷非空集 ∑为有穷输入字母表

f为K* ∑*到K的子集（2K）的映射 SK是初始状态集 ZK为终止状态集。 例子：

NFA N=（{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} 状态图表示

同样NFA也有矩阵表示 f4-2-1.swf

类似DFA, 对NFA N=(K，∑，f，S，Z)也有如下定义

第4章 词法分析

∑*上的符号串t在NFA N上运行 一个输入符号串t，（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFA N上运行的定义为：

f（Q， Tt1）=f（f（Q，T），t1） 其中Q∈K. ∑*上的符号串t被NFA N接受

若t∈∑*，f(S，t)=P，其中S为 N的开始状态，P∈Z，Z为终态集。 则称t为NFA N所接受（识别）

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

NFA N所能接受的符号串的全体记为L(N)

结论：

∑上一个符号串集V∑*是正规的，当且仅当存在一个∑上的不确定的有穷自动机N，使得V=L(N)

下图的NFA称作具有ε转移的不确定的有穷自动机

对任何一个具有ε转移的不确定的有穷自动机NFA N，一定存在一个不具有ε转移的不确定的有穷自动机NFA M，使得L(M)=L(N)。 这里给出与上图等价的一个NFA。

4.3.3 不确定的有穷自动机N的确定化

根据定义，显然DFA是NFA的特例。对于每个NFA M，存在一个DFA M′，使得 L(M)=L(M′)。

对于任何两个有穷自动机M和M′，如果L(M)=L(M′)，则称M与M′是等价的。 我们将介绍一种算法，对于给定的NFA M，构造其等价的DFA M′。 请你注意这个结论：DFA是NFA的特例

对每个NFA N一定存在一个DFA M，使得L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。与某一NFA等价的DFA不唯一。

在有穷自动机的理论里，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。我们不对定理进行证明，只介绍一种算法（这

第4章 词法分析

种算法称为子集法），将NFA转换成接受同样的语言的DFA。

为什麽对DFA如此亲睐呢？因为它的行为很容易用程序来模拟。 DFA M=（K，Σ，f，S，Z）的行为的模拟程序

K:=S； c:=getchar;

while c<>eof do {K:=f(K,c); c:=getchar; };

if K is in Z then return (‘yes’) else return (‘no’)

从NFA的矩阵表示中可以看出，表项通常是一个状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本想法是该DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态。也就是说，在读入输入符号串a1a2…an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，T是从NFA的开始状态沿着某个标记为a1a2…an的路径可以到达的那些状态。

为介绍算法首先定义对状态集合I的几个有关运算：

1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。

回顾在前面章节对转换函数的扩充：如输入字符是空串，则自动机仍停留在原来的状态上，显然，状态集合I的任何状态S都属于ε-closure(I)。

2. 状态集合I的a弧转换，表示为move(I,a)，定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。

我们使用图4.4的NFA N的状态集合来理解上述两个运算。

图 4.4 NFA N

ε-closure(0)=｛0，1，2，4，7｝

即｛0，1，2，4，7｝中的任一状态都是从状态0经任意条ε弧可到达的状态，令｛0，1，2，4，7｝=A，则 move(A,a)=｛3，8｝，因为在状态0，1，2，4和7中，只有状态2

第4章 词法分析

和7有a弧射出，分别到达状态3和8。

而ε-closure(｛3，8｝)=｛1，2，3，4，6，7，8｝。

再看一个例子，对下图所示NFA的状态集合I的运算

图 4.5

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}；

NFA确定化算法：假设NFA N=(K, ∑,f,K0,Kt)按如下办法构造一个DFA M=(S, ∑,d,S0,St)，使得L(M)=L(N)：

① M的状态集S由K的一些子集组成（k的子集构造算法见下页）。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的状态。并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]； ② M和N的输入字母表是相同的，即是∑； ③ 转换函数是这样定义的：

d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = e-closure(move({S1, S2,,... Sj},a)) ④ S0=e-closure(K0)为M的开始状态；

⑤ St={[Si Sk... Se]，其中[Si Sk... Se]∈S且{Si , Sk,,... Se}∩Kt≠φ}

构造NFA N的状态K的子集的算法：

假定所构造的子集族为C，即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 ① 开始，令e-closure(K0)为C中唯一成员，并且它是未被标记的。 ② while （C中存在尚未被标记的子集T）do { 标记T；

for 每个输入字母a do {

U:= e-closure(move(T,a))； if U不在C中 then

将U作为未标记的子集加在C中 } }

例 4.3 应用左面的算法对图4.4的NFA N构造子集，步骤如下：

① 首先计算ε-closure(0)，令T0=ε-closure(0)={0，1，2，4，7}，T0未被标记，它现在是子集族C的唯一成员。

② 标记T0；令T1=ε-closure(move(T0,a))={1，2，3，4，6，7，8}，将T1加入C中，

第4章 词法分析

T1未被标记。

令T2=ε-closure(move (T,b))={1，2，4，5，6，7}，将T2加入C中，它未被标记。 ③ 标记T1；计算ε-closure(move(T1,a))，结果为{1，2，3，4，6，7，8}，即T1，T1已在C中。

计算ε-closure(move(T1,b))，结果为{1，2，4，5，6，7，9}，令其为T3，T3加至C中，它未被标记。

④ 标记T2，计算ε-closure(move(T2,a))，结果为{1，2，3，4，6，7，8}，即T1，T1已在C中。

计算ε-closure(move(T2,b))，结果为{1，2，4，5，6，7}，即T2，T2已在C中。 ⑤ 标记T3，计算ε-closure(move(T3,a))，结果为{1，2，3，4，6，7，8}，即T1。 计算ε-closure(move(T3,b))，结果为{1，2，4，5，6，7，10}，令其为T4，加入C中，T4未被标记。

⑦ 标记T4，计算ε-closure(move(T4,a))，结果为{1，2，3，4，6，7，8}，即T1 计算ε-closure(move(T4,b))结果为{1，2，4，5，6，7}，即T2。 至此，算法终止共构造了五个子集：

T0={0，1，2，4，7} T1={1，2，3，4，6，7，8} T2={1，2，4，5，6，7} T3={1，2，4，5，6，7，9} T4={1，2，4，5，6，7，10}

那么图4.4的NFA N构造的DFA M为 ① S={[T0]，[T1]，[T2]，[T3]，[T4]} ② Σ={a,b}

③ D([T0]，a)=[T1] D([T2]，a)=[T1] D([T0]，b)=[T2] D([T2]，b)=[T2] D([T1]，a)=[T1] D([T3]，a)=[T1] D([T1]，b)=[T3] D([T3]，b)=[T4] D([T4],a)=[T1] D([T4]，b)=[T2] ④ S0=[T0] ⑤ St=[T4]

不妨将[T0]，[T1]，[T2]，[T3]，[T4]重新命名，以利于书写，或用A，B，C，D，E或用0，1，2，3，4分别表示。若采用后者，该DFA M的状态转换图如图4.6所示。图 4.6

DFA MNFA确定化

又例：将下图的

第4章 词法分析

划分子集及重新命名：

{i,1,2} S {1,2,3} A {1,2,4} B {1,2,3,5,6,f} C {1,2,4,5,6,f} D {1,2,4,6,f} E {1,2,3,6,f} F

确定化后的自动机：

Ia {1,2,3} A {1,2,3,5,6,f} C {1,2,3} A {1,2,3,5,6,f} C {1,2,3,6,f} F {1,2,3,6,f} F {1,2,3,5,6,f} C Ib {1,2,4} B {1,2,4} B {1,2,4,5,6,f} D {1,2,4,6,f} E {1,2,4,5,6,f} D {1,2,4,5,6,f} D {1,2,4,6,f} E

4.3.4 确定有穷自动机的化简

我们说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两

第4章 词法分析

个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。

所谓有穷自动机的多余状态，是指这样的状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。例如图4.7(a)的有穷自动机M中的状态s4便是多余状态。 在有穷自动机中，两个状态s和t等价的条件是：

① 一致性条件 状态s和t必须同时为可接受状态或不可接受状态。

② 蔓延性条件 对于所有输入符号，状态s和状态t必须转换到等价的状态里。

如果有穷自动机的状态s和t不等价，则称这两个状态是可区别的。显然在图4.6的DFA M中，状态0和4是可区别的，因为状态4是可接受态(终态)，而0是不可接受态。又如状态2和3是可区别的，因为状态2读出b后到达2，状态3读出b后到达4，而2和4是不等价的。

图 4.7 消除多余状态

对于给定的有穷自动机，如果它含有多余状态，可以非常简单地将多余状态消除，而得到与它等价的有穷自动机，例如图4.7(a)的状态s4连同状态s4射出的两个弧消掉，得到如图4.7(b)的有穷自动机。而在图4.7(b)中，状态s6和s8也是不能从开始状态经由任何输入串而到达的，也将它们连同由它们射出的弧消除而得到如图4.7(c)的有穷自动机。 确定有穷自动机的化简就是指DFA的最小化，也就是寻求最小状态DFA 简言之，最小状态DFA满足： 没有多余状态（死状态）

没有两个状态是互相等价（不可区别）

下图的DFA中，没有多余状态。考察状态C和D，首先C和D同是终态，其次在读入a后分别到达C和F，而C和F也同是终态，C和F读入a后都到达C，读入b后都到达E，所以C和D等价。

确定有穷自动机的化简方法有很多，我们介绍一个方法，叫做\"分割法\"：把一个DFA(不含多余状态)的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。通过将此方法施于图4.8的DFA M上来做一介绍。

DFA的最小化

第4章 词法分析

对于一个DFA M =（K,∑,f, k0,,kt)，存在一个最小状态DFA M’=（K’,∑,f’,k0’,kt’)，,使L(M’)=L(M). 算法的核心

把M的状态集K分成不相交的子集。

结论：接受L的最小状态有穷自动机不计同构是唯一的。

DFA的最小化算法 f4-3-2.swf

过程PP：构造∏new

① 对∏每一个状态组G进行下述工作：

将G划分为子组。G的两个状态s和t分在同一子组的充要条件是：对所有的输入符号a，状态s和t的a转换都是∏的同一组中的状态。 ②形成的所有子组成为∏new的状态组。

图4.8 DFA M和DFA M'

第4章 词法分析

例 4.4 将图4.8中的DFA M最小化。

首先将M的状态分成两个子集：一个由终态(可接受态)组成，一个由非终态组成，这个初始划分P0为：P0=({1，2，3，4}，{5，6，7})，显然第一个子集中的任何状态都与第二个子集中的任何状态不等价。

现在观察第一个子集{1，2，3，4}，在读入输入符号a后，状态3和4分别转换为第一个子集中所含的状态1和4，而1和2分别转换为第二个子集中所含的状态6和7，这就意味着{1，2}中的状态和{3，4}中的任何状态在读入a后到达了不等价的状态，因此{1，2}中的任何状态与{3，4}中的任何状态都是可区别的，因此得到了新的划分P1如下： P1=({1，2}{3，4}{5，6，7})

下面试图在P1中寻找一个子集和一个输入符号使得这个子集中的状态可区别，P1中的子集{3，4}对应输入符号a将再分割，而得到划分P2=({1，2}，{3}，{4}，{5，6，7})。 P2中的{5，6，7}可由输入符号a或b而分割，得到划分P3=({1，2}，{3}，{4}，{5}，{6，7})。

经过考察，P3不能再划分了。令1代表{1，2}消去2，令6代表{6，7}，消去7，我们便得到了图4.8(b)的DFA M′，它是4.8(a)的DFA M的最小化。

比起原来的有穷自动机，化简了的有穷自动机具有较少的状态，因而在计算机上实现起来将简洁些。

DFA的最小化—例子

4.4词法分析程序的自动构造

对有穷自动机和正规表达式进行了上述讨论之后，我们介绍词法分析程序的自动构造方法，这个方法基于有穷自动机和正规表达式的等价性，即：

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

下面介绍从Σ上的一个正规式R构造Σ上的一个NFA M，使得L(M)=L(R)的方法。 我们所介绍的方法称为\"语法制导\"的方法，即按正规式的语法结构指引构造过程，首

第4章 词法分析

先将正规式分解成一系列子表达式，然后使用如下规则为R构造NFA，对R的各种语法结构的构造规则具体描述如下：

①(a)对于正规式 ，所构造的NFA为：

(b) 对于正规式ε，所构造的NFA为：

(c) 对于正规式a，a∈Σ，所构造的NFA为：

② 若s，t为Σ上的正规式，相应的NFA分别为N(s)和N(t),则 (a) 对正规式R=s|t，所构造的NFA(R)如下：

其中x是NFA(R)的初态，y是NFA(R)的终态，x到N(s)和N(t)的初态各有一ε弧，从N(s)和N(t)的终态各有一ε弧到y，现在N(s)和N(t)的初态或终态已不作为N(R)的初态和终态了。

(b) 对正规式R=st，所构造的NFA(R)为：

其中N(s)的初态成了N(R)的初态，N(t)的终态成了N(R)的终态。N(s)的终态与N(t)的

第4章 词法分析

初态合并为N(R)的一个既不是初态也不是终态的状态。 (c) 对于正规式R=S*，NFA(R)为：

这里x和y分别是NFA(R)的初态和终态，从x引ε弧到N(s)的初态，从N(s)的终态引ε弧到y，从x到y引ε弧，同样N(s)的终态可沿ε弧的边直接回到N(s)的初态。N(s)的初态或终态不再是N(s)的初态和终态。

(d) 正规式(s)的NFA同s的NFA一样。

例4.5

为R=(a|b)abb构造NFA N，使得L(N)=L(R)。 从左到右分解R，令r1=a，第一个a，则有：

令r2=b，则有：

令r3=r1|r21，则有：

令r4=r3'，则有：

令r5=a， 令r6=b， 令r7=b，

〖TPBYP623,+12mm。101mm,Y,PZ#〗

第4章 词法分析

令r8=r5r6，

令r9=r8r7，则有：

令r10=r4r9，则最终得到图4.4的NFA N即为所求。

其实，分解R的方式很多，用图4.10(a)(b)(c)(d)分别表明另一种分解方式和所构造的NFA。

图 4.10 从正规式R构造NFA

我们再用较形式的方法说明对于∑上的一个正规式R，可以构造一个∑上的NFA M， 使得L(M)=L(R)。

① R=φ，构造任一具有空终态集的NFA M

② R=ε，构造的NFA M=({k0}, ∑,f,k0,{k0}),其中 f（k0,a）对于所有a∈∑都没定义。 ③ R=a，a∈∑，构造的NFA M=({k0,,k1},∑,f,k0.{k1})，其中 f(k0,a) = k1 ④ R=R1 | R2，将步骤（1）（2）（3）分别应用到R1,R2 产生M1= =(K1,∑,f1,k1,F1), M2=(K2,∑,f2,k2,F2),其中K1,K2不相交。构造的NFA M= (K1∪K2∪{k},∑,f,k,F)，k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)∪f2(k2,a)。若k1F1且k2F2则 F=F1∪F2，否则F=F1∪ F2 ∪{k}

⑤ R=R1.R2 将步骤（1）（2）（3）分别应用到R1,R2 产生M1==(K1,∑,f1,k1,F1)，M2=(K2,∑,f2,k2,F2)，其中K1,K2不相交。构造的NFA M= (K1∪K2,∑,f,k1,F2),令k=(K1∪K2，f包含f1和f2，且

第4章 词法分析

f(k,a)=f1(k,a),当 kF1时； f(k,a)=f2(k,a),当 k∈K2时； f(k1,e)=k2 ⑥ R=R1* 将步骤（1）（2）（3）分别应用到R1,产生M1==(K1,∑,f1,k1,F1)，

构造的NFA M= (K1∪{k0,F0} ,∑,f,k0,F0)其中 k0,F0 是新增加的两个状态，令k= K1∪{k0,F0}

f(k,a)=f1(k,a),当 kF1时; f(k0,ε)=f(F1 ,ε)= {k1,,F0}

我们已经看到，正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序的工具很多。我们以LEX为例介绍如何从正规式产生识别该正规式所描述的单词的词法分析程序。

LEX是一个广泛使用的词法分析程序的自动构造工具，UNIX系统中使用lex命令调用。它用于构造各种各样语言的词法分析程序。我们称这个工具为LEX编译系统，它的源语言称为LEX语言，LEX编译程序的作用如图4.13所示。

图4.13表明，LEX编译系统(在不致引起混淆的情况下，称为LEX)，读入LEX语言的程序(该程序是对一个词法分析程序的说明或描述)，产生一个词法分析程序。在UNIX环境中，Lex.l为LEX的源程序，Lex.yy.c为LEX的目标程序，Lex.yy.c是一个C程序，它包括从正规式构造的表格形式表示的转换图，以及使用该表格识别单词的标准子程序。在Lex.l中有一些C代码段，它们是与正规式相联系的动作，比如登录名字表等，是词法分析程序需要执行的动作。

Lex.yy.c程序经由C编译生成目标文件a.out，这是词法分析程序，它可以将输入字符流变换成单词流。使用LEX生成词法分析程序的过程如图4.14所示。

图 4.13LEX编译系统的作用

图 4.14 使用LEX生成词法分析器

LEX编译系统的源语言LEX语言介绍

LEX程序由三部分组成：说明部分；转换规则和辅助过程，用%%做间隔符。格式为： 说明部分 ％％ 转换规则

第4章 词法分析

％％ 辅助过程

说明部分包括变量的说明、常量说明和正规定义，所谓正规定义是形式如下的一系列定义： d1→r1 d2→r2 … dn→rn

其中Σ是基本字母表，每个di是不同的名字，每个ri是在Σ∪{d1，d2，…,di-1}上的正规式，即基本字母表和前面定义的名字。正规定义的di用做转换规则中出现的正规表达式的成分使用。有些LEX实现版本并不需要\"→\"(参看图4.15)。 转换规则是如下形式的语句： P1 {action 1} P2 {action 2} …… Pn {action n}

其中每个Pi是一个正规式，是Σ∪{d1，d2，…，dn}上的正规式；每个action i是一段C程序代码，当然，一般应是任何实现语言的代码段。它指出在识别出Pi所描述的单词之后，词法分析器所应采取的动作。

第三部分容纳的是action所需要的辅助过程，这些过程可以分别编译并置于词法分析器中。

图4.15给出一个识别PL/0单词的LEX程序片断。从这个例子可以看出LEX程序的架构。关于LEX的详解，请参看附录B。

图 4.15 LEX程序例子--识别PL/0单词的LEX程序

IDENT[a-zA-Z] [a-zA-Z0-9]* NUMBER[0-9] [0-9]* %(

#include 〈stdio.h〉 #include \"code.h\" #include \"symbol.h\" #include \"y.tab.h\" extern int level; int cc=0; %) %%

\"\" { cc++;}

\"＼t\" { tablize(); } /*adjustcc to tabposition*/

\"＼n\" { cc=0; line-copy(); } /*copy a line of input file*/ \"<\" { cc++; return LT;} \">\" { cc++; return GT;} \"=\" { cc++; return EQ;} \"#\" { cc++; return NE;} \

第4章 词法分析

\".\" { cc++; return Period;} \"(\" { cc++; return Lparen;} \")\" { cc++; return Rparen;} \"<=\" { cc++;cc++;return LE;} \">=\" { cc++;cc++;return GE;}

\"∶=\" { cc++; cc++;return ASGN;} \";\" { cc++; return Semicolon;} {NUMBER} { intn;

cc += yyleng;

sscanf(yytext,\"%d\ yylval.number=n; return NUMBER; } {IDENT} {

Symbol *s; cc += yyleng;

if((s=lookup(yytext))==0) /*new identifier*/

s=install(yytext,VARIABLE,level,0); /* install symbol*/ if (s→type==C)

yylval.number=s-〉adr;

else /*it's a VARIABLE or PROC*/ yylval.sym=s; return s-〉type; } %%

yywrap( ) { };

第4章 词法分析

本章小结

【本章小结】

词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。

本章讲述了词法分析程序设计原则，并介绍了正规式和有穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如LEX的原理。

词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。

词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。

第4章 词法分析

课后习题

第4章习题

第1题

构造正规式1(0|1)

第2题

将下图确定化：

*101相应的DFA.

第3题

将下图的（a）和（b）分别确定化和最小化：

第4题

构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。

第4章 词法分析

问答题答案 问答第1题

解：先构造NFA：

用子集法将NFA确定化

. X A AB AC ABY 0 . A AC A AC 1 A AB AB ABY AB

除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。

. X A B C D DFA的状态图：:

0 . A C A C 1 A B B D B

问答第2题 解：

用子集法将NFA确定化：

. S VQ QU VZ 0 VQ VZ V Z 1 QU QU QUZ Z 第4章 词法分析

V QUZ Z Z VZ Z . QUZ Z

重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。

. S A B C D E F DFA的状态图：

0 A C D F F C F 1 B B E F . E F

问答第3题 解：

初始分划得

Π0：终态组{0}，非终态组{1,2,3,4,5} 对非终态组进行审查：

{1,2,3,4,5}a {0,1,3,5}

而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得到新分划 Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查：

∵{1,5} b {4}

{2,3} b {1,2,3,5}，故得到新分划 Π2：{0}，{4}，{1, 5}，{2,3}

{1, 5} a {1, 5}

{2,3} a {1,3}，故状态2和状态3不等价，得到新分划 Π3：{0}，{2}，{3}，{4}，{1, 5}

第4章 词法分析

这是最后分划了 最小DFA：

问答第4题

解：按题意相应的正规表达式是(0*10)*0*，或0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为

用子集法确定化：

I {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y}

重新命名状态集：

S 1 2 3 4 DFA的状态图：

0 2 2 4 4 1 3 3 3 I0 {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} I1 {2} {2} {2}

第4章 词法分析

可将该DFA最小化：

终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，{1,2,4}1 {3}，所以1,2,4为等价状态，可合并。

第5章 自顶向下语法分析方法

第5章 自顶向下语法分析方法