编译原理—清华大学—第2版—第4章词法分析

1、第四章第四章 词法分析词法分析 教学要求：教学要求：本章介绍编译程序的第一个阶本章介绍编译程序的第一个阶段词法分析的设计原理，要求掌握正规文段词法分析的设计原理，要求掌握正规文法、法、DFADFA、NFANFA、正规式和正规集的基本概、正规式和正规集的基本概念和词法分析器的设计原理。念和词法分析器的设计原理。 教学重点：教学重点：词法分析器的任务与设计，自词法分析器的任务与设计，自动机的建立、表示、确定化及化简。动机的建立、表示、确定化及化简。（1 1）分析和识别单词及属性，分析和识别单词及属性， 包括识别包括识别语言的语言的关键字关键字、标识符、常数、运算符等、标识符、常数、运算符等；（2

2、2）跳过各种分隔符，如空格，回车，制表符等；跳过各种分隔符，如空格，回车，制表符等；（3 3）删除注释）删除注释；（4 4）进行词法检查，报告所发现的错误；）进行词法检查，报告所发现的错误；（5 5）建立符号表。）建立符号表。4.14.1词法分析的任务词法分析的任务实现方案：基本上有两种实现方案：基本上有两种1.词法分析单独作为一遍词法分析单独作为一遍2.词法分析程序作为单独的子程序词法分析程序作为单独的子程序S.P.(字符串字符串)词法分析词法分析S.P.(符号串符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺

3、点：效率低S.P.(字符串字符串)词法分词法分析程序析程序语法分语法分析程序析程序取单词取单词单词单词单词符号单词符号 单词符号一般可分为下列五种：单词符号一般可分为下列五种：（）：）：if,for,whileif,for,while等等：各种名称，如常量名、变量名、过程：各种名称，如常量名、变量名、过程名等名等（量）：（量）：25, 3.1415, 25, 3.1415, TRUE, TRUE, “ABCABC”等等：如：如 + - + - * * / = / =等等：逗号，分号，括号等：逗号，分号，括号等词法分析程序的输出形式词法分析程序的输出形式-二元式二元式( (单词类别单词类别, ,

4、单词的属性值单词的属性值) )单词类别可以用整数编码表示单词类别可以用整数编码表示: :一类一种或一字一种一类一种或一字一种单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码编码1 12 23 34 45 5表3.1 int x=10,y=20,sum;词法分析的结果单词类别单词类别单词的属性值单词的属性值1int2指向指向x的符号表入口指针的符号表入口指针4=3105,2指向指向y的符号表入口指针的符号表入口指针4=3205,2指向指向sum的符号表入口指针的符号表入口指针5;例例 int x=10,y=20,sum;词法分析的结果词法分析的结果 4.2 4.2 单

5、词的描述工具单词的描述工具一、正规文法：一、正规文法： 文法文法G=G=（V VN N，V VT T，P P，S S），），P P中每一产中每一产生式的形式都为：生式的形式都为：或或，其中其中AVAVN N ，BVBVN N ，aVaVT T几类单词正规文法的描述几类单词正规文法的描述：标识符标识符l | ll | l字母数字字母数字字母数字字母数字l | d | ll | d | l字母数字字母数字| | d d字母数字字母数字：无符号整数无符号整数d | dd | d无符号整数无符号整数：运算符运算符 + + | - | | - | * * | / | = | = | / | = | |

6、= =：界符界符 , | ; | ( | ) | , | ; | ( | ) |二、正规式二、正规式（一）定义（一）定义（正规式正规式和它所表示的和它所表示的正规集正规集）：）：设字母表为设字母表为 ，辅助字母表，辅助字母表 = ， ， ， ， ，( (，)。1 1、 和和 都是都是 上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为 和和 ；2 2、任何、任何a a ，a a是是 上的一个正规式，它所表示的正规集上的一个正规式，它所表示的正规集为为 aa；3 3、假定假定e e1 1和和e e2 2都是都是 上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集

7、分别为别为L(eL(e1 1) )和和L(eL(e2 2) )，那么，那么，( (e e1 1), ), e e1 1 e e2 2, , e e1 1 e e2 2, , e e1 1 也都也都是正规式是正规式, ,它们所表示的正规集分别为它们所表示的正规集分别为L(eL(e1 1), ), L(eL(e1 1)L(e)L(e2 2), L(e), L(e1 1)L(e)L(e2 2) )和和( (L(eL(e1 1) 。4 4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是 上的上的正规式，仅由这些正规式所表示的字集才是正规式，仅由这些正规式所表示的

8、字集才是 上的正规上的正规集。集。例例:令令 =a，b， 上的正规式和相应的正规集上的正规式和相应的正规集的例子有：的例子有：正规式正规式 正规集正规集a aa ba,bab ab(a b)(a b) aa,ab,ba,bba ,a,aa, 任意个任意个a的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继上所有含有两个相继 的的a或两个相继的或两个相继的b组成组成 的串的串例例 =l l，dd，r=l(lr=l(l d)d) 定义的正规集定义的正规集: : l,ll,ld,ldd,l,ll,ld,ldd, （

9、标识符）标识符）其中：其中：l l代表字母代表字母, ,d d代表数字代表数字, ,正规式即是正规式即是 字母字母( (字母字母| |数字数字) ) 它表示的正规集是它表示的正规集是“字母打头的字母数字串字母打头的字母数字串”。例例4.3 4.3 =d d，. .，e e，+ +，-,-,则则 上的正规式上的正规式 ：d d (.dd(.dd )(e(+ )(e(+ - -)dd)dd ) )表示的是无符号数的集合。其中：表示的是无符号数的集合。其中：d d为为0-90-9的数字。的数字。（二）两个正规式（二）两个正规式等价等价 若两个正规式若两个正规式e e1 1和和e e2 2所表示的所表

10、示的, ,则说则说e e1 1和和e e2 2等价等价, ,写作写作e e1 1= =e e2 2。例如：例如： e e1 1= (a= (a b)b)， e e2 2 = b = b a a又如：又如： b(ab)b(ab) = (ba) = (ba) b b (a (a b)b) = (a= (a b b ) ) （三）正规式的运算律（三）正规式的运算律 设设r,s,tr,s,t为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：1 1、r r s=ss=s r r “或或”服从交换律服从交换律2 2、r r ( (s s t)=(t)=(r r s s) ) t t “或

11、或”的可结合律的可结合律3 3、( (rs)t=r(st)rs)t=r(st) “连接连接”的可结合律的可结合律4 4、r(sr(s t)=rst)=rs rtrt (s(s t)r=srt)r=sr trtr 分配律分配律 5 5、 r=r, rr=r, r =r=r 是是“连接连接”的恒等元的恒等元素素6 6、r r r=rr=rr r = = r r rrrr “或或”的抽取律的抽取律 三、正规文法到正规式三、正规文法到正规式 V VT T= = , , S S V VN N ， （1 1）对正规式）对正规式r r，生成生成正规产生式正规产生式 S Sr r （2 2）若）若x x和和y

12、 y都是正规式都是正规式 对形如对形如A Axyxy的的正规产生式：正规产生式： A AxBxB，B By y，B B V VN N 对形如对形如A Ax x y y的的正规产生式：正规产生式： A AxBxB，A Ay y，B BxBxB，B By y，B B V VN N 对形如对形如A Ax x y y的的正规产生式正规产生式: : A Ax x，A Ay y 不断应用上述规则做变换，直到每个产生式右端只含一个不断应用上述规则做变换，直到每个产生式右端只含一个V VT T对对 上的正规式上的正规式r ,r ,存在一个存在一个G=(VG=(VN N,V,VT T,P,S),P,S)使得使得

13、L(G)=L(r) L(G)=L(r) ，反之亦然。反之亦然。NVNV 例例 r = a(a d) VT=a,d Sa(a d) SaA A(a d) A(a d)B A B(a d)B BGs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B 使用如下规则，最后只剩下一个开始符号定义使用如下规则，最后只剩下一个开始符号定义的产生式，并且右部不含非终结符。的产生式，并且右部不含非终结符。规则规则1 1 ：A-xB,B-y = A=xyA-xB,B-y = A=xy规则规则2 2： A-xA|y = A=xA-xA|y = A=x* *y y规则规则3 3： A-x

14、, A-y = A=x|yA-x, A-y = A=x|y例如：文法例如：文法GSGS为：为： S-aA, S-a, A-aA, A-dA, A-a, A-dS-aA, S-a, A-aA, A-dA, A-a, A-dS=aA|aS=aA|aA=(aA|dA)|(a|d)A=(aA|dA)|(a|d)A=(a|d)A|(a|d)A=(a|d)A|(a|d)A=(a|d)A=(a|d)* *(a|d)=(a|d)(a|d)=(a|d)+ +A A代入代入S S得：得：S=a(a|d)S=a(a|d)+ +|a|aS=a(a|d)S=a(a|d)+ +|）S=a(a|d)S=a(a|d)* *所

15、以，对应正规式为：所以，对应正规式为：a(a|d)a(a|d)* *4.3 4.3 有穷自动机有穷自动机 有穷自动机有穷自动机( (也称有限自动机也称有限自动机,DFA),DFA)是识别是识别正规集的装置。正规集的装置。正规式正规式正规文法正规文法NFANFADFADFA识别单词识别单词输入串输入串转换转换构造构造确定化确定化本章学习思路本章学习思路一个确定的有穷自动机（一个确定的有穷自动机（DFADFA）M M是一个五元组：是一个五元组：M=M=（K K，f f，S S，Z Z）其中其中1.1. 是一个有穷集，它是一个有穷集，它称称一个一个；2.2.一个有穷字母表，它的每个元素称为一个输入符

16、号，一个有穷字母表，它的每个元素称为一个输入符号，所以也称所以也称为为；3.3.，是，是K KK K上的映射，上的映射，f(kf(ki i,a)=k,a)=kj j，(k(ki i，k kj jK)K)表示：当前状态为表示：当前状态为k ki i，输入符为输入符为a a时，将转换为下时，将转换为下一个状态一个状态k kj j，把把k kj j称作称作k ki i的一个后继状态；的一个后继状态；4.4. K K的一个的一个；5.5. K K一个一个，终态也称，终态也称可接受状态可接受状态或或结束状态结束状态。例：例：DFA M=DFA M=（S,U,V,Q, a,b, f, S, QS,U,V,

17、Q, a,b, f, S, Q）其中其中 f f 定义为：定义为：f f（S S，a a）=U=Uf f（V V，a a）=U=Uf f（S S，b b）=V=Vf f（V V，b b）=Q=Qf f（U U，a a）=Q=Qf f（Q Q，a a）=Q=Qf f（U U，b b）=V=Vf f（Q Q，b b）=Q=Q（1 1）DFA DFA 的状态图表示的状态图表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVaaaba，bQb（2 2）DFA DFA 的矩阵表示的矩阵表示f（S，a）=Uf（V，a）

18、=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符字符状态状态0100终态行在表的右端标以终态行在表的右端标以1 1，非终态标以，非终态标以0 0。 =a=a，aa，* *，则有：，则有：a a其中其中QKQK。 即：即： * *，S S为为DFA MDFA M的开始状态，的开始状态，P P Z Z，Z Z为终为终态集。若态集。若f(Sf(S，)=P)=P，则称则称为为DFA MDFA M所所。对于对于 * *中的符号串中的符号串，若存在一条从初态到某，若存在一条从初态到某一终态的道路，且这条路上所有弧上的符号连

19、一终态的道路，且这条路上所有弧上的符号连接成符号串接成符号串 ，则称，则称为为DFA MDFA M所识别所识别例：证明例：证明=baab=baab被如下的被如下的DFADFA所接受。所接受。bSUVQaaaba，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属于终态。得证属于终态。得证。 DFA MDFA M所能识别的符号串的全体记为所能识别的符号串的全体记为L(M)L(M) 结论：结论： 上一个字符串集上一个字符串集V V 是正规的，当且仅当存在是正规的，当且仅

20、当存在一个一个 上的确定有穷自动机上的确定有穷自动机M M，使得使得V=L(M)V=L(M)。DFA M=（K，f，S，Z）的算法的算法:R:=S；c:=getchar;while ceof and RK do R:=f(R,c); c:=getchar; ;if R is in Z then return (yes) else return (no)二、不确定的有穷自动机二、不确定的有穷自动机NFANFA 定义定义 N= N=KK，f f，S S，ZZ，其中其中的有穷非的有穷非空空， 有穷输入有穷输入，K K * * 到到K K的的子集子集的的， K K始状始状， K K止止状状。例例NFA

21、 N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111状态图表示状态图表示表格表示表格表示01SPS,Z0PZ0ZPP1简化为简化为01SPS,Z0P.Z0ZPP1NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P状态集合状态集合I I的有关运算：的有关运算： 1 1、状态集合、状态集合I I，定义，定义I I的的 - -闭包闭包 -closure(I)=I-closure(I)=I ss| |从某

22、个从某个s s I I出发经过任意条出发经过任意条 弧能到达弧能到达s s 2 2、状态集合、状态集合I I的的a a弧转换弧转换定义：定义： move(I,a)=s move(I,a)=s| |从某个从某个s s I I出发经过一条出发经过一条a a弧能到弧能到达达s s I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2； -closure(5,3,4)=5,3,4,6,2,8,7；move(1,2,a)=5,4,3; -closure(move(1,2,a)= -closure(5,3,4)= 5,4,3,6,2,8,7；12534687aaa -cl

23、osure(I)=I-closure(I)=I ss| |从从某个某个s s I I出发经过任意条出发经过任意条 弧能到达弧能到达s s move(I,a)=smove(I,a)=s| |从某个从某个s s I I出发经过一条出发经过一条a a弧弧能到达能到达s s NFANFAD DFAFA的过程的过程( (子集法子集法):): 假设假设NFA N=(K,NFA N=(K,f,K,f,K0 0,K,Kt t) )按如下办法构造一个按如下办法构造一个DFA M,DFA M,使得使得L(M)=L(N)L(M)=L(N). . 不失一般性，设不失一般性，设=a,ba,b，我们构造一张表，我们构造一

24、张表: : 状态状态= -closure(move(Ti,a)= -closure(move(Ti,b)T0= -closure( )TaTbK0首先，置第首先，置第1 1行第行第1 1列为列为 -closure(K-closure(K0 0) )求出这一求出这一列的列的T Ta a，T Tb b；然后，检查这两个然后，检查这两个T Ta a，T Tb b，看它们是否已在表中，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第一列中出现，把未曾出现的填入后面的空行的第的第1 1列上，求出每行第列上，求出每行第2 2，3 3列上的集合列上的集合.重复上述过程，直到所有第重复上述过程

25、，直到所有第2 2，3 3列子集全部出现列子集全部出现在某行第一列为止。在某行第一列为止。 状态状态= -closure(move(Ti,a)= -closure(move(Ti,b)T0= -closure( )TaTbK0例例 将下图的将下图的NFA NNFA N转换成转换成DFA MDFA M023456789101bbbaaNFA N023456789101bbbaa 状态状态T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8=T11,2,4,5,6,7=T2T1= 1,2,3,4,6,7,8T11,2,4,5,6,7,9 =T3T2= 1,2,4,5,6,

26、7T1T2T3= 1,2,4,5,6,7,9T1T4T4= 1,2,4,5,7,10T1T2NoImage= -closure(move(Ti,a)Ta= -closure(move(Ti,b)Tb 现在把这张表看成一个状态转换矩阵，把其中现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机M M，它，它的初态是的初态是 -closure(K-closure(K0 0) ) ，它的终态是含有原，它的终态是含有原终态终态K Kt t的子集。的子集。 不难看出，这个不难看出，这个DFA M

27、DFA M与与M M等价。等价。 -closure(move(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,7 1,2,3,4,6,7,8=T1 1,2,4,5,6,7 =T2T1= 1,2,3,4,6,7,8 T1 1,2,4,5,6,7,9 =T3T2= 1,2,4,5,6,7 T1 T2T3= 1,2,4,5,6,7,9 T1 T4T4= 1,2,4,5,7,10 T1 T2初态初态终态终态b02134abaaaabbbDFA M取取T Ti i的下标的下标i i为为状态名状态名四、四、DFADFA的最小化（化简）的最小化（化简） 最

28、小状态最小状态DFADFA 没有多余状态没有多余状态( (死状态死状态) ) 没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别） 多余状态：多余状态：从自动机的开始状态出发，任何输从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态入串也不能到达的那个状态；或者从这个状态没有通路到达终态。没有通路到达终态。消除多余状态消除多余状态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0

29、s1s2s3s5s7 两个状态两个状态s s和和t t等价等价, ,满足满足: : 一致性一致性同是终态或同是非终态同是终态或同是非终态 蔓延性蔓延性从从s s出发读入某个出发读入某个a(a(a a)和从和从 t t出发出发读入某个读入某个a a到达的状态等价。到达的状态等价。 状态状态2 2和和4 4是不等价的是不等价的( (可区别的可区别的) )。b02134abaaaabbbDFA M2 2是非终态而是非终态而4 4是终态是终态状态状态2 2和和3 3是不等价的，因为读入是不等价的，因为读入b b后分别到后分别到达达2 2和和4 4，而，而2 2和和4 4是不等价的。是不等价的。 对于一

30、个对于一个DFA M =DFA M =（K,f,kK,f,k0 0,k,kt t) )，存在一存在一个最小状态个最小状态DFA MDFA M = =（K K,f,f,k,k0 0,k,kt t),),使使L(ML(M)=L(M).)=L(M). DFADFA的最小化算法的核心：的最小化算法的核心： 把一个把一个DFADFA的状态分成一些不相交的子的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等别的，而同一子集中的任何两个状态都是等价的价的. .将下图中的将下图中的DFA MDFA M最小化最小化 1,2,

31、3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21352746aaaaaaabbbbbbba13546aaaabbbbb1,2,3,4 5,6,71,2 3,41,256,73 4 56,7 1.1.对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个上的上的正规式正规式R,R,使得使得L(R)=L(M)L(R)=L(M)。 2 2. .对于对于上的一个正规式上的一个正规式R R，可以构造一个，可以构造一个上的上的NFA MNFA M，使得，使得L L( (M)=L(R)M)=L(R)。 1.1. 对于对于上的上的NFA MNFA M，可以构造

32、一个，可以构造一个上的正规上的正规式式R,R,使得使得L(R)=L(M)L(R)=L(M)。 第一步：在第一步：在M M的状态转换图上的状态转换图上，一，一个为个为x x结点，一个为结点，一个为y y结点。从结点。从x x结点用结点用弧连接弧连接到到M M的的，从，从M M的的用用弧连接到弧连接到y y结点。形成一个与结点。形成一个与M M等价的等价的M,MM,M只只有有和和。 第二步：逐步消去第二步：逐步消去M M中的所有结点，直至只剩下中的所有结点，直至只剩下x x和和y y。（。（消去规则见下页）消去规则见下页） 最后最后x x和和y y结点间的弧上的标记则为所求的正规式结点间的弧上的标

33、记则为所求的正规式R R。123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3例：例：03124a,baaa,ba,bbb求正规式求正规式R R03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xyxy(a|b)* (aa |bb)(a|b)*0a|bxyaa(a|b)* |bb(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*2 2. .对于对于上的一个正规式上的一个正

34、规式R R，可以构造一个，可以构造一个上的上的NFA MNFA M，使，使得得L L( (M)=L(R)M)=L(R)。(1)R=(1)R=(3)R=a(3)R=a(2)(2)R=R= (4)R=s|t(4)R=s|txyxy xya axyNFA(s)NFA(s)NFA(t)NFA(t) xys st t或或(5)R=st(6)R=s*NFA(s)NFA(s)NFA(t)NFA(t) NFA(s)NFA(s)xy xx1yst或或xx1y s或或例：例：为为构造构造NFA NNFA N，使得使得L(N)=L(R)L(N)=L(R)。23a54b2354ab16解法一：解法一：2354ab162354ab1607继续加上继续加上abbabb即可得到结果。即可得到结果。xiy(a|b)*abbxjyabbia|bxjyabbiab继续对继续对abbab