第三章词法分析

1、词法分析的作用：词法分析的作用：1.逐个读入源程序字符并按照构词规则分成一系列单词。单词中包括保留字、标识符、运算符、标点符号和常量等。2.词法分析是编译过程中的一个阶段。前面我们讲过，词法分析采用正规文法来定义和识别词法分析程序的功能词法分析程序的功能1. 根据词法规则把源程序字符流转换为语义关联的单词符号的序列，同时进行词法检查2. 对数字常数完成数字字符串到（二进制）数值的转换3. 删去空格字符和注解源程序词法分析程序语法分析程序Tokenget token.1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析词法分析S.P.(符号串)语法分析语法分析第一遍

2、第一遍第二遍第二遍单词串单词串优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低词法分析实现方案：词法分析实现方案：基本上有两种While ij do if ij then i:=i-j else j:=j-I while，i，j， do， if，i，j,then, i, := , i, - , j,else, j, :=, j, -, i词法分析器 Pascal程序段程序段词类和属性 computer n. Calculating machine.一般程序语言单词的分类： 1关键字(保留字或基本字)：begin,end 2标识符：用来表示各种名字 3常量：256

3、，3 .14，true,abs 4 运算符：如，、*、/ 等等 5分界符：如逗号，分号，冒号等单词的词类和属性单词的词类和属性词法分析器的二元式输出形式： （词类编码，单词自身的属性值）1. 词类编码提供给语法分析程序使用2. 单词自身的属性值提供给语义分析程序使用3. 具体的分类设计以方便语法分析程序使用为原则4. 单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的单词的词类和属性单词的词类和属性 Pascal源程序经词法分析器的输出 while， id，指向i的符号表入口的指针 relationalop , NE id，指向j的符号表入口的指针 do， if， id，指向i

4、的符号表入口的指针 id，指向j的符号表入口的指针While ij do程序段的单词输出例子：程序段的单词输出例子：u 程序设计语言的单词都能用正规文法描述；u 例如，标识符可定义为u 若把字母、数字视为终结符，则上述产生式为（左线性）正规文法u 若我们用d表示0-9间的数字，则C语言的的文法也是（右线性）正规文法（见P49）u 一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法进行分析。 由有限个结点所组成的有向图。u 每个结点代表在识别分析过程中扫描器所处的状态，其中 含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。u 状态之间可用有向边连接，其上标记一字

5、符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中定义的无符号数的文法对应的状态转

6、换图状态转换图为(化简后):0453126d.dddd.E+|-Edd对于已给的字符串对于已给的字符串w=a1a2an,ai VT,利用利用对对w 识别的步骤识别的步骤如下如下:(1)从初始状态从初始状态S出发出发,自左至右逐个扫描自左至右逐个扫描w的各个字符的各个字符(当前为当前为a1),此时在结点此时在结点S所射出的诸矢线中所射出的诸矢线中,寻找标记为寻找标记为a1的矢线的矢线(若不存在若不存在,则表明则表明w有语法错误有语法错误),读入读入a1并沿矢线所指方向并沿矢线所指方向前进前进,过渡到下一状态过渡到下一状态(设为设为A1).(2)设当前处在设当前处在Ai状态状态,所扫描的字符为所扫

7、描的字符为ai+1,在结点在结点Ai所射出的诸所射出的诸矢线中矢线中,寻找标记为寻找标记为ai+1的矢线的矢线(若不存在若不存在,则表明则表明w有语法错有语法错误误),读入读入ai+1,并进入状态并进入状态Ai+1;(3)重复重复(2),直到直到w中所有字符被读完且恰好进入终态中所有字符被读完且恰好进入终态F时时,宣告宣告整个识别结束整个识别结束,w可被接受可被接受.显然显然,若我们从若我们从初态初态出发出发,分别沿分别沿一切可能一切可能的的路径路径到达到达终态结点终态结点,并并将中径中将中径中矢线上所标记的字符矢线上所标记的字符依次连接起来依次连接起来,便得到便得到状态转换状态转换图图所能识

8、别的所能识别的全部符号串全部符号串,这些符号串组成的集合构成了该这些符号串组成的集合构成了该识别的语言识别的语言= 80;0134256eniL字母字母字母字母数字数字数字= =；0124563L ine= 80; 标识符 , Line 分隔符 , = 常量, 80 分隔符, ； 数字数字字母字母1 1= =0 0 03; ;1输入输出有限控制器通过动画演示给出词法分析程序的完成其功能的过程，同时给出识别的结果状态转换图与文法推导u 用状态转换图识别符号串 的过程，就是为 建立一个推导的过程。u 在第一步（在初始状态 下，扫描到而过渡到下一状态A A1 1），由状态转换图的构造规则可知，中必有

9、产生式;对于识别过程的后续步骤，由状态A Ai i识别后过渡到恰好对应了使用产生式最后在状态识别后到达终态 ，对应了使用产生式进行推导： u u 设设是一是一,是相应的是相应的,则从前面的讨论可则从前面的讨论可以看出如下事实：以看出如下事实：(1)在利用在利用对符号串对符号串进行识别时进行识别时,中每次状态的转换都模拟了中每次状态的转换都模拟了一步直接推导一步直接推导,即识别方法即识别方法(或称分析方法或称分析方法) 是是“ ”的的;(2)因因右线性文法右线性文法只有形如只有形如的产生式，所以推导的的产生式，所以推导的每一步所得句型只含一个非终结符，所以推导的每一步所得句型只含一个非终结符，所

10、以推导的规范规范的，每步的，每步所得的句型也必为所得的句型也必为规范句型规范句型；(3)对于对于所识别的任一符号串所识别的任一符号串 ,必存在必存在G中的一个推导中的一个推导 (即有即有反之反之,对于对于中任一句子中任一句子 ,必存在一条从初必存在一条从初态态 到终态到终态 的路径的路径,此路径上各矢线的标记依次拼接起来所组此路径上各矢线的标记依次拼接起来所组成的符号串恰为成的符号串恰为u 设是一左线性文法,构造相应的状态转换图的方法是:u 首先用的符标记M的结点,其中,开始符 对应的结点为终态结点.另外,再引入一个新结点作为初态.矢线的连接规则为:(1)对于中形如 的产生式,引矢线:且标记为

11、 ;(2)对于G中形如 的产生式,引矢,且标记为 .已给文法已给文法G=(S,U,0,1,SS1 |U1, UU0 | 0,S)u 由构造状态转换图的方法可知,从初态从初态到下一状态到下一状态A A的转换的转换, ,对应了形如对应了形如 的产生式的产生式,即将终结符 归约成非终结符;u 类似地,从状态B转换到状态 ,对应了形对应了形如如的产生式的产生式,即将归约为 ;u 如此下去,直到从某状态 转换到状态(终态),对应了形如对应了形如的产生式的产生式,即将归约为开始符 .此时归约成功,也恰好进入了终态,即状态转换图识别了(或接受)该符号串.u 前面识别的例子对应的归约过程见右图状态转换图实际上

12、是有限自动机的图形表示3.3.1 确定的有限自动机DFA1.1.抽象地看抽象地看, ,状态转换图状态转换图由五个部分组成由五个部分组成: :(1)(1)有限个状态之集有限个状态之集, ,记作记作KK; ;(2)(2)有限个输入符号组成的字母表有限个输入符号组成的字母表, ,记作记作 ; ;(3)(3)从从KK到到KK的的转换函数转换函数 f: Kf: KK. f(p,a)=qK. f(p,a)=q表示若当前状态表示若当前状态为为p p, ,且输入符号为且输入符号为a a, ,则进入下一个状态为则进入下一个状态为q q; ;(4)(4)S S0 0 KK, ,初始初始( (开始开始) )状态状态

13、; ;(5)(5)若干个终态之集若干个终态之集: : Z( Z( K )K )由上述五个要素组成的五元式由上述五个要素组成的五元式 M=(K, M=(K, , f,S, f,S0 0,Z ),Z )称为一个称为一个确定确定的有限自动机的有限自动机 ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )由此可见由此可见, ,一一DFADFA实际上是状态转换图的形式描述实际上是状态转换图的形式描述( (数学定义数学定义), ),状状态转换图是态转换图是DFADFA的几何的几何( (图形图形) )表示

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

15、记为L(M),即 L(M)= x | f(S0,x) Z,x* u 我们之所以把前面定义的有限自动机有限自动机称为确定的FA，是因为在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地唯一地确定FA的下一状态。在转换图上看，若|=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。u 例如，P52图3-4所对应的DFA为 M=(R,U,S,0,1,f,R,S) 其中，f的定义如下：f(R,0)=Uf(U,0)=Uf(U,1)=Sf(S,1)=Su 由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DFA。u 实际上，我们可以证明， 正规文法G， DFA

16、M，使L(M)=L(G)，反之亦然。3.3.2非确定的有限自动机u 若在一左线性文法中含有若在一左线性文法中含有多个右部相同的产生式，多个右部相同的产生式，如如 AUa BUa CUa XUa,u 或在一右线性文法中同时或在一右线性文法中同时含有形如含有形如 UaA UaB UaC UaX 的产生式，的产生式，u 在相应的状态转换图中，在相应的状态转换图中，就会出现这样的结点就会出现这样的结点U，它具有多条标记为同一输它具有多条标记为同一输入符号入符号a的矢线，如右图的矢线，如右图所示所示由上图可知，在由上图可知，在U状态下，输状态下，输入符号为入符号为a时，时，FA的下一状态的下一状态不唯一

17、，而是在状态集不唯一，而是在状态集A,B,C,X中任选其一。具有中任选其一。具有这种性质的这种性质的FA称为非确定的称为非确定的FA（NFA: Nondeterministic FA）u 在形式上，NFA M同样可用五元式定义：M=(K,f,S0,Z)，其中，K, ,S0,Z的含义同DFA,转换函数f的定义为 f: K(K),即将(Si,aj)映射到K的一个子集Sk1,Skm u 类似地，我们可把f的定义域拓广到K* ：(1) f(S,)=S;(2)f(S,aw)=f(f(S,a),w) a,w*.再设 f(S,a)= Sk1,Skm ,且定义mikmikkkkwSfwaSffawSfwSfw

18、SSSfiim11),(),(),(:),(),(21则有这样，我们已把f的定义域扩大到(K) *。根据类似的理由，我们将对f和f不加区分u 对于对于x x* *, ,若集合若集合f(Sf(S0 0,x),x)中含有中含有Z Z中的元素（终态），则说明，至少中的元素（终态），则说明，至少存在一条从初态存在一条从初态S S0 0到某一终态的路到某一终态的路径，此路径上的符号之连接恰为径，此路径上的符号之连接恰为x x，此时，我们称此时，我们称x x为为M M所接受所接受u 所有为所有为M M所接受的符号串之集称为所接受的符号串之集称为NFA MNFA M的接受集（或识别集），记的接受集（或识别集

19、），记作作 L(M).L(M).即即 L(M)L(M)=x | f(Sx | f(S0 0, , x )x ) Z Z , x, x u 例例3.13.1 给定给定M= (S,A,B,C, M= (S,A,B,C, a,b, f , S ,C),a,b, f , S ,C),其状态转换其状态转换图见右。由图可知图见右。由图可知M M是一是一NFANFA。u M M识别符号串识别符号串ababbababb的路径为的路径为 S(S(a a) )A(A(b b) )B(B(a a) )A(A(b b) )B(B(b b) )C C( (接受接受) )。( (参见书中参见书中P60P60的表的表) )

20、注意注意，NFANFA识别输入符号串识别输入符号串时有一个试探过程，为了能时有一个试探过程，为了能走到终态，往往要走许多弯走到终态，往往要走许多弯路（路（带回溯带回溯），这影响了），这影响了FAFA的效率。的效率。3.3.3 对于字母表对于字母表 上的任一上的任一NFA M，必存在与，必存在与M等价的等价的DFA M 令令I是一个状态集的子集，定义是一个状态集的子集，定义-closure（I）为：）为：1）若）若sI，则，则s-closure（I）；）；2）若）若sI，则从，则从s出发经过任意条出发经过任意条弧能够到达的弧能够到达的任何状态都属于任何状态都属于-closure（I）。）。 状态

21、集状态集-closure（I）称为）称为I的的-闭包闭包我们可以通过一例子来说明状态子集的-闭包的构造方法非确定有限自动机的确定化集合I的-闭包的定义例：如图所示的状态图：令I=1，求-closure（I）=？156432aaa根据定义：-closure（I）=1，3我们同样可以通过一例子来说明上述定义,仍采用前面给定的状态图为例- J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合.-Ia是状态子集,其元素为J中的状态,加上从J中每一个状态出发通过弧到达的状态定义2: 令I是NFA M的状态集的一个子集, a,定义: Ia=-closure(J) 其中其中J = f(s,a)

22、SI例：令I=1 Ia=-closure(J) =-closure(f(1，a) =-closure(2，4)=2，4，6156432aaaNFA确定化子集法u 设设 M=(K,M=(K, ,f,S0,Z) ,f,S0,Z) 是是 上的上的NFANFA，现构造，现构造 上上DFA DFA M M=（K, , ,f,S0,Z).方法如下：方法如下：首先从S0出发，求出-closure(S0)，记为DFA的初态q0，依次推导直到没有新状态产生。步骤如下：u 1、令k=-closure(s0)(即为DFA的初态)u 2、对于k中的任一尚未标记的状态qi=si1,si2sik,sik K,作u i)标

23、记qi；u ii)对于每个a ，置u qj= -closure(f(qi,a),若qj不在k中，则作为一个未标记的状态添加到k中，继续循环。例：有NFA M 先从状态1开始，即I=1 a1234startabaccI=-closure(1)=1,4Ia=-closure(f(1,a)f(4,a)=-closure(2,3) = -closure (2,3)=2,3Ib= -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

24、1234startabacc I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 将求得的状态转换矩阵重新编号DFA M状态转换矩阵： 符号状态abc0 2 341221_3344DFA M的状态图：01423start1,42,342acabbc注意：包含原初始状态注意：包含原初始状态1的状态子集为的状态子集为DFA M的初态的初态 包含原终止状态包含原终止状态4的状态子集为的状态子集为DFA M的终态。的终态。3,4自动机的简化一个DFA M的化简是指寻找一个状态数比较少的DFA M,使L(M)=L(M)。DFA的最小化就是寻求最小状态DFA1、最

25、小状态、最小状态DFA的含义的含义:u 没有多余状态(死状态)u 没有两个状态是互相等价（不可区别）2、状态、状态S和和T等价的条件等价的条件 一致性条件 状态S和T必须同时为可接受状态或不可接受状态。 蔓延性条件 对于所有输入符号，状态S和状态T必须转换到等价的状态里。 3、 DFA的最小化的方法（分割法）的最小化的方法（分割法）方法：将DFA的状态分割成一些互不相交的子集。“分割法”u DFA的最小化算法的核心u 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.u 算法：u A、将所有状态分成两个子集终态集和非终态集u

26、B、运用状态等价原则分别对两个子集的状态进行分析和划分，把互相等价的状态构成一个子组。u 两个状态s和t分在同一子组的充要条件是：对所有的输入符号a，状态s和t都转换为同一组中的状态。若发现不等价，继续划分，这样FA的状态被分成互不相交的若干子集。u C、从每个子组中选出一个状态做代表，即可构成简化的FA例:最小化5724361srartaaaaaaabbbbbbb解:(一)区分终态与非终态12345663731546737414212ab123456637315467374142ab123区号区号当输入a时，6，7状态在区号为2的子集内，即可以将区号为1中的1，2化为一个子集12345663

27、7315467374142ab12431243123456637315467374142ab5区号区号将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb到目前为止,我们已了解了对于任意三型语言L(G),存在DFA M使L(M)=L(G),反之,任意的M,存在G,使L(G)=L(M).这称为描述语言的等价性.本节将引入正规表达式正规表达式的概念,它们可用于描述三描述三型语言的特征型语言的特征,特别是对自动生成词法分析程序而言，它是非常有用的工具。所谓正规表达式正规表达式就是用特定的运算符运算符及运算对象运算对象按某种规则构造的表达式，用于描述给定三型语用于描

28、述给定三型语言的所有句子。言的所有句子。3.4.1正规表达式及正规集的定义u 定义 设是一字母表,则上的正规表达式正规表达式(正则表达式,正规式)及其表示的正规集正规集可递归定义如下:(1) 是一正规式, 相应的正规集为;(2) 是一正规式, 相应的正规集为;(3) a,a 是一正规式, 相应的正规集为a;(4) 设r,s是正规式, 且它们所表示的正规集为Lr,Ls,则1. (r) (s)是正规式, 相应的正规集为LrLs;2. (r)|(s)是正规式, 相应的正规集为Lr Ls;3. (r)*是正规式, 相应的正规集为Lr*有限地使用上面的规则(4),所得的表达式均是正规式.定义中的括号主要

29、用于规定运算顺序.我们规定优先级从高到低依次为 *, , |,则可以省略一些括号,例如(r) (s)*)|(r) 可简写为r s*|r.另外, 常常可省略不写: rs*|r正规式与正规集的例子符号串的长度大等于符号串长度为偶数的符号串结尾的任何以正规集正规式babababababbbaabaabaabbabbbabaaabaabababaababaaaaaaaaaaaaaaaiiii,2)|)(|)(|(,)|(,)|(,|,|,*00*给定正规式给定正规式, ,它唯一确定一它唯一确定一正规集正规集; ;反之反之不真不真. .即一个即一个正规集可由多正规集可由多个个 不同的正不同的正规式表示规

30、式表示. .若二正规式描若二正规式描述同一正规集述同一正规集, ,则称二式则称二式( (相等相等) )正规式间的基正规式间的基本等价关系见本等价关系见下页下页. .正规式公理正规式公理u A1. r|s=s|rA2. r|r=ru A3. r|=rA4. (r|s)|t=r|(s|t)u A5. (rs)t=r(st)A6. r(s|t)=rs|rtu A7. (s|t)r=sr|st A8. r=r=u A9. r=r=rA10. r*=(|r)*=|rr* 例子例子例：令=l,d，则上的正规式 r=l(ld)定义的正规集为:l,ll,ld,ldd,其中l代表字母,d代表数字。 正规式即是“

31、字母(字母|数字) ” ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,这就是C和多数程序语言的标识符词法规则.例：令=d，e，+，-,则上的正规式d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .利用以下转换规则利用以下转换规则, ,直至只剩下一个开始符号定义直至只剩下一个开始符号定义的产生式的产生式, ,并且产生式的右部不含非终结符并且产生式的右部不含非终结符. .3.4.2 由正规文法构造相应的正规式由正规文法构造相应的正规式规则规则规则规则1规则规则2规则规则4文法产生式文法产生式正则式正则式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y规则规则3AAx|yA=yx*例:有文法Gs SaA|a, AaA|dA|a|d于是: S=aA|a A=(aA|dA)|(a|d)A=(a|d)A|(a|d)由规则二: A=(a|d)*(a|d) 代入:S=a(a|d)*(a|d)|a 于是: