词法分析器的任务是把构成源程序的字符流翻译成词法记号流。构造词法分析器的一种简单办法是用状态转换图来描述源语言记号的结构，然后手工把这种状态转换图翻译成为识别词法记号的程序。
2.1词法记号及属性2.1.1 词法记号、模式、词法单元
记号名
词法单元例举
模式的非形式描述
if
if
字符i, f
for
for
字符f, o, r
relation
< , <= , = , …
< 或 <= 或 = 或 …
id
sum, count, D5
由字母开头的字母数字串
number
3.1, 10, 2.8 E12
任何数值常数
literal
“seg. error”
引号“和”之间的任意字符串，但引号本身除外
历史上词法定义中的一些问题
忽略空格带来的困难 DO 8 I = 3. 75 DO 8 I = 3, 75 DO8I = 3. 75
关键字不保留 IF THEN THEN THEN=ELSE；ELSE …
关键字、保留字和标准标识符的区别
保留字是语言预先确定了含义的词法单元
标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义
2.1.2 词法记号的属性position = initial + rate * 60的记号和属性值：
2.1.3 词法错误
词法分析器对源程序采取非常局部的观点
难以发现下面的错误 fi (a == f (x) ) …
在实数是a.b格式下，可以发现下面的错误 123.
紧急方式的错误恢复
错误修补
2.2 词法记号的描述与识别2.2.1 串和语言
概念
字母表：符号的有限集合， 例：Σ = {0, 1}
串：符号的有穷序列，例：0110, ε
语言：字母表上的一个串集 {ε, 0, 00, 000, …}, {ε}, ∅
句子：属于语言的串
串的运算
连接 xy，sε = εs = s
积（指数） s0为ε，si为si -1s（i > 0）
语言的运算
和：L ∪ M = {s | s ∈L 或 s ∈ M }
连接：LM = {st | s ∈ L 且 t ∈ M}
指数：L0是{ε }，Li是Li -1L
闭包：L* = L0 ∪ L1 ∪ L2 ∪ …
正闭包： L+ = L1 ∪ L2 ∪ …2.2.2 正规式
正规式用来表示简单的语言，叫做正规集。
正规式
定义的语言
备注
ε
{ε}
a
{a}
a ∈ Σ
(r) | (s)
L(r)∪L(s)
r和s是正规式
(r)(s)
L(r)L(s)
r和s是正规式
(r)*
(L(r))*
r是正规式
(r)
L(r)
r是正规式
正规式的例子 Σ = {a, b}
a | b {a, b}
(a | b) (a | b ) {aa, ab, ba, bb}
aa | ab | ba | bb {aa, ab, ba, bb}
a* 由字母a构成的所有串集
(a | b)* 由a和b构成的所有串集
复杂的例子
( 00|11| ( (01|10) (00|11) (01|10))) 句子：01001101000010000010111001
2.2.3 正规定义
对正规式命名，使表示简洁 d1 → r1 d2 → r2 . . . dn → rn
各个di的名字都不同
每个ri都是Σ ∪{ d1, d2, …, di-1 }上的正规式
正规定义的例子
C语言的标识符是字母、数字和下划线组成的串 letter_ → A | B | … | Z | a | b | … | z | _ digit → 0 | 1 | … | 9 id → letter_(letter_ |digit)*
无符号数集合，例1946,11.28,63E8,1.99E6 digit → 0 | 1 | … | 9 digits → digit digit* optional_fraction → .digits|ε optional_exponent → ( E ( + | - | ε ) digits ) | ε number → digits optional_fraction optional_exponent
简化表示 number → digit+ (.digit+)? (E(+|-)? digit+)?
2.2.4
关系算符的转换图
图片3.1
标识符和保留字的转换图
图片3.2
无符号数的转换图
图片3.3
空白的转换图图片3.4
2.3 有限自动机2.3.1不确定的有限自动机（简称NFA）是一个数学模型，它包括： 1、状态集合S 2、输入符号集合Σ 3、转换函数move : S × ( Σ∪{ε} ) → P(S) 4、状态s0是开始状态 5、F ⊆ S是接受状态集合
2.3.2 确定的有限自动机（简称DFA)一个数学模型，包括： 1、状态集合S 2、输入字母表Σ 3、转换函数move : S × Σ → S 4、唯一的初态 s∈ S 5、终态集合F ⊆ S
2.3.3 NFA到DFA的变换子集构造法 1、DFA的一个状态是NFA的一个状态集合 2、读了输入a1 a2 … an后，NFA能到达的所有状态：s1, s2, …, sk，则DFA到达状态{s1, s2, …, sk}
2.3.4 DFA的化简
死状态
分割算法
2.4 从正规式到有限自动机
从正规式建立识别器
从正规式构造NFA 用语法制导的算法，它用正规式语法结构来指导构造过程
把NFA变成DFA （子集构造法）
将DFA化简 （合并不可区别状态）
2.5 词法分析器的生成器
Lex的使用。