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+ 是等价的。
而且数学家们已经证明了:任何一个正则表达式都有一个等价的有限状态自动机,任何一个有限状态自动机也有一个等价的正则表达式。