本文最后更新于 208 天前,其中的信息可能已经有所发展或是发生改变。
词法的(Lex-i-cal):与语言的单词或词汇有关,但有别于语言的文法和结构的。
词法分析器以字符流作为输入,生成一系列的名字、关键字和标点符号,同时抛弃单词之间的空白符和注释。程序中每一点都有可能出现空白符和注释;如果让语法分析器来处理它们就会使得语法分析过于复杂,这便是将词法分析从语法分析中分离出去的主要原因。词法分析并不很复杂,但是我们却使用能力强大的形式化方法和工具来实现它,因为类似的形式化方法对语法分析研究很有帮助,并且类似的工具还可以应用于编译器以外的其他领域。
词法单词是字符组成的序列,它可以看成是程序设计语言的文法单位。程序设计语言的词法单词可以归类为有限的几组单词类型。例如,典型程序设计语言的一些单词类型为:
类型 | 例子 |
---|---|
ID | foo,n14,last |
NUM | 10,00,515,082 |
REAL | 66.1,.33,10.,1e6,2.2e - 10 |
IF | if |
COMMA | , |
LPAREN | ( |
RPAREN | ) |
IF
、VOID
、RETURN
等由字母字符组成的单词称为保留字(reserved word),在多数语言中,它们不能作为标识符使用。
非单词的例子:
类型 | 例子 |
---|---|
注释 | /* Try again */ |
预处理命令 | #include <stdio.h>,#define NUMS 5, 6 |
宏 | NUMS |
空格符,制表符,换行符 | ,\lt,\n |
例如,对于下列程序:
float match0(char *s) /* find a zero */
{
if(!strncmp(s, "0,0", 3))
return 0;
}
此法分析器将返回下列单词流:
FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN
LBRACE IF LPAREN BANG ID(strncmp) LPAREN ID(s)
COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN
RETURN REAL(0.0) SEMI RBRACE EOF
其中报告了每个单词的单词类型。这些单词中有一些(如标识符和文字常数)有语义值与之相连,因此,词法分析器还给出了除单词类型之外的附加信息。
我们可以用自然语言来描述一种语言的词法单词。例如,下面是对 C
或 Java
中标识符的一种描述:
标识符是字母和数字组成的序列,第一个字符必须是字母。下划线“_”视为字 母。大小写字母不同。如果经过若干单词分析后输入流已到达一个给定的字符,则下 一个单词将由有可能组成一个单词的最长字特串所组成。其中的空格符、制表符、换行符和注释都将被忽略,除非它们作为独立的一类单词。另外需要有某种空白符来分隔相邻的标识符、关键字和常数。
任何合理的程序设计语言都可以用来实现特定的词法分析器。但是我们将用正则表达式的形式语言来指明词法单词,用确定的有限自动机来实现词法分析器,并用数学的方法将两者联系起来。这样将得到一个简单且可读性更好的词法分析器。
我们说一种语言(language)是字符串组成的集合,字符串是符号(symbol)的有限序列。 符号本身来自有限字母表(alphabet)。
Pascal
语言是所有组成合法 Pascal
程序的字符串的集合;素数语言是构成素数的所有十进制数字字符串的集合;C
语言保留字是 C
程序设计语言中不能作为标识符使用的所有字母数字字符串组成的集合。这三种语言中,前两种是无限集合,后一种是有限集合。在这三种语言中, 字母表都是 ASCII
字符集。
以这种方式谈论语言时,我们并没有给其中的字符串赋予任何含义,而只是企图确定每个 字符串是否属于其语言。 为了用有限的描述来指明这类(很可能是无限的)语言,我们将使用正则表达式(regular expression)表示法。每个正则表达式代表-一个字符串集合。
对于某些带有二义性的文法,例如 if18,应当将它看成是一个标识符,还是两个单词 if 和 8?字符串 " if 89" 是以一个标识符开头还是以一个保留字开头?
因此,依据最长匹配规则,if8
是一个标识符;根据优先规则,if
是一个保留字。
用正则表达式可以很方便地指明词法单词,但我们还需要一种用计算机程序来实现的形式化方法。用有限自动机可以达到此目的。
有限自动机:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号;其中一个状态是初态,某些状态是终态。
上图给出了一些有限自动机的例子。为了讨论方便我们给每个状态一个编号。每个例子中的初态都是编号为 1
的状态。标有多个字符的边是多条平行边的缩写形式;因此,在机器 ID
中,实际上有 26
条边从状态 1
通向状态 2
,每条边用不同的字母标记。
在确定的有限自动机(DFA)中,不会有从同一状态出发的两条边标记有相同的符号。
DFA
以如下方式接收或拒绝一个字符串:
显然,在由自动机 ID
识别的语言中,任何字符串都必须以字母开头。任何单字母都能通至状态 2
,因此单字母字符串是可被接收的字符串。从状态 2
出发,任何字母和数字都将重新回到状态 2
,因此一个后跟任意个数字母和数字的字母也将被接收。
非确定有限自动机 (NFA) 是一种需要对从一个状态出发的多条标有相同符号的边进行选择的自动机。它也可能存在标有 \epsilon(希腊字母)的边,这种边可以在不接收输入字符的情况下进行状态转换。
如上图,在初态时,根据输入的字母,自动机既可向左转换,也可向右转换。若选择了向左转换,则接收的是长度为 3
的倍数的字符串;若选择了向右转换,则接收的是长度为偶数的字符串。因此, 由这个 NFA
识别的语言是长度为 2
的倍数或 3
的倍数的所有由字母 a
组成的字符串的集合。
在第一次转换时,这个自动机必须选择走哪条路。如果存在着任何导致该字符申被接收的 可选择路径,那么自动机就必须接收该字符串。因此,自动机必须进行“猜测”,并且必须总是做出正确的猜测。
标有 \epsilon 的边可以不使用输入中的字符。下面是接收同样语言的另一个 NFA:
同样地,这个自动机必须决定选取哪一条 \epsilon 边。若存在着一个状态,既有一些 \epsilon 边,又有一些标有符号的边,则自动机可以选择接收一个输入符号(并沿着标有对应符号的边前进),或者 选择沿着 \epsilon 边前进。
非确定的自动机是一个很有用的概念,因为它很容易将一个(静态的、说明性的)正则表达式转换成一个(可模拟的、准可执行的)NFA
。 转换算法可以将任何一个正则表达式转换为有一个尾巴和一个脑袋的 NFA
,它的尾巴即开始边,简称为尾;脑袋即末端状态,简称为头。
例如,单个符号的正则表达式 a 转换成的 NFA 为:
由 a 和 b 经联结运算而形成的正则表达式 ab 对应的 NFA 是由两个 NFA 组合而成的,即将 a 的头与 b 的尾连接起来。由此得到的自动机有一个用 a 标记的尾和一个从 b 边进入的头。
一般而言,任何一个正则表达式 M 都有一个具有尾和头的 NFA:
我们可以归纳地定义正则表达式到 NFA 的转换。一个正则表达式或者是原语(单个符号或 \epsilon),或者是由多个较小的表达式组合而成。类似地,NFA 或者是基本元素,或者是由多个较小的NFA组合而成。
将正则表达式转换至 NFA
,我们利用单词 IF
、ID
、NUM
以及 error
的一些表达式来举例说明这种转换算法。每个表达式都转换成了一个 NFA
,每个 NFA
的头是用不同单词类型标记的终态结点,并且每一个表达式的尾汇合成一个新的初始结点。由此得到的结果(在合并了某些等价的 NFA
状态之后)如下图所示:
用计算机程序实现确定的有限自动机(DFA)较容易。但实现 NFA
则要困难一些,因为大多数计算机都没有足够好的可以进行“猜测”的硬件。下面给出一个由四个正则表达式转换成的 NFA
:
我们用一个字符串 "in" 来模拟,计算所有的
1
可以到达状态 2
,从状态 4
可到达状态 5
,从 状态 9
则无处可去,而从状态 14
则可以到达状态 15
,由此得到状态集合 {2, 5, 15}
。