第2章 词法分析

词法的(lex-i-cal):与语言的单词或词汇有关,但有别于语言的文法和结构。

韦氏词典

为了将一个程序从一种语言翻译成另一种语言,编译器必须首先把程序的各种成分拆开,并搞清其结构和含义,然后再用另一种方式把这些成分组合起来。编译器的前端执行分析,后端进行合成。

分析一般分为以下3种。

●词法分析:将输入分解成一个个独立的词法符号,即“单词符号”(token),简称单词①。

●语法分析:分析程序的短语结构。

●语义分析:推算程序的含义。

词法分析器以字符流作为输入,生成一系列的名字、关键字和标点符号,同时抛弃单词之间的空白符和注释。程序中每个地方都有可能出现空白符和注释,如果让语法分析器来处理它们就会使得语法分析过于复杂,这便是将词法分析从语法分析中分离出去的主要原因。

词法分析并不太复杂,但是我们却使用能力强大的形式化方法和工具来实现它,因为类似的形式化方法对语法分析研究很有帮助,并且类似的工具还可以应用于编译器以外的其他领域。

2.1 词法单词

词法单词是字符组成的序列,可以将其看作程序设计语言的文法单位。程序设计语言的词法单词可以归类为有限的几组单词类型。例如,典型程序设计语言的一些单词类型为:

图像说明文字

IF、VOID、RETURN 等由字母字符组成的单词称为保留字(reservedword),在多数语言中,它们不能作为标识符使用。

①“token”一词在不少书中翻译成“记号”,我们认为比较贴切的翻译应当是“单词符号”。它是程序设计语言 中“具有独立含义的最小词法单位”,在这个意义上与自然语言中的“单词”的词义相同。但是,它们又不完全相同,因为这里的“token”不仅仅包括“词”,还包括标点符号、操作符、分隔符等。将它翻译成“单词符号”正是为了体现这一点。但为了简洁起见,我们使用“单词”一词。———译者注

非单词的例子是:

图像说明文字

在能力较弱而需要宏预处理器的语言中,由预处理器处理源程序的字符流,并生成另外的字符流,然后由词法分析器读入这个新产生的字符流。这种宏处理过程也可以与词法分析集成到一起。

对于下面一段程序:

图像说明文字

词法分析器将返回下列单词流:

图像说明文字

其中报告了每个单词的单词类型。这些单词中的一些(如标识符和字面量)有语义值与之相连,因此,词法分析器还给出了除单词类型之外的附加信息。

应当如何描述程序设计语言的词法规则? 词法分析器又应当用什么样的语言来编写呢?

我们可以用自然语言来描述一种语言的词法单词。例如,下面是对C或Java中标识符的一种描述:

标识符是字母和数字组成的序列, 第一个字符必须是字母。下划线“_”视为字母。大小写字母不同。如果经过若干单词分析后输入流已到达一个给定的字符,则下一个单词将由有可能组成一个单词的最长字符串所组成。其中的空格符、制表符、换行符和注释都将被忽略,除非它们作为独立的一类单词。另外需要有某种空白符①来分隔相邻的标识符、关键字和常数。

任何合理的程序设计语言都可以用来实现特定的词法分析器。我们将用正则表达式的形式语言来指明词法单词,用确定的有限自动机来实现词法分析器,并用数学的方法将两者联系起来。这样将得到一个简单且可读性更好的词法分析器。

2.2 正则表达式

我们说语言(language)是字符串组成的集合,字符串是符号(symbol)的有限序列。符号本身来自有限字母表(alphabet)。

① 注意,“空白符”是空格符、制表符、换行符等的统称。———译者注

Pascal语言是所有组成合法Pascal程序的字符串的集合,素数语言是构成素数的所有十进制数字字符串的集合,C语言保留字是C程序设计语言中不能作为标识符使用的所有字母数字字符串组成的集合。这3种语言中,前两种是无限集合,后一种是有限集合。在这3种语言中,字母表都是ASCII字符集。

以这种方式谈论语言时,我们并没有给其中的字符串赋予任何含义,而只是企图确定每个字符串是否属于其语言。

为了用有限的描述来指明这类(很可能是无限的)语言,我们将使用正则表达式(regularexpression)表示法。每个正则表达式代表一个字符串集合。

●符号(symbol):对于语言字母表中的每个符号a,正则表达式a表示仅包含字符串a的语言。

●可选(alternation):对于给定的两个正则表达式M 和N,可选操作符(|)形成一个新的正则表达M |N。如果一个字符串属于语言M 或者语言N,则它属于语言M |N。因此,a|b组成的语言包含a和b这两个字符串。

●联结(concatenation):对于给定的两个正则表达式M 和N,联结操作符(•)形成一个新的正则表达式M •N。如果一个字符串是任意两个字符串α和β的联结,且α属于语言M ,β属于语言N,则该字符串属于M •N 组成的语言。因此,正则表达式(a|b)•a定义了包含两个字符串aa和ba的语言。

●∈(epsilon):正则表达式表示仅含一个空字符串的语言。因此,(a•b)| 表示语言{ "","ab"}。

●重复(repetition):对于给定的正则表达式M ,它的克林闭包(Kleeneclosure)是图像说明文字。如果一个字符串是由图像说明文字中的字符串经零至多次联结运算的结果,则该字符串属于M 。因此,((a|b)•a) *表示无穷集合{"","aa","ba","aaaa","baaa","aaba","baba","aaaaaa",…}。

通过使用符号、可选、联结、∈和克林闭包,我们可以规定与程序设计语言词法单词相对应的ASCII字符集。首先,考虑若干例子:

图像说明文字

在书写正则表达式时,我们有时会省略联结操作符或∈符号,并假定克林闭包的优先级高于联结运算,联结运算的优先级高于可选运算,所以ab|c表示(a•b)|c,而(a|)表示(a|∈)。

还有一些更为简洁的缩写形式:[abcd]表示(a|b|c|d),[b-g]表示[bcdefg],[b-gM-Qkr]表示[bcdefgMNOPQkr],M ? 表示(M |∈),M + 表示(M •M*)。这些扩充很方便,但它们并没有扩充正则表达式的描述能力:任何可以用这些简写形式描述的字符串集合都可以用基本操作符集合来描述。图2-1概括了所有这些操作符。

使用这种语言,我们便可以指明程序设计语言的词法单词(见图2-2)。对于每一个单词,我们提供一段C 代码,报告识别的是哪种单词类型。

图像说明文字

图2-2第5行的描述虽然识别注释或空白,但是不提交给语法分析器,而是忽略它们并重新开始词法分析。这个分析器识别的注释以两个短横线开始,且只包含字母字符,并以换行符结束。

最后,词法规范应当是完整的,它应当总是能与输入中的某些初始子串相匹配;使用一个可与任意单个字符相匹配的规则,我们便总能做到这一点(在这种情况下,将打印出“illegalcharacter”错误信息,然后再继续进行)。

图2-2中的规则存在着二义性。例如,对于if8,应当将它看成一个标识符,还是两个单词if和8? 字符串if89是以一个标识符开头还是以一个保留字开头? Lex和其他类似的词法分析器使用了两条消除二义性的重要规则。

●最长匹配:初始输入子串中,取可与任何正则表达式匹配的那个最长的字符串作为下一个单词。

●规则优先:对于一个特定的最长初始子串,第一个与之匹配的正则表达式决定了这个子

串的单词类型。也就是说,正则表达式规则的书写顺序有意义。因此,依据最长匹配规则,if8是一个标识符;根据规则优先,if是一个保留字。

2.3 有限自动机

用正则表达式可以很方便地指明词法单词,但我们还需要一种用计算机程序来实现的形式化方法。可以使用有限自动机达到此目的。有限自动机有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号;其中一个状态是初态,某些状态是终态。

图2-3给出了一些有限自动机的例子。为了方便讨论,我们给每个状态一个编号。每个例子中的初态都是编号为1的状态。标有多个字符的边是多条平行边的缩写形式;因此,在机器ID 中,实际上有26条边从状态1通向状态2,每条边用不同的字母标记。

图像说明文字

在确定的有限自动机(DFA)中,不会有从同一状态出发的两条边标记为相同的符号。DFA 以如下方式接收或拒绝一个字符串:从初始状态出发,对于输入字符串中的每个字符,自动机都将沿着一条确定的边到达另一状态,这条边必须是标有输入字符的边。对n 个字符的字符串进行了n 次状态转换后,如果自动机到达了终态,自动机将接收该字符串。若到达的不是终态,或者找不到与输入字符相匹配的边,那么自动机将拒绝接收这个字符串。由一个自动机识别的语言是该自动机接收的字符串集合。

例如,显然,在由自动机ID 识别的语言中,任何字符串都必须以字母开头。任何单字母都能通至状态2,因此单字母字符串是可被接收的字符串。从状态2出发,任何字母和数字都将重新回到状态2,因此一个后跟任意个数字母和数字的字母也将被接收。

事实上,图2-3所示的自动机接收的语言与图2-2给出的正则表达式相同。

图2-3中是6个独立的自动机,如何将它们合并为一个可作为词法分析器的自动机呢? 我们将在下一章学习合并它们的形式方法;在这里只给出合并它们后得到的机器,如图2-4所示。机器中的每个终态都必须标明它所接收的单词类型。在这个自动机中,状态2是自动机IF 的状态2和自动机ID 的状态2的合并;由于状态2是自动机ID 的终态,因此这个合并的状态也必须是终态。状态3与自动机IF的状态3和自动机ID 的状态2相同,因为这两者都是终态,故我们使用消除二义性的规则优先原则将状态3的接收单词类型标为IF。之所以使用规则优先原则是因为我们希望这一单词被识别为保留字,而不是标识符。

这个自动机可用一个转换矩阵来表示。转换矩阵是一个二维数组(一个元素为向量的向量),数组的下标是状态编号和输入字符。其中有一个停滞状态(状态0),这个状态对于任何输入字符都返回到自身,我们用它来表示不存在的边。

图像说明文字 图像说明文字

另外还需要有一个“终结”(finality)数组,它的作用是将状态编号映射至动作。例如,终态2映射到动作ID,等等。

图像说明文字

识别最长的匹配

很容易看出如何使用转换矩阵来识别一个字符串是否会被接收,但是词法分析器的任务是要找到最长的匹配,因为输入中最长的初始子串才是合法的单词。在进行转换的过程中,词法分析器要一直追踪迄今见到的最长匹配以及这个最长匹配的位置。

追踪最长匹配意味着需要用变量Last-Final (最近遇到的终态的编号)和Input-Position-at-Last-Final来记住自动机最后一次处于终态时的时机。每次进入一个终态时,词法分析器都要更新这两个变量;当到达停滞状态(无出口转换的非终态状态)时,从这两个变量便能得知所匹配的单词和它的结束位置。

图2-5说明了词法分析器识别最长匹配的操作过程。注意,当前输入位置可能相距识别器最近到达终态时的位置已很远。

2.4 非确定有限自动机

非确定有限自动机(NFA)是一种需要对从一个状态出发的多条标有相同符号的边进行选择的自动机。它也可能存在标有∈(希腊字母)的边,这种边可以在不接收输入字符的情况下进行状态转换。

下面是一个NFA 的例子:

图像说明文字

图像说明文字

在初态时,根据输入字母a,自动机既可向左转换,也可向右转换。若选择了向左转换,则接收的是长度为3的倍数的字符串;若选择了向右转换,则接收的是长度为偶数的字符串。因此,这个NFA 识别的语言是长度为2的倍数或3的倍数的所有由字母a组成的字符串的集合。

在第一次转换时,这个自动机必须选择走哪条路。如果存在着任何导致该字符串被接收的可选择路径,那么自动机就必须接收该字符串。因此,自动机必须进行“猜测”,并且必须总是做出正确的猜测。

标有∈的边可以不使用输入中的字符。下面是接收同样语言的另一个NFA:

图像说明文字

同样地,这个自动机必须决定选取哪一条边。若存在一个状态既有一些边,又有一些标有符号的边,则自动机可以选择接收一个输入符号(并沿着标有对应符号的边前进),或者选择沿着边前进。

2.4.1 将正则表达式转换为NFA

非确定的自动机是一个很有用的概念,因为它很容易将一个(静态的、说明性的)正则表达式转换成一个(可模拟的、准可执行的)NFA。

转换算法可以将任何一个正则表达式转换为有一个尾巴和一个脑袋的NFA①。它的尾巴即开始边,简称为尾;脑袋即末端状态,简称为头。例如,单个符号的正则表达式a转换成的NFA 为:

图像说明文字

① 就像一只蝌蚪。———译者注

由a和b经联结运算而形成的正则表达式ab对应的NFA 是由两个NFA 组合而成的,即将a的头与b的尾连接起来。由此得到的自动机有一个用a标记的尾和一个从b边进入的头。

图像说明文字

一般而言,任何一个正则表达式M 都有一个具有尾和头的NFA:

图像说明文字

我们可以归纳地定义正则表达式到NFA 的转换。一个正则表达式或者是原语(单个符号或∈),或者是由多个较小的表达式组合而成。类似地,NFA 或者是基本元素,或者是由多个较小的NFA 组合而成。

图2-6展示了将正则表达式转换至NFA 的规则。我们用图2-2中关于单词IF、ID、NUM以及error的一些表达式来举例说明这种转换算法。每个表达式都转换成了一个NFA,每个NFA 的头是用不同单词类型标记的终态结点,并且每一个表达式的尾汇合成一个新的初始结点。由此得到的结果(在合并了某些等价的NFA 状态之后)如图2-7所示。

图像说明文字

2.4.2 将NFA 转换为DFA

如在2.3节看到的,用计算机程序实现确定的有限自动机(DFA)较容易。但实现NFA 则要困难一些,因为大多数计算机都没有足够好的可以进行“猜测”的硬件。

通过一次同时尝试所有可能的路径,可以避免这种猜测。我们用字符串in来模拟图2-7的NFA。首先从状态1开始。现在,替代猜测应采用哪个转换,我们只是说此时NFA 可能选择它们中的任何一个,因此,它是状态{1,4,9,14}当中的任何一个,即我们需要计算{1}的∈闭包。显然,不接收输入中的第一个字符,就不可能到达其他状态。

现在要根据字符i来进行转换。从状态1可以到达状态2,从状态4可到达状态5,从状态9则无处可去,而从状态14则可以到达状态15,由此得到状态集合{2,5,15}。但是,我们还必须计算闭包:从状态5有一个∈转换至状态8,从状态8有一个转换至状态6。因此这个NFA一定属于状态集合{2,5,6,8,15}。

对于下一个输入字符n,我们从状态6可到达状态7,但状态2、5、8和15都无相应的转换。因此得到状态集合{7},它的∈闭包是{6,7,8}。

现在我们已到达字符串in的末尾,那么,这个NFA 是否已到达了终态呢? 在我们得到的可能状态集合中,状态8是终态,因此in是一个ID 单词。

我们形式化地定义∈闭包如下。令edge(s,c)是从状态s 沿着标有c 的一条边可到达的所有NFA 状态的集合。对于状态集合S,closure(S)是从S 中的状态出发,无需接收任何字符,即只通过边便可到达的状态组成的集合。这种经过∈边的概念可用数学方式表述,即closure(S)是满足如下条件的最小集合T:

图像说明文字

我们可用迭代法来算出T:

图像说明文字

这个算法为什么是正确的? 因为T 只可能在迭代中扩大,所以最终的T 一定包含S。如果在一次迭代之后有T=T曚,则T 也一定包含图像说明文字。因为在NFA 中只有有限个不同的状态,所以算法一定会终止。

现在,当用前面描述的方法来模拟一个NFA 时,假设我们位于由NFA 状态Si、Sk 、Sl 组成的集合d={Si,Sk ,Sl}中。从d 中的状态出发,并吃进输入符号c,将到达NFA 的一个新的状态集合;我们称这个集合为DFAedge(d,c):

图像说明文字

利用DFAedge能够更形式化地写出NFA 模拟算法。如果NFA 的初态是S1,输入字符串中的字符是c1,…,ck ,则算法为:

图像说明文字

状态集合运算是代价很高的运算———对进行词法分析的源程序中的每一个字符都做这种运算几乎是不现实的。但是,预先计算出所有的状态集合却是有可能的。我们可以由NFA 构造一个DFA,使得NFA 的每一个状态集合都对应于DFA 的一个状态。因为NFA 的状态个数有限(n 个),所以这个DFA 的状态个数也是有限的(至多为2π 个)。

一旦有了closure 和DFAedge 的算法, 就很容易构造出DFA。DFA 的状态d1 就是closure(S1),这同NFA 模拟算法一样。抽象而言,如果dj=DFAedge(di,c),则存在着一条从di到dj的标记为c 的边。令∑是字母表。

图像说明文字

这个算法不访问DFA 的不可到达状态。这一点特别重要,因为原则上DFA 有2π 个状态,但实际上一般只能找到约n 个状态是从初态可到达的。这一点对避免DFA 解释器的转换表出现指数级的膨胀很重要,因为这个转换表是编译器的一部分。

只要states[d]中有任何状态是其NFA 中的终态,状态d 就是DFA 的终态。仅仅标志一个状态为终态是不够的,我们还必须告知它识别的是什么单词,并且states[d]中还可能有多个状态是这个NFA 的终态。在这种情况下,我们用一个适当的单词类型来标识d,这个适当的单词类型即组成词法规则的正则表达式表中最先出现的那个单词类型。这就是规则优先的实现方法。

构造了DFA 之后便可以删除“状态”数组,只保留“转换”数组用于词法分析。

对图2-7的NFA 应用这个DFA 构造算法得到了图2-8给出的自动机。

这个自动机还不是最理想的,也就是说,它不是识别相同语言的最小自动机。一般而言,我们称两个状态s1和s2是等价的,如果开始于s1的机器接收字符串σ,则它从状态s2开始也一定接收σ,反之亦然。图2-8中,标为[5,6,8,15]的状态和标为[6,7,8]的状态等价,标为[10,11,13,15]的状态与标为[11,12,13]的状态等价。若自动机存在两个等价状态s1和s2,则我们可以使得所有进入s2的边都指向s1而删除s2。

图像说明文字

那么,如何才能找出所有等价的状态呢? 若s1和s2同为终态或同为非终态,且对于任意符号c,trans[s1,c]=trans[s2,c],则显然它们两者等价。容易看出[10,11,13,15]和[11,12,13]满足这个判别条件。但是这个条件的普遍性还不够充分,考虑下面的自动机:

图像说明文字

其中状态2和4等价,但是trans[2,a]≠trans[4,a]。

在构造出一个DFA 后,用一个算法来找出它的等价状态,并将之最小化是很有好处的;见习题2.6。

2.5 Lex:词法分析器的生成器

构造DFA 是一种机械性的工作,很容易由计算机来实现,因此一种有意义的做法是,用词法分析器的自动生成器来将正则表达式转换为DFA。

Lex就是这样的一个词法分析器的生成器,它由词法规范生成一个C 程序。对于要进行分析的程序设计语言中的每一种单词类型,该规范包含一个正则表达式和一个动作。这个动作将单词类型(可能和其他信息一起)传给编译器的下一处理阶段。

Lex的输出是一个C 程序,即一个词法分析器。该分析器使用2.3节介绍的算法来解释DFA,并根据每一种匹配执行一段动作代码,这段动作代码是用于返回单词类型的C 语句。

图2-2描述的单词类型在Lex中的规范如程序2-1所示。

图像说明文字

该规范中的第一部分,即位于“%{”和“%}”之间的部分,包含有若干由此文件其余部分C 代码使用的include和声明。

这个规范的第二部分包含正则表达式的简写形式和状态说明。例如,在这一部分中的说明digits[0-9]+允许用名字{digits}代表正则表达式中非空的数字序列。第三部分包含正则表达式和动作。这些动作是一段原始的C 代码。每一个动作必须返回一个int类型的值,指出匹配的是哪一种单词。动作代码中可以使用几个特殊的变量。由正则表达式匹配的字符串是yytext,所匹配的字符串的长度是yyleng。

在这个特定的例子中,我们一直用变量charPos追踪着每一个单词的位置,此位置相对文件开始并以字符为单位。通过对宏ADJ的调用,错误信息模块errormsg.h中的变量EM_tokPos将持续不断地告知这个位置。语法分析器将使用这个信息报告语法错误。

这个例子中包含的文件tokens.h定义了IF、ID、NUM等整常数;这是一些由动作代码返回的值,它们指明被匹配的是何种类型的单词。

有一些单词关联有语义值。例如,ID 的语义值是组成标识符的字符串,NUM 的语义值是一个整数,而IF则没有语义值(因为每一个IF都有别于其他单词)。这些值经全局变量yylval传达给语法分析器,yylval是一个表示不同语义值的联合。Lex返回的单词类型告知语法分析器这个联合中的哪一个成员是有效成员。

开始状态

正则表达式是静态的和说明性的,自动机是动态的和命令式的;也就是说,你不必用一个算法来模拟就能看到正则表达式的成分和结构,但是理解自动机常常需要你在自己的头脑中来“执行”它。因此,正则表达式一般更适合于用来指明程序设计语言单词的词法结构。

有时候一步一步地模拟自动机的状态转换过程也是一种合适的做法。Lex有一种将状态和正则表达式混合到一起的机制。你可以声明一组初态,每个正则表达式的前面可以有一组对它而言是合法的初态作为其前缀。动作代码可以明显地改变初态。这相当于我们有这样的一种有限自动机,其边标记的不是符号而是正则表达式。下面的例子给出了一种只由简单标识符、单词if和以“ (”和“ )”作为界定符的注释所组成的语言。

图像说明文字

尽管有可能写出与整个注释相匹配的单个正则表达式,但是随着注释变得越来越复杂,特别是在允许注释嵌套的情况下,这种正则表达式也会越来越复杂,甚至变得不可能。与这个机器对应的Lex的规范为:

图像说明文字

其中INITIAL 是“任何注释之外”的状态。最后一个规则是一种调整,其用途是使得Lex进入此状态。任何不以(STATE)为前缀的正则表达式在所有状态中都能工作,这种特征很少有用处。

利用一个全局变量,并在语义动作中适当增减此全局变量的值,这个例子便很容易扩充成可处理嵌套的注释。

程序设计:词法分析

用Lex写出一个Tiger语言的词法分析器。附录中描述了Tiger的词法单词。本章未对词法分析器应当如何初始化以及它应当如何与编译器的其他部分通信作出说明。你可以从Lex使用手册中得到这些内容,而在图像说明文字TIGER/chap2目录中有一个最基本的介绍文件可帮助你入门。

你应当在连同tiger.lex文件一起提交的文档中描述清楚以下问题。

●你是怎样处理注释的。

●你是怎样处理字符串的。

●错误处理。

●文件结束处理。

●你的词法分析器的其他令人感兴趣的特征。

图像说明文字TIGER/chap2中有如下一些可用的支持文件。

●tokens.h,词法单词常数以及yylval的定义。

●errormsg.h、errormsg.c,报错信息模块,用于产生含文件名和行号的报错信息。

●driver.c,一个运行你的词法分析器来分析输入文件的测试平台。

●tiger.lex,tiger.lex文件的初始代码。

●makefile,编译所有文件的makefile文件。

在阅读附录(Tiger 语言参考手册) 时, 要特别注意以标识符(Identifier)、注释(Comment)、整型字面量(Integerliteral) 和字符串字面量(Stringliteral) 作为标题的段落。

Tiger语言的保留字是:while、for、to、break、let、in、end、function、var、type、array、if、then、else、do、of、nil。

Tiger语言使用的符号是:

图像说明文字

对于字符串字面量,你的词法分析器返回的字符串值应当包含所有已转换到其含义的转义字符。

没有负整型字面量。对于带负号的整型字面量,例如32,要返回两个单词。

目录图像说明文字TIGER/testcases中含有几个简单的Tiger程序实例。

开始时,首先创建一个目录,并复制图像说明文字TIGER/chap2中的内容到此目录。用Tiger语言编写一个小程序保存于文件test.tig中。然后,键入make;它将运行Lex读入tiger.lex并产生lex.yy.c,然后将lex.yy.c与其他C 文件一起进行编译。

最后lextesttest.tig将利用一个测试台对该文件进行词法分析。

推荐阅读

Lex是第一个基于正则表达式的词法分析器的生成器[Lesk1975],它现在仍被广泛使用。

将还未对其边进行过转换检查的状态保存在一个队列或栈中,可以更高效地计算∈闭包[Ahoetal.1986]。正则表达式可以直接转换成DFA 而不需经过NFA[McNaughtonandYamada1960;Ahoetal.1986]。

DFA 转换表可能非常大,而且很稀疏。若用一个二维矩阵(状态×符号) 来表示这张表,则会需要太多的存储空间。在实际中,这个表是经过压缩的。这样做减少了存储空间需求,但却增加了寻找下一状态需要的时间[Ahoetal.1986]。

词法分析器,无论是自动生成的还是手工书写的,都必须有效地处理其输入。当然,输入可以放在缓冲区中,从而一次可以获取成批的字符,然后词法分析器可以每次处理缓冲区中的一个字符。每次读取字符时,词法分析器都必须检查是否已到达缓冲区的末尾。通过在缓冲区末尾放置一个敏感标记(sentinel),即一个不属于任何单词的字符,词法分析器就有可能只对每个单词进行一次检查,而不是对每个字符都进行检查[Ahoetal.1986]。Gray[1988]使用的一种设计可以只需每行检查一次,而不是每个单词检查一次,但它不能适合那种包含行结束字符的单词。Bumbulis和Cowan[1993]的方法只需对DFA 中的每一次循环检查一次;当DFA 中存在很长的路径时,这可减少检查的次数(相对每个字符一次)。

自动生成的词法分析器常常受到速度太慢的批评。从原理上而言,有限自动机的操作非常简单,因而应该是高效的,但是通过转换表进行解释增加了开销。Gray[1988] 指出,直接将DFA 转换为可执行代码(将状态作为case语句来实现),其速度可以和手工编写的词法分析器一样快。例如,Flex(fastlexicalanalyzergenerator)[Paxson1995] 的速度就比Lex要快许多。

习题

2.1 写出下面每一种单词的正则表达式。

a.字母表{a,b,c} 上满足后面条件的字符串:首次出现的a 位于首次出现的b之前。

b.字母表{a,b,c}上由偶数个a 组成的字符串。

c.是4的倍数的二进制数。

d.大于101001的二进制数。

e.字母表{a,b,c}上不包含连续子串baa 的字符串。

f.C 语言中非负整常数组成的语言,其中以0开头的数是八进制常数,其他数是十进制常数。

g.使得方程an+ +bn =cn 存在着整数解的二进制整数n。

2.2 对于下列描述,试解释为什么不存在对应的正则表达式。

a.由a 和b 组成的字符串,其中a 的个数要多于b。

b.由a 和b 组成的回文字符串(顺读与倒读相同)。

c.语法上正确的C 程序。

2.3 用自然语言描述下述有限状态自动机识别的语言。

图像说明文字

2.4 将下面两个正则表达式转换为非确定的有限自动机。

图像说明文字

2.5 将下面的NFA 转换为确定的有限自动机。

图像说明文字

2.6 在下面这个自动机中找出两个等价的状态,并合并它们产生一个识别相同语言且较小的自动机。重复这个过程直到没有等价状态为止。

图像说明文字

实际上,最小化有限自动机的通用算法是以相反的思路来工作的。它首先要找出的是所有不等价的状态偶对。若X 是终结符而Y 不是,或者(通过迭代)图像说明文字但X'和Y'不等价,则状态X 和Y 不等价。用这种迭代方式寻找新的不等价状态偶对且由于没有更多的不等价状态而停止后,如果X、Y 仍不是不等价偶对,则它们就是等价状态。参见Hopcroft和Ullman[1979]中的定理3.10。

2.7 任何接收至少一个字符串的DFA 都能转换为一个正则表达式。将习题2.3c的DFA 转换为正则表达式。*提示:首先假装状态1是初态。然后,编写一个通到状态2并返回到状态1的正则表达式和一个类似的通到状态0并返回到状态1的正则表达式。或者查看Hopcroft和Ullman[1979]一书中定理2.4关于此算法的论述。

*2.8 假设Lex使用下面这个DFA 来寻找输入文件中的单词:

图像说明文字

a.Lex在匹配一个单词之前,必须在该单词之后再检测多少个字符?

b.设你对问题a的答案为k,写出一个至少包含两个单词的输入文件,使得Lex的第一次调用在返回第一个单词前需要检测该单词末尾之后的k 个字符。若对问题a的答案为0,则写出一个包含至少两个单词的输入文件,并指出每个单词的结束点。

2.9 一个基于DFA 的解释型词法分析器使用以下两张表。

●edges 以状态和输入符号为索引,产生一个状态号。

●final 以状态为索引,返回0或一个动作号。

从下面这个词法规范开始:

图像说明文字

为一个词法分析器生成edges和final表。

然后给出该词法分析器分析字符串abaabbaba的每一步。注意,一定要给出此词法分析器重要的内部变量的值。该词法分析器将被反复调用以获得后继的单词。

**2.10 词法分析器Lex有一个超前查看操作符“/”,它使得正则表达式abc/def只有在abc之后跟有def时,才能匹配abc (但是def并不是所匹配字符串的一部分,而是下一个或几个单词的一部分)。Aho等人[1986]描述了一种实现超前查看的错误算法,并且Lex[Lesk1975]中也使用了这种算法(对 于(a|ab)/ba,当输入为aba时,该算法不能进行正确的识别。它在应当匹配a的地方匹配了ab)。Flex[Paxson1995]使用了一种更好的机制,这种机制对于(a|ab/)ba能正确工作,但对zx* /xy*却不能(但能打印出警告信息)。

请设计出一种更好的超前查看机制。

目录

  • 译者序
  • 前言
  • 第一部分 编译基本原理
  • 第1章 绪论
  • 第2章 词法分析
  • 第3章 语法分析 
  • 第4章 抽象语法
  • 第5章 语义分析
  • 第6章 活动记录
  • 第7章 翻译成中间代码
  • 第8章 基本块和轨迹
  • 第9章 指令选择
  • 第10章 活跃分析
  • 第11章 寄存器分配
  • 第12章 整合为一体
  • 第13章 垃圾收集
  • 第14章 面向对象的语言
  • 第15章 函数式程序设计语言
  • 第16章 多态类型
  • 第17章 数据流分析
  • 第18章 循环优化
  • 第19章 静态单赋值形式
  • 第20章 流水和调度
  • 第21章 存储层次