第三章词法分析及有穷自动机.

编译原理第三章词法分析及有穷自动机主要内容●词法分析程序的设计过程。●描述单词的文法：正规文法和正规式及它们之间的转换。●单词识别机制（有穷自动机）。●正规式，正规文法和有穷自动机三者之间相互转换。§1.词法分析程序的任务一、词法分析程序的任务及处理方式1.词法分析程序的任务主要任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。词法分析程序（扫描程序）：执行词法分析的程序。2.词法分析程序的处理方式词法分析程序与语法分析程序接口方式有两种：第一种方式：字符串表示的源程序词法分析程序单词串表示的源程序语法分析程序字符单词图2.1将词法分析作为单独一遍扫描，即在语法分析之前，实现源程序的词法分析工作。其输出（单词串）形成一个中间文件（内部形式的源程序表），然后移交给语法分析程序。第二种方式：将词法分析程序编写成一个子程序，每当语法分析程序需要读一个新单词时，便去调用它。注：后一种方式比较好。因为不需要在内存中构造和保存中间文件。字符串表示的源程序词法分析程序语法分析程序字符回送单词图2.2取单词二、词法分析程序的I/O1.输入字符串表示的源程序2.输出单词符号序列或单词符号。1)程序语言的单词符号单词：指语言中具有独立意义的最小语法单位。语言中的单词符号：一般可归结为五种：保留字（基本字）：如if,for,and等――个数确定标识符：表示常量、变量、类型、过程等名称――个数不确定常数：如34，-0.37等――个数不确定运算符：如+，-，*，/，等――个数确定界线符：如逗号，分号，括号等――个数确定注：·保留字，运算符，界线符可列表，供词法分析程序查询；·标识符和常数可用正规文法或正规式描述，供词法分析程序识别。2)输出的单词形式二元组：（单词的种别码，单词自身值）1o单词的种别码：表示单词的种类分类的原则：处理简单分类的方法：使每一个单词对应一个整数码分类的目的：最大限度地区别各个单词单词地分类法有多种：一种一类一字一类或一符一类具体：保留字：一字一种。如：if1then2。。。标识符：统归一种。常数：整数，实数，布尔统为一种或按类型分整数11实数12布尔13或全体一种+29:=17=21-1418=22*151923/16=20…运算符：+，-，*，/，，等统为一种；或一符一种：2o单词自身值（可有可无）单词自身值是单词的机内代码或者单词在表格中的地址码。如：标识符：自身的字符串（1，’a’）常数：自身的二进制数（11，’100’的二进制数）例：一种一类的单词输出形式设保留字、标识符、常数、运算符、分界符的种别码分别为1，2，3，4，5；将ifa1thenb:=10表示为一种一类的单词输出形式。ifa1thenb:=10＝词法分析器=(1,’if’)(字符串表示的源程序)(2,’a’),(4,’’)(3,’1’的二进制数)(1,’then’)(2,’b’)(4,’:=’)(3,’10’的二进制数)例：采用一字一类或一符一类地分类技术，则保留字单词自身值可无，但事先构造一个保留字单词对照表，其值可在词表中查到。ifa1thenb:=10＝词法分析器=(1,◎)字符串表示的源程序(10,‘a’)(23,◎)(3,’1’的二进制数)(2,◎)(10,’b’)(17,◎)(11,’10’的二进制数)上面符号◎表示要查保留词表表2.1保留字单词表单词类别码单词类别码...............If1+29Then2-14else3*15....../16............23for19:=17...§2.词法分析程序的设计过程一、词法分析程序的设计过程设计过程：词法分析程序设计过程：①把有的单词（如：标识符和常数）用正规文法或正规式描述；②将正规文法或正规式转换成等价的状态转换图（最小化的DFA图）；③根据状态转换图设计词法分析程序（状态转换图可视为词法分析程序的框图）。正规文法NFA转换正规式DFA化简最少化的DFA词法分析程序转换规则分裂法子集法状态转换图（DFA图）二、用状态转换图设计词法分析程序1.词法分析程序的预处理词法分析程序在识别单词前，需要对输入到缓冲区的源程序进行预处理。预处理：删去无用的空格，跳格，回车和换行等编辑性字符；删去注释部分每次对一串定长（如120个字符）的输入字符进行预处理，并装入一个指定的扫描缓冲区中。扫描缓冲区是一个一分为二的区域，每一个区域可容纳120个字符，且相互交替使用。搜索指针从单词起点开始搜索，如果遇到半区的边界但尚未达到单词的终点时，则可将后续的120个输入字符装进缓冲区的另一半中。搜索指针图2.3单词起点1201202.状态转换图状态转换图是为了识别正规文法或正规式而专门设计的有向图。他是有穷自动机的非形式化表示。状态转换图的组成：1o有限个状态结点状态结点代表正规文法的非终结符（用单圈表示）；开始状态结点：用双箭头指示；终止状态结点：用双圈表示。2o弧线→弧上的标记x指明在射出弧的结点状态下可能出现的输入字符或字符类,即终结符。(→表示机器的识别方向).大多数单词结构是用正规文法描述的x例：标识符∷=字母|标识符字母|标识符数字整数∷=数字|整数数字运算符∷=+|-|*|/|….界线符∷=；|，|(|)|…..。。。3.由正规文法构造状态转换图1)左线性正规文法构造状态转换图左线性正规文法的一般形式：U∷=a|wa左线性正规文法构造状态转换图的步骤如下：①增加一个开始状态结点s（假定文法的词汇表中不含s）；②以每个非终结符为状态作结点；③对于形如U∷=a的每一个规则，引一条从开始状态s到状态U的弧，弧上标记为a；对于形如U∷=wa的每一个规则，引一条从状态w到状态U的弧，弧上标记为a；④以识别符号为终止状态。SUaWUa例：设有正规文法G[Z]：Z∷=U0|V1U∷=Z1|1V∷=Z0|0（描述的语言为L(G)={01,10}）则状态转换图如下：SUV010101Z＋以开始符号Z作终态新增加开始状态S01字母2非字母和非数字字母或数字例：标识符的转换图：从开始状态出发到某一终止状态结点为止，所经过的路径上的符号串，称能为该状态转换图所接收（识别）的符号串。如：标识符x26为上述转换图识别，识别路径为x012非字母和非数字21612)右线性正规文法构造状态转换图①右线性正规文法U∷=a|aV构造状态转换图的步骤：②增加一个终止状态结点z（假定文法的词汇表中不含z）；③以每个非终结符为状态作结点；对于形如U∷=a的每一个规则，引一条从开始状态U到终止状态z的弧，弧上标记为a；对于形如U∷=aV的每一个规则，引一条从状态U到状态V的弧，弧上标记为a；④以识别符号为开始状态。UaZUVa４．根据状态转换图设计词法分析程序状态转换图实际上是编写词法分析程序的框图根据状态转换图写出相应的词法分析程序的方法：1o对于每个状态构造一小段程序。功能：①从输入串中读一个字符；②判明读入字符与由此状态出发的哪条弧上的标记匹配，便转至相匹配的那条弧所指的状态；③均不匹配时便失败（不能达到正常出口）2o再根据图形决定小段程序之间的调用。注：词法分析程序除了识别单词外，还可为语法程序提供更多的信息。因此，可在这些小段程序中加上一些语义处理（如对数值进行10=2等）例：设有关于单词无符号数的文法G=(VN,VT,P,N1)其中，VN={N1,N2,N3,N4,N5,N6,N7}VT={d,．,e,f,∧}P：N1∷=dN2|．N3|eN5N2∷=dN2|．N3|eN5|∧N3∷=dN4这里d表示数字（0～9）；e＝10；f＝；∧表示空字符；N1表示无符号数，其一般形式为：d…d．d…defd…dN4∷=dN4|eN5|∧N5∷=dN7|fN6N6∷=dN7N7∷=dN7|∧试构造识别此单词的词法分析程序1根据右线性正规文法，画出状态转换图N1=3N2=34N2=34·N3=34·5N4=34·56N4=34·56(达到出口),自上而下的推导过程。N1eN5N2N3N7N6N4d出口dfe∧∧d·ed·出口∧d出口dd2根据状态转换图写词法分析程序为每一个状态结点写一个过程或函数：对N1结点：ProcedurePN1BeginCh:=getchar();Ifch=”e”thenPN5Elseifch=”d”thenPN2Elseifch=”·”thenPN3ElseerrorEnd;对N2结点：ProcedurePN2BeginCh:=getchar();Ifch=”e”thenPN5Elseifch=”d”thenPN2Elseifch=”·”thenPN3Elsereturn;End;对N3,N4,N5,N6,N7结点分别写出程序段：……§3正规式与有穷自动机为了进一步讨论词法分析程序的自动生成，需要将状态转换图的概念加以形式化；同时将由正规文法描述的单词由正规式描述，可利用有穷自动机生成词法分析程序。一、正规式与正规集语言的单词结构不仅由正规文法描述，还可以由正规式描述。例：标识符∷=字母|标识符字母|标识符数字此正规文法描述了一个语言的集合。定义在{字母，数字}上的以字母开头的符号串的集合。这个集合还可以用正规式描述：字母(字母|数字)*。正规式描述的字符串的集合称为正规集1．正规式（也称正则式，正则表达式）和正规集的递归定义设有字母表∑={a1,a2,…,an},那么(1)ε,Φ,ai都是∑上的正规式，它们所描述的正规集分别为{ε}，Φ，{ai}；(2)若e1和e2都是∑上的正规式，它们所描述的正规集L(e1)、L(e2)，则：1o正规式的“或”（|）运算：e1|e2也是正规式，相应正规集为L(e1|e2)=L(e1)∪L(e2)；2o正规式的“连接”（.）运算：e1e2也是正规式，相应正规集为L(e1e2)=L(e1)L(e2)；3o正规式的“闭包”（*）运算:(e1)*也是正规式，相应正规集为L((e1)*)=(L(e1))*；(3)仅由有限次使用(1),(2)定义的表达式才是∑上的正规式，由这些正规式所表示的字符集才是∑上的正规集。例：设∑={a,b}，则∑上的正规式和正规集有正规式正规集1oa和baL(a)={a}和L(b)={b}L(a)=L(a)∪L(a)∪L(a)∪…={a}={a,aa,...}基本3oa|bL(a|b)=L(a)∪L(b)={a,b}4oabL(ab)=L(a)L(b)={ab}5oa*L(a*)=(L(a))*=L(a)∪L(a)∪L(a)∪….={a}*={ε,a,aa,aaa,..…}复合6oba*L(ba*)=L(b)L(a*)={b,ba,baa,baaa,……}7oa|ba*L(a|ba*)=L(a)∪L(ba*)={a,b,ba,baa,……}8o(a|b)*L((a|b)*)=(L(a|b))*={a,b}*={ε,a,b,aa,ab,……所有ab组成的串}9oa(a|b)*L(a(a|b)*)=L(a)(L(a)∪L(b))*={a}{a,b}*10o(a|b)*(aa|bb)(a|b)*L((a|b)*(aa|bb)(a|b)*)={a,b}*{aa,bb}{a,b}*012+123++2o注：.正规式仅由字母∑中的终结符号，通过或，连接和闭包三种运算组成的式子。例：有字母表∑={a，b}，下面正规式，求正规集。ba*正规集：b开头后面跟0个或若干个a。a(a|b)*正规集：a开头后面跟0个或a、b任意排列。例：有字母表∑={a，b}，下面用自然语言描述的正规集，求正规式(可能不唯一)。以ab结尾的所有字符串。(a|b)*ab包含偶数个b的所有字符串。(bb)*只包含一个a的所有字符串。b*ab*不包含ab子串的所有字符串。b*a*以a开头b结尾的所有字符串。a(a|b)*b２