编译方法 马知行 曹启君 机械工业出版社 编译原理演示文稿3.doc

编译方法 马知行 曹启君 机械工业出版社 编译原理演示文稿3 第三章词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列(识别单词)，用以语法分析。 执行词法分析的程序称为词法分析程序或扫描程序(扫描器)。 3.1词法分析的基本概念3.1.1词法分析的意义词法分析程序完成的是编译第一阶段的工作。 词法分析工作可以是独立的一遍，把字符流的源程序变为单同序列，输出在一个中间文件上，这个文件做为语法分析程序的输入而继续编译过程、为减少与外存储器交换数据，将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。 词法分析程序每得到一次调用，便从源程序文件中读入一些字符，直到识别出一个单词。 这样把词法分析程序和语法分析程序是放在同一遍里，而省掉了中间文件，节省了运行时间。 正如前面所说，正则文法是上下文无关文法的特例，也就是说，词法分析可以看作语法分析的的一部分，词法描述完全可以归并到语法描述中去，。 那么为什么将词法分析做为一个独立的阶段？为什么把编译过程的分析上作划分成词法分析和语法分析两个阶段？主要的考虑因素为1使整个编译程序的结构更简洁、清晰和条理化。 词法分析比语法分析简单的多，由于源程序结构上的一些细节，常使得识别单词的工作交给语法分析处理比较曲折和费时。 例如，空白和注释的处理；早期的FORTRAN受书写格式限制，需在识别单词时进行特殊处理等等。 如果这些工作都在语法分析时一并考虑，显然会使得分析程序的结构变得十分复杂。 2编译程序的工作效率也是要考虑的。 正则文法和上下文无关文法采用的识别器是不同的，把词法分析从语法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。 由于单词的结构可采用与正则文法对应的有限自动机进行识别，进而可建立词法分析程序的自动构造工具。 3可增强编译程序的可移植性。 在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。 另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的“”的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。 词法分析程序的主要功能是从字符流的源程序中识别单词，它要从左至右逐个字符地扫描源程序，有时还可完成其它一些任务。 如滤掉源程序中的注释和空白（由空格，制表或回车换行字符引起的空白）、为了使编译程序能将发现的错误信息与源程序的出错位置联系起来，同法分析程序负责记录新读入的字符行的行号，以便行号与出错信息相联；在支持宏处理功能的源语自中，可以由词法分析程序完成其预处理等等。 也可完成一些语法分析的工作，如说明部分的处理。 3.1.2词法分析的输入输出词法分析程序的功能是读入源程序，输出单词符号。 读入可采用从文件中逐个读入符号,或者建立一个缓冲区,先将字符读入缓冲区,然后从缓冲区中读入字符，使用缓冲区也可以采用双区域方式，即将缓冲区分成二部分一部分在分析时，更换另一部数据，从而提高词法分析的效率。 单词符号是一个程序设计语言的基本语法符号。 程序设计语言的单同符号大致可分成5种1.基本字，也称关键字，如C语言中的main，int，if,while和for等。 2.标识符，用来表示各种名字，如常量名、变量名、类型名、函数名和过程名等。 3.常数，各种类型的常数，如25，3.1415，TRUE和“ABC”等。 4.运算符，如+,-,*,/,”，终态结点用双圈表示。 若f(S，a)=S则从状态结点S到状态结点S画标记为a的弧；例上述状态图的五元式的DFA为DFA M=(S0，S1，S2,S3,a,b,f,S0,S3,)其中f(S0，a)S1f(S0，b)S0f(S1，a)S1f(S1，b)S2f(S2，a)S1f(S2，b)S3f(S3，a)S1f(S3，a)S0例接受语言（a|b）*abb的DFA状态图另外一个DFA还可以用矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f（k，a）的值。 其中用“=”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。 则上例中可表示成字符状态a bS0S1S00S1S1S20S2S1S30S3S1S01定义3.3扩充了映象f定义如下f(R,)=R,其中R为任意状态，f(R,t)=f(f(R,t),)其中*，t定义3.4对于某个DFA M=(K,，f，S，Z），如有f（S，）=P，PZ,则称字符串可被DFA所接受若M是又初始状态，又是终止状态，显然也是可以被接受的。 DFA M所能接受的全体记为L（M）例试证abaaba为上述的DFA所接受。 f(S,abaaba)=f(U,baaba)=f(V,aaba)=f(U,aba)=f(Q,ba)=f(Q,a)=QQZ得证。 结论:上的一个字符串集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L（M）。 2.不确定的有穷自动机（NFA）定义3.5一个不确定的有穷自动机（NFA）M是一个五元组M=(K,，f，S，Z）其中1K是一个有穷状态集2.是一个有穷输入字符字母表3.f是个从K到K的子集的映象。 4.S K，是一个非空初态(开始状态)集；5.Z K，是一个非空终态(终止状态)集。 一个NFA可用带标记的有向图来表示，这张有向图又称状态转换图，简称转换图。 它的结点是状态，有标记的边代表转换函数，这种转换图，从一个状态出发的不同边可以有相同的标记，该转换图的边可以用标记。 例下列是同一NFA的状态图形式与代数形式M=（S,A,B,Z,a,b,f,S,Z）其中f:f（S，a）Af（S，b）Bf（A，a）Zf（A，b）Bf（B，a）A,Bf（B，b）Zf（Z，a）A,Zf（Z，b）显然该自动机能接受字符串baaaaba abaaaaabababa定义3.6扩充了映象f定义如下f(R,)=R,其中R为任意状态，f(R,t)是所有集合f(Q i,)日并集，即f(R,t)=f(Q1,)f(Q2,)f(Q3,)，f(Q n,)其中*，t而f(R,t)=Q1，Q2，Q3，Q n直观起见f(Q1，Q2，Q3，Q n,)=f(Q i,t)因而，假如f(R,t)=Q1，Q2，Q3，Q n,则f(R,t)=f(Q1，Q2，Q3，Q n,)定义3.7对于某个NFA M=(K,，f，S，Z），如对于某个NFA存在状态P，PZ，且Pf(S0,),S0S,则称字符串可被该NFA所接受定义3.8对于任何两个有限自动机M和M，如果L（M）=L（M）,则称M和M是等价的。 3.NFA到DFA的转换对于一个NFA总是存在与之对应的DFA。 新的DFA的每个状态对应NFA的一个状态集,其中NFA的状态集是输入各种符号串所能到达的状态集,用DFA的状态来保存NFA在读入符号后能到达的所有状态踪迹。 这样NFA转换表里，每个条目是一个状态集，在DFA的转换表中，每个条目只有一个状态。 若NFA有n个状态,所有的状态集个数为2n-1(不能出现空集),DFA到NFA转换的思想是让DFA的每个状态代表NFA的状态集，这个DFA也就是用它的状态去保持NFA在读入符号后能到达的所有状态踪迹。 也就是说，在读入输入串a1a2a3a n后,DFA到达一个表征NFA状态子集T的状态，这个子集T是从NFA的开始状态沿着某些标有a1a2a3a n的路径的状态数集合，一般来说，当某个NFA的状态集合K包含n个状态时，相应的DFA的状态集合K将包含2n-1个状态。 但事实上其中很多状态是达不到的。 从NFA构造相应的DFA的算法: (1)将全部开始状态，以及从这些状态用弧能到达的状态集作为DFA的开始状态。 (2)对于每个新添的DFA状态作对每个输入符号a，作移动集合（f(T,a)|TS i）以及移动集合用弧能到达的状态集作为DFA的状态。 (3)重复2直至没有新的状态添入为止 (4)包含原NFA的终止状态的状态为新的终止状态。 例试构造上例中的相应的DFA。 解列出DFA的状态:a bSABAZBBA,BZZA,ZA,BA,B,ZB,ZA,ZA,ZBA,B,ZA,B,ZB,ZB,ZA,B,ZZ令S,A,B,Z,A,B,A,Z,A,B,Z,B,Z分别为S0,S1,S2,S3,S4,S5,S6,S7。 则相应的DFA M为M=（S0,S1,S2,S3,S4,S5,S6,S7，a,b,f,S0,S3,S5,S6,S7)其中f见图例将如图表示的NFA确定化a bX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,Y令状态X,5,1、5,3,1、5,4,1、5,3,1,2,6,Y、5,4,1,2,6,Y、5,4,1,6,Y、5,3,1,6,Y分别为0，1，2，3，4，5，6则4.确定自动机的化简为提高语言的识别效率，应该尽量压缩DFA的状态，也就是能不能找到一个状态数最少的DFA,可以证明在不考虑同构的前提下,最小化的DFA是唯一的。 所谓确定自动机M的最小化实际上是找一个状态数最少的M使L（M）=L（M）。 定义3.9如果DFA M从状态S出发，输入是，它可以停在某个终止状态，但是从T出发同样的输入，它停在一个非终止状态，或者相反，称为串可区分（可区别）状态S和T。 例可区分任何终止和非终止状态。 最小化DFA状态数的算法就是把DFA的状态数分成一些不相交的子集，每一子集的状态都是不可区别的。 每个子集合并成一个状态。 终止状态和非终止状态是可区分的,因此最初应划分成两个组，终止状态组和非终止状态组。 极小化DFA的状态数算法 (1)构造状态集合的初始划分，分成两组，状态F和非终止状态K-F。 (2)应用下面的过程对构造新的划分newnew=；do=new；for(中的每个组G)把G划分成小组，G的两个状态S和T在同一小组中，当且仅当对所有的输入符号a，S和T的a的转换是到的同一组中while(!=new); (3)在最终划分中的每个状态组中选一个状态代表它。 (4)如果等价的DFA中有对任何字符a都转换到本身，而不能从开始状态到的那些状态，以及不可能从开始状态到达的那些状态删除。 从任何其它到上述状态的转换都成为无定义。 例对图表示的DFA最小化0，1，2，34对于状态3输入b时不在同一组，故0，1，234对于状态1输入b时不在同一组，故0，2134而0，2对于任何输入都在同一组中，故不能再分了。 a b012113212314412解为了方便起见将图代表的DFA列一张表(如下)状态数最小的状态图如下5.正规式和有限自动机的转换可以证明对于正规式都存在与之等价的有穷自动机，反之亦成立。 从正规式到有限自动机利用转换系统构造NFA，把具有唯一开始状态和唯一终止状态允许标记有弧的NFA称为转换系统转换系统的构造,a的转换系统分别是转换规则如下:令SABZ,ABZ,BZ分别为S 0、S1和S2，则相应的DFA为DFA A0=(S0,S1,S2,a,b,S0,S0,S1,S2)其中（S0,a）=S1（S0,b）=S2（S1,a）=S1（S1,b）=S2（S2,b）=S2即: （2）解a bSA ABA ABAB ACZA ABA ACZABCZ ACZABCZ ABCZACZ令SA，AB，A，ACZ，ABCZ分别为S0,S1,S2,S3,S4则最小化为S0,S1,S2,，S3,S4S1的输入b不在同一组中，故S0,S2,，S1，S3,S4S0,S2，S1，S3,S4分别为S，A，Z则相应的DFA为DFA A0=(S，A，Z,a,b,S,Z)其中（S,a）=A,（S,b）=S（A,a）=A（A,b）=Z（Z,a）=Z（Z,b）=Z注意据题意不必确定化和最小化，但不能含弧从有限自动机到正规式把M的所有状态转换图上加上两个结点X、Y，从X结点用所有的初始结点，从M的所有终态结点用弧连接到Y结点，形成只有一个开始状态和一个终止状态的转换系统。 然后用下列规则逐步替换（适当可用等价的状态替换）直至只剩结点X、Y为止。 例试写出下图的正规式解故FA的正规式为(a|bb*a(bb*a)*a)*化简为(|bb*a(bb*a)*）a)*即(bb*a)*a)*正规文法和有穷自动机间的转换正规文法也可描述正规集，正规文法与有穷自动机有特殊关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M）=L(G) (1)右线性文法字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，（不妨取成相同的名字）G的开始符号S是开始状态S；增加一个新状态Z，做为NFA的终态；对G中的形如AtB其中t为终结符，A和B为非终结符的产生式，构造M的一个转换函数f（A,t）=B；即从A到B画一条弧标记为t。 对G中形如At的产生式，构造M的一个转换函数f（A，t）=Z。 从A到Z画一条弧标记为t例:与文法GS等价的NFA M如图GSSaA|bB|b AaB|bA|a BaS|bA|a则其NFA如图 （2）左线性文法字母表与G的终结符集相同；为G中的每个非终结符生成M的一个状态，G的识别符号Z是终止状态Z；增加一个新状态S，做为NFA的开始状态；对G中的形如ABt和t其中t为终结符，A和B为非终结符的产生式，构造M的一个转换函数f（B,t）=A；即对G中形如At的产生式，构造M的一个转换函数f（S，t）=A，即从B到A画一条弧标记为t。 例:与文法GZ等价的FA M如图GZZZa|Aa|Bb ABa|a BAb|b则下面介绍有穷自动机转换成等价的正规文法 （1）右线性文法对于f(A,t)=Z用产生式At代替;对于f(A,t)=B用产生式AtB代替 （2）左线性文法对于f(S,t)=A用产生式At代替;对于f(A,t)=B用产生式BAt代替例:给出与图相应的NFA写出等价的正规文法解右线性文法GA:Ab Bb Cb Db AaB AbD BbC CaA CbD DaB DbD即AaB|bD|b BbC|b CaA|bD|b DaB|bD|b左线性文法由于左线性文法只能有一个识别符号代表终止状态。 故引进新的终止状态Z，分别从C和D中引弧至Z，然后消去弧（凡是引非到有弧射出的状态，即直接引入非到Z，最后消去弧）GZBa Db BAa DAb CBb BDa DDb ACa DCb Zb ZAb ZBb ZCb ZDb3.2.3状态图前面说过可以用图来描述有限自动机,这种图也就称为状态图,它用箭头表示开始状态,用双圈表示终止状态。 从状态图到正规文法和从状态图到有限自动机类似，在这里不再重复了。 3.2词法分析程序的设