第2章词法分析.ppt

1、第2章 词法分析,2.1 词法分析器设计方法 2.2 一个简单的词法分析器示例 2.3 正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造 2.5 词法分析器的自动生成,词法分析的任务: 从左至右逐个字符地对源程序进行扫描, 产生一个个单词符号, 把字符串形式的源程序改造成为单词符号串形式的中间程序。 词法分析程序也叫词法分析器或扫描器。其功能是输入源程序,输出单词符号。,词法分析可采用如下两种处理结构： (1)把词法分析程序作为主程序。将词法 分析作为独立的一遍来完成。,(2) 把词法分析程序作为语法分析程序调 用的子程序。进行语法分析时,每当需 要一个单词时便调用词法分析程序

2、。,2.1 词法分析器设计方法,2.1.1 单词符号的分类与输出形式 1. 单词符号分类 单词符号是程序语言的基本语法单位。 程序语言的单词符号通常分为五种： (1)保留字：如if、while (2)标识符：标记常量、变量、函数等的名字 (3)常数：如实型0.618、布尔型TRUE (4)运算符：如+、-、*、/、 (5)界符：分界符，如, 、 ; 、( 、) 注意：保留字、运算符和界符的个数确定， 标识符和常数的个数不确定。,2. 单词符号的输出形式 ( 单词种别, 单词自身的值 ) (1) 单词种别: 单词种别表示单词的种类。 一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上

3、的方便。通常，每种单词对应一个整数码。 保留字：可全体视为一种，也可一字一种； 标识符：统归为一种； 常数：统归为一种,或按整、实、布尔等再分； 运算符和界符：一符一种，或统归为一种。,(2) 单词自身的值 单词自身的值是编译其它阶段需要的信息。 对于单词符号,若一个种别只含一个单词,则其种别编码就代表它自身的值。若一个种别含多个单词,则除种别编码外, 还应给出单词自身的值,以便把同一种类的单词区别开来。 注意：标识符自身的值是标识符自身的字符串,常数自身的值是常数本身的二进制数值。 此外,也可用指向某类表格中一特定项目的指针来区分同类中的不同单词。例如,对于标识符,可用它在符号表的入口指针作

4、为自身的值;常数可用它在常数表的入口指针作为自身的值。,2.1.2 状态转换图 词法分析中,可用状态转换图识别单词。状态转换图中,结点代表状态；结点之间由有向边连接，有向边上可标记字符。 如图,状态i下,若输入字符为x,则读入x并转到状态j;若输入字符为y,则读入y并转到状态k。,状态转换图中状态的数目是有限的，其中必有一个初态和若干个终态，终态结点用双圈表示。识别标识符的状态转换图如下：,识别无符号整数的状态转换图如下：,*,识别无符号数的状态转换图如下：,在状态转换图中, 到达单词符号的终态时即给出相应的单词编码。 若到达终态时多读入了一个符号,则识别出该单词后再将多读入的那个符号退回。对

5、此类情况的处理方法是在终态上以*作为标识。,图2-4 不含回路的分支状态,对不含回路的分支状态，可让它对应一个switch( )语句或一组if-else语句。,状态i 对应的switch语句如下： s=getchar ( ); switch (s) case a: case z: ; /*实现状态j功能的语句*/ case 0: case 9: ; /*实现状态k功能的语句*/ ,对于含回路的状态，可让它对应一个while语句。,状态i 对应的while语句如下： getchar ( ); while (letter( )|digit( ) getchar (); ; /*实现状态j功能的语句

6、*/,状态转换图中的终态一般对应一个return( )语句。return意味着从词法分析器返回到调用段，一般指返回到语法分析器。,2.2 一个简单的词法分析器示例,2.2.1 C语言子集的单词符号表示 大多数程序语言的单词符号都可用状态转换图予以识别。下面构造一个C语言子集的简单词法分析器，该C语言子集的所有单词符号及其种别编码和内码值如下表所示。由于直接使用整数编码不利于记忆，故该例采用一些助记符表示种别编码。,表2.1 C语言子集的单词符号及内码值,2.2.2 C语言子集对应的状态转换图的设计 首先对输入串做预处理。 即剔除多余的空格、注释等。 其次把保留字作为一类特殊标识符处理。 即对保

7、留字不专设对应的状态转换图， 当状态转换图识别出一个标识符时就 去查表，确定它是否为一个保留字。C语言子集对应的状态转换图如下：,注意: (1)状态2识别出一个单词符号后需先查保留字表,若匹配则为保留字,否则为标识符。若为标识符,还需查符号表,看表中是否有此标识符。若符号表中无此标识符,则先将它登录到符号表中,再返回它在符号表中入口地址作为内码值;若表中有此标识符,则直接返回其入口地址作为内码值。 (2)状态4识别出一个常数后需先将它转换成二进制常数再登录到常数表,然后返回它在常数表中的入口指针作为内码值。,2.2.3 状态转换图的实现 状态转换图易于用程序实现,最简单的办法是让每个状态对应一

8、小段程序。对图25,首先引进一组变量和过程： (1)character: 字符变量,存放最新读入 的源程序字符。 (2)token: 字符数组,存放构成单词符号 的字符串。 (3)getbe( ): 若character中字符为空,则 调用getchar( ),直至character为非空。,(4)concatenation( ): 将token中字符串与 character中字符连接作为token中的新 字符串。 (5)letter( )和digit( ): 判断character中的字 符是否为字母和数字的布尔函数,若是 则返回true, 否则返回false。 (6)reserve( ):

9、 按token数组中的字符串查 保留字表, 若是保留字则返回其编码, 否则返回0。,(7) retract( ): 扫描指针回退一个字符, 同 时将character置为空白。 (8)buildlist( ): 将标识符登录到符号表或 将常数登录到常数表。 (9)error( ): 进行出错处理。,C语言子集对应的的词法分析器如下: token= ; /*对token数组初始化*/ s=getchar( ); getbe( ); /*滤除空格*/ switch (s) case a: case z: while (letter ( )digit ( ) concatenation ( ); /

10、*将当前读入 的字符送入token数组*/ getchar ( ); ,retract ( ); /*扫描指针回退一个字符*/ c=reserve ( ); if (c=0) buildlist ( ); /*将标识符登录到符号表*/ return (id, id在符号表中的入口指针); else return (保留字码, null) ; break;,case 0: case 1: case 9: while (digit ( ) concatenation ( ); getchar ( ); retract ( ); buildlist ( ); /*将常数登录到常数表中*/ retur

11、n (num, num的常数表入口指针); break;,case +: return (+，null); break; case-: return (-，null); break; case *: return (*，null); break; case : getchar ( ); if (character= =) return(relop,LE); else retract ( ); return (relop,LT); break;,case =: getchar ( ); if (character=) return(relop,EQ); else retract ( ); ret

12、urn (=, _ ); break; case ;: return (;, -); break; default: error ( ); ,2.3 正规表达式与有限自动机简介,2.3.1 正规表达式与正规集 状态转换图对构造词法分析器非常有效，为便于词法分析器的自动生成，需将状态转换图的概念形式化。正规表达式就是一种形式化表示法，它可以表示单词符号的结构，从而精确定义单词符号集。正规表达式简称正规式，它表示的集合称为正规集。,下面以标识符为例来说明正规式与正规集: 标识符是以字母开头的字母数字串。 若用letter表示字母, 用digit表示数字, 则标识符可表示为: letter(lett

13、er|digit )* 其中并置表示两者的连接, 表示两者选一, * 表示零次或多次引用。 letter(letter|digit)* 为标识符的正规式， 该正规式表示的集合为标识符的正规集。,正规式和正规集的递归定义： (1)和为字母表上的正规式， 它们表示的正规集分别为和。 (2) 对任一a, a是上的正规式， 它表示的正规集为a。 (3)若R和S是上的正规式, 它们表示的 正规集为L(R)和L(S), 则 R|S是上的正规式， 它表示的正规集为L(R)L(S)；, RS是上的正规式， 它表示的正规集为L(R)L(S); 连接积 (R)*是上的正规式， 它表示的正规集为(L(R)*；闭包

14、(4)仅由有限次使用(1)(3)得到的表示式是 上的正规式, 它表示的集合是上的 正规集。,说明： 1上的一个字指的是由中字符构成的 一个有穷序列; 不包含任何字符的序列称为空字。 *表示上所有字的全体, 包括空字。 例如, 若=a, b 则*=, a, b, aa, ab, ba, bb, aaa, ,2表示不含任何元素的空集。 注意、和的区别： 表示不包含任何字符的序列,它是正规集中的一个元素；表示不含任何字的集合, 它是一个空的正规集；表示由空字组成的集合。,3使用括号可改变运算符的运算次序。 若规定*优先于, 优先于|, 则在不混淆情况下,可省去括号。 4*的正规式R和S的连接可形式化

15、为 RS= | R 反之, 若从s2出发能识别而停于终态, 从s1出发也能识别而停于终态, 则称s1和s2等价, 否则称s1和s2是可区分的。,DFA M的状态最小化过程： 将M的状态集分割成一些不相交的子集，使得任意两个不同子集的状态是可区分的，而同一子集中的任意两个状态都是等价的。最后, 从每个子集中选出一种状态，同时消去其它等价状态，就得到最简的DFA M且L(M)=L(M)。,DFA M的化简方法： (1)首先将DFA M的状态集S中的终态与非终态分开,形成两个子集,得到基本划分。 (2)对当前已划分出的I(1),I(2),I(m)子集, 看 每个I是否能进一步划分。对某个I(i)=

16、s1,s2,sk, 若存在输入字符a使得Ia(i)不全包含在当前划分的某个子集I(j)中, 即跨越两个子集, 则将I(i)一分为二。 (3)重复(2), 直到每个子集均不能再分。 不能再分是指子集要么仅有一个状态，要么有多个状态但这些状态不可区分。,如何进行子集的划分呢？ 假定当前子集I(i)=s1,s2,其中s1和s2经过有向边a分别到达状态t1和t2, 而t1和t2分属于当前已划出的两个不同子集I(j)和I(k),则应将I(i)分为两部分： I(i1)= s | sI(i)且s经有向边a到达t1 I(i2)= I(i) I(i1) 由于t1和t2是可区分的， 因此I(i1)中的状态与I(i

17、2)中的状态可区分。,划分结束后, 子集个数不再增加, 从每个子集中选一个状态形成新的DFA。 例如， I(i)=s1, s2, s3 若挑选s1作为I(i)的代表，则原来指向s2和s3的有向边均改为指向新DFA中的s1。 若I(i)中含原来的初态，则s1为新初态； 若I(i)中含原来的终态，则s1为新终态。,例2.9 化简由例2.8得到的DFA。,解: (1)先将状态集S=0,1,2,3,4,5,6划分为 终态集3,4,5,6和非终态集0,1,2。 (2)考察0,1,2a:因0,2,1a=1,3不属于 3,4,5,6和0,1,2,故将0,1,2划分为 0,2和1。,(3)考察0,2b:因0,

18、2b=2,4,不属于已划分 出的某个子集, 故0,2划分为0和2。 (4)考察3,4,5,6a： 3,4,5,6a=3,6,属于3,4,5,6,故不划分。 (5)考察3,4,5,6b： 3,4,5,6b=4,5,属于3,4,5,6,故不划分。 (6)按顺序把状态子集0,1,2,3,4,5,6 重命名为0,1,2,3, 得到化简后的DFA M:,2.4.4 正规式到有限自动机构造示例 例2.10 试用DFA的等价性证明正规式 (a|b)*与(a*b*)*等价。 解: (1)正规式(a|b)*对应的NFA如下：,用子集法确定化得如下转换表:,重命名转换表得:,于是得到DFA 如下:,化简: 因0,

19、1a=1, 故不划分。 因0,1b=1, 故不划分。 因此, 最简DFA如下:,重命名得状态转换矩阵:,由于(a|b)*和(a*b*)*对应的状态转换矩阵相同, 故二者等价。,(2) (a*b*)*对应的NFA如图2-20所示, 用子集法将NFA确定化得下述转换表:,例2.11 C语言可接受的合法文件名为 device: name.extension 其中device:和.extension可省。假定device, name和extension都是字母串, 长度不限但至少为1, 试画出识别文件名的DFA M。 解: 所求正规式为(cc*:|)cc*(.cc*|) 相应的NFA M如下图所示：,

20、首先进行预处理。 然后用子集法确定化、重命名。,于是得到DFA如下：,最后对DFA化简,化简后仍为上图。,例2.12 某高级程序语言无符号数的正规式 为 digit+(.digit+)?(e (+|)?digit+)? 其中digit表示数字, ()?表示()中内容 可有可无, 试给出其DFA M。 解: 用d代表digit，其NFA如下图所示：,用子集法将NFA M确定化,然后重命名。,于是得到下图所示的DFA M :,由状态转换矩阵可见, 状态5和6面对输入符号的下一状态相同, 但状态5为非终态, 状态6为终态, 故上述DFA已为最简。,例2.13 构造一DFA, 它接收=a,b上所有 满

21、足下述条件的字符串: 该字符串中的 每个a都有至少一个b直接跟在其右边。 解: = a,b, 所求正规式为b*(abb*)*。 相应的NFA M如下图所示:,用子集法将NFA M确定化, 然后重命名。,于是得到DFA M 如下:,用DFA M的化简方法得到最终划分： 0,2,3, 1 重命名后得到化简的DFA M如下:,从FA M到正规式的转换规则如下:,2.5 词法分析器的自动生成,由于不同高级语言中单词的结构大致相同, 基本上都可用一组正规式描述,因而希望构造一自动生成系统: 只要给出某高级语言单词的一组正规式及识别各类单词时应采取的语义动作, 该系统便可自动产生该语言的词法分析程序。,L

22、EX是美国Bell实验室研制的一个词法分析程序的自动生成工具。对任一高级程序语言，用户必须用正规式描述该语言的各个词法类(LEX的源程序)，LEX就可自动生成该语言的词法分析程序。 LEX及其编译系统的作用如下:,LEX源程序由用“%”分隔的三部分组成： 正规式的辅助定义式、识别规则、 用户子程序。 LEX源程序的书写格式： 辅助定义式 % 识别规则 % 用户子程序 其中, 一、三部分可省, 识别规则不可省。若用户子程序缺省, 则第二个“%”可省; 但若无辅助定义式, 第一个“%”不能省。,一个简单的LEX源程序如下： (单词的类别编码用整数编码表示) Auxiliary Definitions /*辅助定义*/ letterA|B|C| |Z|a|b|c|z digit0|1|2|3|9 % Recognition Rules /*识别规则*/ 1 while return (1,null) 2 do return (2,null) 3 if return (3,null) 4 else return (4,null) 5 switch return (5,null),6 return (6,null