陈火旺编译原理chapter3

第三章词法分析词法分析的主要任务：自左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造为单词符号串的中间程序。

P1

©张捷§3.1对于词法分析器的要求3.1.1词法分析器的功能和输出形式（1）词法分析器的功能：输入源程序，输出单词符号把构成源程序的字符串转换成语义上关联的单词符号的序列5种单词符号：⑴

关键字：程序语言定义的具有固定意义的标识符。⑵标识符：表示各种名字。⑶常数：整型、实型、布尔型、文字型。⑷运算符：如＋、－、*、/⑸界符：如,;()/**/等

P2

©张捷（2）单词符号：一个程序语言的基本语法符号，输出的单词符号常表示成二元式：（单词种别，单词符号属性值）

单词种别

标识符

一种

常数

一种，整数、实数、布尔用整数编码

关键字

全体视为一种或一字一种

算符

一符一种

界符

一符一种

单词符号属性值

如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。

单词符号属性是指单词符号的特性或特征，属性值则是反应特性或特征的值。

P3

©张捷例如：某个标识符常将存放其相关信息的符号表项指针作为其属性值；某个常数则将存放它的常数表项的指针作为其属性值。

P4

©张捷例如：C++代码段：while(i>=j)i--;

经过词法分析器处理后转换为这样的单词符号序列：

<while,-><(,-><id,指向i的符号表项的指针><>=,-><id,指向j的符号表项的指针><),-><id,指向i的符号表项的指针><--,-><;,->

P5

©张捷6【课堂练习】写出下面程序的单词符号序列

while(*p!='\0'){p++;}while <while

，->( <(，->* <*，->p <ID，符号表入口指针>!= <!=，->'\0' <CONST，常数表项的指针>) <)，->{ <{，->p <ID，符号表入口指针>++ <++，->; <;，->} <}，->

P6

©张捷3.1.2词法分析器作为一个独立子程序在实现编译程序时，常将词法分析程序从语法分析中独立出来，作为一个独立的阶段。这样做有什么好处？可使编译程序结构更简洁，清晰和条理化可用更有效的特殊方法和工具进行处理/改进编译程序的效率有利于集中力量考虑其他枝节问题/增强编译程序的可移植性但不一定是独立的一遍（如果独立一遍则要保存源程序的内码形式），可设计一个独立的子程序（语法分析器调用之）。

P7

©张捷§3.2词法分析器的设计3.2.1输入、预处理

输入缓冲区（输入串存放其中）。预处理（注释、没有意义的空格、跳格、回车、换行等）预处理子程序：当词法分析器调用时处理一串确定长度的输入字符并装入扫描缓冲区。词法分析器对扫描缓冲区扫描时采用2个指示器：一个指向当前单词的开始位置（起点指示器）；另一个用于向前搜索以寻找单词的终点（搜索指示器）。

P8

©张捷扫描缓冲区的设计：起点指示器搜索指示器输入缓冲区预处理子程序扫描器扫描缓冲区输入单词符号列表图3.1词法分析器

P9

©张捷二、扫描器——词法分析的主要部分扫描器的构造原理设置二个指示器（起点指示器、搜索指示器），一个可以互补使用的一分为二的扫描缓冲区，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。扫描缓冲区总长度为2×120个字符，扫描器单词长度的要求是单词长度≤1/2扫描缓冲区长度。

P10

©张捷2．扫描器的工作原理调用预处理子程序，把120个输入字符装进扫描缓冲区的某半区，搜索指针从起点指针开始向前寻找单词的终点，若在该半区内查找到单词的终点，便输出二元式，再把起点指针移到此处的后一个字符，继续搜索下一个单词，如果在搜索到该半区的边缘，尚未到达单词终点，那么就调用预处理子程序，把后续的120个字符装进另半区，继续搜索。

P11

©张捷3.2.2单词符号的识别：超前搜索 超前搜索：识别的单词符号的简单方法

关键字的识别：象FORTRAN这样的语言，对关键字不加保护，关键字的识别较麻烦。 例如：FORTRAN中的如下代码

1DO99K=1,10 2IF(5.EQ.M)I=10 3DO99K=1.10 4IF(5)=551、2是DO和IF语句，3、4是赋值语句。

P12

©张捷标识符的识别：后跟算符或界符；常数的识别：算术常数、布尔常数、字符串；算符和界符的识别：对于复合运算符，超前搜索；

了解某个源语言的词法规则就可以为它设计一个词法分析器了。设计词法分析器的一种非常好的工具就是状态转换图。

P13

©张捷三、状态转换图-设计词法分析器的好工具（好途径）1．转换图是一张有限方向图

结点

代表状态，用圆圈表示

箭弧

状态之间的连接，箭弧上的标记（字符）代表

在射出结点状态下可能出现的输入字符或字符类。

初态

识别出某一类字符串的开始，初态只有一个

终态

识别出某一单词，至少有一个。用双圈表示

P14

©张捷3.2.3状态转换图-设计词法分析器的好工具（好途径）

状态转换图是一个有限方向图，结点代表状态，用圆圈表示箭弧状态之间的连接，箭弧上的标记（字符）代表在射出结点状态下可能出现的输入字符或字符类。初态识别出某一类字符串的开始，初态只有一个终态识别出某一单词，至少有一个。用双圈表示132XY(a)转换图示例01②字母其它字母或数字*(b)识别标识符的转换图

P15

©张捷01②数字其它数字*(c)识别整数的转换图012345⑦*6数字数字数字数字数字数字其它其它数字E或DE或D＋或－(d)识别FORTRAN实型常数的转换图

P16

©张捷17Ｃ语言无符号整数的描述十进制整数:(DEC，值)dec→0|(1|...|9)(0|...|9)*BCA01-90-9其它

十进制整数

P17

©张捷18识别标识符符过程12字母字母或数字其它初态*终态3

P18

©张捷19利用状态转换图识别单词1.从初态出发2.读入一个字符3.按当前字符转入下一状态4.重复2,3直到无法继续转移5.若当前状态是终止状态，说明读入的字符组成一个单词；否则，说明输入不符合词法规则

P19

©张捷

一个状态转换图可用于识别（或接受）一定的字符串。大多数程序语言的单词符号都可以用转换图予以识别。作为一个综合例子，我们来构造一个识别某个简单语言的所有单词符号的转换图。表3.1列出了这个小语言的所有单词符号，以及它们的种别编码和内部值。

P20

©张捷表3.1单词符号及内部表示单词符号种别编码助忆符内码值

DIM1

$DIM-

IF2

$IF-

DO3

$DO-

STOP4

$STOP-

END5

$END-标识符6

$IDID在符号表中的位置常数(整)7

$INTINT在常数表中的位置＝8

$ASSIGN-＋9

$PLUS-*10

$STAR-**11

$POWER-

,12

$COMMA-

(13

$LPAR-

)14

$RPAR-

P21

©张捷3点限制：⑴所有关键字都是保留字，避免采用超前搜索技术。⑵保留字表；关键字不专设对应的转换图。⑶

关键字、标识符和常数之间无界符、算符，则必须至少用一个空白符隔开。这些限制仅仅是为了现阶段将例子做得简单些；在这些限制下，多数单词符号的识别就不必使用超前搜索技术。

P22

©张捷01②空白字母字母或数字非字母或数字*3④⑬⑤数字数字非数字*＝⑥＋7*⑧*非*⑨*，()其它⑫⑪⑩……图3.3对简单语言进行词法分析的状态转换图

P23

©张捷注：一个程序语言的所有单词符号的识别也可以通过多张状态转换图加以描述。3.2.4状态转换图的实现（程序实现）引进全局变量和过程：⑴ch

字符变量，存放最新读进的源程序字符；⑵strToken

字符数组，存放构成单词符号的字符串；⑶GetChar子程序过程，将下一个输入字符读到ch中，搜索指示器前移一字符位置；⑷GetBC

子程序过程，检查ch

中的字符是否为空白。若是则调用GetChar直至ch中进入一个非空白字符；

P24

©张捷⑸Concat子程序过程，将ch中的字符连接到strToken之后；⑹IsLetter和IsDigit布尔函数过程，分别判断ch中的字符是否为字母和数字；⑺Reserve整型函数过程，对strToken中的字符串查找保留字表，如果它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）；⑻Retract子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符；⑼InsertId

整型函数过程，将strToken中的标识符插入符号表，返回符号表指针；

P25

©张捷⑽

InsertConst

整型函数过程，将strToken中的常数插入常数表，返回常数表指针；构造状态转换图对应的程序，一般让每个状态结点对应一段程序段。不含回路的分叉结点：可对应switch语句或if语句含回路的状态结点：可对应循环语句（while）iljkij字母数字/字母或数字其它（a）（b）图3.4状态转换图（a）具有不含回路的分叉结点的转换图；（b）具有含回路的状态结点的转换图；

P26

©张捷·由状态转换图编写扫描器的一般方法

P27

©张捷

P28

©张捷

终态结点对应一个形如return(code,value)的语句，意味着从分析器返回到调用者（语法分析器）。对带星号*的终态结点意味着多读入一个字符，这个字符应予退回，也就是说，必须把搜索指示器回调一个字符位置。应该使用Retract过程来完成。

P29

©张捷

状态转换图3.3的词法分析器构造：intcode,value;strToken:=“”;/*置strToken为空串*/GetChar();GetBC();if(IsLetter())begin

while(IsLetter()orIsDigit())begin

Concat();GetChar();endRetract();code:=Reserve();

if(code=0)beginvalue:=InsertId(strToken);

return($ID,value);endelse

return(code,-);end

P30

©张捷elseif(IsDigit())begin

while(IsDigit())begin

Concat();GetChar();endRetract();value:=InsertConst(strToken);

return($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);elseif(ch=‘*’)begin

Getchar();

if(ch=‘*’)return($POWER,-);Retract();return($STAR,-);end

P31

©张捷elseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseif(ch=‘{’)return($LBRACE,-);elseif(ch=‘}’)return($RBRACE,-);elseProcError(); /*错误处理*/【实验】用一种程序设计语言设计上面的词法分析程序

P32

©张捷§3.3正规表达式与有限自动机3.3.1正规式与正规集

递归定义：⑴ε和都是∑上的正规式，其所表示的正规集分别为：{ε}和；

⑵任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}；⑶假定U和V都是∑上的正规式，它们所表示的正规集分别记为L(U)和L(V),那么(U|V)、(U·V)和(U)*也都是正规式，所表示的正规集分别为：L(U)∪L(V)、L(U)L(V)和(L(U))*；仅由有限次使用上述三个步骤而得到的表达式才是∑上的正规式，由这些正规式所表示的字集才是∑上的正规集。

P33

©张捷34正规式和正规集的例子例1令Σ={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,…}

P34

©张捷

例3.1令∑={a,b},下面是∑上的正规式和相应的正规集。 正规式 正规集

ba* ∑上所有的以b为首后跟任意多个a的字

a(a|b)*

∑上所有的以a为首的字

(a|b)*(aa|bb)(a|b)*

∑上所有含有2个相继的a或者2个

相继的b的字例3.2令∑={A,B,0,1},下面是∑上的正规式和相应的正规集。 正规式 正规集

(A|B)(A|B|0|1)* ∑上“标识符”的全体

(0|1)(0|1)*

∑上“数”的全体

P35

©张捷36一个正规式r表示的正规集也就是r的语言，记为L(r)例:r=letter(letter|digit)*

表示的语言为：L(r)=L(letter)(L(letter)∪L(digit))*={A,…,Z,a,…,z}({A,…,Z,a,…,z,0,…,9})*

P36

©张捷如果两个正规式所表示的正规集相同，则认为这两个正规式等价：U=V

L（U）=L（V）

例如：b(ab)*=(ba)*b,(a|b)*=(a*b*)*令U、V、W均为正规式，则下面的关系普遍成立：

①U|V=V|U(交换律) ②U|(V|W)=(U|V)|W（结合律） ③U(VW)=(UV)W(结合律) ④U(V|W)=UV|UW(分配律) (U|V)W=UW|VW ⑤εU=Uε=U

P37

©张捷38正规式运算符的优先级* 高于"连接"高于|“连接”高于|，具有结合律、分配律| 具有交换律、结合律() 指定优先关系

P38

©张捷3.3.2确定有限自动机(DFAdeterministicfiniteautomation)

一个确定的有限自动机(DFA)M是一个五元式：M=(S，∑，δ，s0，F)其中：

S是有限状态集；∑是有穷字母表；每个元素称为一个输入字符。δ是S×∑至S的单值部分映射，δ(s，a)=s′表示现行状态s，输入字符为a时将转换到下一状态s′。称s′为s的一个后继状态。

s0∈S是唯一的初态；

F

是一个终态集（可为空）

P39

©张捷40DFA的例子M=({S,Z,A,B},{a,b},δ,S,{Z})其中δ为δ(S,a)=A δ(S,b)=Bδ(A,a)=Z δ(A,b)=Bδ(B,a)=A δ(B,b)=Zδ(Z,a)=ZaSABZababab=>

P40

©张捷状态转换矩阵（行：状态，列：输入字符，矩阵元素为δ(s,a)）

例如：DFAM=({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

对应状态转换矩阵如表3.2:表3.2状态转换矩阵状态ab012132213333

P41

©张捷

对应状态转换图:

一个DFA可以表示成一个（确定的）状态转换图。

假定DFAM含m个状态和n个输入字符，则这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用∑中的一个不同输入字符作标记。整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点0③12aaabbba,b图3.5状态转换图识别所有含有相继两个a或相继两个b的字。

P42

©张捷3.可识别

对于∑*中的任何字α，若存在一条从初态结点到某一终态结点的通路上所有弧的标识符连接成的字等于α，则称α可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字ε可为M所识别（接受）。DFAM所能识别的字的全体记为L(M),

L(M)是一个正规集。

P43

©张捷定理如果一个DFAM的输入字母表为∑

,则称M是∑上的一个DFA。可以证明：∑上的一个字集V⊆∑*是正规的，当且仅当存在∑上的DFAM使得V=L(M)。

DFA的确定性：映射δ：S×∑→S是一个单值函数，即s∈S，a∈∑，δ(s,a)唯一确定下一状态。从转换图的角度看，每一状态节点至多有n条弧射出，且每条弧有各自不同输入字符。若允许δ是一个多值函数，就得到非确定有限自动机。

P44

©张捷3.3.3非确定有限自动机(NFA)

一个非确定的有限自动机(NFA)M是一个五元式：M=(S,∑,δ,S0,F)其中：S是有限状态集； ∑是有穷字母表；

δ是S×∑*至S的幂集的映射即δ：S×∑*→2s

S0S是非空的初态集；

FS是一个终态集（可为空）NFA和DFA的不同在于:δ的值域是S的幂集，δ：SΣ*

→2S开始状态有不止一个箭弧上的输入字可以用正规式表示

P45

©张捷46NFA的例子M=({S,Z,A,B},{a,b},δ,{S},{Z})

δ

：δ(S,a)={A} δ(S,b)={B}δ(A,a)={Z} δ(A,b)={B}δ(B,a)={A,B}δ(B,b)={Z}δ(Z,a)={A,Z}δ(Z,b)={}SABZabababaaa

P46

©张捷2．表示形式状态转换图一个含有m个状态和n个输入字符的NFA可表示成如下状态转换图。该图含有m个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用∑*中的一个字（可以相同的字且可以是空字ε)作标记（输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点，某些结点既可以是初态结点也可以是终态结点。

P47

©张捷

对于∑*中的任何一个字，若存在一条从某一初态结点到某一终态结点的通路而且通路上所有的弧的标记字依次连接成的字等于，则称可为NFA所识别（读出或接受）。若M的某些结点既是初态结点又时终态结点或者存在一条从某个初态结点到某个终态结点的ε的通路，那么空字ε可为M所接受。识别所有含有相继两个a或相继两个b的字。图3.6′

非确定有限自动机3012(a|b)*aa|bb(a|b)*

P48

©张捷显然：DFA是NFA的特例，但是对于每个NFAM存在一个DFAM〃,使得L(M)=L(M〃)证明：⑴假定NFAM=<S，∑，δ，S0，F>，对于M的状态转换图进行以下改造：①引入新的初态结点X和终态结点Y；X,YS，从X至S0中任意初态结点连一条ε有向弧，从F中任意终态结点连一条ε有向弧到Y。②对M的状态转换图使用图3.7所示的替换规则进行替换，其中k是最新引入状态。

P49

©张捷

重复上述替换，直到每条弧的标记或为ε或为∑中单个字母，即可得到NFAM′，显然L(M′)=L(M)。⑵

将M′变换成DFA，方法如下：

①假定I是M′状态集的子集，定义I的ε闭包ε_closure(I)为：

(a)若q∈I，则q∈ε_closure(I) (b)若q∈I，则从q出发经过任意条ε弧而能到达的任何状态q′∈ε_closure(I) ijAB代之以ijkABi代之以代之以ijA|BjABAijkεεijA*图3.7替换规则

P50

©张捷②假定I是M′状态集的子集，a∈∑，定义

Ia=ε_closure(J)

其中J是那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全体。分两步：1、求J=Move(I,a);2、求J的ε闭包ε_closure(J)③假定∑={a1,……,ak}，构造表（即状态转换表）含(k+1)列，首行首列为ε_closure(X)；如果某一行第一列的状态子集已经确定，例如记为I，那么置该行的i+1列为Iai(i=1,……,k)；然后检查该行上的所有状态子集，看它们是否已在表的第一列中出现，将未曾出现者填入到后面空行的第一列。重复上述过程直至出现在第i+1列(i=1,……,k)上所有的状态子集均已在第一列上出现。因为M′的状态子集个数是有限的，故必定在有限步内终止。

P51

©张捷视该表为状态转换表，将其中每个状态子集视为新的状态，显然，该表唯一地刻划了一个DFAM〃，初态是首行首列的那个状态，终态是那些含有原终态的状态子集。根据上述构造方法，显然有：L(M〃)=L(M′)=L(M)

上述把NFA确定为DFA的方法为子集法。【例3.3】

正规式(a|b)*(aa|bb)(a|b)*对应的NFA如图3.6所示，其中X为初态，Y为终态。按照上述证明过程构造出来的状态转换矩阵见表3.3。YX534126aεbεaabbεabε图3.6非确定有限自动机

P52

©张捷

正规式（a|b）*(aa|bb)(a|b)*对应的NFA构造NFAX534126aεbεaabbεabε

P53

©张捷表3.3对应于例3.3中正规式的状态转换矩阵IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}

P54

©张捷对表3.3中所有状态子集重新命名，得到表3.4所列的状态转换矩阵。表3.4对表3.3中状态子集重新命名后的状态转换矩阵状态ab012132215334465565634

P55

©张捷与表3.4相对应的状态转换图如图3.8所示。其中0为初态，3，4，5，6为终态。⑤③④⑥210bbbabbbbaaaaaa图3.8未化简的DFAa,ba43012εbε【课堂练习】：将下面的NFA确定化为DFAa(a|b)*b

P56

©张捷四、确定有限自动机的化简一个确定有限自动机M的化简是指：寻找一个状态数比M少的DFAM′，使得L（M）=L（M′）1．状态等价和可区别（1）状态等价假设s和t是M的两个不同状态，若从状态s出发能读出某个字ω而停于终态，那么，同样从t出发也能读出同样的字ω而停于终态，反之，若从t出发能读出某个字ω而停于终态，则从s出发也能读出同样的字ω而停于终态，则称s和t是等价的。（2）可区别若DFAM的两个状态s和t不等价，则称s和t是可区别的

P57

©张捷2.化简（最少化）一个DFAM的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一个子集中的任何两个状态都是等价的，在每个子集中选出一个代表同时消去其它等价状态

例1：终态和非终态是可区别的。原因：终态能读出空字ε而非终态不能读出空字ε。例2：图3.8中的状态1和状态2是可区别的。⑤③④⑥210bbbabbbbaaaaaa图3.8未化简的DFA

P58

©张捷分划步骤：（1）初始分划将S的终态和非终态分开成2个子集(可区别的)，形成基本划分∏；

∏

={Z，S-Z}△{I(1),I(2)}（2）进一步分划

设∏含m个子集：∏＝{I(1),I(2),……,I(m)}并且属于不同子集的状态是可区别的。分析I(i)是否可进一步划分：

对于某I(i)，令I(i)={q1,q2,…,qk}，若存在一个输入字符a使得Ia(i)不全包含在现行Π的某一子集I(j)中，就将I(i)一分为二。例如，假定状态s1和s2经a弧分别达到状态t1和t2，而t1和t2属于现行Πm的两个不同子集。将I(i)分成两半，使得一半含有s1：

I(i1)={s|s∈I(i1)且s经a弧到达t1所在子集中的某状态},

另一半含有s2：I(i2)=I(i)-I(i1)。

I(i1)中状态与I(i2)中的状态是可区别的，形成新的分划。重复上述分划过程，直至分划中所含子集数不再增长为止。即每个子集中状态是互相等价的，而不同子集中的状态则是可互相区别的。

P59

©张捷（3）选代表对于最后分划∏中的每一个子集，选取子集中的一个状态代表其它状态，I={q1,q2,…，qk}，挑选q1,凡导入到q2，…，qk的弧都改成导入到q1中，然后将q2，…，qk从原来的状态集s中删除。（4）经如此化简之后得到的DFAMˊ和原来的M是等价的，即L(M)=L(Mˊ)。

P60

©张捷⑤③④⑥210bbbabbbbaaaaaa图3.8未化简的DFA【例3.6】对图3.8所示的DFAM化简

P61

©张捷解：1°初始分划终态组{3，4，5，6}

非终态组{0，1，2}2°进一步分划考察{3，4，5，6}{3，4，5，6}a={3，6}{3，4，5，6}{3，4，5，6}b={4，5}{3，4，5，6}

则{3，4，5，6}不能分划ÍÍ

P62

©张捷3°

考察{0，1，2}

{0，1，2}a={1，3}Í{3，4，5，6}

{1，3}Í{0，1，2}

应把{0，1，2}一分为二

{0，2}a={1}，{1}a=3

形成{0，2}，{1}

至此整个分划含三组{3，4，5，6}{1}和{0，2}

4°

考察{0，2}

{0，2}b={2，5}Í{3，4，5，6}

Í

{1}

Í

{0，2}

将{0，2}一分为二，得{0}，{2}。

至此整个分划含四组{0},{1},{2},{3,4,5,6}。每组不可再分。

P63

©张捷5°选代表令状态3代表{3，4，5，6}，把原来导入4，5，6的弧全都导入3，并删除4，5，6，最后可得下图【作业】：P64：7(1)，12

0③12aaabbba,b图3.5状态转换图

P64

©张捷3.3.4正规文法与有限自动机(FA)的等价性对于正规文法G和有限自动机M，如果L(G)=L(M)，则称G和M是等价的。关于正规文法与有限自动机的等价性，有以下结论：

1

对于每一个右线性正规文法或左线性正规文法G，都存在一个FAM，使L(M)=L(G)。

2

对于每一个FAM，都存在一个右线性正规文法GR和一个左线性正规文法GL，使L(M)=L(GR)=L(GL)。证明1:(1)给定右线性正规文法G=(VT,VN,S,ρ),增加一个新的终结状态符号f，fVN

，令M=(Q,VT,,S,F),其中，F=f，Q=VN∪f。

P65

©张捷状态转换函数定义如下：

(a)产生式Aa,则令(A,a)=f(b)产生式AaA1aA2...aAn

则令

(A,a)=A1,A2,...,An

显然，上述M是一个NFA。

对于右线性正规文法G，在的最左推导过程中，利用AaB一次就相当于在M中从状态A经过一条a弧到达状态B(包括a＝ε)。利用Aa一次则相当于在M中从状态A经过一条a弧到达终态f(包括a＝ε)。故而，在正规文法G中，的充要条件是：在M中，从状态S到状态f有一条通路，其所有弧上的符号连接起来恰好等于w，即w∈L(G)当且仅当w∈L(M)，故L(G)=L(M)。Sw＋Sw＋

P66

©张捷

(2)给定左线性正规文法G=(VT,VN,S,ρ)。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，

q0VN

。令M=(Q,VT,,q0,S),其中，Q=VN∪q0,状态转换函数定义如下：

(a)产生式Aa,则令(q0,a)=A(b)产生式

A1Aa,A2Aa,…,AnAa

则令(A,a)=A1,A2,...,An

与(1)类似，可以证明L(G)=L(M)

对于左线性正规文法G，在的最左归约过程中，利用Aa一次就相当于在M中从状态q0经过一条a弧到达状态A(包括a＝ε)。利用ABa一次则相当于在M中从状态B经过一条a弧到达状态A(包括a＝ε)。当我们归约到开始符号S时，M恰好到达终态S。Sw＋

P67

©张捷证明2：设DFAM=(S,

,,s0,F)。(1)右线性正规文法G的构造方法如下：若s0F,则令G=(,S,s0,ρ),ρ的定义如下：对任何a及A,BVN,若有(A,a)=B,则：

(a)BF,AaB(b)BFAaaB

若s0F,新增s0′S,令s0′s0，用s0′做开始符号

(2)构造左线性正规文法，G=(,S,f,ρ),ρ定义如下：对任何a及A,BS,有(A,a)=B,则

(a)A是初态，B

a(b)A不是初态,BAa

P68

©张捷例3.4设DFAM=<{A,B,C,D},{0,1},δ,A,{B}>,其状态转换图如图3.9(a)所示。不难发现L(M)=0(10)*。BACD0100110,1⇒(a)BAfDC⇒0,100000111(b)图3.9状态转换图（a）初始的转换图；（b）从等价的右线性正规文法导出的转换图。

P69

©张捷(1)根据以上证明过程获得的右线性正规文法为：GR=<{0,1},{A,B,C,D},A,ρ>,其中ρ由下列产生式组成：

A→0|0B|1DB→0D|1CC→0|0B|1DD→0D|1D显然L(GR)=L(M)=0(10)*。(2)再从GR出发构造NFAM为：

M=<{A,B,C,D,f},{0,1},δ′,A,{f}>，

其中M的状态转换图如图3.9(b)所示。显然L(M)=L(GR)。(3)最后从NFAM出发构造左线性正规文法：GL=<{0,1},{B,C,D,f},f,ρ′>，其中ρ′由下列产生式组成：

f→0|C0C→B1B→0|C0D→1|C1|D0|D1|B0易证L(GL)=L(M)。

P70

©张捷3.3.5正规式与有限自动机的等价性

(1)对于任何FAM,都存在一个正规式r,使L(r)=L(M)。

(2)对于任何正规式r,都存在一个FAM,使L(M)=L(r)。证明1：对于上任一NFAM，能构造上一个正规表达式r，使得L(r)=L(M)。

把状态转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在M的转换图上加进x,y两个结点。从x用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到y，从而构成一个新的NFAM′，L(M)=L(M′)。下面，逐步消去NFAM′中的状态结点，直至剩下x,y为止。在消除结点的过程中，逐步用正规式标记弧。消除结点的过程是直观的，只需反复使用下面的替换规则。

P71

©张捷123r2r1123r2r1r313r1r213r1r213r1r2*r3替换规则代之以代之以代之以13r1r2

P72

©张捷证明2：对正规表达式r的运算符数目作归纳。（1）设r具有零个运算，则r=或r=

或r=a（2）假设结论对少于k(k1)个运算符的正规表达式r成立。当r有i个运算时，有三种情况：情况1：r=r1r2

情况2：r=r1r2情况3：r=r1*

有M1=(S1,1,1，q1,{f1}),M2=(S2,2,2，q2,{f2})

且L(M1)=L(r1),L(M2)=L(r2)，且Mi没有从终态发出的弧。不妨设S1∩S2=,由M1和M2构造M,使得L(M)=L(r).构造方法图示如下：q0q0q1q0q1ar=r=

r=a

P73

©张捷q0q1f1f2q2f0M2M1q0q1f1q2f0M2M1f2q1f1r=r1r2r=r1*r=r1r2M1

P74

©张捷上述证明方法，是对于一个正规表达式r,构造一个FAM,且L(M)=L(r)的算法。【例3.5】与正规式r1=1*,r2=01*,r3=01*|1等价的有限自动机：q7q5q6q81εεεε(a)对应于正规式1*的转换图⇒

P75

©张捷⇒q3q6q5q7q4q80εεεεε1(b)对应于正规式01*的转换图q1⇒q3q6q5q7q4q100εεεεε1(c)对应于正规式01*|1的转换图q7q9q2εε1εε图3.13与正规式等价的有限自动机(a)对应于正规式1*的转换图；(b)对应于正规式01*的转换图；

(c)对应于正规式01*|1的转换图。

P76

©张捷正规文法NFA正规表达式123456DFA最小化重要结论：由上述三个证明可以得到正规文法、正规式、DFA和NFA在识别语言能力上是等价的。

P77

©张捷（1）有限自动机(FA)正规文法1.对转换函数δ(A,t)=B，可写成一个产生式:A→tB算法:2.对终态Z,增加一个产生式:Z→ε3.有限自动机的开始状态对应于文法的开始符号,

有限自动机的字母表对应于文法的终结符号集。ABt

P78

©张捷【例】:给出如图NFA等价的正规文法GABCDstartaaabbbbG=（{a，b}，{A，B，C，D}

，A，P）其中P:AaBAbDBbC

CaACbDCεDaBDbDDε→→→→→→→→→1.对转换函数δ(A,t)=B，可写成一个产生式:A→tB2.对终态Z,增加一个产生式:Z→ε3.有限自动机的开始状态对应于文法的开始符号,

有限自动机的字母表对应于文法的终结符号集。

P79

©张捷（2）正规文法G有限自动机M算法:1.M的字母表与G的终结符号集相同.2.M的开始状态S对应G的开始符号S;

为G中的每个非终结符生成M的一个状态,3.增加一个新状态Z,作为NFA的终态4.对G中的形如A→tB的产生式,其中t为终结符或ε,A和B为非终结符,构造M的一个转换函数δ(A,t)=B5.对G中的形如A→t的产生式,构造M的一个转换函数

δ(A,t)=Z

P80

©张捷【例】:求与文法G[S]等价的NFAG[S]:S→aA|bB|ε

A→aB|bA

B→aS|bA|εSZABstartaaabbbεε求得：

P81

©张捷1.(a)对于正规式φ,构造NFA:

(b)对于正规式ε,构造NFA:

(c)对于正规式a,a∈Σ,则NFA:xyxyεxya（3）正规式有限自动机FA

P82

©张捷2.若s,t为Σ上的正规式,相应的NFA分别为N(s)和N(t);(a)对于正规式R=s|t,NFA(R)xyN(s)N(t)εεεε

或:N(s)xN(t)y

(b)对正规式R=st,NFA(R)xyN(s)N(t)εεε(c)对于正规式R=s*,NFA(R)xyN(s)εεεε

P83

©张捷【例】:为R=(a|b)*abb构造NFA,使得L(N)=L(R)从左到右分解R,令r1=a,第一个a,则有

23a令r2=b,则有

45b令r3=r1|r2,则有

164532abεεεε令r4=r3

则有:

164532abεεεε*0ε7εεε

P84

©张捷令r10=r4r9

则最终得到NFAM:

164532abεεεε0ε7εεε1089abb令r5=a,令r6=b令r7=b令r8=r5r6令r9=r8r7

则有

910b87baR=(a|b)*abb

P85

©张捷例:M:03214starta,ba,ba,bbbaa解:(1)加x,yx03412yεεεaa,ba,ba,babb（4）有限自动机正规式

P86

©张捷解:(1)加xyx03412yεεεaa,ba,ba,babb(2)消除M中的所有结点a|bx024yεεεaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bεxy(a|b)*(aa|bb)(a|b)*

P87

©张捷利用以下转换规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.规则规则1规则2规则3文法产生式正规式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y（5）正规文法正规式例:有文法G[s]

S→aA|a,

A→aA|dA|a|d于是:S=aA|aA=(aA|dA)|(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)|ε)

P88

©张捷算法:1)对任何正规式r,选择一个非终结符S作为开始符号.

并产生产生式S→r2)若x,y是正规式,对形为A→xy的产生式,重写为

A→xBB→y,其中B为新的非终结符,B∈VN

同样:对于A→x*yA→xAA→yA→x|yA→xA→y例:将R=a(a|d)*转换成相应的正规文法解:1)S→a(a|d)*

2)S→aA

A→(a|d)*S→aA

A→(a|d)AA→εS→aA

A→aA|dAA→ε（6）正规式正规文法

P89

©张捷3.4词法分析器的自动产生一个描述词法分析器的LEX程序由一组正规式和与每个正规式相应的一个“动作”（Action）组成。动作本身是一小段程序代码，指出了当按正规式识别出一个单词符号时应采取的行动。将LEX程序编译后所得的结果程序记为L，作用相当于FA，可用来识别和产生单词符号。结果程序L含有一张状态转换表和一个控制程序。LEX编译程序词法分析器L词法分析器LLEX源程序输入串单词符号串图3.14LEX编译系统的作用

P90

©张捷

3.4.1语言LEX的一般描述LEX程序包括2个部分：

(a)正规定义式：∑上的正规定义式是如下的定义序列，

d1→r1，d2→r2,……,di→ri

di

表示不同的名字，每个ri

是∑∪{d1,……,di-1}上的符号所构成的正规式。ri不含有di,di+1,……,dn，对于任何ri可以构成一个∑上的正规表达式，只要反复地将式中出现的名字代之以相应的正规式即可。

(b)识别规则：例：Pascal标识符的集合可表示成下列正规定义式：

letter→A|B|……|Z|a|b|……|z digit→0|1|……|9 id→letter(letter|digit)*

P91

©张捷例：Pascal无符号数的集合可由下列正规定义式表示：

digit→0|1|……|9 digits→digitdigit* fraction→.digits exponent→

E(+|-|ε)digits num→

digits(fraction|ε)(exponent|ε)LEX源程序中的识别规则是一串如下形式的LEX语句：

P1{A1}

P2{A2}

…………… Pm{Am}

其中每个Pi是一个正规式，称为词形。Pi中除出现∑中的字符外，还可以出现正规定义式左部所定义的任何简名di,即Pi是∑∪{d1,……,dn}上的一个正规式。由于每个di最终都可化为纯粹∑上的正规式，Pi也同样如此。

P92

©张捷

Ai是一小段程序代码，指出了在识别出词形为Pi的单词之后词法分析器应采取的动作。识别规则完全决定了词法分析器L的功能。分析器只能识别具有词形P1……Pm的单词符号。LEX所产生的目标程序L(词法分析器)如何工作：扫描字符、寻找最长子串匹配Pi，放入Token缓冲区中，L调用动作子程序Ai，当Ai工作完后，L将所得单词符号二元式交给语法分析程序。L重新调用时重复此过程。特殊情况：(a)找不到词形Pi与输入串匹配，L应报错（含非法字符串等）及相应处理。

(b)存在一个最长子串匹配若干个不同的Pi(二义情况)，以最先出现的Pi为准。(服从最长匹配前提下前面的Pi匹配优先权高)与Pi对应的Ai返回Pi的种别编码和属性值，用LEX过程表示为return(code,value)。

P93

©张捷Pi是标识符则value为符号表入口指针；Pi是整型常数则为常数表入口指针；如果既不是标识符又不是整型常数则无意义；AUXILIARYDEFINITIONS