图1 编译程序总框

一、词法分析器要求

1.功能和输出形式

功能：输入源程序，输出单词符号

单词符号分类：关键字（begin、while、if等等）、标识符、常数、运算符（+、-、*、/等等）、界符（如逗号、分号、括号等等）

单词符号表示形式：二元式（单词种别，单词符号的属性值）

单词种别通常用整数编码。一般而言，标识符统归为一种，常数按类型（整、实、布尔）分种，关键字可视为一种，也可以一字一种，运算符采用一符一种，界符一般用一符一种。

特别的，若一个种别只含一个单词符号，种别编码就代表自身。若一个种别含有多个单词符号，则除了要给出种别编码外，还要给出相应的单词符号的属性值

二、词法分析器设计

1.输入、预处理

图2 词法分析器结构图

词法分析器工作过程：输入源程序 → 放入输入缓冲区 → 调用预处理子程序 → 装入扫描缓冲区 → 单词符号识别 → 输出单词符号

词法分析器对扫描缓冲区进行扫描时一般采用两个指示器：

起点指示器：指向当前正在识别的单词的开始位置（新单词的首字符）

搜索指示器：用于向前搜索以寻找单词的终点

为保证单词符号不被扫描缓冲区的边界打断，扫描缓冲区最好采用一分为二的区域，即使用两个半区，如下图所示：

工作过程：搜索指示器从单词起点出发，若搜索到半区的边缘仍未到达单词的终点，调用预处理程序，令其把后续的输入字符装进另半区。

我们认定，在搜索指示器对另半区进行扫描的期间内，现行的单词的终点必定能到达。

单词符号识别的方法：超前搜索

2.状态转换图

转换图是一张有限方向图 。结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记代表射出结点状态下可能出现的输入字符或字符类。

一张转换图只包含有限个状态，其中一个被认为是初态，同时至少有一个终态（用双圈表示）。

终态结上打个 * 意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串

三、正规表达式与有限自动机

1.正规式与正规集

递归定义

(1) ε 和 ∅ 都是 Σ 上的正规式，它们表示的正规集分别为{ε}和 ∅ ；

(2) 任何 a ∈ Σ ，a 是 Σ 上的一个正规式，它所表示的正规集为{a}；

(3) 假定 U 和 V 都是 Σ 上的正规式，它们所表示的正规集分别为 L(U) 和 L(V)，那么，(U|V)、(U·V) 和(U)* 也都是正规式，它们所表示的正规集分别为 L(U) ∪ L(V)、L(U) ∩ L(V)（连接积）和 (L(U))*（闭包）。

L(U|V) = L(U) ∪ L(V)

L(U·V) = L(U) ∩ L(V)

L((U)*) = (L(U))*

算符优先顺序：先‘ * ’次‘ · ’最后‘ | ’。

2.确定有限自动机（DFA）

确定有限自动机(DFA) M是一个五元式

编译原理——词法分析总结

(1) S 是一个有限集，它的每一个元素称为一个状态。

(2) Σ 是一个有穷字母表，它的每一个元素称为一个输入字符。

(3) δ 表示单值部分映射。δ (s，a) = s’ 意味着：当现行状态为 s 、输入字符为 a 时，将转换到下一状态 s’。称 s’ 为 s 的一个后继状态。

(4) s0 ∈ S ，表示唯一的初态。

(5) F ⊆ S，表示一个终态集（可空）。

3.非确定有限自动机（NFA）

非确定有限自动机(NFA) M是一个五元式

编译原理——词法分析总结

(1) S 同确定有限自动机(1)。

(2) Σ 同确定有限自动机(2)。

(3) δ 表示多值映射。从现行状态 s 出发，输入若干个相同或不同的字符，其后继状态可能唯一。

(4) S0∈ S，是一个非空初态集 。

(5) F ⊆ S，表示一个终态集（可空）。

4.非确定有限自动机(NFA)转换为确定有限自动机(DFA)

假定 NFA M = < S，Σ，δ，S0，F >

(1) 引进新的初态结点 X 和终态结点 Y ( Y ∉ S )。

从 X 到 S0 中任意状态结点连一条 ε 箭弧，从 F 中任意状态结点连一条 ε 箭弧到 Y 。

(2) 利用下图三条替换规则对 M 进行替换，其中 k 是新引入的状态。

编译原理——词法分析总结

重复这种分裂过程，直至状态转换图中每一条箭弧上的标记或为 ε ，或为 Σ 中的单个字母。将最终得到的NFA记作 M’。

(3) 利用子集法将 M’ 进一步变换为DFA，方法如下：

① 假定 I 是 M’ 的状态集的子集，定义 I 的 ε 闭包，ε_CLOSURE(I)为：

(a) 若 q ∈ I，则 q ∈ ε_CLOSURE(I)；

(b) 若 q ∈ I，那么从 q 出发经任意条 ε 弧而能到达的任何状态 q’ 都属于ε_CLOSURE(I)；

也就是说，ε_CLOSURE(I) 等于 I 所包含的状态以及由它们出发经过任意条 ε 弧而能到达的状态的集合。

② 假定 I 是 M’ 的状态集的子集，a ∈ Σ，定义

Ia = ε_CLOSURE(J)

其中，J 是指从 I 所包含的状态分别出发，经过一条 a 弧而能到达的状态结点的集合。

③ 假定 Σ = {a1 ... ak} ，构造状态转换表（状态转换矩阵），此表每一行包含 k + 1 列。置该表的首行首列为 ε_CLOSURE(X)，则置第 i + 1 列 Iai (i = 1，...，k ) 为 ε_CLOSURE(Iai)。之后，检查该行上的所有状态集是否已在第一列出现，将未出现者填入后面空行的第一列，重复上述步骤，直至 Iai 列上的所有状态集均已在第一列上出现。