更新于2024-04-21 22:34:13

Ch3: 词法分析#

0. 词法分析的模式和主要功能#

0.1: 词法分析的工作方式:#

词法分析程序主要有两种工作方式:

1. 词法分析和语法分析完全分开，变为两个等地位的模块，词法分析的输出作为语法分析的输入，词法分析和语法分析一共至少扫描文本两遍。
2. 词法分析作为语法分析的调用子模块，每当语法分析需要读入一个单词时，调用词法分析子模块从字符流种读入一个单词。词法分析和语法分析放在一起扫描文本一遍。一般采用的都是这个方式。

0.2: 词法分析程序的输出:#

词法分析程序每次从字符流中取出一个字符时，以单词符号的形式发送至语法分析程序。

单词符号是一个二元组**(单词种别，单词本身的值)，其中单词的种别往往用整数编码来表示，单词本身的值是用来区分单凭单词种别无法区分的单词。比如const int i=1,j = 25，$1$和$25$都是常量，但是需要有单词本身的值来区分。特别的，一般标识符本身的值往往是单词符号表中的指针**。

0.3: 词法分析的主要功能:#

词法也是语法的一部分，但是仍旧将词法分析和语法分析分开的原因是：

1. 使编译程序的结构更加清楚明了
2. 改进编译程序的效率
3. 增加编译程序的可移植、可维护性。

除了1. 识别单词，词法分析还具有：

2. 滤去注释与空格
3. 记录新读入的字符和行号
4. 宏展开
5. 词法分析的预处理…

0.4 用来描述词法规则的工具#

描述词法规则的工具主要有：

1. 状态转换图
2. 扩展巴科斯范式(EBNF)
3. 正规文法($\star$)
4. 正规表达式($\star$)
5. 有限状态自动机($\star$)

1. 正规文法#

3型文法$G(V_N,V_T,P,S)$(左线性/右线性)能够描述一个正规集。

2. 正规表达式#

2.1 正规式和正规集的定义:#

正规表达式所表示的正规式和正规集一般用递归定义：

定理$2.1.1$ 运算符号的优先级为: $^* > \cdot > |$ 。并且$^*,\cdot,|$都是左结合的。

左结合： 相同优先级的运算符的运算顺序: $a\cdot b\cdot c=(a\cdot b)\cdot c$

例$2.1.1$ $d^*(.dd^*|\varepsilon)(e(+|-|\varepsilon)dd^*|\varepsilon)$表示一个无符号数。

配合ppt中例题使用

2.2 正规式的代数规律(运算符的性质):#

引申性质:

$$\begin{align} r^* &= (r | \varepsilon)^* \\ (a | b)^* &= (a^*b^*)^* \\ (r^*)^*&=r^* \end{align}$$

2.3 正规式和正规文法的等价性#

如果正规式$e$所表达的字符串的正规集$L[e]$和正规文法$G[S]$所表达的正规语言$L[G]$相等，则说该正规式和该正规文法等价。

2.3.1 正规式和正规文法的相互转换#

注意: 注意正规文法的左/右线性要保持好！不能混用！

当正规式转换为正规文法时，可以使用代入规则。并且可以使用更加熟悉的”+ *“来代替”| $\cdot$两个运算，化简更快更熟悉(+*的运算性质和”|$\cdot$完全一致)

3. 有穷自动机#

定义：有穷自动机(有限自动机)(Finite Automata)是一种识别装置，用来自动识别正规集[正规文法构成的语言的集合/正规式所表示的集合]。分为确定的有穷自动机和不确定的有穷自动机。

3.1 确定的有穷自动机DFA(Deterministic Finite Automata)#

定义$3.1.1$ 一个确定的有穷自动机M是一个5元组

$$M = (K,\Sigma,f,S,Z)$$

其中:

$K$是一个有穷的状态集合。

$\Sigma$是一个有穷的输入符号表。每个元素称为一个输入符号。

$f$是状态转换函数，$f: K\times \Sigma \to K$定义了从一个状态接受一个合法符号后转换到的一个确定的状态。注意，确定有穷自动机不因为空串$\varepsilon$转换状态。

$S$是唯一的一个起始状态，并且$S\in K$

$Z$是一个终止状态集合，且$Z \subseteq K$，注意$Z = \varnothing$的情况。​

以上是定义表示法，还有矩阵表示法(状态转换矩阵)[易被计算机表示]和图表示法(状态图)[直观]。见书Page48即可。注意表示方法。

1. 如何表示初态节点
2. 如何表示终态节点

定义$3.1.2$ 定义符号串$t$可以被自动机所接受: 如果在状态图上存在一条从初态节点到某一终态节点的道路，且该条道路上的所有弧连接成的符号串等于$t$，则称符号串可以被自动机接受。注意：只有当起始节点恰好也是终止节点时，$\varepsilon$才可被接受

定义$3.1.3$ 定义在自动机$M$上的运算：

$$f(U,t) = f(U,t_1t_x) = f(f(U,t_1),t_x) \\ f(U,\varepsilon) = U$$

其中$U\in K, t\in\Sigma^*,t_1\in\Sigma,t = t_1t_x$。

则$t$可被接受也等价于$f(S,t) = u,u \in Z$。

定义集合$L(M)$:

为自动机$M$的语言。

定理$3.1.1$ $\Sigma$上的一个串集合$V \subseteq \Sigma^*$是正规的当且仅当存在一个确定的有穷自动机$M$的语言$L(M) = V$。

3.2 不确定的有穷自动机NFA(Nondeterministic Finite Automata)#

定义$3.2.1$ 不确定的有穷自动机$M$也是一个5元组：

$$M = (K,\Sigma,f,S,Z)$$

其中:

$K$是一个有穷的状态集合。

$\Sigma$是一个有穷的输入符号表。每个元素称为一个输入符号。

$f$是一个状态转移函数，$f: K \times \Sigma^* \to 2^{K}$，其中$2^K$是$K$的幂集，$\Sigma^*$是$\Sigma$上的字符串集。首先是可以因为$\varepsilon$转换状态，接着是因为一个输入可以有$n$个后继状态。

$S$是一个初始状态集合，$S \subseteq K$且$S \neq \varnothing$

$Z$是一个终止状态集合，$Z\subseteq K$。可为空！

当然$NFA$也可以用状态图和状态转移矩阵表示。接受字符串的定义也和$DFA$完全一致。不过$\varepsilon$可以被不确定的有穷自动机$M$接受的条件是:

1. 存在一个初始节点也是终止节点。
2. 从初始节点出发存在一条$\varepsilon$的路径到终止节点。

定理$3.2.2$ 对于任意一个不确定的有穷自动机$M'$，一定存在一个确定的有穷自动机$M$,使得$L(M') = L(M)$. 也就是一定存在一个确定的有穷自动机$M$使得$M'$和$M$等价。

3.3 $NFA$转换为$DFA$: 子集法#

定义$3.3.1$ 状态集合$I$的$\varepsilon$闭包：

$$\varepsilon-closure(I) = \{u|v经过<任意>条\varepsilon能够抵达u,其中v\in I\}$$

定义$3.3.2$ 状态集合$I$的$a$弧转换：

$$move(I,a) = \{u|v经过<一条>a弧可以抵达u,其中v \in I \}$$

3.3.1 子集法转换#

用确定的有穷自动机$M$的一个状态来对应不确定自动机$N$的一组状态。

把不确定有穷自动机$N = (K,\Sigma,f,K_0,K_t)$转换为确定的有穷自动机$M = (S,\Sigma,D,S_0,S_t)$：

如果是手算，一般是构建一个表格。

横行是输入字符集，纵列是状态集合。

3.4 DFA的最小化#

定义$3.4.1$ 当一个DFA既没有多余状态，也没有等价状态时，该$DFA$是化简了的，也是最小化了的。

最小化$DFA$的步骤有2步！！

1. 消除多余状态
2. 合并等价状态

3.4.1 消除多余状态#

定义$3.4.2$ 有穷自动机的多余状态是

1. 从开始状态出发无法到达的状态。
2. 从该状态出发无法到达终止状态的状态。

对于这2种多余状态的处理办法是: 简单地去掉该节点和和该节点相关的边即可。

建议还是先$bfs$找出多余的状态。

3.4.2 合并等价状态#

定义$3.4.3$ 有穷自动机的状态$u$和$v$是等价状态，当且仅当$u,v$满足：

$$\begin{align} &1. u和v同时是终止状态(可接受状态)或者同时是非终止状态(不可接受状态)。 \\ &2. \forall a \in (\Sigma \cup\varepsilon), u和v必须由a弧上转移到等价的状态上。 \end{align}$$

定义$3.4.4$ 有穷自动机的状态$u$和$v$如果不等价，则称状态$u$和$v$是可区分的。

好用的结论：

1. 一致性条件: 如果状态$u$和状态$v$的所有后继都一样，则$u$和$v$一定等价。
2. 蔓延性条件: 如果状态$u$和状态$v$对于某一输入字符(非空串)，一个有后继而另一个没有，则则$u$和$v$一定可区分。

用来合并不含多余状态的DFA(也没有空弧)的等价状态的方法是分割法: 一个一个把不等价的状态从等价集合中分开。

执行步骤:

3.5 正规式和有穷自动机的等价性#

定理$3.5.1$ 对于任何一个不确定的有穷自动机(NFA)$M$，一定存在一个相同$\Sigma$上的正规式$r$，使得$L(r) = L(M)$。

定理$3.5.2$ 对于任何一个正规式$r$，一定存在一个相同$\Sigma$上的不确定的有穷自动机(NFA)$M$，使得$L(M) = L(r)$。

3.5.1 不确定有穷自动机$M$转换为等价的正规式$r$#

3.5.1.1 添加新的节点$x$和$y$#

在原不确定有穷自动机$M$中添加两个新的节点$x$和$y$，其中$x$向每一个起始节点添加一条$\varepsilon$弧，每个终止节点向$y$添加一条$\varepsilon$弧。

3.5.1.2 将自动机的弧转换为正规式，直至只剩下节点$x$和$y$#

1. 顺序

2. 选择

3. 循环

最后节点$x$和$y$上弧的正规式就是最后的答案。

3.5.2 正规式$r$转换为等价的不确定有穷自动机$M$#

这个过程有点像结构化编程。把正规式$r$自顶向下分解。这个过程也叫做**“语法制导”**。

Attention: 弧上不能出现$a|b$，而$a,b$是可以接受的。。

3.5.2.0 基本转换#

1. $\varnothing$表达式

2. $r = \varepsilon$

3. $r = a, a \in \Sigma$

3.5.2.1 顺序 $r = r_1r_2$#

将一个正规式的终止节点和另一个正规式的起始节点连接起来

3.5.2.2 选择 $r = r_1 | r_2$#

让起始节点$x$分别空弧连接到两个正规式的起始节点，再从每一个正规式的终止节点连空弧到终止节点$y$

3.5.2.3 循环 $r = r_1^*$#

从$r_1$的终止节点连接一条空弧到$r_1$的初始节点。

从初始节点$x$到终止节点$y$非常重要！！($r_1^*$)，否则是$r_1^+$

有时可以思考能否像下面的情况一样尽量简化一些:

少一些空弧总是好的！

3.6 正规文法和不确定有穷自动机的等价性#

定理$3.6.1$ 从正规文法$G$可以直接构造一个等价的不确定的有穷自动机$M$，从不确定有穷自动机$M$也可以直接构造出一个等价的正规文法$G$

3.6.1 从正规文法$G$中导出不确定有穷自动机$M$#

一般只考虑形如$A \to aB, \ a\in(\Sigma \cup\{\varepsilon\})$的正规式。

正规文法$G(V_N,V_T,P,S)$到不确定有穷自动机$M(K,\Sigma,f,K_S,K_Z)$转换。

1. $K = V_N$: 将非终结符集作为状态集合。
2. $\Sigma = V_T$: 字符表即终结符集合
3. $K_S = \{S\}$: 起始状态集合仅包含开始符号$S$
4. 添加一个新的状态Z作为唯一的终止状态。
5. 对每一条形如$A \to aB$的产生式添加一条从状态$A$到状态$B$的$a$弧（$f(A,a) = B$)。
6. 对每一条形如$A \to a$的产生式添加一条从状态$A$到终止状态$Z$的$a$弧。

大功告成！

3.6.2 从不确定有穷自动机$M$中导出正规文法$G$​#

M不能有空弧，且只能有一个起始状态，否则将不为正规文法。

确定的有穷自动机$M(K,\Sigma,f,S,Z)$转换为正规文法$G(V_N,V_T,P,S)$

1. $V_N = K$: 非终结符集合就是状态集合
2. $V_T = \Sigma$: 终结符集合就是字符表
3. $S = S$ :开始符就是起始状态
4. 对于$A$通过$a$弧转换为状态$B$的状态转换函数$f(A,a) = B$，添加一条$A \to aB$的产生式
5. 对于终止状态$Z$，添加一条$Z \to \varepsilon$的产生式

大功告成！