2.3.1 对于词法分析器的要求一、词法分析器的功能和输出形式功能,输入源程序、输出单词符号输出的单词符号的表示形式,
(单词种别，单词自身的值 )
单词符号的种类：
基本字：如 begin,repeat,?
标识符 ——表示各种名字：如变量名、数组名和过程名
常数：各种类型的常数
运算符,+,-,*,/,?
界符：逗号、分号、括号和空白词法分析例 C程序
while (i>=j) i--;
输出单词符号：
<while,->
<(,->
<id,指向 i的符号表项的指针 >
<>=,->
<id,指向 j的符号表项的指针 >
<),->
<id,指向 i的符号表项的指针 >
<--,->
<;,->
例 FORTRAN程序
IF (5.EQ.M) GOTO 100
输出单词符号：
逻辑 IF (34,-)
左括号 (2,-)
整常数 (20,‘ 5?的二进制 )
等号 (6,-)
标识符 (26,‘ M?)
右括号 (16,-)
GOTO (30,-)
标号 (19,‘ 100?的二进制 )
词法分析器与语法分析器的关系词法分析器语法分析器符号表源程序单词符号取下一单词
...
词法分析器的结构预处理子程序扫描器输入缓冲区扫描缓冲区单词符号输入 列表
2.3.2 词法分析器的设计输入串放在输入缓冲区中。
预处理子程序：剔除无用的空白,跳格,
回车和换行等编辑性字符 ;区分标号区,
捻接续行和给出句末符等扫描缓冲区
↑ ↑
起点 搜索指示器 指示器一、输入、预处理二、单词符号的识别,超前搜索
1 基本字识别,
例如 FORTRAN语言中关键字不加以特殊保护,
1 DO99K=1,10
2 DO99K=1.10
3 IF(5.EQ.M)GOTO55
4 IF(5)=55
5 IF(M)10,5,6
都正确,需要超前搜索才能确定哪些是基本字单词符号的识别,超前搜索逻辑 IF语句的一般形式：
IF〈 条件 〉 语句
例,IF (N.LE.100) N=N+1
算术 IF语句
一般形式,IF〈 算术表达式 〉 N1,N2,N3
当算术表达式的值小于 0时执行标号为 N1的语句，
等于 0时执行标号为 N2的语句，大于 0时执行标号为
N3的语句。
2 标识符识别,
字母开头的字母数字串，后跟界符或算符
3 常数识别,
识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。
5.EQ.M
5.E08
逻辑常数和用引号括起来的字符串常数一般都好识别，但 FORTRAN的文字常数的识别较麻烦，如,3HABC。
当分析器读到尾跟 H的无符号常数时要先把该常数的值翻译出来，然后把 H后的ｎ个字符作为字符串常数输出。
4 算符和界符的识别
把多个字符符合而成的算符和界符拼合成一个单一单词符号。
,=,**,.EQ.,++,--,>=
三,状态转换图
1 概念状态转换图是一张有限方向图。
21
3
X
Y
结点代表状态，用圆圈表示 。
状态之间用箭弧连结，箭弧上的标记 (字符 )代表射出结状态下可能出现的输入字符或字符类。
一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。
识别标识符的状态转换图
1 2 3字母 其他字母或数字
*
识别 整常数 的状态转换图
1 2 3数字 其他数字
*
一个状态转换图可用于识别 (或接受 )一定的字符串。
识别 FORTRAN实型常数的
DFA
实数有两种表示形式：
小数形式：即日常习惯使用的小数形式。
3.141592 -0.125 3.0 -2,等
指数形式：用指数形式表示的实数由两部分组成，即数字部分和指数部分。
7.8E-12 -0.125E5
0.125D+45(双精度,8字节 )
识别 FORTRAN实型常数的
DFA
几点重要限制 ——不必使用超前搜索
所有基本字都是保留字 ;
基本字作为特殊的标识符来处理 ; 只需查保留字表 。
如果基本字,标识符和常数 (或标号 )之间没有确定的运算符或界符作间隔,则必须使用一个空白符作间隔 。
DO99K=1,10
要写成 DO 99 K=1,10
3 状态转换图的实现思想：每个状态结对应一小段程序。
做法,
1)对不含回路的分叉结，可用一个 CASE语句或一组 IF-THEN-ELSE语句实现
2)对含回路的状态结，可对应一段由 WHILE结构和 IF语句构成的程序,
3)终态结表示识别出某种单词符号，因此，对应语句为
RETURN (C,VAL)
其中,C为单词种别,VAL为单词自身值,
全局变量与过程
1)ch 字符变量、存放最新读入的源程序字符
2)strToken 字符数组，存放构成单词符号的字符串
3)GetChar 子程序过程，把下一个字符读入到 ch 中
4)GetBC 子程序过程，跳过空白符，直至
ch 中读入一非空白符
5)Concat 子程序，把 ch中的字符连接到
strToken
6)IsLetter和 IsDisgital 布尔函数，判断
ch中字符是否为字母 和数字
7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送 0
8) Retract 子程序，把搜索指针回调一个字符位置
9)InsertId 整型函数，将 strToken中的标识符插入符号表，返回符号表指针
10)InsertConst 整型函数过程，将
strToken中的常数插入常数表，返回常数表指针。
1 2
3 4
5
6
7 8
9
10
11
12
13
0
空白字母字母或数字非字母与数字数字 非数字数字
=
+
* 非 *
,
(
)
其它
*
*
*
*
int code,value;strToken,=,,; /*置 strToken为空串 */
GetChar(); GetBC();
if (IsLetter())
begin
while (IsLetter() or IsDigit())
begin
Concat(); GetChar();
end
Retract();
code,= Reserve();
if (code = 0) /*不在保留字表中 */
begin
value,= InsertId(strToken);
return ($ID,value);
end
else
return (code,-);
end
else if (IsDigit())
begin
while (IsDigit())
begin
Concat( ); GetChar( );
end
Retract();
value,= InsertConst(strToken);
return($INT,value);
end
else if (ch =?=?) return ($ASSIGN,-);
else if (ch =?+?) return ($PLUS,-);
else if (ch =?*?)
begin
GetChar();
if (ch =?*?) return ($POWER,-);
Retract(); return ($STAR,-);
end
else if (ch =?;?) return ($SEMICOLON,-);
else if (ch =?(?) return ($LPAR,-);
else if (ch =?)?) return ($RPAR,-);
else if (ch =?{?) return ($LBRACE,-);
else if (ch =?}?) return ($RBRACE,-);
else ProcError( ); /* 错误处理 */
2.3.3.1 正规式和正规集正规集可以用正规表达式 （ 简称正规式 ）
表示 。
正规表达式是表示正规集一种方法 。 一个字集合是正规集当且仅当它能用正规式表示 。
正规表达式与有限自动机正规式和正规集的递归定义：
对给定的字母表?
1)? 和?都是?上的正规式，它们所表示的正规集为 {?}和?;
2) 任何 a,a是?上的正规式，它所表示的正规集为 {a};
3) 假定 e1和 e2都是?上的正规式，它们所表示的正规集为 L(e1)和 L(e2)，则
i) (e1|e2)为正规式，它所表示的正规集为
L(e1)?L(e2)，
ii) (e1.e2)为正规式，它所表示的正规集为
L(e1)L(e2)，
iii) (e1)*为正规式，它所表示的正规集为 (L(e1))*，
仅由 有限次 使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式表示的字集才是?上的正规集。
所有词法结构一般都可以用正规式描述 。
若两个正规式所表示的正规集相同,则称这两个正规式等价 。 如
b(ab)*=(ba)*b (a*b*)*=(a|b)*
对正规式，下列等价成立：
e1|e2 = e2|e1 交换律
e1 |(e2|e3) = (e1|e2)|e3 结合律
e1(e2e3) = (e1e2)e3 结合律
e1(e2|e3) = e1e2|e1e3 分配律
(e2|e3)e1 = e2e1|e3 e1 分配律
e? =? e = e e1e2 <> e2 e1
正则表达式的扩展
(1)一个或多个重复 +
例：长度大于 1的由 a或 b组成的串
(a|b)+
(2) 任意字符 (除回车换行）,
例：任意串
.*
以 b开头的任意串
b.*
(3) 字符范围 [ ]
长度大于 1的小写字母串 [a-z]+
a,b,c组成的长度大于 1的任意串 [abc]+
(4) 不在给定集合中的任意字符 ～
只有一个 b的任意串 (～ b)*b(～ b)*
(5) 可选的子表达式？
带符号整数 (+|-)？ [0-9]+
正则表达式的扩展
2.3.3.2 确定有限自动机
(DFA)
对状态图进行形式化,则可以下定义：
自动机 M是一个五元式 M=(S,?,f,S0,F),其中：
1,S,有穷状态集,
2,?：输入字母表 (有穷 )，
3,f,状态转换函数,为 SS的单值部分映射,
f(s,a)=s?表示：当现行状态为 s,输入字符为
a时,将状态转换到下一状态 s?。 我们把 s?称为
s的一个后继状态 。
4,S0?S是唯一的一个初态；
5 F?S,终态集 (可空 ),。
例如,DFA M=({0,1,2,3},{a,b}，
f,0,{3}),其中,f定义如下：
f(0,a)=1 f(0,b)=2
f(1,a)=3 f(1,b)=2
f(2,a)=1 f(2,b)=3
f(3,a)=3 f(3,b)=3
0 3
1
2
a
a
a a
状态转换图
b
b bb
a b
0 1 2
1 3 2
2 1 3
3 3 3
状态转换矩阵对于?*中的任何字?,若存在一条从初态到某一终态的道路,且这条路上所有弧上的标记符连接成的字等于?,则称?为 DFA
M所 识别 (接收 )
DFA M所识别的字的全体记为 L(M)。
可以证明,?上的字集 V*是正规集,当且仅当存在上的 DFA M,使得 V＝ L(M)。
程序设计语言与有穷自动机在程序设计语言中，标识符一般可定义为：
identifier= [a-z] [a-z0-9 ] *
识别这样的一个串的过程可表示为下图：
例：前后有花括号的注释可由以下的 DFA接受：
程序设计语言与有穷自动机有 C风格注释的有穷自动机
2.3.3.3 非确定有限自动机
(NFA)
定义：一个非确定有限自动机 (NFA) M是一个五元式 M=(S,?,f,S0,F),其中：
1 S,有穷状态集；
2?,输入字母表 (有穷 )；
3 f,状态转换函数,为 S*?2S的部分映射 (非单值 )；
4 S0?S是非空的初态集；
5 F?S,终态集 (可空 )。
从状态图中看 NFA和 DFA的区别：
1 弧上的标记可以是?*中的一个字,而不一定是单个字符；
2 同一个字可能出现在同状态射出的多条弧上 。
DFA是 NFA的特例 。
0
2
1
a,b
aa a,b
bb
a,b
0 1 2a b
a b
识别所有含相继两个 a
或相继两个 b的字
{ambn | m,n?1}
定义：对于任何两个有限自动机 M和 M?，
如果 L(M)=L(M?)，则称 M与 M?等价。
定理：对于每个 NFA M都存在一个 DFA
M?，使得 L(M)=L(M?)。
1,假定 NFA M=<S,?,?,S0,F>，我们对 M
的状态转换图进行以下改造：
1) 引进新的初态结点 X和终态结点 Y,X,Y?S，
从 X到 S0中任意状态结点连一条?箭弧,从
F中任意状态结点连一条?箭弧到 Y。
2) 对 M的状态转换图进一步施行替换，其中 k
是新引入的状态。
证明,
代之为 i kA B ji jAB
代之为i jA|B i j
B
A
代之为i j
A*
i k j
A
按下面的三条规则对 V进行分裂,
逐步把这个图转变为每条弧只标记为?上的一个字符或?，最后得到一个 NFA M?，
显然 L(M?)=L(M)
(a|b)*(aa|bb)(a|b)*
X Y(a|b)*(aa|bb)(a|b)*
X Y? 1 2
4
5
3
6
a
b
a
b
a
b
a
b
将正则式表示为 NFA
反复裂结，可得：
2,把上述 NFA确定化 ——采用子集法,
设 I是的状态集的一个子集，定义 I的?-闭包?-closure(I)为,
i) 若 s?I，则 s-closure(I)；
ii) 若 s?I,则从 s出发经过任意条?弧而能到达的任何状态 s?都属于?-closure(I)
即
-closure(I)=I?{s?|从某个 s?I出发经过任意条?弧能到达 s?}
设 a是?中的一个字符，定义
Ia=?-closure(J)
其中,J为 I中的某个状态出发经过一条 a
弧而到达的状态集合。
-closure({1})={1,3}=I
J={2,4,6}
Ia=?-closure(J)=(2,3,4,5,6,7,8)
5
1 a? 3 6
4
2
7
8
a
a
确定化的过程,
设字母表只包含两个 a和 b,X为初态，
构造如下表,
I I a I b
-C los ure ({X })
首先，置第 1行第 1列为?-closure({X})求出这一列的 Ia,Ib；
然后，检查这两个 Ia,Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第 1列上，求出每行第 2,3
列上的集合,..
重复上述过程，直至第 2,3列子集全部出现在第一列为止。
I Ia Ib
{X,1,2} {1,2,3} {1,2,4}
{1,2,3} {1,2,3,5,6,Y} {1,2,4}
{1,2,4} {1,2,3} {1,2,4,5,6,Y}
{1,2,3,5,6,Y} {1,2,3,5,6,Y} {1,2,4,6,Y}
{1,2,4,5,6,Y} {1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,4,6,Y} {1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,3,6,Y} {1,2,3,5,6,Y} {1,2,4,6,Y}
X Y? 1 2
4
5
3
6
a
b
a
b
a
b
a
b
这张表实际是一个状态转换矩阵，其中的每个子集是一个状态，它刻划了一个确定的有限自动机 M，初态是?-closure({X}),终态是含有原终态 Y的子集。
不难看出，这个 DFA M与 M?等价。
I a b
0 1 2
1 3 2
2 1 4
3 3 5
4 6 4
5 6 4
6 3 5
0
1
2
3
4
5
6
a a b
b b a
ba aba
b
a
b
2.3.3.5 正规式与有限自动机的等价性定理：
1,对任何 FA M，都存在一个正规式 r，使得 L(r)=L(M)。
2,对任何正规式 r，都存在一个 FA M，使得 L(M)=L(r)。
对转换图概念拓广，令每条弧可用一个正规式作标记。 (对一类输入符号 )
证明：
1 对?上任一 NFA M，构造一个?上的正规式 r，使得 L(r)=L(M)。
首先，在 M的转换图上加进两个状态 X和 Y，
从 X用?弧连接到 M的所有初态结点，从 M的所有终态结点用?弧连接到 Y，从而形成一个新的 NFA，记为 M?，它只有一个初态 X和一个终态 Y，显然 L(M)=L(M?)。
然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下 X和 Y为止；
代之为i jr1 r2 k i kr1r2
代之为 i jr1|r2i j
r2
r1
代之为 i k
r1r2*r2
i jr1 r3 k
r2
最后,X到 Y的弧上标记的正规式即为所构造的正规式 r，
显然 L(r)=L(M)=L(M?)
1
2
3
5
4U1
V1
U2
V2 W2
W1
1
2 5
4
V1(U1|U2)*W1
V1(U1|U2)*W2
V2(U1|U2)*W2
V2(U1|U2)*W1
证明 2,对于?上的正规式 r，构造一个
NFA M，使 L(M)=L(r)，并且 M只有一个终态，而且没有从该终态出发的箭弧。
下面使用关于 r中运算符数目的归纳法证明上述结论。 (Thompson结构法）
(1) 若 r具有零个运算符，则 r=?或 r=?或 r=a，其中 a。此时下图所示的三个有限自动机显然符合上述要求。
q0 q0 qf aq0 qf
(2) 假设结论对于少于 k(k?1)个运算符的正规式成立。
当 r中含有 k个运算符时,r有三种情形：
情形 1,r=r1|r2,r1,r2中运算符个数少于 k。
从而，由归纳假设，对 ri存在 Mi=<Si,?i,?i,
qi,{fi}>，使得 L(Mi)=L(ri)，并且 Mi没有从终态出发的箭弧（ i=1,2）。不妨设 S1∩ S2=?，
在 S1 ∪ S2中加入两个新状态 q0,f0。
令 M=<S1∪ S2∪ {q0,f0},?1∪?2,?,q0,{f0}>，其中?定义如下：
(a)?(q0,?)={q1,q2}
(b)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}
(c)?(q,a)=?2(q,a),当 q?S2-{f2},a2∪ {?}
(d)?(f1,?)=?(f2,?)={f0}。
M的状态转换如右图所示。
L(M)=L(M1)∪ L(M2)
=L(r1)∪ L(r2)=L(r)
q0 f0
M1q1 f1
M2q2 f2
情形 2,r=r1r2,设 Mi同情形 1(i=1,2)。
令 M=<S1∪ S2,?1∪?2,?,q1,{f2}>，其中?定义如下：
(a)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}。
(b)?(q,a)=?2(q,a),当 q?S2,a2∪ {?}。
(c)?(f1,?)={q2}。
M的状态转换如右图所示。
L(M)=L(M1)L(M2)
=L(r1)L(r2)=L(r)。
M1q1 f1 M2q2 f2
情形 3,r=r1*。设 M1同情形 1。
令 M=<S1∪ {q0,f0},?1,?,q0,{f0}>，其中 q0,
f0?S1,?定义如下：
(a)?(q0,?)=?(f1,?)={q1,f0}
(b)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}。
M的状态转换如右图所示。
L(M) = L(M1)* = L(r1)* = L(r)
至此，结论 2获证。
M1q1 f1
q0 f0
上述证明过程实质上是一个将正规表达式转换为有限自动机的算法，前面介绍的裂结法也可以完成该转换。
2.3.3.6 确定有限自动机的化简对 DFA M的化简,寻找一个状态数比 M少的 DFA M?，使得 L(M)=L(M?)
假设 s和 t为 M的两个状态，称 s和 t等价,
如果从状态 s出发能读出某个字?而停止于终态，那么同样，从 t出发也能读出?
而停止于终态；反之亦然。
两个状态不等价，则称它们是 可区别 的。
DFA M最小化的基本思想,
把 M的状态集划分为一些不相交的子集，
使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。
具体做法,对 M的状态集进行划分
首先，把 S划分为终态和非终态两个子集，
形成基本划分?;
假定到某个时候,?已含 m个子集，记为
={I(1),I(2),?,I(m)}，检查?中的每个子集看是否能进一步划分 ;
对某个 I(i)，令 I(i)={s1,s2,?,sk}，若存在一个输入字符 a使得 Ia(i)不会包含在现行?的某个子集 I(j)中，则至少应把 I(i)分为两个部分。
例如，假定状态 s1和 s2经 a弧分别到达 t1和
t2，而 t1和 t2属于现行?中的两个不同子集，
说明有一个字?,t1读出?后到达终态，而
t2读出?后不能到达终态，或者反之，那么对于字 a?,s1读出 a?后到达终态，而
s2读出 a?不能到达终态，或者反之，所以
s1和 s2不等价。则将分成两半，使得一半含有 s1:
I(i1)={s|s?I(i)且 s经 a弧到达 t,
且 t与 t1属于现行?中的同一子集 }
另一半含有 s2,I(i2)=I(i)-I(i1)
一般地，对某个 a和 I(i)，若 Ia(i)落入现行?中 N
个不同子集，则应把 I(i)划分成 N个不相交的组，
使得每个组 J的 Ja都落入的?同一子集。这样构成新的划分。
重复上述过程，直到?所含子集数不再增长。
对于上述最后划分?中的每个子集，我们选取每个子集 I中的一个状态代表其他状态，则可得到化简后的 DFA M?。
若 I含有原来的初态，则其代表为新的初态，
若 I含有原来的终态，则其代表为新的终态 。
0
1
2
3
5
4
6
a a b
b b a
ba aba
b
a
b
0
1
2
3
a a
b b
ba
a
b
(单词种别，单词自身的值 )
单词符号的种类：
基本字：如 begin,repeat,?
标识符 ——表示各种名字：如变量名、数组名和过程名
常数：各种类型的常数
运算符,+,-,*,/,?
界符：逗号、分号、括号和空白词法分析例 C程序
while (i>=j) i--;
输出单词符号：
<while,->
<(,->
<id,指向 i的符号表项的指针 >
<>=,->
<id,指向 j的符号表项的指针 >
<),->
<id,指向 i的符号表项的指针 >
<--,->
<;,->
例 FORTRAN程序
IF (5.EQ.M) GOTO 100
输出单词符号：
逻辑 IF (34,-)
左括号 (2,-)
整常数 (20,‘ 5?的二进制 )
等号 (6,-)
标识符 (26,‘ M?)
右括号 (16,-)
GOTO (30,-)
标号 (19,‘ 100?的二进制 )
词法分析器与语法分析器的关系词法分析器语法分析器符号表源程序单词符号取下一单词
...
词法分析器的结构预处理子程序扫描器输入缓冲区扫描缓冲区单词符号输入 列表
2.3.2 词法分析器的设计输入串放在输入缓冲区中。
预处理子程序：剔除无用的空白,跳格,
回车和换行等编辑性字符 ;区分标号区,
捻接续行和给出句末符等扫描缓冲区
↑ ↑
起点 搜索指示器 指示器一、输入、预处理二、单词符号的识别,超前搜索
1 基本字识别,
例如 FORTRAN语言中关键字不加以特殊保护,
1 DO99K=1,10
2 DO99K=1.10
3 IF(5.EQ.M)GOTO55
4 IF(5)=55
5 IF(M)10,5,6
都正确,需要超前搜索才能确定哪些是基本字单词符号的识别,超前搜索逻辑 IF语句的一般形式：
IF〈 条件 〉 语句
例,IF (N.LE.100) N=N+1
算术 IF语句
一般形式,IF〈 算术表达式 〉 N1,N2,N3
当算术表达式的值小于 0时执行标号为 N1的语句，
等于 0时执行标号为 N2的语句，大于 0时执行标号为
N3的语句。
2 标识符识别,
字母开头的字母数字串，后跟界符或算符
3 常数识别,
识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。
5.EQ.M
5.E08
逻辑常数和用引号括起来的字符串常数一般都好识别，但 FORTRAN的文字常数的识别较麻烦，如,3HABC。
当分析器读到尾跟 H的无符号常数时要先把该常数的值翻译出来，然后把 H后的ｎ个字符作为字符串常数输出。
4 算符和界符的识别
把多个字符符合而成的算符和界符拼合成一个单一单词符号。
,=,**,.EQ.,++,--,>=
三,状态转换图
1 概念状态转换图是一张有限方向图。
21
3
X
Y
结点代表状态，用圆圈表示 。
状态之间用箭弧连结，箭弧上的标记 (字符 )代表射出结状态下可能出现的输入字符或字符类。
一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。
识别标识符的状态转换图
1 2 3字母 其他字母或数字
*
识别 整常数 的状态转换图
1 2 3数字 其他数字
*
一个状态转换图可用于识别 (或接受 )一定的字符串。
识别 FORTRAN实型常数的
DFA
实数有两种表示形式：
小数形式：即日常习惯使用的小数形式。
3.141592 -0.125 3.0 -2,等
指数形式：用指数形式表示的实数由两部分组成，即数字部分和指数部分。
7.8E-12 -0.125E5
0.125D+45(双精度,8字节 )
识别 FORTRAN实型常数的
DFA
几点重要限制 ——不必使用超前搜索
所有基本字都是保留字 ;
基本字作为特殊的标识符来处理 ; 只需查保留字表 。
如果基本字,标识符和常数 (或标号 )之间没有确定的运算符或界符作间隔,则必须使用一个空白符作间隔 。
DO99K=1,10
要写成 DO 99 K=1,10
3 状态转换图的实现思想：每个状态结对应一小段程序。
做法,
1)对不含回路的分叉结，可用一个 CASE语句或一组 IF-THEN-ELSE语句实现
2)对含回路的状态结，可对应一段由 WHILE结构和 IF语句构成的程序,
3)终态结表示识别出某种单词符号，因此，对应语句为
RETURN (C,VAL)
其中,C为单词种别,VAL为单词自身值,
全局变量与过程
1)ch 字符变量、存放最新读入的源程序字符
2)strToken 字符数组，存放构成单词符号的字符串
3)GetChar 子程序过程，把下一个字符读入到 ch 中
4)GetBC 子程序过程，跳过空白符，直至
ch 中读入一非空白符
5)Concat 子程序，把 ch中的字符连接到
strToken
6)IsLetter和 IsDisgital 布尔函数，判断
ch中字符是否为字母 和数字
7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送 0
8) Retract 子程序，把搜索指针回调一个字符位置
9)InsertId 整型函数，将 strToken中的标识符插入符号表，返回符号表指针
10)InsertConst 整型函数过程，将
strToken中的常数插入常数表，返回常数表指针。
1 2
3 4
5
6
7 8
9
10
11
12
13
0
空白字母字母或数字非字母与数字数字 非数字数字
=
+
* 非 *
,
(
)
其它
*
*
*
*
int code,value;strToken,=,,; /*置 strToken为空串 */
GetChar(); GetBC();
if (IsLetter())
begin
while (IsLetter() or IsDigit())
begin
Concat(); GetChar();
end
Retract();
code,= Reserve();
if (code = 0) /*不在保留字表中 */
begin
value,= InsertId(strToken);
return ($ID,value);
end
else
return (code,-);
end
else if (IsDigit())
begin
while (IsDigit())
begin
Concat( ); GetChar( );
end
Retract();
value,= InsertConst(strToken);
return($INT,value);
end
else if (ch =?=?) return ($ASSIGN,-);
else if (ch =?+?) return ($PLUS,-);
else if (ch =?*?)
begin
GetChar();
if (ch =?*?) return ($POWER,-);
Retract(); return ($STAR,-);
end
else if (ch =?;?) return ($SEMICOLON,-);
else if (ch =?(?) return ($LPAR,-);
else if (ch =?)?) return ($RPAR,-);
else if (ch =?{?) return ($LBRACE,-);
else if (ch =?}?) return ($RBRACE,-);
else ProcError( ); /* 错误处理 */
2.3.3.1 正规式和正规集正规集可以用正规表达式 （ 简称正规式 ）
表示 。
正规表达式是表示正规集一种方法 。 一个字集合是正规集当且仅当它能用正规式表示 。
正规表达式与有限自动机正规式和正规集的递归定义：
对给定的字母表?
1)? 和?都是?上的正规式，它们所表示的正规集为 {?}和?;
2) 任何 a,a是?上的正规式，它所表示的正规集为 {a};
3) 假定 e1和 e2都是?上的正规式，它们所表示的正规集为 L(e1)和 L(e2)，则
i) (e1|e2)为正规式，它所表示的正规集为
L(e1)?L(e2)，
ii) (e1.e2)为正规式，它所表示的正规集为
L(e1)L(e2)，
iii) (e1)*为正规式，它所表示的正规集为 (L(e1))*，
仅由 有限次 使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式表示的字集才是?上的正规集。
所有词法结构一般都可以用正规式描述 。
若两个正规式所表示的正规集相同,则称这两个正规式等价 。 如
b(ab)*=(ba)*b (a*b*)*=(a|b)*
对正规式，下列等价成立：
e1|e2 = e2|e1 交换律
e1 |(e2|e3) = (e1|e2)|e3 结合律
e1(e2e3) = (e1e2)e3 结合律
e1(e2|e3) = e1e2|e1e3 分配律
(e2|e3)e1 = e2e1|e3 e1 分配律
e? =? e = e e1e2 <> e2 e1
正则表达式的扩展
(1)一个或多个重复 +
例：长度大于 1的由 a或 b组成的串
(a|b)+
(2) 任意字符 (除回车换行）,
例：任意串
.*
以 b开头的任意串
b.*
(3) 字符范围 [ ]
长度大于 1的小写字母串 [a-z]+
a,b,c组成的长度大于 1的任意串 [abc]+
(4) 不在给定集合中的任意字符 ～
只有一个 b的任意串 (～ b)*b(～ b)*
(5) 可选的子表达式？
带符号整数 (+|-)？ [0-9]+
正则表达式的扩展
2.3.3.2 确定有限自动机
(DFA)
对状态图进行形式化,则可以下定义：
自动机 M是一个五元式 M=(S,?,f,S0,F),其中：
1,S,有穷状态集,
2,?：输入字母表 (有穷 )，
3,f,状态转换函数,为 SS的单值部分映射,
f(s,a)=s?表示：当现行状态为 s,输入字符为
a时,将状态转换到下一状态 s?。 我们把 s?称为
s的一个后继状态 。
4,S0?S是唯一的一个初态；
5 F?S,终态集 (可空 ),。
例如,DFA M=({0,1,2,3},{a,b}，
f,0,{3}),其中,f定义如下：
f(0,a)=1 f(0,b)=2
f(1,a)=3 f(1,b)=2
f(2,a)=1 f(2,b)=3
f(3,a)=3 f(3,b)=3
0 3
1
2
a
a
a a
状态转换图
b
b bb
a b
0 1 2
1 3 2
2 1 3
3 3 3
状态转换矩阵对于?*中的任何字?,若存在一条从初态到某一终态的道路,且这条路上所有弧上的标记符连接成的字等于?,则称?为 DFA
M所 识别 (接收 )
DFA M所识别的字的全体记为 L(M)。
可以证明,?上的字集 V*是正规集,当且仅当存在上的 DFA M,使得 V＝ L(M)。
程序设计语言与有穷自动机在程序设计语言中，标识符一般可定义为：
identifier= [a-z] [a-z0-9 ] *
识别这样的一个串的过程可表示为下图：
例：前后有花括号的注释可由以下的 DFA接受：
程序设计语言与有穷自动机有 C风格注释的有穷自动机
2.3.3.3 非确定有限自动机
(NFA)
定义：一个非确定有限自动机 (NFA) M是一个五元式 M=(S,?,f,S0,F),其中：
1 S,有穷状态集；
2?,输入字母表 (有穷 )；
3 f,状态转换函数,为 S*?2S的部分映射 (非单值 )；
4 S0?S是非空的初态集；
5 F?S,终态集 (可空 )。
从状态图中看 NFA和 DFA的区别：
1 弧上的标记可以是?*中的一个字,而不一定是单个字符；
2 同一个字可能出现在同状态射出的多条弧上 。
DFA是 NFA的特例 。
0
2
1
a,b
aa a,b
bb
a,b
0 1 2a b
a b
识别所有含相继两个 a
或相继两个 b的字
{ambn | m,n?1}
定义：对于任何两个有限自动机 M和 M?，
如果 L(M)=L(M?)，则称 M与 M?等价。
定理：对于每个 NFA M都存在一个 DFA
M?，使得 L(M)=L(M?)。
1,假定 NFA M=<S,?,?,S0,F>，我们对 M
的状态转换图进行以下改造：
1) 引进新的初态结点 X和终态结点 Y,X,Y?S，
从 X到 S0中任意状态结点连一条?箭弧,从
F中任意状态结点连一条?箭弧到 Y。
2) 对 M的状态转换图进一步施行替换，其中 k
是新引入的状态。
证明,
代之为 i kA B ji jAB
代之为i jA|B i j
B
A
代之为i j
A*
i k j
A
按下面的三条规则对 V进行分裂,
逐步把这个图转变为每条弧只标记为?上的一个字符或?，最后得到一个 NFA M?，
显然 L(M?)=L(M)
(a|b)*(aa|bb)(a|b)*
X Y(a|b)*(aa|bb)(a|b)*
X Y? 1 2
4
5
3
6
a
b
a
b
a
b
a
b
将正则式表示为 NFA
反复裂结，可得：
2,把上述 NFA确定化 ——采用子集法,
设 I是的状态集的一个子集，定义 I的?-闭包?-closure(I)为,
i) 若 s?I，则 s-closure(I)；
ii) 若 s?I,则从 s出发经过任意条?弧而能到达的任何状态 s?都属于?-closure(I)
即
-closure(I)=I?{s?|从某个 s?I出发经过任意条?弧能到达 s?}
设 a是?中的一个字符，定义
Ia=?-closure(J)
其中,J为 I中的某个状态出发经过一条 a
弧而到达的状态集合。
-closure({1})={1,3}=I
J={2,4,6}
Ia=?-closure(J)=(2,3,4,5,6,7,8)
5
1 a? 3 6
4
2
7
8
a
a
确定化的过程,
设字母表只包含两个 a和 b,X为初态，
构造如下表,
I I a I b
-C los ure ({X })
首先，置第 1行第 1列为?-closure({X})求出这一列的 Ia,Ib；
然后，检查这两个 Ia,Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第 1列上，求出每行第 2,3
列上的集合,..
重复上述过程，直至第 2,3列子集全部出现在第一列为止。
I Ia Ib
{X,1,2} {1,2,3} {1,2,4}
{1,2,3} {1,2,3,5,6,Y} {1,2,4}
{1,2,4} {1,2,3} {1,2,4,5,6,Y}
{1,2,3,5,6,Y} {1,2,3,5,6,Y} {1,2,4,6,Y}
{1,2,4,5,6,Y} {1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,4,6,Y} {1,2,3,6,Y} {1,2,4,5,6,Y}
{1,2,3,6,Y} {1,2,3,5,6,Y} {1,2,4,6,Y}
X Y? 1 2
4
5
3
6
a
b
a
b
a
b
a
b
这张表实际是一个状态转换矩阵，其中的每个子集是一个状态，它刻划了一个确定的有限自动机 M，初态是?-closure({X}),终态是含有原终态 Y的子集。
不难看出，这个 DFA M与 M?等价。
I a b
0 1 2
1 3 2
2 1 4
3 3 5
4 6 4
5 6 4
6 3 5
0
1
2
3
4
5
6
a a b
b b a
ba aba
b
a
b
2.3.3.5 正规式与有限自动机的等价性定理：
1,对任何 FA M，都存在一个正规式 r，使得 L(r)=L(M)。
2,对任何正规式 r，都存在一个 FA M，使得 L(M)=L(r)。
对转换图概念拓广，令每条弧可用一个正规式作标记。 (对一类输入符号 )
证明：
1 对?上任一 NFA M，构造一个?上的正规式 r，使得 L(r)=L(M)。
首先，在 M的转换图上加进两个状态 X和 Y，
从 X用?弧连接到 M的所有初态结点，从 M的所有终态结点用?弧连接到 Y，从而形成一个新的 NFA，记为 M?，它只有一个初态 X和一个终态 Y，显然 L(M)=L(M?)。
然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下 X和 Y为止；
代之为i jr1 r2 k i kr1r2
代之为 i jr1|r2i j
r2
r1
代之为 i k
r1r2*r2
i jr1 r3 k
r2
最后,X到 Y的弧上标记的正规式即为所构造的正规式 r，
显然 L(r)=L(M)=L(M?)
1
2
3
5
4U1
V1
U2
V2 W2
W1
1
2 5
4
V1(U1|U2)*W1
V1(U1|U2)*W2
V2(U1|U2)*W2
V2(U1|U2)*W1
证明 2,对于?上的正规式 r，构造一个
NFA M，使 L(M)=L(r)，并且 M只有一个终态，而且没有从该终态出发的箭弧。
下面使用关于 r中运算符数目的归纳法证明上述结论。 (Thompson结构法）
(1) 若 r具有零个运算符，则 r=?或 r=?或 r=a，其中 a。此时下图所示的三个有限自动机显然符合上述要求。
q0 q0 qf aq0 qf
(2) 假设结论对于少于 k(k?1)个运算符的正规式成立。
当 r中含有 k个运算符时,r有三种情形：
情形 1,r=r1|r2,r1,r2中运算符个数少于 k。
从而，由归纳假设，对 ri存在 Mi=<Si,?i,?i,
qi,{fi}>，使得 L(Mi)=L(ri)，并且 Mi没有从终态出发的箭弧（ i=1,2）。不妨设 S1∩ S2=?，
在 S1 ∪ S2中加入两个新状态 q0,f0。
令 M=<S1∪ S2∪ {q0,f0},?1∪?2,?,q0,{f0}>，其中?定义如下：
(a)?(q0,?)={q1,q2}
(b)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}
(c)?(q,a)=?2(q,a),当 q?S2-{f2},a2∪ {?}
(d)?(f1,?)=?(f2,?)={f0}。
M的状态转换如右图所示。
L(M)=L(M1)∪ L(M2)
=L(r1)∪ L(r2)=L(r)
q0 f0
M1q1 f1
M2q2 f2
情形 2,r=r1r2,设 Mi同情形 1(i=1,2)。
令 M=<S1∪ S2,?1∪?2,?,q1,{f2}>，其中?定义如下：
(a)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}。
(b)?(q,a)=?2(q,a),当 q?S2,a2∪ {?}。
(c)?(f1,?)={q2}。
M的状态转换如右图所示。
L(M)=L(M1)L(M2)
=L(r1)L(r2)=L(r)。
M1q1 f1 M2q2 f2
情形 3,r=r1*。设 M1同情形 1。
令 M=<S1∪ {q0,f0},?1,?,q0,{f0}>，其中 q0,
f0?S1,?定义如下：
(a)?(q0,?)=?(f1,?)={q1,f0}
(b)?(q,a)=?1(q,a),当 q?S1-{f1},a1∪ {?}。
M的状态转换如右图所示。
L(M) = L(M1)* = L(r1)* = L(r)
至此，结论 2获证。
M1q1 f1
q0 f0
上述证明过程实质上是一个将正规表达式转换为有限自动机的算法，前面介绍的裂结法也可以完成该转换。
2.3.3.6 确定有限自动机的化简对 DFA M的化简,寻找一个状态数比 M少的 DFA M?，使得 L(M)=L(M?)
假设 s和 t为 M的两个状态，称 s和 t等价,
如果从状态 s出发能读出某个字?而停止于终态，那么同样，从 t出发也能读出?
而停止于终态；反之亦然。
两个状态不等价，则称它们是 可区别 的。
DFA M最小化的基本思想,
把 M的状态集划分为一些不相交的子集，
使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。
具体做法,对 M的状态集进行划分
首先，把 S划分为终态和非终态两个子集，
形成基本划分?;
假定到某个时候,?已含 m个子集，记为
={I(1),I(2),?,I(m)}，检查?中的每个子集看是否能进一步划分 ;
对某个 I(i)，令 I(i)={s1,s2,?,sk}，若存在一个输入字符 a使得 Ia(i)不会包含在现行?的某个子集 I(j)中，则至少应把 I(i)分为两个部分。
例如，假定状态 s1和 s2经 a弧分别到达 t1和
t2，而 t1和 t2属于现行?中的两个不同子集，
说明有一个字?,t1读出?后到达终态，而
t2读出?后不能到达终态，或者反之，那么对于字 a?,s1读出 a?后到达终态，而
s2读出 a?不能到达终态，或者反之，所以
s1和 s2不等价。则将分成两半，使得一半含有 s1:
I(i1)={s|s?I(i)且 s经 a弧到达 t,
且 t与 t1属于现行?中的同一子集 }
另一半含有 s2,I(i2)=I(i)-I(i1)
一般地，对某个 a和 I(i)，若 Ia(i)落入现行?中 N
个不同子集，则应把 I(i)划分成 N个不相交的组，
使得每个组 J的 Ja都落入的?同一子集。这样构成新的划分。
重复上述过程，直到?所含子集数不再增长。
对于上述最后划分?中的每个子集，我们选取每个子集 I中的一个状态代表其他状态，则可得到化简后的 DFA M?。
若 I含有原来的初态，则其代表为新的初态，
若 I含有原来的终态，则其代表为新的终态 。
0
1
2
3
5
4
6
a a b
b b a
ba aba
b
a
b
0
1
2
3
a a
b b
ba
a
b
