《第三章编译原理》由会员分享，可在线阅读，更多相关《第三章编译原理（99页珍藏版）》请在金锄头文库上搜索。
1、本章重点单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。回顾回顾什麽是词法分析程序4实现词法分析（lexicalanalysis）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序和语法分析程序的关
2、系源程序词法分析程序语法分析程序Tokengettoken.词法分析程序的主要任务：读源程序，产生单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，常常遇到的术语Token单词,词标，符号lexeme词素，词位pattern模式，式样帮助理解术语Ingeneral，thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput.Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thep
3、atternissaidtomatcheachstringintheset.A lexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.e.g.Constpi=3.14159；中的pi是token“identifier”的lexeme，其pattern为letterfollowedbylettersand/ordigit.词法分析工作从语法分析工作独立出来的原因：简化设计改进编译效率增加编译系统的可移植性正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分.单词符号的语法可以
4、用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造.首先表述一些基本术语和概念.符号符号一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。字母表字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。符号串符号串 由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=0，1上的符号串.字母表A=a,b,c上的一些符号串有：
5、a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。可以使用字母表示符号串，如x=STR表示“x是由符号S、T和R，并按此顺序组成的符号串”。符号串的长度符号串的长度 如果某符号串x中有m个符号，则称其长度为m，表示为x=m，如001110的长度是6。空符号串空符号串，即不包含任何符号的符号串，用表示，其长度为0，即=0。介绍有关符号串的一些运算。符号串的头符号串的头, ,尾，固有头和固有尾尾，固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。举个例子:
6、设z=abc,那么z的头是,a,ab,abc,除abc外，其它都是固有头；z的尾是,c,bc,abc,z的固有尾是,c,bc。当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x；如果只是为了强调x在符号串z中的某处出现，则可表示为：z=x；符号t是符号串z的第一个符号，则表示为z=t。符号串的连接符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于的含义，显然有x=x =x。例如x=ST，y=abu，则它们的连接xy=STabu，看出x=2，y=3，xy=5符号串的符号串的方幂方幂：符号串自身连接n次得到的符号串 an 定义为 aa
7、aa n个a a1=a, a2=aa且a0=例；若x=AB则:x0= x1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n0) 符号串集合符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 两个符号串集合两个符号串集合A A和和B B的乘积的乘积 定义为AB=xy|xA且yB 若集合A=ab,cde 集合B=0,1 则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括）组成的集合。* *称为称为的闭包的闭包。上的除外的所有符号串组成的集合记为+。+ +称为称为的正闭包的正闭包。例：例：=a,b=a,b * *=,a,b
8、,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,正规式正规式也称正则表达式,正规表达式（regularexpression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=，。1。和都是上的正规式，它们所表示的正规集分别为和；2。任何a，a是上的一个正规式，它所表示的正规集为a；3。假
9、定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1)。4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。正规式中的符号其中的“”读为“或”（也有使用“+”代替“”的）；“”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为“”、“”、“”。连接符“”一般可省略不写。“”、“”和“”都是左结合的。例子令=a，b，上的正规
10、式和相应的正规集的例子有：正规式正规集aaaba,babab(ab)(ab)aa,ab,ba,bba,a,a,任意个a的串正规式正规集(ab),a,b,aa,ab所有由a和b组成的串(ab)(aabb)(ab)上所有含有两个相继的a或两个相继的b组成的串讨论下面两个例子例3.1令=l，d，则上的正规式r=l(ld)定义的正规集为:l,ll,ld,ldd,其中l代表字母,d代表数字,正规式即是字母(字母|数字),它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和多数程序设计语言允许的的标识符的词法规则.例3.2=d，e，+，-,则上的正规式d(dd)(e(+-)dd)
11、表示的是无符号数的集合。其中d为09的数字。程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .4若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)be1=(ab),e2=(ab)4设r,s,t为正规式，正规式服从的代数规律有：1。rs=sr“或”服从交换律2。r(st)=(rs)t “或”的可结合律3。(rs)t=r(st)“连接”的可结合律4。r(st)=rsrt(st)r=srtr分配律5。r=r,r=r是“连接”的恒等元素零一律6。rr=rr=rrr“或”的抽取
12、律有穷自动机有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。关于有穷自动机有穷自动机我们将讨论如下题目确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化确定的有穷自动机DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f
13、，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；DFA定义3.f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态或结束状态。一个DFA的例子：DFAM=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（
14、Q，b）=Q一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；DFA的状态图表示bSUVQaaaba，b一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非
15、终态标以0。DFA 的矩阵表示的矩阵表示字符字符状态状态0001为了说明DFA如何作为一种识别机制,我们还要理解下面的定义*上的符号串上的符号串t t在在DFA MDFA M上运行上运行一个输入符号串t，（将它表示成Tt1的形式，其中T，t1*）在DFAM=（K，f，S，Z）上运行运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK扩充转换函数f为 K*K上的映射，且： f（ki，）=ki*上的符号串上的符号串t t被被DFADFA M M接受接受M=（K，f，S，Z）若t*，f(S，t)=P，其中S为M的开始状态，PZ，Z为终态集。则称t为DFAM所接受接受（识别识别）.例例：证
16、明证明t=baab被下图的被下图的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属于终态。属于终态。得证。得证。bSUVQabba, baaDFAM所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一
17、地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。DFA的行为很容易用程序来模拟.DFAM=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;whileceofdoK:=f(K,c);c:=getchar;ifKisinZthenreturn(yes)elsereturn(no)reviewRegularexpressionsonthealphabetaredefinedbythefollowingrecursiverules:1)Everysymbolof isaregularexpres
18、sion2) and f isaregularexpression3)ifr1 andr2 areregularexpressions,soare(r1 )r1 r2 r1 |r2 r1 *4)Nothingelseisaregularexpression. = 0,1,2,3,4,5,6,7,8,9 (1|2|3|4|5|6|7|8|9|0) * is a regular expression(1|2|3|4|.8|9|0) (1|2|3.|8|9|0) * is a regular expression(1|2|3.|8|9|0)+reviewDFAM=（K，f，S，Z）1) A fini
19、te set of states, one of which is designated the initial state or start state, and some of which are designated as final states.2) An alphabet of possible input symbols.3) A finite set of transitions that specifies for each state and for each symbol of the input alphabet, which state to go to next.D
20、FADFA = digit,not digitDFAM所能接受的符号串的全体记为L(M).对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的.结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。FA等价不确定的有穷自动机NFA定义NFAM=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2K）的一种映射，SK是初始状态集，ZK为终止状态集.例子NFAM=（S，P，Z，0，1，f，S，P，Z）其中f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z状态图表示SPZ00,111
21、1矩阵表示矩阵表示简化为f为K*到K的子集（2K）的一种映射具有转移的不确定的有穷自动机123abc有如下定理:对任何一个具有转移的不确定的有穷自动机NFAN，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。与上例等价的一个NFA.2acbb31acacbb类似DFA,对NFAM=K，f，S，Z也有如下定义*上的符号串t在NFAM上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在NFAM上运行运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK.*上的符号串t被NFAM接受若t*，f(S0，t)=P，其中S0S，PZ，则称t为NFA
22、M所接受接受（识别识别）*上的符号串t被NFA M接受也可以这样理解对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFAM所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。00011110100011100000010001100NFAM所能接受的符号串的全体记为L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。(0|1)*(000|111)(0|1)D
23、FA是NFA的特例.对每个NFAN一定存在一个DFA，使得L(M)=L(N)。对每个NFAN存在着与之等价的DFAM。有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一不唯一.从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是：DFADFA的每一个状态对的每一个状态对应应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.NFA确定化算法:假设NFAN=(K,f,K0,Kt)按如下办法构造一个DFAM=(S,d
24、,S0,St)，使得L(M)=L(N)：1.M的状态集S由K K的一些子集的一些子集组成。用S1S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1S2；2M和N的输入字母表是相同的，即是；3转换函数是这样定义的：d(S1S2,.Sj,a)=R1R2.Rt 其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)为M的开始状态；5St=SiSk.Se，其中SiSk.SeS且Si,Sk,.SeKt定义对状态集合I的几个有关运算：1
25、.状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。2.状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。状态集合I的有关运算的例子I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa构造NFAN的状态状态
26、K K的子集的子集的算法：假定所构造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。1开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2while（C中存在尚未被标记的子集T）do 标记T；for每个输入字母adoU:=-closure(move(T,a)；ifU不在C中then将U作为未标记的子集加在C中NFA的确定化例子4f35621iaaaabbbb4f35621iaaaabbbb等价的DFAaCDBAEFSbaaaaabbbbbabF确定有穷自动机的化简说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等
27、价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性同是终态或同是非终态传播性从s出发读入某个aa和从t出发读入某个a到达的状态等价。C和D同是终态,读入a到达C和F,C和F同是终态,C和F读入a都到达C,读入b都到达E.C和D等价aCDBAEFSbaaaaabbbbbabF最小
28、状态DFA对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFAM=（K,f, k0,kt)，,使L(M)=L(M).结论接受L的最小状态有穷自动机不计同构是唯一的。“分割法”DFA的最小化算法的核心把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非状态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.DFA的最小化算法 DFA M =（K,f, k0, kt),最小状态DFAM 1.构造状态的一初始划分： 终态k
29、t 和非终态K- kt两组(group) 2.对施用过程过程PPPP 构造新划分new 3.如new =,则令 final= 并继续步骤4，否则:=new重复2 . 4.为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r M 的开始状态是含有S0的那组的代表 M 的终态是含有F的那组的代表 5.去掉M中的死状态.过程过程PPPP :Construction of newFor each group G of do begin 1.Partiton G into subgroups such that two s
30、tates s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in new by the set of all subgroups formed end DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B C,D
31、,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa3.4词法分析程序的自动构造对有穷自动机和正规表达式进行了上述讨论之后,我们介绍词法分析程序的自动构造方法,这个方法基于有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性,即：即：1.对于上的一个NFAM，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个正规式R，可以构造一个上的NFAM，使的L(M)=L(R)。从上的一个正规式R构造上的一个NFAM，使得L(M)=L(R)的方法。“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：.“对于上
32、的一个正规式R,可以构造一个上的NFAM，使得L(M)=L(R).”说明一种构造方法：(1)R=,构造任一具有空终态集的NFAM(2）R=，构造的NFAM=(k0,f,k0.k0): f（k0,a)对于所有a都没定义。 (3）R=a,构造的NFA M=(k0,k1,f,k0.k1): f(k0,a)=k1(4)R=R1|R2,将步骤（1）（2）（3）分别应用到R1,R2产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M= (K1K2k,f,k,F) : k是新增加的状态符号， f包含f1和f2,且f(k,a)=f1(k1,a)f2(k
33、2,a).若k1F1且k2F2则F=F1F2，否则F=F1F2k(5)R=R1.R2将步骤（1）（2）（3）分别应用到R1,R2产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M= (K1K2,f,k1,F2) : f包含f1和f2,且f(k,a)=f1(k,a),当 kF1时; f(k,a)=f2(k,a),当 kK2时;f(k1,)=k2,(6)R=R1*将步骤（1）（2）（3）分别应用到R1,产生M1=(K1,f1,k1,F1),构造的NFA M= (K1k0,F F0,f,k0,F0)其中 k0,F F0 是新增加的两个状态,
34、f(k,a)=f1(k,a),当 kF1时; f(k0,)=f(F1 ,)= k1,F F0,再用状态图说明可用方法对于正规式x,x构造的NFA（两种）X对于正规式,构造的NFA（三种）FSF对于正规式R=,构造的NFAFS对于正规式r,r=R1|R2构造的NFA对于正规式r,r=R1R2构造的NFA对于正规式r,r=R1*构造的NFAR=(a|ab)*bb*正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法来构造词法分析程序词法分析程序的设计技术可应用于其它
35、领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。习题4.7练习1（1）34(b)5本章小结词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。识别Pl
36、0单词的FANFA的确定化MoreexampleDFA的最小化算法英文描述1.Construct an initial partition of the set of states with two groups:the accepting states F and the nonaccepting states S-F.2.Apply the procedure PP.(Construction of new) to to construct a new partition new.3.If new =,let final= and continue with step (4). Other
37、wise,repeat step(2) with := new.4. Choose one state in each group of the partition final as the representative for the group.The representatives will be the states of the reduced DFA M.let s be a representative state, and suppose on input a there is a transition from s to t .Let r be the representat
38、ive of ts group(r may be t).Then M has a transition from s to r on a.Let the start state of M be the representative of the group containing the start state s0 of M.and let the accepting states of M be the representative that are in F.Note that each group of final either consists only of states in F or has no states in F.5.If M has a dead state, that is, a states d that is not accepting and that has transitions to itself on all input symbols, then remove d from M,Also remove any states not reachable from the start state. Any transitions to d from other states become undefined.
