1 词法分析程序的设计

1.1 词法分析流程

逐个读入源程序字符并按照构词规则切分成一系列单词（token）。

单词是语言中具有独立意义的最小单位，包括保留关键字、标识符、常量、运算符、标点符号、分界符等。

词法分析是编译过程中的一个阶段，在语法分析前进行，也可和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。

词法分析程序的主要任务及输出：

读源程序，产生用二元组表示的单词符号
滤掉空格，跳过注释、换行符
记录源程序的行号，以便出错处理程序准确定位源程序的错误
宏展开等…

2 正则表达式

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表示方法。

例如：$r = a (a \mid b)^* (\varepsilon \mid(. \mid \_ )(a \mid b)(a \mid b)^*)$

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 $r$ 定义（表示）一个语言，记为$L(r)$。

这个语言也是根据 $r$ 的子表达式所表示的语言递归定义的。

2.1 正则表达式的定义

C语言无符号整数的 RE

十进制整数的RE：$(1|\ldots| 9)(0|\ldots| 9)^{*} \mid 0$

八进制整数的RE：$0(1|2| 3|4| 5|6| 7)(0|1| 2|3| 4|5|6|7)^{*}$

十六进制整数的RE：$0 x(1|\ldots| 9|a| \ldots|f| A|\ldots| F)(0|\ldots| 9|a| \ldots|f| A|\ldots| F)^{*}$

2.2 正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)。

2.2.1 RE的代数定律

正则文法与正则表达式等价：

对任何正则文法 G，存在定义同一语言的正则表达式 r
对任何正则表达式 r，存在生成同一语言的正则文法 G

3 正则定义

正则定义（Regular Definition）是具有如下形式的定义序列：

$$
\begin{array}{c}d_{1} \rightarrow r_{1} \ d_{2} \rightarrow r_{2} \ \cdots \ d_{n} \rightarrow r_{n}\end{array}
$$

其中：

每个 $d_i$ 都是一个新符号，它们都不在字母表 Σ 中，而且各不相同
每个 $r_i$ 是字母表$\Sigma \cup{d_{1}, d_{2}, \ldots, d_{i-1}}$上的正则表达式

给一些 RE 命名，并在之后的 RE 中像使用字母表中的符号一样使用这些名字。

例1：C语言中标识符的正则定义

$digit \rightarrow 0|1| 2|\ldots| 9$
$ letter \_ \rightarrow A|B| \ldots |Z| a|b| \ldots |z| \_ $
$id \rightarrow letter \_ (letter \_ |digit )^*$

例2：（整型或浮点型）无符号数的正则定义

$digit \rightarrow 0|1|2|…|9$
$digits \rightarrow digit\quad digit { }^{*}$
$optionalFraction \rightarrow.digits \mid \varepsilon$
$optionalExponent \rightarrow(E(+|-| \varepsilon) digits ) \mid \varepsilon$
$number \rightarrow digits \quad optionalFraction \quad optionalExponent$

4 有穷自动机

有穷自动机（Finite Automata，FA）由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型。

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）。

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

4.1 FA模型

输入带（input tape）：用来存放输入符号串
读头（head）：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动
有穷控制器（finite control）：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态

4.2 转换图

结点：FA的状态

初始状态（开始状态）：只有一个，由start箭头指向
终止状态（接收状态）：可以有多个，用双圈表示

带标记的有向边：如果对于输入$a$，存在一个从状态$p$到状态$q$的转换，就在$p$、$q$之间画一条有向边，并标记上$a$。

4.3 FA定义（接收）的语言

给定输入串$x$，如果存在一个对应于串$x$的从初始状态到某个终止状态的转换序列，则称符号串$x$被该FA接收。

由一个有穷自动机M接收的所有符号串构成的集合称为是该FA定义（或接收）的语言，记为$L(M)$。

$L(M)$ =所有以abb结尾的字母表$\{a, b\}$上的符号串的集合

4.3.1 最长子串匹配原则

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。

在到达某个终态之后，只要输入带上还有符号，DFA就继续前进，以便寻找尽可能长的匹配。

5 有穷自动机的分类

FA的分类：

确定的FA(Deterministic finite automata, DFA)
非确定的FA(Nondeterministic finite automata, NFA)

5.1 确定的有穷自动机 (DFA)

$$
M = ( S，Σ ，δ，s_0，F )
$$

$S$：有穷状态集
$Σ$：输入字母表，即输入符号集合。假设$ε$不是$Σ$中的元素
$δ$：将$S× Σ$映射到$S$的转换函数。 $\forall s \in S$，$a \in \Sigma$，$\delta(s, a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态
$s_0$：开始状态 (或初始状态)，$s_0 \in S$
$F$：接收状态（或终止状态）集合，$F \subseteq S$

5.1.1 一个DFA

可以用转换表表示DFA。

5.1.2 DFA的算法实现

输入：以文件结束符eof结尾的字符串x。DFA：D 的开始状态$s_0$，接收状态集 F，转换函数move

输出：如果 D接收 x，则回答“yes”，否则回答“ no”

方法：将下述算法应用于输入串 x

s = s0;
c = nextChar();
while (c! = eof) {
    s = move(s, c);
    c = nextChar();
}
if (s在F中) return "yes"; 
else return "no;

函数nextChar()返回输入串x的下一个符号
函数move(s, c)表示从状态s出发，沿着标记为c的边所能到达的状态

5.2 非确定的有穷自动机(NFA)

$$
M = ( S，Σ ，δ，s_0，F )
$$

S：有穷状态集
Σ：输入字母表，即输入符号集合。假设ε不是Σ中的元素
δ：将S× Σ映射到$2^S$的转换函数。 $\forall s \in S$，$a \in \Sigma$，$\delta(s, a)$表示从状态s出发，沿着标记为a的边所能到达的集合
$s_0$：开始状态 (或初始状态)，$s_0 \in S$
F：接收状态（或终止状态）集合，$F \subseteq S$

5.2.1 一个 NFA

5.3 DFA和NFA的等价性

对任何NFA：N ，存在识别同一语言的DFA：D
对任何DFA：D ，存在识别同一语言的NFA：N

例如：$r=(a|b)^*abb$

正则文法$\ce{<->}$正则表达式$\ce{<->}$FA

5.4 带有“ε-边”的NFA

$$
M = ( S，Σ ，δ，s_0，F )
$$

S：有穷状态集
Σ：输入字母表，即输入符号集合。假设ε不是Σ中的元素
δ：将$S \times(\Sigma \cup{\varepsilon})$映射到$2^S$的转换函数。 $\forall s \in S$，$a \in \Sigma \cup{\varepsilon}$，$\delta(s, a)$表示从状态s出发，沿着标记为a的边所能到达的集合
$s_0$：开始状态 (或初始状态)，$s_0 \in S$
F：接收状态（或终止状态）集合，$F \subseteq S$