第03章 有限自动机和词法分析

第03章有限自动机和词法分析主要内容：词法分析过程涉及的几个问题词法分析器的生成技术有限自动机正则表达式3.1词法分析有关词法分析器的几个问题和处理方法：

1)词法分析器的功能、分类

2)单词的分类、Token表示

3)字符串、保留字的处理

4)空格符、制表符和换行符

5)复合型符号

6)括号类匹配预检

7)词法错误校正

8) 词法分析独立化的意义3.1.1词法分析器的功能词法分析器功能：读源程序的字符序列，逐个拼出单词,并构造相应的内部表示TOKEN。同时检查源程序中的词法错误。引入Token的原因：编译程序总是用某种程序语言书写的程序，语言的操作对象只能是该语言规定的各种数据。而编译程序的操作对象是程序中的各种语法单位，因此，必须把它们表示成某种数据结构形式。

词法分析器的两种形式:CharList

独立词法分析器语法分析TokenList

附属词法分析器语法分析callTokenCharList3.1.2单词的内部表示Token定义：Token表示最小的语义单位--单词的信息。即：单词内部表示的数据结构形式。单词不是程序设计语言中的语法概念，是编译程序中引进的一个概念。是最小的语义单位，不能分割。Token中需要记录有关单词的信息：单词的类别码(Token.class)：标识单词的种类---词法信息单词的特征属性（Token.seman，标识符名，符号表地址等）：---语义信息Token设计示例程序表示ASC∏Token.classToken.semanIf9666019666Then478656E602478656E6Begin26567696E60326567696E6End56E6460456E646+B205B2(820682单词的分类:标识符：字母打头的字母/数字串整常数：数字打头的数字串实常数：整数.整数保留字：begin，end，var，read，write，integer，real符号：+，*，(，)，:，:=，;控制：(换行符）字符串：

标识符的语义信息的表示方法有两种：

a字符数组法：字符串空间中的地址被表示为对偶地址（head,leng），如下图所示：

b指针数组法：字符串空间中的地址用指针表示，如下图所示：(4,3)(2,2)

x1z12名表“x1”“z12”heighteofageeofx1eofyeof0123保留字的处理：两种识别保留字的方法：

1.建立保留字表：顺序、散列、散列＋顺序2.拼写的同时进行判断：自动机

例：假设保留字只有begin和end的情况见下图：beginndeNot(e)Not(g)Not(i)Not(n)Not(b,e)Not(n)Not(d)该方法的优点：速度快；缺点：自动机太大。

运算符的处理：

1.不区分，统一成一类

2.区分，每个运算符为一类

空格符和制表符以及换行符的处理

1.无用的空格符和制表符要删掉；2.字符串内的空格不能删；

实现方法：进入字符串时令标志变量StringFlag为true,退出时为false。3.换行符不能删，用于错误定位。括号类配对预检括号类：

如：begin…end,if…then,[],{},()，record…end处理方法：

对每类括号设置一个计数器（初值=0）每当遇到开括号，则计数器加1每当遇到闭括号时，计数器减1词法分析结束时，如果计数器0，则表明括号不匹配，报错。向前看多个字符的处理对于复合型特殊符，如“:=”的处理方法：读到“:”时不能判断是否为冒号，必须读下一字符。下图是对枚举类型如10..100和实数如3.14的处理：D.D..DD注：对于pascal和Ada等语言至多向前看两个字符即名。例：错误单词12.3e+q的处理方法：每当一个字符被扫描时，缓存并判断已扫部分的类型或无效（Invalid），当不能进一步扫描时，进行倒退工作，返回最后Invalid前面的类型，如右表中返回RealConstant。BufferedTokenTokenFlag1IntegerConstant12IntegerConstant12.Invalid12.3RealConstant12.3eInvalid12.3e+Invalid词法错误校正词法错误种类：语言不允许的符号：#括号类配对错误：单词的后继符错（偶尔）：词法错误校正：

a删除已被读过的字符，并重新扫描未被读过的字符

b删除已读过的第一个字符，重新扫描它的后继部分的字符。校正后的标示词法分析独立化的意义1）使语法分析器和语义分析器的算法更加清晰和简练；

2）便于利用自动机、正则表达式等理论技术加以自动化；3）更加有利于构造出高效的词法分析器；

4）有利于编译器的移植。3.2有限自动机描述程序设计语言中的单词的识别过程。主要内容：确定有限自动机DFA的定义确定有限自动机DFA的实现非确定有限自动机NFANFA到DFA的转换DFA的化简一个确定的有穷自动机（DFA）M是一个五元组：M=（SS，Σ，，S0，Z）其中1.SS是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；3.是转换函数，是在SS×Σ→SS上的映射，即:如（ki，a）=kj，（ki∈SS，kj∈SS）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S0∈SS,是唯一的一个初态；5.ZSS,是一个终态集，终态也称可接受状态或结束状态。3.2.1确定的有穷自动机（DFA）定义:DFA的两种表示方式

状态转换图：

结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。

状态转换表：可用二维数组描述。标识出初始状态和终止状态。Trans（SI，a）＝SJDFA例1：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QDFA的状态图表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bbDFA的矩阵表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QabSUVUQVVUQQQQ字符状态0100DFA例2：整常数集：如16,135,258实常数集：如16.135,258.5S0dS1d0d.2d3dd1DFA例3：第二位为2的整数集(包括一位)：如x2ad标识符集：如x,ab3_7d2dL-L,DL,D∑*上的符号串t被M接受定义1：对于∑*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFAM所接受，若M的初态结同时又是终态结，则空字可为M所接受（识别）。定义2：若t∑*，f(S，t)=P，其中S为DFA

M的开始状态，PZ，Z为终态集。

则称t为DFAM所接受（识别）。∑*上的符号串t（我们将输入符号串t表示成t1tx的形式，其中t1∈∑，tx∈∑*）在M上在DFAM上运行的定义为：

f（Q,t1tx）=f（f（Q,t1）,tx）

其中Q∈K扩充转换函数f，是K×Σ*→K上的映射，且：

f（Q，）=Q例：证明t=baab被如下的DFA所接受。DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba,bb证明：

f（S，baab）

=f（f（S，b），aab）

=f（V，aab）

=f（f（V，a），ab）

=f（U，ab）

=f（f（U，a），b）

=f（Q，b）

=QQ属于终态。得证。3.2.2确定有穷自动机的实现DFA的确定性的特点：初始状态唯一。转换函数f:SSSS是一个单值函数，也就是说，对任何状态SSS,和输入符号a,f(S,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。没有空边。即没有输入为（）用DFA构造词法分析器的方法1状态转换表的形式：（数组T存放转换函数）

1.State(当前状态):=初始状态 2.读一个字符CurrentChar 3.如果CurrentCharEof并且

T(State,CurrentChar)error

则State:=新的状态T(State,Current)，

转到第2步工作。4.如果CurrentChar=Eof并且State=终止状态，则接受当前字符串，程序结束。否则报错

特点：程序短小，但占用存储空间多代码如下：intScanner(charinput[]){S:=S0;in=0;ch=input[in++];While(TT(S,ch)undef&&chEof){S=TT(S,ch);ch=input[in++];};If(ch=EOF&&SFinalStates)return(1)elsereturn(0)}用DFA构造词法分析器的方法2状态转换图的形式：

每个状态:对应一个带标号的case语句；

转向边:转向对应状态。特点：程序长，但占用存储空间少。

Switch(satate){case

Si:Switch(ch){Casea：satate:=Sj;break;Caseb：satate:=Sk;break;other:Error;}}ajbki3.2.3非确定有限自动机NFA定义：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中:

是字母表;SS:

是状态集;

S0:

是初始状态集;f:

是转换函数，但不要求是单值的;

f:SS(∪{})SSTS:

是终止状态集.NFA的特点：一个状态的不同输出边可标有相同的符号。允许有多个开始状态。允许输出边上标有空串符号。<<=:=:aa*3.2.4NFA到DFA的转换定理：对于每一个非确定自动机A,存在一个确定自动机A’,使得L(A)=L(A’).相关算法：

1）-闭包：close_（SS）

2）nextstate函数：nextstate（SS,a)

一、close_（SS）计算方法：1.首先令close_:=SS;2.若在close_中存在状态S，

1）它末被处理过；

2）它存在指向close_之外状态S1的边；则令：close_:=close_

{S1};3.重复2，直到close_不再变化为止。-闭包的例子：

iakdjcmbdci,j,k,mba则：close_(i)={i,j,k,m}二、nextstate的定义a0a2b1c则：nextstate(0,a)={1,2}定义：nextstate(SS,a)={s1|S(a)S1,SSS}如下图所示：三、NFA到DFA的转换过程:1.初始化：AllStateSet={SS0},UnHandledStateSet={SS0}；2.判断结束：若UnHandledStateSet空，则结束，否则转下；3.从UnHandledStateSet选择一个状态SS；4.对于每个符号a，做下面工作：

1）求SS1=Close(nextstate(SS,a)；

2）若SS1空，则TT[SS,a]=空；

3）否则，检查AllStateSet中有无SS1，

①若无，则把SS1追加到UnHandledStateSet和AllStateSet中，并令TT[SS,a]=SS1；②否则，令TT[SS,a]=SS1。5.从UnHandledStateSet中删除状态SS，并转向步骤2。NFA到DFA的转换例子：a03a2a1bacbabc[0][1,2][1,2][3*][1,3*][2][3*][2][1,3*][2][1,3*][2][2][3*]31,201,32acaaaba|cb*3.2.5DFA的极小化

状态等价:对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。

方法:

1)状态合并法;

2)状态分离法.

状态合并法（状态吸收方法）

寻找等价状态S1和S2，如果S2为初始状态，则S1和S2对调，S2的出现修改为S1，删除状态S2。

状态分离法

1）初始化为两个不等价状态集组：非终止状态组和终止状态组；2）对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态都等价为止。状态合并法的例子：134a|dc2b134ac2b67c5bd化简为：实现方法：134ac2b67c5bd第一步：画FA的状态转换表；abcd10252334*4*5667*7*第二步：4吸收7；abcd10252334*4*5664*#####第三步：3吸收6；abcd10252334*4*53##########第四步：2吸收5；abcd10222334*4*###############第五步：画出FA。abcd10222334*4*134a|dc2b3.3正则表达式主要内容：基本概念正则表达式定义及一些性质扩充的正则表达式及程序设计语言中单词的定义正则表达式的局限性。正则定义

3.3.1正则符号串集的相关基本概念

字母表：非空有限集，其元素称为符号或字母.

符号串：符号的有限序列，也称为字。或表示空串,空串集{}不同于空集。

符号串长度：符号串中字符的个数||,||=0,|ab|=2

符号串连接：和都是符号串，则为符号串的连接特别有：==

符号串集的乘积：A和B是符号串的集合，则称

AB={|A，B}特别有：A=A=A，其中表示空集。符号串的方幂：设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。

A0={}

A1=A,A2=AA

AK=AA......A(k个)

符号串集合的星闭包：

A*=A0A1A2A3......3.3.2正则表达式的定义若用RE表示上的正则表达式，用L(RE)表示RE所包含的字符串集合

，则：■

是正则表达式，即：RE

，其中L()={}。■

是正则表达式，即：RE

，其中L()={}。■a是正则表达式，即：aRE

，其中L(a)={a}。■

A和B是正则表达式，即ARE，BRE，则有：

(A)

RE

，L((A)) =L(A)

A|B

RE

，L(A|B) =L(A)L(B)

A·B

RE

，L(A·B) =L(A)L(B)

A*

RE

，L(A*) =L(A)*

例1：={a,b}.正则表达式eab*2.a(a|b)*

L(e)上所有以a为首后跟任意多个（包括0个）b的字符串集上所有以a为首的字符串集若D={0,1,2,，9}.则：RealC=D+.D+扩充的正则表达式：

A的正闭包：A+=A1A2A3......，即一次或多次重复任何符号:“…”在字母表中任何符号.符号范围:[0--9]{0,1,2,3,4,5,6,7,8,9}

[a--zA--Z]

[a—z]|[A--Z]

[abc]

(a|b|c)不在给定范围内的符号:~(a|b|c)或[^

a]可选:

（＋|-）?

//可选+或-或不选正则表达式的性质：

A|B=B|A 选择的可交换性

A|(B|C)=(A|B)C 选择的可结合性

A(BC)=(AB)C 连接的可结合性

A(B|C)=AB|AC 连接的可分配性(A|B)C=AC|BC连接的可分配性

A**=A*

幂的等价性例2：整常数集：IntC=D+实常数集：RealC=D+.D+标识符集：IDE=L(L|D|_)*3.3.3正则表达式的局限性：1）正则表达式不能用于描述配对或嵌套的结构；例：A={anban|n>0}2）正则表达式不能用于描述重复串。例：{wcw|w是a和b的串}无法用正则表达式表示（保证两边w是相同的）。原因是：正则表达式中没有变量。3.3.4正则定义正则定义：Mr//本质是为正则表达式命名功能：为较长的正则表达式提供一个简化了的名字

如：E=((a+bc)+(a+bc)(a+bc))(ab+c)+(ab+c)

其中a+bc出现了三次，ab+c出现了二次，如用正则定义可表示如下：

E1

a+bcE2

ab+cE

(E1+E1E1)E2+E2例3：标识符：

letter[a-zA-Z] digit[0-9] identifierletter(letter|digit)*数字：

整数Int[1-9]Digit*|0实数realInt.Int特殊符号：运算符ch+|-|…3.3.5正则表达式与有限自动机等价定理：对任一确定有限自动机A，存在一正则表达式e,使得L(A)=L(e),反之亦然。关系图：DFA正则表达式NFA正则表达式到FA的转换规则：13ab12a|b13b*123ab12ab123bR=(a|b)*abbxiy(a|b)*abbxjyεabbiεa|bxjyεabbiεab例：为R=(a|b)*abb构造NFA，使得L(N)=L(R)。xjyεbεiabklab123ab12ab12313ab12a|b13ab*

cabcDFA到正则表达式的转换规则：例：03124a,baaa,ba,bbb求正规式R03124a,baaa,ba,bbbxyεεε024a|baaa|ba|bbbxyεεε024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε0a|baa(a|b)*bb(a|b)*xyε0a|bxyεaa(a|b)*|bb(a|b)*xy(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*习题作业

S={a,b,c}，试给出S一个不包含连续两个b的所有符号串集合的正则定义。

S={a,b,c}，叙述正则式((b|c)*a(b|c)*a)*(b|c)*

描述的符号串。S＝{0,1}，叙述正则式(00|11)

((01|10)(00|11)

(01|10)

)

(00|11)

描述的符号串。给出能被5整除的二进制数表示形式的正则定义。*3.4词法分析器的构造词法分析器（Scanner）输入流词法描述（正则表达式）NFADFATokenListerror词法分析器的构造方法用DFA人工构造：1.确定词法分析器的接口，即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍。2.确定单词分类和Token结构。3.根据2步，构造每一类单词的描述：正则表达式NFADFA。4.根据3步设计算法实现DFA。利用工具自动生成：ScanGen、Lex3.4.1用DFA人工构造词法分析器单词的TOKEN输出表如下：

identifier($id,Name)

number($int,Numb)

+($plus,‘‘);($semi,‘‘):=($assi,‘‘):($colon,‘‘)<=($le,‘‘)<($lt,‘‘)单词的一个DFA15L023L|DD4869710D+;:<==otherother状态(0)的代码：Ls0:string:=‘‘;ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a’..’z’:gotoLs1;‘0’..’9’:gotoLs2;’+’:gotoLs3;’;’:gotoLs4;’:’:gotoLs5;’<’:gotoLs8;end;状态(1)的代码：Ls1:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a’..’z’|‘0’..’9’:gotoLs1;other:beginBACK;return($id,string)endendend;状态(2)的代码：Ls2:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘0’..’9’:gotoLs2;other:beginBACK;return($int,string)endendend;状态(3)(4)(5)(6)的代码：Ls3:return($plus,’’);Ls4:return($semi,’’);Ls5:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs6;other:gotoLs7;endend;Ls6:return($assi,’’);状态(7)(8)(9)(10)的代码：Ls7:beginBACK;return($plus,’’)endLs8:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs9;other:gotoLs10;endend;Ls9:return($le,’’);Ls10:beginBACK;return($lt,’’)end3.4.2词法分析器的生成器Lex功能：依据语言的正则表达式，自动生成该语言的词法分析程序。执行过程：正则表达式文件Lex.lLex词法分析器lexyy.cC编译器a.out输入流Token序列Lex的常规表达式（1）字符

含义

A-Z,0-9,a-z构成了部分模式的字符和数字。.匹配任意字符，除了

\n。-用来指定范围。例如：A-Z指从

A到

Z之间的所有字符。[]一个字符集合。匹配括号内的

任意

字符。如果第一个字符是

^那么它表示否定模式。例如：[abC]匹配

a,b和

C中的任何一个。

*匹配

0个或者多个上述的模式。

+匹配

1个或者多个上述模式。

?匹配

0个或1个上述模式。

$作为模式的最后一个字符匹配一行的结尾。Lex的常规表达式（2）字符

含义

{}指出一个模式可能出现的次数。

例如：A{1,3}表示

A可能出现1次或3次。\用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。^否定。|表达式间的逻辑或。"<一些符号>"

字符的字面含义。元字符具有。/向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前面的部分。如：如果输入

A01，那么在模版

A0/1中的

A0是匹配的。()将一系列常规表达式分组。常规表达式举例常规表达式

含义

joke[rs]匹配

jokes或

joker。A{1,2}shis+匹配

AAshis,Ashis,Ashiss,Ashisss。(A[b-e])+匹配在

A出现位置后跟随的从

b到

e的所有字符中的

1个或多个。标记声明举例标记

相关表达式

含义

数字(number)([0-9])+1个或多个数字字符(chars)[A-Za-z]任意字符空格(blank)""一个空格字(word)(chars)+1个或多个

chars

变量(variable)(字符)+(数字)*(字符)*(数字)*Lex输入文件的格式输入文件格式：{declarations}

%%{rules}

%%{auxiliaryprocedures}%{声明变量,常量%}正则定义p{action}Lex编程

Lex编程可以分为三步：以Lex可以理解的格式指定模式相关的动作。在这一文件上运行Lex，生成扫描器的C代码。编译和链接C代码，生成可执行的扫描器。Lex的输入格式

一个Lex程序分为三个段：第一段：是C和Lex的全局声明第二段：包括模式（C代码）第三段：是补充的C函数。这些段以%%来分界。（1）C和Lex的全局声明这一段中我们可以增加C变量声明。

%{intwordCount=0;/*保存统计出来的字数

*/

%}

chars[A-Za-z]numbers([0-9])+delim[""\n\t]whitespace{delim}+

words{chars}+

%%两个百分号标记指出了Lex程序中这一段的结束和三段中第二段的开始。

（2）Lex的模式匹配规则{words}{wordCount++;/*increasethewordcountbyone*/}{whitespace}{/*donothing*/}{numbers}{/*onemaywanttoaddsomeprocessinghere*/}%%

（3）C代码

Lex编程的第三段，也就是最后一段覆盖了C的函数声明（有时是主函数）。Lex有一套可供使用的函数和变量。其中之一就是yywrap。一般来说，yywrap()的定义如下例。

voidmain(){yylex();/*starttheanalysis*/printf("Noofwords:%d\n",wordCount);}intyywrap(){return1;}例：识别PL/0单词的LEX程序%{#include<stdio.h>#include“code.h”#include“symbol.h”#include“y.tab.h”externintlevel;int