第三章词法分析

词法分析的作用：逐个读入源程序字符并按照构词规则分成一系列单词。单词中包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段。前面我们讲过，词法分析采用正规文法来定义和识别词法分析程序的功能根据词法规则把源程序字符流转换为语义关联的单词符号的序列，同时进行词法检查对数字常数完成数字字符串到（二进制）数值的转换删去空格字符和注解第三章词法分析及词法分析程序源程序词法分析程序语法分析程序Tokengettoken….1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点:结构清晰、各遍功能单一缺点：效率低词法分析实现方案：基本上有两种Whilei<>jdoifi>jtheni:=i-jelsej:=j-I

‘while’，‘i’，‘<>’，‘j’，‘do’，‘if’，‘i’，‘>’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'词法分析器

Pascal程序段词类和属性

computern.Calculatingmachine.一般程序语言单词的分类：

1．关键字(保留字或基本字)：begin,end2．标识符：用来表示各种名字3．常量：256，3.14，true,‘abs’4．运算符：如，＋、－、*、/等等5．分界符：如逗号，分号，冒号等单词的词类和属性词法分析器的二元式输出形式—：（词类编码，单词自身的属性值）词类编码提供给语法分析程序使用单词自身的属性值提供给语义分析程序使用具体的分类设计以方便语法分析程序使用为原则单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的单词的词类和属性Pascal源程序经词法分析器的输出〈while，——〉〈id，指向i的符号表入口的指针〉〈relational－op,NE〉〈id，指向j的符号表入口的指针〉〈do，——〉〈if，——〉〈id，指向i的符号表入口的指针〉

〈id，指向j的符号表入口的指针〉Whilei<>jdo程序段的单词输出例子：3.2正规文法和状态转换图正规文法定义了3型语言，常见的单词可由正规文法定义。状态转换图可用于识别3型语言；它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示3.2.1由正规文法构造状态转换图程序设计语言的单词都能用正规文法描述；例如，标识符可定义为

<标识符><标识符>字母<标识符><标识符>数字

<标识符>字母若把字母、数字视为终结符，则上述产生式为（左线性）正规文法若我们用d表示0-9间的数字，则C语言的<无符号数>的文法也是（右线性）正规文法（见P49）一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析。状态转换图由有限个结点所组成的有向图。每个结点代表在识别分析过程中扫描器所处的状态，其中含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点）由右线性文法构造状态转换图设G=(VN,VT,P,S)是一右线性文法,并设|VN|=K,则所要构造的状态转换图共有K+1个状态(结点).用VN中的每个符号分别标记其中的K个结点,且令G的开始符S为初态结点;余下的一个结点作为终态结点,用F(VN)标记.我们用如下规则来连接这K+1个结点:(1)对于G中产生式AaB,从结点A引一有向边到结点B,并用a标记这一有向边;(2)对于G中产生式Aa,从结点A引一有向边到终态结点F,并用a标记这一有向边;(3)对于G中产生式A(若有的话),则将结点A设为终态.例如,P49中定义的无符号数的文法对应的状态转换图为(化简后):0453126d.dddd.E+|-Edd利用状态转换图识别符号串的方法对于已给的字符串w=a1a2…an,aiVT,利用~对w识别的步骤如下:(1)从初始状态S出发,自左至右逐个扫描w的各个字符(当前为a1),此时在结点S所射出的诸矢线中,寻找标记为a1的矢线(若不存在,则表明w有语法错误),读入a1并沿矢线所指方向前进,过渡到下一状态(设为A1).(2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所射出的诸矢线中,寻找标记为ai+1的矢线(若不存在,则表明w有语法错误),读入ai+1,并进入状态Ai+1;(3)重复(2),直到w中所有字符被读完且恰好进入终态F时,宣告整个识别结束,w可被接受.显然,若我们从初态出发,分别沿一切可能的路径到达终态结点,并将中径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该~识别的语言=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;标识符,‘Line’分隔符,‘=’常量,‘80’分隔符,‘；数字数字字母字母11==0003;;1输入输出有限控制器通过动画演示给出词法分析程序的完成其功能的过程，同时给出识别的结果状态转换图与文法推导用状态转换图识别符号串w的过程，就是为w建立一个推导S*w的过程。在第一步（在初始状态S下，扫描到a1而过渡到下一状态A1），由状态转换图的构造规则可知，G中必有产生式Sa1A1;对于识别过程的后续步骤，由状态Ai识别ai+1后过渡到Ai+1恰好对应了使用产生式Aiai+1Ai+1,…,最后在状态An-1识别an后到达终态F，对应了使用产生式Aan 进行推导：

Sa1A1a1a2A2……a1a2…an-1An-1a1a2…an右线性文法与状态转换图设G是一右线性文法,M是相应的状态转换图,则从前面的讨论可以看出如下事实：(1)在利用M对符号串w进行识别时,M中每次状态的转换都模拟了一步直接推导,即识别方法(或称分析方法)是“”的;(2)因右线性文法只有形如AaB、Aa的产生式，所以推导的每一步所得句型只含一个非终结符，所以推导的规范的，每步所得的句型也必为规范句型；(3)对于M所识别的任一符号串x,必存在G中的一个推导S*x(即有xL(G);反之,对于L(G)中任一句子y,必存在一条从初态S到终态F的路径,此路径上各矢线的标记依次拼接起来所组成的符号串恰为y由左线性文法构造状态转换图设G=(VN,VT,P,S)是一左线性文法,构造相应的状态转换图的方法是:首先用G的VN符标记M的结点,其中,开始符S对应的结点为终态结点.另外,再引入一个新结点R(VN)作为初态.矢线的连接规则为:(1)对于G中形如Aa的产生式,引矢线:RA,且标记为a;(2)对于G中形如ABa的产生式,引矢线BA,且标记为a.由左线性文法构造状态转换图的例子已给文法G=({S,U},{0,1},{SS1|U1,UU0|0},S)RUSU00UU00SU11SS11用左线性文法构造出的状态转换图来识别文法的句子,其过程与前面右线性文法构造的状态转换图用法一样不过,就识别的方法而言,它却属于“”分析.我们以句子00011为例,给出其识别的的步骤.见右表.步骤当前状态 余留的符号串1 R 000112 U 00113 U 0114 U 115 S 16 S (识别结束)识别符号串与归约由构造状态转换图的方法可知,从初态R到下一状态A的转换,对应了形如Ba

的产生式,即将终结符a归约成非终结符B;类似地,从状态B转换到状态A,对应了形如ABa的产生式,即将Ba归约为A;如此下去,直到从某状态A转换到状态S(终态),对应了形如SAa的产生式,即将Aa归约为开始符S.此时归约成功,也恰好进入了终态,即状态转换图识别了(或接受)该符号串.前面识别00011的例子对应的归约过程见右图00011UUUSS3.3有限自动机状态转换图实际上是有限自动机的图形表示3.3.1确定的有限自动机DFA1.抽象地看,状态转换图由五个部分组成:(1)有限个状态之集,记作K;(2)有限个输入符号组成的字母表,记作;(3)从K到K的转换函数

f:KK.f(p,a)=q表示若当前状态为p,且输入符号为a,则进入下一个状态为q;(4)S0K,初始(开始)状态;(5)若干个终态之集:Z(K)由上述五个要素组成的五元式M=(K,,f,S0,Z)称为一个确定的有限自动机

(DFA:DeterministicFiniteAutomata)由此可见,一DFA实际上是状态转换图的形式描述(数学定义),状态转换图是DFA的几何(图形)表示.DFA的接受集2.为定义DFA所接受(或识别)的符号串集合,我们先将其转换函数f的定义域拓广到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定义可知,对于x*,f^(s,x)=t的含义是,当M从状态s出发,依次扫描完x的各个符号后将进入状态t.即只要f有定义,f^与f的效果是一致的.我们称DFAM接受(或识别)某符号串x*,用状态转换图来说,就是从初态S0出发,经一恰好标有x的路径后可达到某终态SZ

;用f^描述就是: SZ,f(S0,x)=S

M的接受集我们把一DFAM所接受的符号串的全体称为M的接受集,记为L(M),即L(M)={x|f(S0,x)Z,x*}确定的有限自动机我们之所以把前面定义的有限自动机称为确定的FA，是因为在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地确定FA的下一状态。在转换图上看，若||=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。例如，P52图3-4所对应的DFA为M=({R,U,S},{0,1},f,R,{S})其中，f的定义如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DFA。实际上，我们可以证明，正规文法G，DFAM，使 L(M)=L(G)，反之亦然。3.3.2非确定的有限自动机若在一左线性文法中含有多个右部相同的产生式，如 AUaBUaCUaXUa,或在一右线性文法中同时含有形如 UaAUaBUaCUaX的产生式，在相应的状态转换图中，就会出现这样的结点U，它具有多条标记为同一输入符号a的矢线，如右图所示图3-8NFA的状态转换图由上图可知，在U状态下，输入符号为a时，FA的下一状态不唯一，而是在状态集{A,B,C,…,X}中任选其一。具有这种性质的FA称为非确定的FA（NFA:Nondeterministic

FA）UABCXaaaa...非确定有限自动机的定义在形式上，NFAM同样可用五元式定义：M=(K,,f,S0,Z)，其中，K,,S0,Z的含义同DFA,转换函数f的定义为f:K(K),即将(Si,aj)映射到K的一个子集{Sk1,…,Skm}

类似地，我们可把f的定义域拓广到K*：(1)f^(S,)={S};(2)f^(S,aw)=f^(f(S,a),w)a,w*.再设f(S,a)=

{Sk1,…,Skm},且定义这样，我们已把f的定义域扩大到(K)*。根据类似的理由，我们将对f和f^不加区分NFA的接受集对于x*,若集合f(S0,x)中含有Z中的元素（终态），则说明，至少存在一条从初态S0到某一终态的路径，此路径上的符号之连接恰为x，此时，我们称x为M所接受所有为M所接受的符号串之集称为NFAM的接受集（或识别集），记作L(M).即L(M)={x|f(S0,x)Z,x}例3.1给定M=({S,A,B,C},{a,b},f,S,{C}),其状态转换图见右。由图可知M是一NFA。M识别符号串ababb的路径为S(a)A(b)B(a)A(b)B(b)C(接受)。(参见书中P60的表)SABCaa,babbaa注意，NFA识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（带回溯），这影响了FA的效率。能否提高其工作效率就是我们下一小节讨论的课题。事实上，对任一NFAM，总可构造一个DFAM’，使L(M’)=L(M)成立。这就是NFA与DFA的等价性。3.3.3NFA与DFA的等价性定理3.1对于字母表上的任一NFAM，必存在与M等价的DFAM’

令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。状态集ε-closure（I）称为I的ε-闭包我们可以通过一例子来说明状态子集的ε-闭包的构造方法非确定有限自动机的确定化集合I的ε-闭包的定义例：如图所示的状态图：令I={1}，求ε-closure（I）=？156432aεaaε根据定义：ε-closure（I）={1，3}我们同样可以通过一例子来说明上述定义,仍采用前面给定的状态图为例----J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合.--Ia是状态子集,其元素为J中的状态,加上从J中每一个状态出发通过ε弧到达的状态定义2:令I是NFAM’的状态集的一个子集,a∈Σ,定义:Ia=ε-closure(J)其中J=∪f(s,a)S∈I例：令I={1}Ia=ε-closure(J)=ε-closure(f(1，a))=ε-closure({2，4})={2，4，6}156432aεaaεNFA确定化—子集法设M=(K,,f,S0,Z)是上的NFA，现构造上DFA M’=（K’,,f’,S0’,Z’).方法如下：首先从S0出发，求出ε-closure(S0)，记为DFA的初态q0，依次推导直到没有新状态产生。步骤如下：1、令k’={ε-closure(s0)}(即为DFA的初态)2、对于k’中的任一尚未标记的状态qi={si1,si2……sik},sik∈K,作i)标记qi；ii)对于每个a∈∑，置qj=ε-closure(f(qi,a)),若qj不在k’中，则作为一个未标记的状态添加到k’中，继续循环。例：有NFAM’

先从状态1开始，即I={1}a1234startabaccεI=ε-closure({1})={1,4}Ia=ε-closure(f(1,a)∪f(4,a))=-closure({2,3}∪φ)=ε-closure({2,3})={2,3}Ib=ε-closure(f(1,b)∪f(4,b))=-closure(φ)=φIc=ε-closure(f(1,c)∪f(4,c))=φ从上一步中获得新状态{2,3},再计算I={2,3}的Ia,Ib,得到I={2,3},Ia={2},Ib={4},Ic={3,4}…1234startabaccεIIaIbIc

{1,4}{2,3}φφ{2,3}{2}{4}{3,4}{2}{2}{4}φ{4}φφφ{3,4}φφ{3,4}将求得的状态转换矩阵重新编号DFAM状态转换矩阵：符号状态abc02341221________3344DFAM的状态图：01423start{1,4}{2,3}{4}{2}acabbc注意：包含原初始状态1的状态子集为DFAM的初态包含原终止状态4的状态子集为DFAM的终态。{3,4}自动机的简化一个DFAM的化简是指寻找一个状态数比较少的DFAM’,使L(M)=L(M’)。DFA的最小化就是寻求最小状态DFA1、最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）2、状态S和T等价的条件

一致性条件——状态S和T必须同时为可接受状态或不可接受状态。蔓延性条件——对于所有输入符号，状态S和状态T必须转换到等价的状态里。

3、DFA的最小化的方法（分割法）方法：将DFA的状态分割成一些互不相交的子集。“分割法”DFA的最小化算法的核心把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.算法：A、将所有状态分成两个子集－－－终态集和非终态集B、运用状态等价原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子组。两个状态s和t分在同一子组的充要条件是：对所有的输入符号a，状态s和t都转换为同一组中的状态。若发现不等价，继续划分，这样FA的状态被分成互不相交的若干子集。C、从每个子组中选出一个状态做代表，即可构成简化的FA例:最小化5724361srartaaaaaaabbbbbbb解:(一)区分终态与非终态12345663731546737414212ab123456637315467374142ab123区号区号当输入a时，6，7状态在区号为2的子集内，即可以将区号为1中的1，2化为一个子集123456637315467374142ab12431243123456637315467374142ab5区号区号将区号代替状态号得:12345ab5214355231155243aaaaabbbbb到目前为止,我们已了解了对于任意三型语言L(G),存在DFAM使L(M)=L(G),反之,任意的M,存在G,使L(G)=L(M).这称为描述语言的等价性.本节将引入正规表达式的概念,它们可用于描述三型语言的特征,特别是对自动生成词法分析程序而言，它是非常有用的工具。所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式，用于描述给定三型语言的所有句子。3.4正规表达式与正规集3.4.1正规表达式及正规集的定义定义设是一字母表,则上的正规表达式(正则表达式,正规式)及其表示的正规集可递归定义如下:(1)是一正规式,相应的正规集为;(2)是一正规式,相应的正规集为{};(3)a,a是一正规式,相应的正规集为{a};(4)设r,s是正规式,且它们所表示的正规集为Lr,Ls,则 1.(r)•(s)是正规式,相应的正规集为Lr•Ls; 2.(r)|(s)是正规式,相应的正规集为LrLs; 3.(r)*是正规式,

相应的正规集为Lr*有限地使用上面的规则(4),所得的表达式均是正规式.定义中的括号主要用于规定运算顺序.我们规定优先级从高到低依次为*,•,|,则可以省略一些括号,例如((r)•((s)*)|(r)可简写为r•s*|r.另外,•常常可省略不写:rs*|r正规式与正规集的例子给定正规式,它唯一确定一正规集;反之不真.即一个正规集可由多个不同的正规式表示.若二正规式描述同一正规集,则称二式等价(相等)正规式间的基本等价关系见下页.正规式公理A1.r|s=s|r A2.r|r=r A3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st) A6.r(s|t)=rs|rtA7.(s|t)r=sr|st A8.r=r=A9.r=r=r A10.r*=(|r)*=|rr*例子例：令={l,d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字。正规式即是“字母(字母|数字)

”,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,这就是C和多数程序语言的标识符词法规则.例：令={d，，e，+，-},则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。

程序设计语言的单词都能用正规式来定义.利用以下转换规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.3.4.2由正规文法构造相应的正规式规则规则1规则2规则4文法产生式正则式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y规则3A→Ax|yA=yx*例:有文法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)|ε)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)*转