2.1 词法分析器的设计方法
2.1.1 单词符号的分类与输出形式
- 单词符号分类
· 保留字（基本字）
· 标识符
· 常数
· 运算符
· 界符 - 词法分析程序输出单词的形式
词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）
（1）单词种别：表示单词的种类
（2）单词自身的值：是编译中其他阶段所需要的信息
2.1.2 状态转换图
可以用状态转换图来识别单词。
状态转换图是有限的有向图，结点代表状态，用圆圈表示；
结点间可由有向边连接，有向边上可标记字符
2.3 正规表达式与有限自动机简介
2.3.1 正规表达式与正规集
letter(letter|digit)：其中letter与（……）的并置表示两者的连接，|表示letter与digit二选一，表示零次或多次引用
| 表示或，• 表示连接（通常可省略），* 表示闭包。
假定优先级：* > • > |，则在不出现混淆的情况下可不用括号
——
对于给定的字母表∑，正规式和正规集的递归定义如下：
1.空字和ø都是∑上的正规式，他们所表示的正规集分别为{空字}和ø
2.对任一个a属于∑，a是∑上的一个正规式，它所表示的正规集为{a}
3.如果R和S是∑上的正规式，他们所表示的正规集分别为L(R)和L(S)则：
•R | S 是∑上的正规式，它所表示的正规集为L(R)UL(S);
•R • S 是∑上的正规式，它所表示的正规集为L(R)L(S);
•(R)是∑上的正规式，它所表示的正规集为(L(R));
•R是∑上的正规式，它所表示的正规集为L(R)。
4.仅有有限次使用规则（1）～（3）得到的表示式式∑上的正规式，它所表示的集合是∑上的正规集
——
Rº = {空字},R=RºUR1UR2UR3……，则称R是R的闭包。R+ = RR*，并称R+是R的正闭包
R+ =R1UR2UR3……
正规式具有以下性质：
1.交换律：R | S = S | R;
2.结合律： R | (S | T) = (R | S) | T R(ST)=(RS)T
3.分配律：R(S | T) = RS | RT (R | S)T = RT | ST
4.同一律： eR = Re = R (e为空字)
2.3.3有限自动机
有限自动机（FA）是更一般化的状态转换图，分为确定有限自动机DFA和非确定有限自动机NFA两种
1.确定有限自动机（DFA）
一个确定的有限自动机Md（记为DFA Md）是一个五元组，Md = (S, ∑, f, s0, )，其中
（1）S是一个有限状态集， 它的每一个元素称为一个状态
（2）∑是一个有穷输入字母表， 它的每一个元素称为一个输入字符
（3）f是一个从S x ∑到S的单值映射， 即f(si, a) = sj且有si, s属于S和a属于∑；
（4）s0属于S，是唯一的一个初态；
（5）Z属于S，是一个终态集
f(si, a)=sj表示当前状态为si且输入字符为a时，自动机将转换到下一个状态sj，也即sj称为si的一个后继状态。
P18
例如f(s1, a) = s2, f(s1, b) = s3, f(s1, c) = s4，有
非确定有限自动机（NFA）
一个非确定有限自动机Mn（记为NFA Mn）是一个五元组，Mn = (S, ∑, f, Q, Z)，其中
（1）S、∑、Z的意义与DFA相同、
（2）f是一个从S x ∑到S的子集映射；
（3）Q属于S，是一个非空初态集*
NFA和DFA的主要区别主要有两点
1.NFA可以有若干个初始状态，而FA只有一个初始状态；
2.NFA的状态转换函数f不是单值函数，而是一个多值函数，即f(si, a)={某些状态的集合}（si属于S），它表示不能由当前状态和当前输入字符唯一的确定下一个要转换的状态，也即允许同一个状态对同一个输入字符可以有不同的输出边。
例如f(s1, a) = {s1, s2, s3}
∑*表示输出边上所标记的不仅是字符，也可以是字。
此外NFA还允许f(s1,e) = {某些状态的集合}（e代表空字），即在NFA的状态转换图红输出边上的标记还可以是e（空字）。
