《【教学课件】第四章词法分析.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章词法分析.ppt（90页珍藏版）》请在三一办公上搜索。
1、第四章词法分析,第一节 词法分析程序的设计,第二节 单词的描述工具,第三节 有穷自动机,第四节 正规式和有穷自动机的等价性,第五节 正规文法和有穷自动机的等价性,第六节 词法分析程序的自动构造工具,第七节典型例题及解答,知识结构,词法分析,自动构造工具,正规集,正规式,有穷自动机（NFA DFA),正规文法,知识结构,第四章 词法分析,4.1词法分析程序的设计,主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，,一.词法分析程序与语法分析程序的接口方式,词法分析工作可以是独立的一遍，把字符流的源程序变为单词序列，输出在一个中间文件上，这个
2、文件作为语法分析程序的输入而继续编译过程,更通常情况，常将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词，或说直到下一单词的第一个字符为止,二.词法分析程序的输出,1.单词符号一般可分为下列五种：基本字（关键字）：begin、end、if、while、var标识符：常量名、变量名、过程名常数（量）：25、3.1415、true、“ABC”运算符：、*、=界符：逗点、分号、括号,2.输出表示：（单词种别，单词自身的值）单词种别：语法分析需要的信息单词自身的值：编译其他阶段需要的信息,（标识
3、符，指向该标识符所在符号表中位置的指针）单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5,if i=5 then x:=y关键字if(3,if)标识符i（1，指向i的符号表入口）等号（4,=）常数5（2,5）关键字then（3,then）标识符x（4,指向x的符号表入口）赋值号:=（4,：=）标识符y（1,指向y的符号表入口）分号;（5,;）,三.将词法分析工作分离的考虑,1.使整个编译程序的结构更简洁、清晰和条理化：2.编译程序的效率会改进：3.增强编译程序的可移植性：,4.2单词的描述工具,一.正规文法程序设计语言中的几类单词可用下述规则描述：l
4、|ll|d|l|dd|d+|-|*|/|=|=,|;|(|)|其中l表示az中的任何一个英文字母，d表示09中的任何一个数字,例4.1：d|.e d|.e|d e|d|d|s d d|其中，s表示正或负号(+,-),二.正规式正规表达式（regular expression）是说明单词的pattern的一种重要的表示法（记号），是定义正规集的工具,定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，和都是上的正规式，它们所表示的正规集分别为和 任何a，a是上的一个正规式，它所表示的正规集为a,假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),
5、e1 e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)仅由有限词使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集,其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的,例4.2 令=a，b,上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(ab)aa,a
6、b,ba,bba,a,a,任意个a的串(ab),a,b,aa,ab 所有由a和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串,例4.3=d，e，+，-,则上的正规式d(dd)(e(+-)dd)其中d为09的数字表示的是：无符号数的集合,若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)be1=(ab),e2=(ab),设r,s,t为正规式，正规式服从的代数规律有：rs=sr“或”服从交换律r(st)=(rs)t“或”的可结合律(rs)t=r(st)“连接”的可结合
7、律r(st)=rsrt(st)r=srtr分配律r=rr=r是“连接”的恒等元素（零一律）rr=rr=rrr“或”的抽取律,三.正规文法和正规式的等价性,1.将上的一个正规式r转换成文法G=(VN,VT,P,S)：令VT，确定产生式和VN的元素用如下办法：,选择一个非终结符S生成产生式Sr，并将S定为G的识别符号。若x和y都是正规式，BVN，则：(R1)对形如 Axy的正规产生式，重写为：AxB，By(R2)对形如Ax*y的正规产生式，重写为：AxB，Ay，BxB，By(R3)对形如Axy的正规产生式，重写为:Ax，Ay不断应用R做变换，直到每个产生式右端只含一个VN,例4.4将 r=a(a|
8、d)*转换成相应的正规文法令S是文法的开始符号，形成Sa(a|d)*：R1 SaA A(a|d)*R2S aA A(a|d)B A B(a|d)B B R3 SaA A AaB AdB BaB BdB B,2.将正规文法转换成正规式：基本上是上述过程的逆过程，最后只剩下一个开始符号定义的正规式，其转换规则如表4.1所示：,例4.5Gs:SaA Sa AaAAdA Aa Ad SaA|a AaA|a|dA|d(a|d)A|(a|d)(a|d)*(a|d)s=a(a|d)*(a|d)|a=a(a|d)*(a|d)|)=a(a|d)*|)r=a(a|d)*,4.3有穷自动机,一.确定的有穷自动机（D
9、FA）（有限自动机）DFA：能准确地识别正规集一个确定的DFA：M=（K，f，S，Z）K是一个有穷集，它的每个元素称为一个状态是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表,f是转换函数，是在KK上的映射，即，如f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态SK是唯一的一个初态Z K是一个终态集，终态也称可接受状态或结束状态,例4.6：DFA M=（S，U,V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Q
10、f（Q，a）=Qf（U，b）=Vf（Q，b）=Q,一个DFA可以表示成一个状态图（状态转换图）假定DFAM含有m个状态，n个输入符号，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点(、)和若干个终态结点(双圈、+)，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧,图4.1状态图表示,例4.6中的DFA的状态图表示如图4.1所示：,一个DFA可以表示成一个矩阵表示，该矩阵的行表示状态，列表示输入符号，矩阵元素表示相应状态和输入符号将转换成的新状态，即k行a列为f(k,a)的值。用标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终
11、态标以0,图4.2矩阵表示,例4.5中的DFA的矩阵表示如图4.2所示：,若t*，f(S，t)=P，其中S为 M的开始状态，P Z，Z为终态集，则称t为DFA M所接受（识别）设QK，函数f(Q,)=Q，一个输入符号串t（t1tx，t1,tx*），在DFAM上运行的定义为：f(Q,t1tx)=f(f(Q,t1),tx),例如，证明t=baab被例4.6的DFA所接受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 M所能接受的符号串的全体记为L(M)结论：上一个符号串集V是
12、正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)DFA的确定性表现在转换函数f:KK是一个单值函数，也就是说,对任何状态kK和输入符号a，f(k,a)唯一地确定了下一个状态,二.不确定的有穷自动机NFA一个NFA：M=（K，f，S，Z）K是一个有穷集，它的每个元素称为一个状态是一个有穷字母表，它的每个元素称为一个输入符号f是一个从K*到K的子集的映像，即：K*2 KSK是一个非空初态集ZK是一个终态集,例4.7：一个NFA M=（0，1，2，3，4，a，b，f，0，2,4）其中f(0,a)=0,3 f(2,b)=2f(0,b)=0,1 f(3,a)=4f(1,b)=2 f(4,a
13、)=4f(2,a)=2 f(4,b)=4它的状态图表示如图4.3所示：,一个NFA也可以用一个矩阵表示.*上的符号串t在NFA N上运行.*上的符号串t被NFA N识别（读出、接受）.DFA是NFA的特例对每个NFA N存在一个DFA,使得L(M)=L(N)对于任何两个有穷自动机M和N，如果L(M)=L(N)，则称M与N是等价的,三.NFA转换为等价的DFA定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机将NFA转换成接受同样语言的DFA，这种算法称为子集法,定义对状态集合I的几个有关运算：1.状态集合I的-闭包，表示为-closure(I)，定义为一状态集，
14、是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)2.状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体,使用图4.4的NFAN的状态集合来理解上述两个运算：,-closure(0)=0,1,2,4,7令A=0,1,2,4,7,move(A,a)=3,8-closure(3,8)=1,2,3,4,6,7,8,图4.4NFAN,对于一个NFAN=（K，f，K0，Kt）来说，若I是K的一个子集，设Is1,s2,sj，a是中的一个元素，则move(I,a)=f(s1,a
15、)f(s2,a)f(sj,a),假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：M的状态集S由K的一些子集组成。用S1 S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1 S2M和N的输入字母表是相同的，即是转换函数是这样定义的：D(S1 S2,.Sj,a)=R1R2.Ri 其中 R1,R2,.,Ri=-closure(move(S1,S2,.Sj,a),S0=-closure(K0)为M的开始状态 St=Sj
16、Sk.Se，其中Sj Sk.SeS且Sj,Sk,.Se Kt,构造NFA N的状态K的子集的算法，见图4.5：假定所构造的子集族为C，即C=(T1,T2,.Ti),其中T1,T2,.Ti为状态K的子集,例4.8应用图4.5的算法对图4.4的NFAN构造子集 步骤如下：1.首先计算-closure(0)：令T0=-closure(0)=0,1,2,4,7，T0未被标记，它现在是子集族C的唯一成员2.标记T0：令T1=-closure(move(T0,a)=1,2,3,4,6,7,8，将T1加入C中，T1未被标记。令T2=-closure(move(T0,b)=1,2,4,5,6,7，将T2加入C
17、中，T2未被标记3.标记T1：-closure(move(T1,a)=1,2,3,4,6,7,8，即T1，T1已在C中。T3=-closure(move(T1,b)=1,2,4,5,6,7,9，将T3加入C中，T3未被标记,4.标记T2：-closure(move(T2,a)=1,2,3,4,6,7,8，即T1，T1已在C中。-closure(move(T2,b)=1,2,4,5,6,7，即T2，T2已在C中5.标记T3：-closure(move(T3,a)=1,2,3,4,6,7,8，即T1。-closure(move(T3,b)=1,2,4,5,6,7,10,令其为T4，在入C中，T4未
18、被标记6.标记T4：-closure(move(T4,a)=1,2,3,4,6,7,8，即T1。-closure(move(T4,b)=1,2,4,5,6,7，即T2,a,b,0,01247,T0=01247,38,5,38,1234678,5,124567,T1=1234678,38,59,59,1245679,T2=124567,38,5,T3=1245679,38,5 10,5 10,12456710,T4=12456710,38,5,至此，算法终止共构造了5个子集：T0=0,1,2,4,7T1=1,2,3,4,6,7,8T2=1,2,4,5,6,7T3=1,2,4,5,6,7,9T4=
19、1,2,4,5,6,7,10那么图4.4的NFAN构造的DFAM为：1.S=T0,T1,T2,T3,T4 2.=a,b,3.D(T0,a)=T1 D(T3,a)=T1 D(T0,b)=T2 D(T3,b)=T4 D(T1,a)=T1 D(T4,a)=T1 D(T1,b)=T3 D(T4,b)=T2 D(T2,a)=T1 D(T2,b)=T24.S0=T05.St=T4为便于书写，将T0、T1、T2、T3、T4重新命名为A、B、C、D、E或用0、1、2、3、4分别表示，若采用后者，该DFAM的状态转换图如图4.6所示：,图4.6DFAM,四.DFA的化简最小状态DFA：没有多余状态(死状态)没有
20、两个状态是互相等价（不可区别）一个有穷自动机可以通过消除无用状态和合并等价状态而转换成一个最小的与之等价的有穷自动机有穷自动机的无用状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态或者从这个状态没有通路到达终态例如图4.7的有穷自动机M中的状态s4便是无用状态,图4.7消除多余状态,在有穷自动机中，两个状态s和t等价的条件是：一致性条件必须同是为可接受状态或不可接受状态蔓延性条件对于所有输入符号，必须转换到等价的状态里,分割法：把一个DFA（不含多余状态）的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的,DFAM最小化方法：
21、先分成终态集合和非终态集合对每个集合中的符号分别用输出字母去查看它们到达状 态的集合是否在同一个集合中如果不在同一个集合，将它们划分在不同的集合中直到不能再划分为止,例4.9将图4.8中的DFAM最小化P0=(1,2,3,4,5,6,7)aP1=(1,2,3,4,5,6,7)aP2=(1,2,3,4,5,6,7)aP3=(1,2,3,4,5,6,7)b令1代表1,2消去2，令6代表6,7，消去7，得到图4.8(b)的DFA M，它是4.8(a)的DFA M的最小化,图4.8DFAM和DFAM,4.4正规式和有穷自动机的等价性,对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(
22、M)第一步，在M的状态转换图上加进两个结，一个为x结点，一个为y结点。从x结点用弧连接到M的所有初始结点，从M的所有终态结点用弧连接到y结点。形成一个与M等价的M,M只有一个初态x和一个终态y 第二步，逐步消去M中的所有结点，直至只剩下x和y结点。在消结过程中，逐步用正规式来标记弧,其消结的规则如下：,最后x和y结点间的弧上的标记则为所求的正规式r,例4.10以例4.7的NFAM为例，M的状态图在图4.3，求 正规式r,使L(r)=L(M),对于上的一个正规式R，可以构造一个上的NFA M，似的L(M)=L(R)语法制导方法：按正规式的语法结构指引构造过程，首先将正规式分解成一系列子表达式，然
23、后使用下面规则为r构造NFA，对r的各种语法结构的构造规则具体描述如下：,1.对于正规式，所构造的NFA为：,例4.11为r=(a|b)*abb构造NFAN,使得L(N)=L(r)从左到右分解r,令r1=a,第1个a,则有令r2=b,则有令r3=r1|r2,则有,令r4=r3，则有：,令r5=a，令r6=b，令r7=b，令r8=r5r6，令r9=r8r7，则有：令r10=r4r9，则最终得到图4.4的NFA N即为所求。,其实，分解R的方式很多，用图4.10(a)(b)(c)(d)分别表明另一种分解方式和所构造的NFA。,图4.10从正规式r构造NFA,4.5正规文法和有穷自动机的等价性,采用
24、下面的规则可以从正规文法G直接构造一个有穷自动机NFAM；使得L（M）L（G）：M的字母表与G的终结符集相同为G中的每个非终结符生成M的一个状态，G的开始符S是开始状态S,增加一个新状态Z，作为NFA的终态对G中的形如AtB的规则（其中t为终结符或，A和B为非终结符的产生式），构造M的一个转换函数f(A,t)=B对G中形如At的产生式，构造M的一个转换函数f(A,t)=Z,例4.12：与文法GS等价的NFAM如图4.11GS:Sa A SbBS AaB AbA BaSBbA B,有穷自动机转换成等价的正规文法：对转换函数f(A,t)=B,可写一产生式：AtB对可接受状态Z，增加一产生式：Z有穷
25、自动机的初态对应文法开始符有穷自动机的字母表为文法的终结符集,例4.13：给出与图4.12的NFA等价的正规文法GG（A，B，C，D，a，b，P，A），其中P为：Aa B C AbD DaBBbC DbDCaA D CbD,4.6词法分析程序的自动构造工具,以LEX为例介绍如何从正规式产生识别该正规式所描述的单词的词法分析程序LEX是一个广泛使用的工具，UNIX系统中使用lex命令调用。它用于构造各种各样语言的词法分析程序,图 4.13LEX编译系统的作用,图 4.14 使用LEX生成词法分析器,LEX程序由三部分组成：说明部分：变量说明、常量说明、正规定义%转换规则：Pn action n%
26、辅助过程：容纳的是action所需要的辅助过程,图4.15给出一个识别PL/O单词的LEX程序片断：IDENTa-zA-Z a-zA-Z0-9*NUMBER0-9 0-9*%(#include stdio.h#include code.h“#include symbol.h“#include y.tab.h“extern int level;int cc=0;%)%cc+;t tablize();/*adjustcc to tabposition*/n cc=0;line-copy();/*copy a line of input file*/cc+;return GT;=cc+;return
27、 EQ;,#cc+;return NE;,cc+;return colon;.cc+;return Period;(cc+;return Lparen;)cc+;return Rparen;=cc+;cc+;return GE;=cc+;cc+;return ASGN;cc+;return Semicolon;NUMBER intn;cc+=yyleng;sscanf(yytext,%d,IDENT Symbol*s;cc+=yyleng;if(s=lookup(yytext)=0)/*new identifier*/s=install(yytext,VARIABLE,level,0);/*i
28、nstall symbol*/if(stype=C)yylval.number=s-adr;else/*its a VARIABLE or PROC*/yylval.sym=s;return s-type;%yywrap();,图 4.15 LEX程序例子-识别PL/0单词的LEX程序,4.7典型例题及解答,1.构造正规式1（01）*101相应的DFA,2.将图4.18所示的DFA最小化,3.下面是用于生成词法分析器scanner的LEX的源文件，请给出scanner对输入串ababcbacaabaababaa的输出结果：%a+b*a printf(1%sn,yytext);(ab)+c?pr
29、intf(2%sn,yytext);aa printf(3%sn,yytext);(a|b)*c printf(4%sn,yytext);,【本章小结】词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词,交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了正规式和有穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如LEX的原理。词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。,第4章习题第1题：构造正规式1(0|1)*101相应的DFA,第2题：将下图确定化：,第3题：将下图的（a）和（b）分别确定化和最小化：,第4题：构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。,第4章作业题P72：1.(2)(3)2.4.6.7.9.,
