第三章 词法分析

词法分析程序的功能及实现方案

1.功能

①根据词法规则识别及组合单词，进行词法检查。
②对数字常数完成数字字符串到（二进制）数值的转换。
③删去空格字符和注解。

2.实现方案

（1）词法分析单独作为一遍

（2）词法分析程序作为单独的子程序

单词的种类及词法分析程序的输出形式

1.单词的种类

1. 保留字：begin、end、for、do…
2. 标识符
3. 常数：无符号数、布尔常数、字符串常数等
4. 分界符：+、-、*、/

2.词法分析程序的输出形式

几种常用的单词内部形式：
1、按单词种类分类

2、保留字和分界符采用一符一类

3、标识符和常数的单词值可为指示字（指针值）

正则文法和状态图

1.状态图的画法（根据文法画出状态图）

例如：正则文法
Z::= U0 | V1
U ::=Z1 | 1
V ::=Z0 | 0
左线性文法
L(G[Z]) = { Bn | n>0 }, 其中 B= {01,10}

画法：

结果：

个人理解：每一次状态转换相当于一次规约，箭头上面的Vt是当前读入符号。

2.识别算法（自然语言描述）

利用状态图可按如下步骤分析和识别字符串x：
1、置初始状态为当前状态，从x的最左字符开始，重
复步骤2，直到x右端为止。
2、扫描x的下一个字符，在当前状态所射出的弧中找
出标记有该字符的弧，并沿此弧过渡到下一个状态；
如果找不到标有该字符的弧，那么x不是句子，过程到此结束；
如果扫描的是x的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态Z，则x是句子。

正则表达式与有穷自动机

1.正则表达式和正则集合的递归定义

正则表达式是正则语言的一种更简洁的表示方式。形式语言和自动机理论已经证明，正则文法和正则表达式是等价的。

注意：
①正则表达式ε对应正则文法的文法规则有一条：Z::=ε；
②正则表达式对应正则文法的文法规则为空；

正则表达式中的运算符：
| ：或（选择）
• ：连接
星号和{ }：重复
（）：括号（元符号）
运算符的优先级：
先星号， 后 • ， 最后 | ，• 在正则表达式中可以省略。
注意：正则表达式相等<=>这两个正则表达式表示的语言相等。

正则表达式的性质

2.正则文法 => 正则表达式

利用以下转换规则，直至只剩下一个开始符号定义的产生式，并且产生式的右部不含非终结符：

规则	文法产生式	正则式
规则1	A→xB, B→y	A=xy
规则2	A→xA I y	A=x*y
规则3	A→x, A→y	A=x I y

例：有文法G [ s ]
S→a A | a
A→a A | d A | a | d
于是：S = a A | a
A= ( a A | d A ) | ( a | d )
=> A = ( a | d ) A | ( a | d )
由规则二： A= ( a | d )* ( a | d )
代入：S = a ( ( a | d )* ( a | d ) ) | a
于是：S = a ( ( a | d )* ( a | d ) |ε)

3.正则表达式 => 正则文法

算法：

1. 对任何正则式 r，选择一个非终结符S作为识别符号，并产生产生式 S→r
2. 若x, y是正则式，对形为A→x y的产生式，重写为A→xB和B→y，其中B为新的非终结符，B∈Vn
   同样，对于
   A→x* y => A→xA A→y
   A→x | y => A→x A→y

4.确定有穷自动机（DFA）

一个确定的有穷自动机（DFA）M是一个五元式:M = ( S , Σ，δ, s0, Z )
其中:

1. S — 有穷状态集
2. Σ — 输入字母表
3. δ — 映射函数(也称状态转换函数)
   S×Σ→S
   δ(s, a) = s’ s, s’ ∈S, a∈Σ
4. s0 — 初始状态 s0 ∈S
5. Z— 终止状态集 Z是S的子集

例如: M: ({ 0, 1, 2, 3 }, { a, b }, δ，0，{3} )
δ( 0，a ) = 1 δ( 0，b ) =2
δ( 1，a ) = 3 δ( 1，b ) =2
δ( 2，a ) = 1 δ( 2，b ) =3
δ( 3，a ) = 3 δ( 3，b ) =3
状态转移函数δ可用一矩阵来表示：

注：所谓确定的状态机，其确定性表现在状态转移函数是单值函数！
一个DFA也可以用一个状态转换图表示：

DFA M所接受的符号串：
令α= a1 a2…an，α∈Σ*，若δ(δ(…δ(δ(s0,a1),a2)…,an-1),an)= sn, 且sn∈Z
则可以写成δ(s0, α) =sn, 我们称α可为M所接受。
自然语言描述：换言之，若存在一条从初始状态到某一终止状态的路径，且这条路径上所有弧的标记符连接成符号串α,则称α为DFA M(接受)识别。
DFA M所接受的语言为：L(M)={α|δ(s0,α)= sn, sn∈Z}

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

若δ是一个多值函数，且输入可允许为ε，则有穷自动机是不确定的。即在某个状态下，对于某个输入字符存在多个后继状态。
NFA的形式定义：
一个非确定的有穷自动机NFA M’是一个五元式:
NFA M’ = ( S, Σ∪{ε}, δ, S0, Z )
其中 S — 有穷状态集
Σ∪{ε}—输入符号加上ε，即自动机的每个结点所射出
的弧可以是Σ中的一个字符或是ε。
S0 — 初态集
Z — 终态集
δ— 转换函数 S×Σ∪{ε} →2S
(2S ：S的幂集—S的子集构成的集合）
NFA M’所接受的语言为:L(M’) = {α |δ(S0 ,α) = S’ S’∩Z≠Φ}

6.NFA的确定化

非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的。也就是说，我们能够：

为了使得NFA确定化，我们首先给出两个定义：
（1）集合 I 的 ε-闭包
令 I 是一个状态集的子集，定义ε- closure(I)为：
①若s∈I，则s∈ε- closure(I)；
②若s∈I，则从 s 出发经过任意条ε弧能够到达的任何状态都属于ε- closure(I)。状态集ε- closure(I)称为 I 的ε-闭包。
（2）令 I 是NFA M’的状态集的一个子集，a∈Σ
定义: Ia = ε- closure(J)其中J = ∪δ(s, a) S∈I
自然语言：
①J 是从状态子集 I 中的每个状态出发，经过标记为 a 的弧而达到的状态集合。
②Ia是状态子集，其元素为 J 中的状态，加上从 J 中每一个状态出发通过 ε 弧到达的状态。

根据上述定义（1）、（2），可以将上述的M’确定化。然后，将求得的状态转换矩阵重新编号，得到DFA M状态转换矩阵。并可根据状态转换矩阵画出DFA M的状态图。至此，NFA确定化成功。

7.正则表达式与DFA的等价性

定理：在Σ上的一个字集V（V是Σ*的子集）是正则集合，当且仅当存在一个DFA M，使得V = L( M )。

（1）有穷自动机 => (右线性)正则文法

算法：
1.对转换函数f (A, t) = B，可写成一个产生式:A→tB
2.对可接受状态Z，增加一个产生式：Z→ε
3.有穷自动机的初态对应于文法的开始符号，有穷自动机的字母表为文法的终结符号集。

（2）（右线性）正则文法 => 有穷自动机M

算法:

1. 字母表与G的终结符号相同。
2. 为G中的每个非终结符生成M的一个状态，G的开始符号S是开始状态S。
3. 增加一个新状态Z，作为NFA的终态。
4. 对G中的形如A→tB，其中t为终结符或ε, A和B为非终结符的产生式，构造M的一个转换函数f (A, t) = B。
5. 对G中的形如A→t的产生式，构造M的一个转换函数f (A, t) = Z。

（3）正则式 => 有穷自动机

语法制导方法：
Step 1.
（a）对于正则式φ,所构造NFA:

（b）对于正则式ε,所构造NFA:

（c）对于正则式a, a∈Σ,则 NFA:

step 2.
若s,t为Σ上的正则式,相应的NFA分别为N(s)和N(t);
（a）对于正则式R = s | t , NFA®：

（b）对正则式R = s·t , NFA®：

（c）对于正则式R = s*, NFA®：

（d）对R = ( s )，与R = S的NFA一样。

（4）有穷自动机 => 正则式

算法:
1)在M上加两个结点x, y。从x用ε弧连接到M的所有初态结点，从M的所有终态结点用ε弧连接到y，形成与M等价的M’。M’只有一个初态x和一个终态y。
2)逐步消去M’中的所有结点，直至剩下x和y为止。在消除结点的过程中，逐步用正则式来标记箭弧。其消结规则如下：

5.DFA的简化（极小化）

定义：对于任一个DFA，存在一个唯一的状态最少的等价的DFA，它叫做该DFA简化（极小化）后的DFA。
定理：一个有穷自动机是化简的 <=> 它没有多余状态并且它的状态中没有两个是互相等价的
方法：一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。

(1) 有穷自动机的多余状态：从该自动机的开始状态出发,任何输入串也不能到达那个状态。
消除方法：画状态转换矩阵或状态图。
(2) 等价状态（状态 s 和 t 等价 的条件是满足：
①一致性条件：状态 s 和 t 必须同时为可接受状态或不接受状态。
②蔓延性条件：对于所有输入符号，状态 s 和 t 必须转换到等价的状态里。

即有：对于所有输入符号c，Ic(s) = Ic(t)，即状态 s、t 对于c具有相同的后继，则称 s，t 是等价的。

简化步骤：
①作出待简化DFA，按照终态与否划分初始的两个区

②将字汇表依次输入各状态，检查各区中状态之间的后继集合是否完全相同。如果不同，则开一个新区，将相应状态划分开。反复进行这一动作，直到在也分不出更多的区。
例：


③最后得到的每一个区就是简化后的DFA的各个状态，用区号代替状态号，可得到最终的状态转换矩阵，并可根据它画出状态转换图。