1
编译原理第三章 词法分析上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 3月
2
本章目的词法分析器从输入串中识别单词,编译程序对源程序的分析由此开始 。 单词构词规则可由状态转换图表示,手工编程实现这些状态转换图,便可产生高效的词法分析器 。 构词规则也可由正规式表示,据此转换成识别单词的有限自动机,这就得到了识别单词的状态转换图 。
软件工具 Lex能实现这种转换 。
3
第三章 词法分析
§ 3.1 构造一个简单的词法分析器一,词法分析器的功能程序与由自然语言书写的文章一样,它是由一系列的句子组成的,而句子是由单词按一定规则组成的,单词是由字符组成的,因此归根结蒂源程序是由程序语言的字母表上的字符串组成 。 词法分析就应从输入字符串中识别出一个个单词,并对其中由用户定义的名字,在符号表中予以登记 。
4
[例 3.1]有下列程序段：
begin
length:=length+1；
if length<20 then read (nextch)
end；
它的输入字符串和识别出的单词流如图 3.1(a)、
(b)所示 。 其中 __表示空白 （ 空格 ） 键,符号 ↙
表示 RETURN键符,length和 nextch为程序中定义的变量,它们在符号表中应予以记载
5
词法分析与语法分析的关系：
由词法分析识别出的单词流是语法分析的输入,
语法分析据此判别它们是否构成合法句子 。 由词法分析开始形成的符号表,在以后的编译各阶段要频繁使用 。
词法分析可以作为单独一遍,如图 3.2(a)所示,
但由于词法分析比较简单,将它作为语法分析的子程序,每当语法分析程序需要一单词时,
就调用词法分析子程序,从输入串中识别当前单词,这是一种十分自然有效的工作方法,结构如图 3.2(b)所示 。
6
词法分析器 语法分析器单词流输入串图 3.2 词法分析器与语法分析器的关系
(a) 词法分析为单独一遍 (b) 词法分析器是一子程序语法分析器词法分析器符号表输入串取下一单词返回下一单词
7
1,单词符号的种类单词符号是程序语言最基本的语法符号,通常有五种,
(1)基本字 。 有的称关键字或保留字,如 if,while、
for,do,goto等,它们具标识符的特征,但它们是由语言定义的,其意义是固定的 。 多数语言中规定,它们不能作为标识符或标识符的前缀,用户不能用它们来定义用户使用的名字,在这种情况下,我们称它们为保留字,如 Pascal和 C等 。 但也有的语言允许将基本字作为标识符或标识符的前缀,如 Fortran和 PL/1；
8
(2)标识符 。 用户用来命名程序中出现的变量,数组,函数,过程,标号等,通常是一个字母开头的字母数字串；如 length,nextch等；
(3)常数 。 包括各种类型的常数,如整型,实型,
布尔型,字符型常数,216,3.1416,TRUE、
alpha等 。
(4)运算符 。 如 +,=,*,/等；
(5)界符 。 如 ;,,,(,)及双字符界符,=,/*,*/
及空白符等 。
对于一个确定的程序语言来说,保留字 (或基本字 )、
运算符,界符的数目是确定的,通常在几十个至百余个之间 。 标识符,常数则由用户指定,如何指定,使用多少个,程序语言均未加限制 。
9
2,单词的编码识别出来的单词符号应采用某种中间表示,以便为编译的后续阶段引用,其原则在于便以区别,
便于识别,表示方法可多种多样,以有利于编译处理为准,通常单词符号可以用一个二元组来表示：
(单词类别,单词符号的属性值 )
第一元用以区分单词符号所属的类,以整数编码 。
第二元用以区分在该类中哪一个单词符号,即单词符号的值,它的编码,随类别不同而不同 。
10
单词的二元组的确定方法
有限类：
由于基本字，运算符，界符的数目有限，一般可以对每个单词定义一个种别码，即一字一种，这时，它的第二元就没有识别意义了，即一级编码形式。显然以后对这类单词的识别十分简便。也可以将关系运算符 <,≤,>,≥,=、归为一类，则第二元就应是区分为哪一个关系运算符的值了。
无限类：
对于常数可以统归为一类，也可以按整型、实型、
布尔型、字符型分类。标识符类似处理，在这种情况下每一类别中的常数或标识符将由单词符号的属性值来区别是哪一个单词符号。通常将常数表的入口指针作为常数的属性值，而将符号表的入口指针作为标识符的属性值。
11
从图 3.1(a)字符串中识别出单词，并依次输出为：
(begin,—— )
(标识符,length 在符号表的入口指针 )
(:=,—— )
(标识符,length在符号表的入口指针 )
(+,—— )
(常数,1在常数表的入口指针 )
(；,—— )
(if,—— )
(标识符,length在符号表的入口指针 )
(<,—— )
(常数,20在常数表的入口指针 )
(then,—— )
(read,—— )
( (,—— )
(标识符,nextch在符号表的入口指针 )
( ),—— )
(end,—— )
(；,—— )
12
3,输入预处理从输入串识别单词并给出单词的中间码,是词法分析器的主要工作,它可以从输入缓冲区中读字符并识别 。 但在多数情况下,先对输入串作预处理：
剔除注释和多余的空白符和制表换行符等编辑性字符,记录新读入字符行的行号,以便在发现错误时,
报告错误所在程序行,这些处理由预处理程序来完成,这样词法分析就会既简单又清晰 。 因此我们另设一个扫描缓冲区,当词法分析需要时,预处理程序就从输入缓冲区中读字符并作预处理,将经处理的字符装满扫描缓冲区,而词法分析器就从扫描缓冲区中读字符并识别 。 因此输入预处理通常称为扫描器 。
13
4,词法错误非法字符 (字母表以外的 ) 和非法常数可在词法分析时被发现,除此之外没有什么词法错误是在词法分析时发现的,往往要推迟到语法分析时才发现,例如,把 if写成 fi,则词法分析作为标识符处理 。
le ngth,中间多了空白,词法分析将 le和 ngth
作两个标识符处理,由此而造成的后果,将在其他分析过程中才反映出来 。
14
5,词法分析器的建立方法传统上使用汇编语言写词法分析器,但这并不容易,通常用系统程序设计语言来写一个词法分析器,但它不如用生成工具 Lex产生词法分析器方便,虽然如此,用汇编语言写词法分析器仍有它可取之处,因为它的分析速度最快 。
在规模上,词法分析器相对于编译程序来说可以说是不值一提的,但是编译有相当一部分时间是花在词法分析上的,因此提高词法分析的分析速度是值得重视的,为此将讨论一些有用的技术 。
15
二,扫描缓冲区一个长度为 2N的扫描缓冲区,分为长度为 N的左右两个半区,缓冲区设置两个指针,开始指针和向前指针 forward。 开始时两个指针均指向下一个待分析单词符号的第一个字符,然后向前指针向前扫描,直到该单词符号恰被识别时止,这时向前指针恰在被识别单词符号的下一个字符,因此两指针间的字符串便为已识别的单词符号 。 识别完后,开始指针移至向前指针位置,准备下个单词符号的识别,如图
3.3所示 。… t h e n r e a d （ n e x t c h ) …
开始指针 向前指针图 3.3 由左右两半区组成的扫描缓冲区
16
当向前指针将越过某半区的边界时，则由扫描器在另一半区装入 N个新字符，向前指针便从新装入字符的半区的开始位置继续扫描，
只要单词符号的长度 ≤N，那么用这种扫描缓冲区来识别单词符号是安全的。按照这种方式，每当向前指针向前移动时均需测试是否已到达所在半区之边界，若是，则在另半区装入新的内容，如图 3.4所示：
17
if (forward到达左半区末尾 )
{
重装右半区 ;
forward=forward+1;
}
else if (forward到达右半区末尾 )
{
重装左半区 ;
将 forward移至左半区起点 ;
}
else
{
forward=forward+1;
}
图 3.4 向前指针移动时的测试
18
除了在左半区的末尾外,在其他情况下,向前指针移动时都要测试两次,如果在左,右半区末尾附加一个结尾标记 eof,如图 3.5所示：
… t h e n r e eof d （ n e x t c h ) eof
图 3.5 附有结尾标记的扫描缓冲区
a …
19
在这种情况下，向前指针移动时的测试如图 3.6所示。
forward=forward+1;
if (forward != eof)
{if (forward到达左半区末尾 )
{重装右半区 ;
forward=forward+1;
}
else if (forward到达右半区末尾 )
{重装左半区 ;
将 forward移至左半区起点 ;
}
else
{词法分析结束 ;
}
}
图 3.6 具有结尾标记的测试
20
三,超前搜索对于 Fortran和 PL/1这类语言,基本字可以作为标识符或标识符的前缀,遇到这种情况,究竟作为基本字识别还是作为标识符识别,需超过该单词符号继续向前扫描,直到可以识别时止 。 例如 Fortran中
100 DO 110 I =1,10
是个循环语句,循环变量 I的初值为 1,终值为 10（ 步长度为 1） 在 100语句和 110语句之间进行循环,而
100 DO 110 I =1,10
则是个赋值语句,左部变量为 DO 110 I,因此当向前指针到达 DO后的 1时并不能断定已识别 DO,还必须超前搜索到等号后的第一个界符时,才能断言此 DO是保留字,还是标识符的前缀 。
显然,保留字就没有这种问题 。
21
四,状态转换图可以用状态转换图来识别单词，状态转换图是有限的有向图。结点代表状态，结点间可由有向边连接，有向边上可标记字符，如图 3.7表示在状态 i下，若输入字符为 x，则转换到状态 j，若输入字符为 y，则转换到状态 k，状态 (即结点 )
数是有限的，其中必有一初始状态，若干个终止状态，终止状态的结点用双圈表示，以示区别
i j
k
x
y
图 3.7 关于输入字符的状态转换
22
图 3.8给出了识别标识符，无符号整数，无符号数的状态转换图，其初始状态均用 0状态表示。
(c) 无符号数图 3.8 状态转换图
0 1 2字母 其他
*
(a) 标识符
0 1 2数字 其他
*
(b) 无符号整数数字
0 1 2数字
· *
(b)
数字
3 4 5 6 7数字
E
数字数字其他数字
+ |
-
E
其他其他数字字母 |数字
23
识别了一类单词符的终止状态,可以给出相应的单词编码,某些终态其实是在输入了一个界符后才成为识别状态的,这表明和识别的单词符号相比,它多输入了一个符号,识别后应予退回,对这类情况,在终态上标以
"*"作为标志 。
24
因此,对各类单词的识别均可用状态转换图来表示,图 3.9就是一个简单词法分析的状态转换图,识别保留字,标识符,无符号整数,
运算符,界符,它是一个很小的子集 。
25
0 1 2
3 4
5
6
7 8
9
10 11
12
13
14
15 16
17
1918
20
21
开始空白 字母 |数字字母 非字母与数字
*
*
*
*
*
*
*
数字数字 非数字
+
-
*
<
非 *
=
>
其他
=
> =
其他
,=
其他;
返回 (id,id在符号表中的位置 )
或返回 (保留字,——)
返回 (常数,在常数表中的位置 )
返回 (+,——)
返回 ( -,——)
返回 (*,——)
返回 (**,——)
返回 (relop,LE)
返回 (relop,NE)
返回 (relop,LT)
返回 (relop,EQ)
返回 (relop,GE)
返回 (relop,GT)
返回 (:=,——)
返回 (:,——)
返回 (;,——)
26
在状态 2时,所识别的字符串应先与保留字表逐一比较,若匹配,则是一个保留字,否则就是标识符 。 若为标识符,则应先查看符号表；表中无此标识符,则将它记入符号表；
然后返回,它在符号表中的入口指针作为该标识符的属性值 。
在状态 4时，应将识别的常数转换成二进制常数，然后查常数表；表中无此常数，将它记入常数表；然后返回它在常数表中的入口指针作为该常数的属性值。
27
五,状态转换图的实现状态转换图的程序实现是容易的,相应于图
3.9的词法分析程序如下：
token=“”； /*置 token为空串 */。
s=getchar()；
getbe()；
switch(s)
28
{case?a?,/*字母开头 */
case 'b':…
case 'z'：
while(letter()||digit())
{concatenation()；
getchar()； }
retract()；
c=reserve()；
if(c==0){buildlist()；
return（ id,指向 id的符号表入口指针 ） ；
}
else {return（ 保留字码,null） }
break；
29
case?0?,/*数字开头 */
case '1':
…
case '9'：
while(digit())
{concatenation()；
getchar()；
}
retract()；
buildlist()；
return(num,num的常数表入口指针 )；
break；
30
case?+?,/*算术运算符 */
return(plus-op,null)；
break；
case'-'：
return(mimus-op,null)；
break；
case'*'：
getchar()；
if(character=='*'){return(power-op,null)； }
retract()；
return(star,null)；
break；
31
case'<',/*关系运算符 */
getchar()；
if(character=='='){return(rel-op,LE)； }
else if(character=='>'){return(rel-op,NE)； }
retract()；
return(rel-op,LT)； break；
case'=',return(rel-op,EQ)； break；
case'>',getchar()；
if(character=='='){return(rel-op,GE)； }
retract()；
return(rel-op,GT)；
break；
32
case?:?,/*界符 */
getchar()；
if(character=='=')
{
return(assign-op,null)；
}
retract()；
return(colon,null)；
break；
case';':
return(semicolon,null)；
}
33
其中引进的变量和过程为：
token,字符数组,存放单词符号的符号串 。
getchar：将下一输入字符读入 character的过程,将向前指针移向下一字符 。
getbe：若 character中的字符为空白,则调用
getchar,直至 character为非空白时止 。 开始指针移到向前指针位置 。
concatenation,将 token 中的字符串与
character中字符连接,作为 token中的新的字符串 。
34
letter和 digit：判断 character中字符是否为字母和数字的布尔函数过程,是则返回 true，
否则返回 false。
reserve：按 token中字符串,查找保留字表,
若是保留字,返回它的编码,否则返回 0。
retract:向前指针回退一个字符,character置为空白 。
buildlist：为标识符建符号表,为常数建常数表 。
35
§ 3.2 正规表达式与正规集状态转换图对构造词法分析程序是有用的,
将状态转换图的概念形式化是为了词法分析器自动生成的需要 。 正规表达式是一种表示法,它可以表示单词符号的结构,从而精确定义单词符号集 。 正规表达式简称正规式,
它表示的集合为正规集 。
36
一,正规式与正规集的定义
[例 3.2] 程序语言中使用的标识符是一个字母开头的字母数字串,如果字母用 letter表示,数字用 degit表示,
那么标识符就可以表示为：
letter(letter|digit)*
其中 letter与 (letter|digit)*的并置表示两者的连接,括号中表示 letter或 digit,'*'表示零次或多次引用 '*'号所标记的表达式,因此 (letter|digit)*是 letter|digit的零次或多次并置,表示一长度为 0,1,2,… 的字母数字串,因此
letter(letter|digit)*
表示字母开头的字母数字串,也即标识符集,
letter(letter|digit)*便是表示标识符的正规式,标识符集便是这个正规式表示的正规集 。
37
定义 3.1 正规式和正规集的递归定义如下：
对于给定的字母表?
(1)?和?是?上的正规式,
它们所表示的正规集分别是 {?}和?；
(2) 对每一个 a,则 a是?上的一个正规式,它所表示的正规集为 {a}；
(3) 如果 R和 S是?上的正规式,它们所表示的正规集分别为 L(R)和 L(S)。
则：
(R|S)是上的正规式,它所表示的正规集为 L(R)∪ L(S)；
(R·S)是上的正规式,它所表示的正规集为 L(R)L(S)；
(R)*是上的正规式,它所表示的正规集为 (L(R))*；
(R)也是上的正规式,它所表示的正规集为 L(R)；
(4) 仅有限次使用规则 (1),(2),(3)得到的表示式,是上的正规式,它所表示的集合是上的正规集 。
38
上述定义中,规则 (1),(2)为基始规则,规则 (3)为归纳规则,规则 (4)是界限规则或终止规则 。
正规式间的运算,|”为或,,·”为连接,通常它可省略,
,*” 为闭包,括号是为了限定运算次序 。 如果规定 *
优先于 ·,·优先于 |,那么有些括号省略后不会引起混淆,正规式便可以更简洁 。
[例 3.3] 设? ={a,b,c},则 (a|((b)*c))是一正规式,这是因为
a,b,c都是正规式,所以 (b)*是正规式,((b)*c)是正规式,所以 (a|((b)*c))是正规式,省去不必要的括号后,正 规 式 为 a|b*c 。 它 的 正 规 集
L(a|b*c)=L(a)∪ L(b*c)=L(a)∪ L(b*)L(c)=L(a)∪ L*(
b)L(c)={a}∪ {b}*{c}={a}∪ {,b,bb,… }{c}={a,c,bc,bbc,
… }
39
[例 3.4]? ={a,b},则 R=a(a|b)*是上的正规式,它表示的正规集：
L(R)=L(a(a|b)*)=L(a)L((a|b)*)=L(a)(L(a|b))*
=L(a)(L(a)∪ L(b))*={a}({a}∪ {b})*={a}{a,b}*
={a}{ε,a,b,aa,ab,ba,bb,aaa,… }
={a,aa,ab,aaa,aab,aba,abb,aaaa,… }
即为?上 a开头的字符串集 。
40
[例 3.5]? ={a,b,0,1},则 R=(a|b)(a|b|0|1)*为上的正规式,
它表示的正规集
L(R)=L((a|b)(a|b|0|1)*)=L(a|b)(L(a|b|0|1))*
=L(a)∪ L(b))(L(a)∪ L(b)∪ L(0)∪ L(1))*
={a,b}{a,b,0,1}*
是?上 a,b开头的 a,b,0,1字符串的集合 。
41
二,正规式的性质定义 3.2?上正规式 R和 S,如果它所表示的正规集
L(R)=L(S),则称 R和 S等价,记为 R=S。
不难证明,正规式具有下列性质：
(1)交换律,R|S=S|R
(2)结合律,R|(S|T)=(R|S)|T
R(ST)=(RS)T
(3)分配律,R(S|T)=RS|RT
(R|S)T-RT|ST
(4)同一律,εR=Rε=R
42
三,正规式与正规文法正规式与正规文法都用来描述程序语言的词法结构,
它们有着相同的表达能力：对任一正规文法,都可找到一个正规式,使正规式表示的正规集恰为正规文法产生的语言,反之亦然 。 正规式简洁,正规文法易识别,根据需要,可在两者之间进行转换,这里不详细讨论了 。
43
§ 3.3 有限自动机有限自动机 (FA)是更一般化的状态转换图,有确定有限自动机 DFA与非确定有限自动机 NFA之分 。 DFA
识别快,易为计算机直接实现 。
一,有限自动机的定义定义 3.3 一个非确定有限自动机 Mn (记为 NFA Mn )是一个五元组 Mn=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是唯一的一个初态；
F? S,是一个终态集；
是 S×?-->2s的一个单值映射,即：
(si,a)={s1,s2,… },其中 si?S,a,2s?S
44
定义 3.4 一个确定有限自动机 Md (记为 NFA Md )是一个五元组 Md=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是唯一的一个初态；
F? S,是一个终态集；
是 S×?-->S的一个单值映射,即：
(si,a)={sj},其中 si,sj?S,a,
45
定义 3.5 一个有限自动机 M (记为 FA M )是一个五元组
M=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是非空的初态集；
F? S,是一个终态集；
是 S×?-->2s的一个单值映射上述拓广在于：
(1)初始状态可以是一个初态集；
(2)输入字符串可以是上的字符串,包括空串 。
不难证实,定义 3.3与定义 3.5的描述能力是相同的,在此我们不予证明了 。
46
二,FA的表示用状态转换图或状态转换矩阵来表示一个有限自动机会更直观些 。
1.状态转换图用 m个结点表示 FA M的 m个状态，表示终态的结点用双圈表示，用起始标记?来表示初始状态的结点，
用有向边来表示状态变换的映射。如?(si,a)=sj可表示如图 3.10(a)，对于?(si,b)=sj可以表示如图 3.10 (b)。
a b
Si Sj SjSi
图 3.10 状态转换
(a) (b)
47
(a) 例 3.9的 NFA
S0 S3
S1
S2
S4
0,1
00
0,1
1
1
0,1
S0 S1
S3S2 1
1
00
1
1
00
(b) 例 3.10的 DFA
图 3.11 用状态转换图表示 FA
因此，例 3.9和例 3.10的 FA，
用状态转换图表示如图 3.11
所示。
48
2.状态转换矩阵一个有限自动机中,如果 |S|=m,|?|=n,则可用一个 m?n矩阵来表示上的状态变换 。
例 3.9,例 3.10的状态转换矩阵如图 3.12
所示,为清楚起见,用表的方式表示,
并列出状态集 S和字母表?。
49
三,FA M识别的的语言定义 3.6 对 FA M和任一?上的字符串?(即*)如果存在一条从初始状态到终止状态的通路,通路上有向边所标识的字符依次连接所得的字符串恰为?,则称?为 FA M所接受或称?为 FA M
所识别 。 为 FA M所能识别的字符串集称为 FA
M所识别的语言,记为 L(M)。
显然,若初态同时为终态,则?可为 FA M接受 。
例 3.9的有限自动机所识别的语言为含有两个相连的 0或两个相连的 1的字符串 。
例 3.10的有限自动机所识别的语言为含偶数个 0和偶数个 1的字符串 。
50
定义 3.7 给出 FA M和 FA M?,如果 L(M)=L(M?)，
则称有限自动机 M和 M?等价 。
定理 3.1 对任一给定的 NFA M一定存在一个 DFA
M?使：
L(M)=L(M?)
证明的基本思想是基于子集法,即将 NFA M中的状态子集定义为 DFA M?的一个状态,从 NFA
M出发可构造出等价的 DFA M?,这里不作形式化的证明,只在 NFA M的确定化一节中给出了构造等价的 DFA M?的算法 。
DFA是 NFA的特别,NFA可以有 DFA与之等价,
因此两者描述能力是相同的,DFA便于识别,
NFA便于定理证明,都是有用的 。
51
四,NFA M的确定化定理 3.1表明,任一给定的 NFA M,都可找到一个与之等价的 DFA M?,其基本方法是子集法,
具体方法如下：
首先定义 FA M的一个状态子集 I的?闭包,
-closure(I)：
(1)若 si? I,则 si -closure(I) ；
(2)若 si? I,则从 si出发,经?通路能到达的任何状态 sj,都有 sj -closure(I) 。
其次,对 FA M的一个状态子集 I及 a,可以定义状态子集 Ia?S,对任一 sj? Ia,必有 si? I，
使得 si与 sj之间存在一条通路,通路上的标记字符串恰为 a。
如果记 J为从 I的一个状态出发经过有向边而能到达状态集,则 Ia=? -closure(J)
52
然后按如下步骤确定化：
(1) 构造一张表,它共有 |?|+1列,第一列为状态子集 I,然后对每个 a分别设一列 Ia；
(2) 第一行第一列的状态子集 I为? -closure(S0),，
其中 S0为初始状态；
(3) 为第一列中的 I和每个 a,求 Ia,并记入相应的列,如果它不同于第一列中已有的状态子集 I,则将它列入第一列中 。
(4) 重复 (3),直到对每个 I及 a均已求得,并且没有新的状态子集加入第一列时为止 。
上述过程在有限步后必可终止
(5) 将第一列中的每个状态子集,命名为新的状态,则上述转换表,便成为新的状态转换矩阵,其状态转换函数是上的单值映射,它相应于一个 DFAM’。
53
五,DFA M的简化定义 3.8 对一给定的 DFA M,有状态 si,sj
S且,si?sj,如果凡从 si出发能识别字符串?而停于终态,从 sj出发也能识别?此而停于终态,反之凡若从 sj出发能识别?
而停于终态,从 si出发也能识别此?而停于终态,则称 si和 sj是等价的,否则就是可区分的 。
显然,将 DFA M的两个等价状态合并得到
DFA M’,L(M)=L(M’)。
54
定义 3.9 如果 DFA M没有无关状态,并且没有彼此等价的不同的两个状态,则该 DFA M称为是归约的,或称为是简化了的 。
所谓无关状态是指：对一个处于初始状态的 FA
M,任何输入序列都不能到达的状态 。 一个
FA M 删去了无关状态后得到 FA M’,则
L(M)=L(M’)。
因此一个 DFA M如果不是归约的,则首先应删去无关状态,再合并等价状态 。
不难检验上述等价定义构成了状态间的等价的一个等价关系,按此等价关系可对状态集 S作等价分割,然后将每一个等价类合并为一个新的状态,这样得到的 DFA M’,显然是 DFA M
的简化 。
55
二,由正规式构造等价的 NFA M
定理不只是证明了 NFA与正规式间的等价性,而且也给出了构造 NFA M的方法 。
为了减少状态数和有向边,实际采用下列三条分解规则来构造 NFA M。 这时,
状态之间的有向边上标记可拓广为正规式,这三条规划分别如图 3.21所示 。
56
R1|
R2
R1
R2
R*
si sj
si sj
si sj
si sj
si sk sj
si sk sj
图 3.21 转换规则
57
对于给定的正规式 R：
第一步,构造与之等价的 NFA M；
第二步,将 NFA M确定化为 DFAM’
第三步,将 DFAM’化简为 DFAM’’
习题,3.10
编译原理第三章 词法分析上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 3月
2
本章目的词法分析器从输入串中识别单词,编译程序对源程序的分析由此开始 。 单词构词规则可由状态转换图表示,手工编程实现这些状态转换图,便可产生高效的词法分析器 。 构词规则也可由正规式表示,据此转换成识别单词的有限自动机,这就得到了识别单词的状态转换图 。
软件工具 Lex能实现这种转换 。
3
第三章 词法分析
§ 3.1 构造一个简单的词法分析器一,词法分析器的功能程序与由自然语言书写的文章一样,它是由一系列的句子组成的,而句子是由单词按一定规则组成的,单词是由字符组成的,因此归根结蒂源程序是由程序语言的字母表上的字符串组成 。 词法分析就应从输入字符串中识别出一个个单词,并对其中由用户定义的名字,在符号表中予以登记 。
4
[例 3.1]有下列程序段：
begin
length:=length+1；
if length<20 then read (nextch)
end；
它的输入字符串和识别出的单词流如图 3.1(a)、
(b)所示 。 其中 __表示空白 （ 空格 ） 键,符号 ↙
表示 RETURN键符,length和 nextch为程序中定义的变量,它们在符号表中应予以记载
5
词法分析与语法分析的关系：
由词法分析识别出的单词流是语法分析的输入,
语法分析据此判别它们是否构成合法句子 。 由词法分析开始形成的符号表,在以后的编译各阶段要频繁使用 。
词法分析可以作为单独一遍,如图 3.2(a)所示,
但由于词法分析比较简单,将它作为语法分析的子程序,每当语法分析程序需要一单词时,
就调用词法分析子程序,从输入串中识别当前单词,这是一种十分自然有效的工作方法,结构如图 3.2(b)所示 。
6
词法分析器 语法分析器单词流输入串图 3.2 词法分析器与语法分析器的关系
(a) 词法分析为单独一遍 (b) 词法分析器是一子程序语法分析器词法分析器符号表输入串取下一单词返回下一单词
7
1,单词符号的种类单词符号是程序语言最基本的语法符号,通常有五种,
(1)基本字 。 有的称关键字或保留字,如 if,while、
for,do,goto等,它们具标识符的特征,但它们是由语言定义的,其意义是固定的 。 多数语言中规定,它们不能作为标识符或标识符的前缀,用户不能用它们来定义用户使用的名字,在这种情况下,我们称它们为保留字,如 Pascal和 C等 。 但也有的语言允许将基本字作为标识符或标识符的前缀,如 Fortran和 PL/1；
8
(2)标识符 。 用户用来命名程序中出现的变量,数组,函数,过程,标号等,通常是一个字母开头的字母数字串；如 length,nextch等；
(3)常数 。 包括各种类型的常数,如整型,实型,
布尔型,字符型常数,216,3.1416,TRUE、
alpha等 。
(4)运算符 。 如 +,=,*,/等；
(5)界符 。 如 ;,,,(,)及双字符界符,=,/*,*/
及空白符等 。
对于一个确定的程序语言来说,保留字 (或基本字 )、
运算符,界符的数目是确定的,通常在几十个至百余个之间 。 标识符,常数则由用户指定,如何指定,使用多少个,程序语言均未加限制 。
9
2,单词的编码识别出来的单词符号应采用某种中间表示,以便为编译的后续阶段引用,其原则在于便以区别,
便于识别,表示方法可多种多样,以有利于编译处理为准,通常单词符号可以用一个二元组来表示：
(单词类别,单词符号的属性值 )
第一元用以区分单词符号所属的类,以整数编码 。
第二元用以区分在该类中哪一个单词符号,即单词符号的值,它的编码,随类别不同而不同 。
10
单词的二元组的确定方法
有限类：
由于基本字，运算符，界符的数目有限，一般可以对每个单词定义一个种别码，即一字一种，这时，它的第二元就没有识别意义了，即一级编码形式。显然以后对这类单词的识别十分简便。也可以将关系运算符 <,≤,>,≥,=、归为一类，则第二元就应是区分为哪一个关系运算符的值了。
无限类：
对于常数可以统归为一类，也可以按整型、实型、
布尔型、字符型分类。标识符类似处理，在这种情况下每一类别中的常数或标识符将由单词符号的属性值来区别是哪一个单词符号。通常将常数表的入口指针作为常数的属性值，而将符号表的入口指针作为标识符的属性值。
11
从图 3.1(a)字符串中识别出单词，并依次输出为：
(begin,—— )
(标识符,length 在符号表的入口指针 )
(:=,—— )
(标识符,length在符号表的入口指针 )
(+,—— )
(常数,1在常数表的入口指针 )
(；,—— )
(if,—— )
(标识符,length在符号表的入口指针 )
(<,—— )
(常数,20在常数表的入口指针 )
(then,—— )
(read,—— )
( (,—— )
(标识符,nextch在符号表的入口指针 )
( ),—— )
(end,—— )
(；,—— )
12
3,输入预处理从输入串识别单词并给出单词的中间码,是词法分析器的主要工作,它可以从输入缓冲区中读字符并识别 。 但在多数情况下,先对输入串作预处理：
剔除注释和多余的空白符和制表换行符等编辑性字符,记录新读入字符行的行号,以便在发现错误时,
报告错误所在程序行,这些处理由预处理程序来完成,这样词法分析就会既简单又清晰 。 因此我们另设一个扫描缓冲区,当词法分析需要时,预处理程序就从输入缓冲区中读字符并作预处理,将经处理的字符装满扫描缓冲区,而词法分析器就从扫描缓冲区中读字符并识别 。 因此输入预处理通常称为扫描器 。
13
4,词法错误非法字符 (字母表以外的 ) 和非法常数可在词法分析时被发现,除此之外没有什么词法错误是在词法分析时发现的,往往要推迟到语法分析时才发现,例如,把 if写成 fi,则词法分析作为标识符处理 。
le ngth,中间多了空白,词法分析将 le和 ngth
作两个标识符处理,由此而造成的后果,将在其他分析过程中才反映出来 。
14
5,词法分析器的建立方法传统上使用汇编语言写词法分析器,但这并不容易,通常用系统程序设计语言来写一个词法分析器,但它不如用生成工具 Lex产生词法分析器方便,虽然如此,用汇编语言写词法分析器仍有它可取之处,因为它的分析速度最快 。
在规模上,词法分析器相对于编译程序来说可以说是不值一提的,但是编译有相当一部分时间是花在词法分析上的,因此提高词法分析的分析速度是值得重视的,为此将讨论一些有用的技术 。
15
二,扫描缓冲区一个长度为 2N的扫描缓冲区,分为长度为 N的左右两个半区,缓冲区设置两个指针,开始指针和向前指针 forward。 开始时两个指针均指向下一个待分析单词符号的第一个字符,然后向前指针向前扫描,直到该单词符号恰被识别时止,这时向前指针恰在被识别单词符号的下一个字符,因此两指针间的字符串便为已识别的单词符号 。 识别完后,开始指针移至向前指针位置,准备下个单词符号的识别,如图
3.3所示 。… t h e n r e a d （ n e x t c h ) …
开始指针 向前指针图 3.3 由左右两半区组成的扫描缓冲区
16
当向前指针将越过某半区的边界时，则由扫描器在另一半区装入 N个新字符，向前指针便从新装入字符的半区的开始位置继续扫描，
只要单词符号的长度 ≤N，那么用这种扫描缓冲区来识别单词符号是安全的。按照这种方式，每当向前指针向前移动时均需测试是否已到达所在半区之边界，若是，则在另半区装入新的内容，如图 3.4所示：
17
if (forward到达左半区末尾 )
{
重装右半区 ;
forward=forward+1;
}
else if (forward到达右半区末尾 )
{
重装左半区 ;
将 forward移至左半区起点 ;
}
else
{
forward=forward+1;
}
图 3.4 向前指针移动时的测试
18
除了在左半区的末尾外,在其他情况下,向前指针移动时都要测试两次,如果在左,右半区末尾附加一个结尾标记 eof,如图 3.5所示：
… t h e n r e eof d （ n e x t c h ) eof
图 3.5 附有结尾标记的扫描缓冲区
a …
19
在这种情况下，向前指针移动时的测试如图 3.6所示。
forward=forward+1;
if (forward != eof)
{if (forward到达左半区末尾 )
{重装右半区 ;
forward=forward+1;
}
else if (forward到达右半区末尾 )
{重装左半区 ;
将 forward移至左半区起点 ;
}
else
{词法分析结束 ;
}
}
图 3.6 具有结尾标记的测试
20
三,超前搜索对于 Fortran和 PL/1这类语言,基本字可以作为标识符或标识符的前缀,遇到这种情况,究竟作为基本字识别还是作为标识符识别,需超过该单词符号继续向前扫描,直到可以识别时止 。 例如 Fortran中
100 DO 110 I =1,10
是个循环语句,循环变量 I的初值为 1,终值为 10（ 步长度为 1） 在 100语句和 110语句之间进行循环,而
100 DO 110 I =1,10
则是个赋值语句,左部变量为 DO 110 I,因此当向前指针到达 DO后的 1时并不能断定已识别 DO,还必须超前搜索到等号后的第一个界符时,才能断言此 DO是保留字,还是标识符的前缀 。
显然,保留字就没有这种问题 。
21
四,状态转换图可以用状态转换图来识别单词，状态转换图是有限的有向图。结点代表状态，结点间可由有向边连接，有向边上可标记字符，如图 3.7表示在状态 i下，若输入字符为 x，则转换到状态 j，若输入字符为 y，则转换到状态 k，状态 (即结点 )
数是有限的，其中必有一初始状态，若干个终止状态，终止状态的结点用双圈表示，以示区别
i j
k
x
y
图 3.7 关于输入字符的状态转换
22
图 3.8给出了识别标识符，无符号整数，无符号数的状态转换图，其初始状态均用 0状态表示。
(c) 无符号数图 3.8 状态转换图
0 1 2字母 其他
*
(a) 标识符
0 1 2数字 其他
*
(b) 无符号整数数字
0 1 2数字
· *
(b)
数字
3 4 5 6 7数字
E
数字数字其他数字
+ |
-
E
其他其他数字字母 |数字
23
识别了一类单词符的终止状态,可以给出相应的单词编码,某些终态其实是在输入了一个界符后才成为识别状态的,这表明和识别的单词符号相比,它多输入了一个符号,识别后应予退回,对这类情况,在终态上标以
"*"作为标志 。
24
因此,对各类单词的识别均可用状态转换图来表示,图 3.9就是一个简单词法分析的状态转换图,识别保留字,标识符,无符号整数,
运算符,界符,它是一个很小的子集 。
25
0 1 2
3 4
5
6
7 8
9
10 11
12
13
14
15 16
17
1918
20
21
开始空白 字母 |数字字母 非字母与数字
*
*
*
*
*
*
*
数字数字 非数字
+
-
*
<
非 *
=
>
其他
=
> =
其他
,=
其他;
返回 (id,id在符号表中的位置 )
或返回 (保留字,——)
返回 (常数,在常数表中的位置 )
返回 (+,——)
返回 ( -,——)
返回 (*,——)
返回 (**,——)
返回 (relop,LE)
返回 (relop,NE)
返回 (relop,LT)
返回 (relop,EQ)
返回 (relop,GE)
返回 (relop,GT)
返回 (:=,——)
返回 (:,——)
返回 (;,——)
26
在状态 2时,所识别的字符串应先与保留字表逐一比较,若匹配,则是一个保留字,否则就是标识符 。 若为标识符,则应先查看符号表；表中无此标识符,则将它记入符号表；
然后返回,它在符号表中的入口指针作为该标识符的属性值 。
在状态 4时，应将识别的常数转换成二进制常数，然后查常数表；表中无此常数，将它记入常数表；然后返回它在常数表中的入口指针作为该常数的属性值。
27
五,状态转换图的实现状态转换图的程序实现是容易的,相应于图
3.9的词法分析程序如下：
token=“”； /*置 token为空串 */。
s=getchar()；
getbe()；
switch(s)
28
{case?a?,/*字母开头 */
case 'b':…
case 'z'：
while(letter()||digit())
{concatenation()；
getchar()； }
retract()；
c=reserve()；
if(c==0){buildlist()；
return（ id,指向 id的符号表入口指针 ） ；
}
else {return（ 保留字码,null） }
break；
29
case?0?,/*数字开头 */
case '1':
…
case '9'：
while(digit())
{concatenation()；
getchar()；
}
retract()；
buildlist()；
return(num,num的常数表入口指针 )；
break；
30
case?+?,/*算术运算符 */
return(plus-op,null)；
break；
case'-'：
return(mimus-op,null)；
break；
case'*'：
getchar()；
if(character=='*'){return(power-op,null)； }
retract()；
return(star,null)；
break；
31
case'<',/*关系运算符 */
getchar()；
if(character=='='){return(rel-op,LE)； }
else if(character=='>'){return(rel-op,NE)； }
retract()；
return(rel-op,LT)； break；
case'=',return(rel-op,EQ)； break；
case'>',getchar()；
if(character=='='){return(rel-op,GE)； }
retract()；
return(rel-op,GT)；
break；
32
case?:?,/*界符 */
getchar()；
if(character=='=')
{
return(assign-op,null)；
}
retract()；
return(colon,null)；
break；
case';':
return(semicolon,null)；
}
33
其中引进的变量和过程为：
token,字符数组,存放单词符号的符号串 。
getchar：将下一输入字符读入 character的过程,将向前指针移向下一字符 。
getbe：若 character中的字符为空白,则调用
getchar,直至 character为非空白时止 。 开始指针移到向前指针位置 。
concatenation,将 token 中的字符串与
character中字符连接,作为 token中的新的字符串 。
34
letter和 digit：判断 character中字符是否为字母和数字的布尔函数过程,是则返回 true，
否则返回 false。
reserve：按 token中字符串,查找保留字表,
若是保留字,返回它的编码,否则返回 0。
retract:向前指针回退一个字符,character置为空白 。
buildlist：为标识符建符号表,为常数建常数表 。
35
§ 3.2 正规表达式与正规集状态转换图对构造词法分析程序是有用的,
将状态转换图的概念形式化是为了词法分析器自动生成的需要 。 正规表达式是一种表示法,它可以表示单词符号的结构,从而精确定义单词符号集 。 正规表达式简称正规式,
它表示的集合为正规集 。
36
一,正规式与正规集的定义
[例 3.2] 程序语言中使用的标识符是一个字母开头的字母数字串,如果字母用 letter表示,数字用 degit表示,
那么标识符就可以表示为：
letter(letter|digit)*
其中 letter与 (letter|digit)*的并置表示两者的连接,括号中表示 letter或 digit,'*'表示零次或多次引用 '*'号所标记的表达式,因此 (letter|digit)*是 letter|digit的零次或多次并置,表示一长度为 0,1,2,… 的字母数字串,因此
letter(letter|digit)*
表示字母开头的字母数字串,也即标识符集,
letter(letter|digit)*便是表示标识符的正规式,标识符集便是这个正规式表示的正规集 。
37
定义 3.1 正规式和正规集的递归定义如下：
对于给定的字母表?
(1)?和?是?上的正规式,
它们所表示的正规集分别是 {?}和?；
(2) 对每一个 a,则 a是?上的一个正规式,它所表示的正规集为 {a}；
(3) 如果 R和 S是?上的正规式,它们所表示的正规集分别为 L(R)和 L(S)。
则：
(R|S)是上的正规式,它所表示的正规集为 L(R)∪ L(S)；
(R·S)是上的正规式,它所表示的正规集为 L(R)L(S)；
(R)*是上的正规式,它所表示的正规集为 (L(R))*；
(R)也是上的正规式,它所表示的正规集为 L(R)；
(4) 仅有限次使用规则 (1),(2),(3)得到的表示式,是上的正规式,它所表示的集合是上的正规集 。
38
上述定义中,规则 (1),(2)为基始规则,规则 (3)为归纳规则,规则 (4)是界限规则或终止规则 。
正规式间的运算,|”为或,,·”为连接,通常它可省略,
,*” 为闭包,括号是为了限定运算次序 。 如果规定 *
优先于 ·,·优先于 |,那么有些括号省略后不会引起混淆,正规式便可以更简洁 。
[例 3.3] 设? ={a,b,c},则 (a|((b)*c))是一正规式,这是因为
a,b,c都是正规式,所以 (b)*是正规式,((b)*c)是正规式,所以 (a|((b)*c))是正规式,省去不必要的括号后,正 规 式 为 a|b*c 。 它 的 正 规 集
L(a|b*c)=L(a)∪ L(b*c)=L(a)∪ L(b*)L(c)=L(a)∪ L*(
b)L(c)={a}∪ {b}*{c}={a}∪ {,b,bb,… }{c}={a,c,bc,bbc,
… }
39
[例 3.4]? ={a,b},则 R=a(a|b)*是上的正规式,它表示的正规集：
L(R)=L(a(a|b)*)=L(a)L((a|b)*)=L(a)(L(a|b))*
=L(a)(L(a)∪ L(b))*={a}({a}∪ {b})*={a}{a,b}*
={a}{ε,a,b,aa,ab,ba,bb,aaa,… }
={a,aa,ab,aaa,aab,aba,abb,aaaa,… }
即为?上 a开头的字符串集 。
40
[例 3.5]? ={a,b,0,1},则 R=(a|b)(a|b|0|1)*为上的正规式,
它表示的正规集
L(R)=L((a|b)(a|b|0|1)*)=L(a|b)(L(a|b|0|1))*
=L(a)∪ L(b))(L(a)∪ L(b)∪ L(0)∪ L(1))*
={a,b}{a,b,0,1}*
是?上 a,b开头的 a,b,0,1字符串的集合 。
41
二,正规式的性质定义 3.2?上正规式 R和 S,如果它所表示的正规集
L(R)=L(S),则称 R和 S等价,记为 R=S。
不难证明,正规式具有下列性质：
(1)交换律,R|S=S|R
(2)结合律,R|(S|T)=(R|S)|T
R(ST)=(RS)T
(3)分配律,R(S|T)=RS|RT
(R|S)T-RT|ST
(4)同一律,εR=Rε=R
42
三,正规式与正规文法正规式与正规文法都用来描述程序语言的词法结构,
它们有着相同的表达能力：对任一正规文法,都可找到一个正规式,使正规式表示的正规集恰为正规文法产生的语言,反之亦然 。 正规式简洁,正规文法易识别,根据需要,可在两者之间进行转换,这里不详细讨论了 。
43
§ 3.3 有限自动机有限自动机 (FA)是更一般化的状态转换图,有确定有限自动机 DFA与非确定有限自动机 NFA之分 。 DFA
识别快,易为计算机直接实现 。
一,有限自动机的定义定义 3.3 一个非确定有限自动机 Mn (记为 NFA Mn )是一个五元组 Mn=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是唯一的一个初态；
F? S,是一个终态集；
是 S×?-->2s的一个单值映射,即：
(si,a)={s1,s2,… },其中 si?S,a,2s?S
44
定义 3.4 一个确定有限自动机 Md (记为 NFA Md )是一个五元组 Md=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是唯一的一个初态；
F? S,是一个终态集；
是 S×?-->S的一个单值映射,即：
(si,a)={sj},其中 si,sj?S,a,
45
定义 3.5 一个有限自动机 M (记为 FA M )是一个五元组
M=(?,S,so,F,?),其中
是一个有穷字母表,它的每一个元素称为一个输入符号；
S是一个有限状态集,它的每一个元素称为一个状态；
so?S,是非空的初态集；
F? S,是一个终态集；
是 S×?-->2s的一个单值映射上述拓广在于：
(1)初始状态可以是一个初态集；
(2)输入字符串可以是上的字符串,包括空串 。
不难证实,定义 3.3与定义 3.5的描述能力是相同的,在此我们不予证明了 。
46
二,FA的表示用状态转换图或状态转换矩阵来表示一个有限自动机会更直观些 。
1.状态转换图用 m个结点表示 FA M的 m个状态，表示终态的结点用双圈表示，用起始标记?来表示初始状态的结点，
用有向边来表示状态变换的映射。如?(si,a)=sj可表示如图 3.10(a)，对于?(si,b)=sj可以表示如图 3.10 (b)。
a b
Si Sj SjSi
图 3.10 状态转换
(a) (b)
47
(a) 例 3.9的 NFA
S0 S3
S1
S2
S4
0,1
00
0,1
1
1
0,1
S0 S1
S3S2 1
1
00
1
1
00
(b) 例 3.10的 DFA
图 3.11 用状态转换图表示 FA
因此，例 3.9和例 3.10的 FA，
用状态转换图表示如图 3.11
所示。
48
2.状态转换矩阵一个有限自动机中,如果 |S|=m,|?|=n,则可用一个 m?n矩阵来表示上的状态变换 。
例 3.9,例 3.10的状态转换矩阵如图 3.12
所示,为清楚起见,用表的方式表示,
并列出状态集 S和字母表?。
49
三,FA M识别的的语言定义 3.6 对 FA M和任一?上的字符串?(即*)如果存在一条从初始状态到终止状态的通路,通路上有向边所标识的字符依次连接所得的字符串恰为?,则称?为 FA M所接受或称?为 FA M
所识别 。 为 FA M所能识别的字符串集称为 FA
M所识别的语言,记为 L(M)。
显然,若初态同时为终态,则?可为 FA M接受 。
例 3.9的有限自动机所识别的语言为含有两个相连的 0或两个相连的 1的字符串 。
例 3.10的有限自动机所识别的语言为含偶数个 0和偶数个 1的字符串 。
50
定义 3.7 给出 FA M和 FA M?,如果 L(M)=L(M?)，
则称有限自动机 M和 M?等价 。
定理 3.1 对任一给定的 NFA M一定存在一个 DFA
M?使：
L(M)=L(M?)
证明的基本思想是基于子集法,即将 NFA M中的状态子集定义为 DFA M?的一个状态,从 NFA
M出发可构造出等价的 DFA M?,这里不作形式化的证明,只在 NFA M的确定化一节中给出了构造等价的 DFA M?的算法 。
DFA是 NFA的特别,NFA可以有 DFA与之等价,
因此两者描述能力是相同的,DFA便于识别,
NFA便于定理证明,都是有用的 。
51
四,NFA M的确定化定理 3.1表明,任一给定的 NFA M,都可找到一个与之等价的 DFA M?,其基本方法是子集法,
具体方法如下：
首先定义 FA M的一个状态子集 I的?闭包,
-closure(I)：
(1)若 si? I,则 si -closure(I) ；
(2)若 si? I,则从 si出发,经?通路能到达的任何状态 sj,都有 sj -closure(I) 。
其次,对 FA M的一个状态子集 I及 a,可以定义状态子集 Ia?S,对任一 sj? Ia,必有 si? I，
使得 si与 sj之间存在一条通路,通路上的标记字符串恰为 a。
如果记 J为从 I的一个状态出发经过有向边而能到达状态集,则 Ia=? -closure(J)
52
然后按如下步骤确定化：
(1) 构造一张表,它共有 |?|+1列,第一列为状态子集 I,然后对每个 a分别设一列 Ia；
(2) 第一行第一列的状态子集 I为? -closure(S0),，
其中 S0为初始状态；
(3) 为第一列中的 I和每个 a,求 Ia,并记入相应的列,如果它不同于第一列中已有的状态子集 I,则将它列入第一列中 。
(4) 重复 (3),直到对每个 I及 a均已求得,并且没有新的状态子集加入第一列时为止 。
上述过程在有限步后必可终止
(5) 将第一列中的每个状态子集,命名为新的状态,则上述转换表,便成为新的状态转换矩阵,其状态转换函数是上的单值映射,它相应于一个 DFAM’。
53
五,DFA M的简化定义 3.8 对一给定的 DFA M,有状态 si,sj
S且,si?sj,如果凡从 si出发能识别字符串?而停于终态,从 sj出发也能识别?此而停于终态,反之凡若从 sj出发能识别?
而停于终态,从 si出发也能识别此?而停于终态,则称 si和 sj是等价的,否则就是可区分的 。
显然,将 DFA M的两个等价状态合并得到
DFA M’,L(M)=L(M’)。
54
定义 3.9 如果 DFA M没有无关状态,并且没有彼此等价的不同的两个状态,则该 DFA M称为是归约的,或称为是简化了的 。
所谓无关状态是指：对一个处于初始状态的 FA
M,任何输入序列都不能到达的状态 。 一个
FA M 删去了无关状态后得到 FA M’,则
L(M)=L(M’)。
因此一个 DFA M如果不是归约的,则首先应删去无关状态,再合并等价状态 。
不难检验上述等价定义构成了状态间的等价的一个等价关系,按此等价关系可对状态集 S作等价分割,然后将每一个等价类合并为一个新的状态,这样得到的 DFA M’,显然是 DFA M
的简化 。
55
二,由正规式构造等价的 NFA M
定理不只是证明了 NFA与正规式间的等价性,而且也给出了构造 NFA M的方法 。
为了减少状态数和有向边,实际采用下列三条分解规则来构造 NFA M。 这时,
状态之间的有向边上标记可拓广为正规式,这三条规划分别如图 3.21所示 。
56
R1|
R2
R1
R2
R*
si sj
si sj
si sj
si sj
si sk sj
si sk sj
图 3.21 转换规则
57
对于给定的正规式 R：
第一步,构造与之等价的 NFA M；
第二步,将 NFA M确定化为 DFAM’
第三步,将 DFAM’化简为 DFAM’’
习题,3.10
