词法分析
词法分析(英語:lexical analysis)是计算机科学中将字符序列转换为标记(token)序列的过程。进行词法分析的程序或者函数叫作词法分析器(lexical analyzer,简称lexer),也叫扫描器(scanner)。词法分析器一般以函数的形式存在,供语法分析器调用。
标记
编辑这里的标记是一个字串,是构成源代码的最小单位。从输入字符流中生成标记的过程叫作标记化(tokenization),在这个过程中,词法分析器还会对标记进行分类。
词法分析器通常不会关心标记之间的关系(属于语法分析的范畴),举例来说:词法分析器能够将括号识别为标记,但并不保证括号是否匹配。
针对如下C语言表达式:
sum=3+2;
将其标记化后可以得到下表内容:
语素 | 标记类型 |
---|---|
sum | 标识符 |
= | 赋值操作符 |
3 | 数字 |
+ | 加法操作符 |
2 | 数字 |
; | 语句结束 |
标记经常使用正则表达式进行定义,像lex一类的词法分析器生成器就支持使用正则表达式。语法分析器读取输入字符流、从中识别出语素、最后生成不同类型的标记。其间一旦发现无效标记,便会报错。
扫描器
编辑词法分析的第一阶段即扫描器,通常基于有限状态自动机。扫描器能够识别其所能处理的标记中可能包含的所有字符序列(单个这样的字符序列即前面所说的“语素”)。例如“整数”标记可以包含所有数字字符序列。很多情况下,根据第一个非空白字符便可以推导出该标记的类型,于是便可逐个处理之后的字符,直到出现不属于该类型标记字符集中的字符(即最长一致原则)。
标记生成器
编辑标记化(tokenization)即将输入字符串分割为标记、进而将标记进行分类的过程。生成的标记随后便被用来进行语法分析。
例如对于如下字符串:
The quick brown fox jumps over the lazy dog
计算机并不知道这是以空格分隔的九个英语单词,只知道这是普通的43个字符构成的字符串。可以通过一定的方法(这里即使用空格作为分隔符)将语素(这里即英语单词)从输入字符串中分割出来。分割后的结果用XML可以表示如下:
<sentence>
<word>The</word>
<word>quick</word>
<word>brown</word>
<word>fox</word>
<word>jumps</word>
<word>over</word>
<word>the</word>
<word>lazy</word>
<word>dog</word>
</sentence>
然而,语素只是一类字符构成的字符串(字符序列),要构建标记,语法分析器需要第二阶段的评估器(Evaluator)。评估器根据语素中的字符序列生成一个“值”,这个“值”和语素的类型便构成了可以送入语法分析器的标记。一些诸如括号的语素并没有“值”,评估器函数便可以什么都不返回。整数、标识符、字符串的评估器则要复杂的多。评估器有时会抑制语素,被抑制的语素(例如空白语素和注释语素)随后不会被送入语法分析器。
例如对于某程序设计语言的源程序片段:
net_worth_future = (assets - liabilities);
在进行语法分析后可能生成以下单词流(空格被抑制):
NAME "net_worth_future" EQUALS OPEN_PARENTHESIS NAME "assets" MINUS NAME "liabilities" CLOSE_PARENTHESIS SEMICOLON
尽管在某些情况下需要手工编写词法分析器,一般情况下词法分析器都用自动化工具生成。
关联项目
编辑参考文献
编辑- CS164: Programming Languages and Compilers (Class Notes #2: Lexical)
- Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X 624
- Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
- Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6