TinyC编译器5—词法分析

1.词法分析的概念

词法分析也称为 分词 ，此阶段编译器从左向右扫描源文件，将其字符流分割成一个个的 词 （ token 、 记号 ，后文中将称为 token ）。所谓 token ，就是源文件中不可再进一步分割的一串字符，类似于英语中单词，或汉语中的词。

TOKEN-TYPE              TOKEN-VALUE
-----------------------------------------------
T_IF                    if
T_WHILE                 while
T_ASSIGN                =
T_GREATTHAN             >
T_GREATEQUAL            >=
T_IDENTIFIER            name / numTickets / ...
T_INTEGERCONSTANT       100 / 1 / 12 / ....
T_STRINGCONSTANT        "This is a string" / "hello" / ...

编译器中的 token 中一般用一个 struct 来表示：

typedef enum {T_IF, T_WHILE, T_ADD, T_INTCONSTANT, T_STRINGCONSTANT, T_IDENTIFIER, ...
} TokenType;typedef struct _Token {TokenType type;union {char *stringval;int *intval;double *doubleval;} value;
} TokenRecord;

词法分析器每扫描到一个完整的 token 后，立即 新建一个 TokenRecord ，将此 token 的类型记录在此结构的 type 域中，将其字面值记录在 value 域中对应的子域内，并将此 TokenRecord 结构传递给下一阶段的语法分析模块使用，然后接着扫描下一个 token 。这样从语法分析模块的角度来看，源程序就变成了一个连续的 token stream 了。

分词扫描的方法目前主流使用的是正则表达式，下面将进行介绍。

2.正则语言和正则表达式

2.1正则语言的定义

• 只有一个空句子的集合是一个正则语言，只有一个单符号句子的集合也是一个正则语言。如以下每个集合都是一个正则语言：{ε}, {a}, {b}, ..., {z}。注意：{ε} 不要和空集搞混了，空集中没有任何元素，但是{ε} 中有一个空句子元素。
• 如果句子集合 R1 和 R2 是正则语言，则 R1 和 R2 的并集 R 也是一个正则语言，R = R1 ∪ R2。
• 如果句子集合 R1 和 R2 是正则语言，则 R1 和 R2 的连接集合 R 也是一个正则语言。连接集合 R = { s1 s2 | s1 ∈ R1, s2 ∈ R2 } 。
• 如果句子集合 R 是正则语言，则 R 的重复集合 R* 也是一个正则语言，重复集合 R* = { s1 s2 ... sn | si ∈ R , n ∈ N }，此处 n 可以等于 0 ，此时 R* 中只有一个空句子。

但是正则语言如何表示出来呢，这时候正则表达式登场。

2.2正则表达式

• 只有一个空句子的集合的正则表达式为 ε ，只有一个单符号句子的集合 {θ} 的正则表达式为 θ 。
• 如果正则语言 R1 和 R2 的正则表达式为 r1 和 r2 ，那么正则表达式 r1|r2 表示 R1 和 R2 的并集。
• 如果正则语言 R1 和 R2 的正则表达式为 r1 和 r2 ，那么正则表达式 r1 r2 表示 R1 和 R2 的连接集合。
• 如果正则语言 R 的正则表达式为 r ， 那么正则表达式 r* 表示 R 的重复集合 R* 。
• 正则表达式 (r) 和 r 是等价的。

举个例子：正则表达式 a 表示集合 {a}， b 表示集合 {b} ， a|b 表示集合 {a, b} ， ab* 表示集合 {a, ab, abb, abbb, ... } 。

2.2.2特殊字符

以下 11 个字符：* [ ] ^ $ . | ? * + ( ) 被保留作特殊用途，如果想使用这些字符的字面值，需要在前面加反斜杠 “\” 转义。另外，一些不便书写的字符可以通过在前面加 “\” 转义，如 \n 和 \t 分别表示换行符和制表符。

2.2.3字符集

如： [abferx] ，用方括号括起来的字符，表示匹配这些字符中的其中一个，相当于 (a|b|f|e|r|x) 。方括号内的特殊字符不需要转义（ [ ] - ^ 除外），如 [af({] 表示 匹配 “a”, “f”, “{”, “(” 中的其中一个。方扩号内可以使用 “-“ 来定义一个范围，且可以定义多个范围，如 [0-9] 表示匹配单个数字， [a-zA-Z] 表示匹配单个字母。

2.2.4取反字符集

如： [^abc] ，在方括号内的第一个字符为 ^ ，表示这是一个取反字符集，表示匹配一个不在方括号内部的字符。

2.2.5  *、?和+

* 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）0次或多次；

? 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）0次或1次；

+ 表示匹配前面的字符（或者由括号括起来的表达式、方括号括起来的字符集）1次或多次。

2.2.6 ”.” 通配符

. 表示匹配除换行符外的任意字符一次。

综上所诉：

正则表达式可以用来表示源程序中的 token ，如：

• 整数 ： [0-9]+
• 小数 ： [0-9]+\.[0-9]*
• 字符串 ： \”[^\”]*\”
• 标识符 ： [_a-zA-Z][_a-zA-Z0-9]*
• 关键字 if ： if

3.正则表达式背后的原理：有限状态自动机

有限状态自动机（finate automaton）是用来判断字符串（句子）是否和正则表达式匹配的假想机器，它有一个字母表 Σ 、一个状态集合 S ，一个转换函数 T ，当它处于某个状态时，若它读入了一个字符（必须是字母表里的字符），则会根据当前状态和读入的字符自动转换到另一个状态，它有一个初始状态，还有一些所谓的接受状态。

上图中圆圈表示各种状态，各箭头及签头上的字符表示状态的转换表，自动机只有一个初始状态，用一个不含字符的箭头指向此状态，可以认为此为自动机的入口，自动机可以有一个或多个接受状态，用双圆圈表示。

上图中的自动机的字母表为 {a, b}，初始状态为 S1 ，当它读入一个 a 后，就转到状态 S2 ，若读入的是 b ，则转到 S4，然后一个接一个字符的转换其状态，若字符结束时自动机处在其接受状态，则表示此字符串被其接受。

经过观察可知，此图中的自动机能接受的字符串为 “ab”, “abb”, “abbb”, ... ，也就是说，此自动机与正则表达式 ab+ 是等价的。

而且数学家们已经证明了：任何一个正则表达式都有一个等价的有限状态自动机，任何一个有限状态自动机也有一个等价的正则表达式。