编译原理-词法分析.ppt

1、1,本章在编译程序中的地位,表 格 管 理,词法分析器,语法分析器,语义分析与中间代码产生,优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,出 错 处 理,2,词法分析,任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号。,单词：标识符，保留字，常数，算符，界符 词法分析阶段的工作所依循的是语言的词法规则。描述词法规则的有效工具是正规式和有限自动机。,3,3.1 对词法分析器的要求,3.1.1 词法分析器的功能和输出形式 输入源程序，扫描识别, 输出单词符号 程序语言的单词符号一般分为五种： 关键字(保留字

2、或基本字)：如 begin,end,if,then,else,while,do等 标识符：用来表示各种名字，如 X1 字面常数：如 256，3.14，true,abc 运算符：如 、*、/ 等等 分界符：如 逗号，分号，冒号等,4,单词符号的内部表示是二元式： (词类种别编码, 单词符号自身的属性值) 1. 词类种别编码提供给语法分析程序使用； 2.单词自身的属性值提供给语义分析程序使用。 3. 具体的分类设计方法以方便语法分析程序使用为原则。,单词符号的内部表示,5,例子,考虑下述C语言代码段： while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列： = ,

3、- ,6,3.1.2 词法分析器作为独立子程序,把词法分析设计成一个独立程序，每当语法分析器需要一个单词符号时就调用这个子程序。 每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析器处理。如图所示：,7,输入、预处理：词法分析第一步,词法分析程序,预处理用于删除空白符、回车符、换行符及注释等。,2）相关问题,词法分析器可以作为一个独立的子程序，也可以作为一遍独立的扫描来安排。 扫描缓冲区,双缓冲区, 搜索 起点 指示器 指示器, 起点 搜索 指示器 指示器,8,9,关键字的识别(1)、超前搜索,像FORTRAN这样的语言，关键字的识别甚为麻烦。因为 1

4、. 关键字不加保护（只要不引起矛盾，用户可以用它们作为普通标识符）。 2. 关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。,10,关键字的识别(2),下面是几个FORTRAN的正确语句，空白可有可无，不作分隔符： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55 语句1和2分别是DO和IF语句，它们都是以某关键字开头的。 语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。,11,标识符、常数的识别,标识符的识别 是字母开头的字母数字串，后跟算符或界符，识别不困难，例如 DO99K=1.10 常数的识别 算术常数的识别:

5、 多数语言很直接，有的须采用超前搜索，如FORTRAN语言中： IF(5.EQ.M)GOTO55 - 5.E08 逻辑(布尔)常数的识别: 比较容易 FORTRAN文字常数的识别: 麻烦, 须作特殊处理,12,算符、界符的识别,算符的识别 单个字符构成的算符的识别较容易 如 i+j 多个字符构成的算符的识别须使用超前搜索 如 i+界符的识别 界符的识别比较简单,13,3.2.3 状态转换图,状态转换图用来： 描述单词符号的结构 识别单词符号串 是设计词法分析器的工具 手工生成词法分析器的方法:,构造识别单词符号的状态转换图,14,状态转换图,状态转换图是一张有限方向图，只包含有限个状态，即有限

6、个结点。 1. 结点代表状态，用圆圈表示 2. 终止状态用双圈表示 3. 初始状态前标记符号“ ”来表示 4. 状态之间用箭弧连结 5. 箭弧上的标记代表在射出结点即箭弧始结点状态下可能出现的输入字符或字符类，箭弧标记表示状态转换的条件。,15,状态转换图：例,在状态1下，若输入字符为X，则读进X，并转换到状态2。 若输入字符为y，则读进y，并转换到状态3。 若输入字符非x和非y，则此转换图不工作。,一个状态转换图可用于识别一定的字符串,16,状态转换图识别字符串：例1,识别标识符的状态转换图。其中0为初态，2为终态。 这个转换图识别标识符的过程是: 从初态0开始，若在状态0下输入字符是字母，

7、则读进它，并转入状态1。在状态1之下，若输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到发现输入字符不再是字母或数字时(这个字符已经被读进)就进入状态2。,17,状态转换图识别字符串: 例,识别标识符的状态转换图。其中0为初态，2为终态。 状态2是终态，它意味着到此已经识别出一个标识符。终态上打个*号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串。如果在状态0时输入字符不为“字母”，则意味着这个转换图不工作。,18,状态转换图识别字符串: 例2,例2 是识别整数的转换图。其中0为初态，2为终态, 打了*号。 识别的过程类似前例。,19,例3 是一个识别FOR

8、TRAN实型常数的转换图。其中0为初态，7为终态。,状态转换图识别字符串: 例3,该转换图可以识别下面形式的一些实数: 123. , .123, 123E3 ,123.456 .123E+10, 123.456E-3 等,某简单语言的单词符号编码,状态图,letter,digit,letter,（IDN，入口）,digit,digit,(其它), (其它),（NUM，值）,（ASG，_）,=,*,（STAR，_）,s,*,（POWER，_）,其它,IDNletter(letter|digit)*,NUMdigit(digit)*,ASG=,POWER*,STAR*,空白,21,22,3.3 正

9、规表达式与有限自动机,为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要将转换图的概念形式化。 本节主要讨论词法分析器自动产生所需要的工具, 引入：正规式，正规集，有限自动机等概念。 本节是本章的重点和难点。,23,3.3.1 正规式与正规集,对于字母表，有符号串集合*和+, 我们感兴趣的是它的一些特殊的子集，即所谓正规集。 使用正规式这个概念来描述正规集。 例如, =a,b,c,z,0,1,2,9 * =所有字母数字串 我们对如下子集感兴趣 : 字母开头的字母数字串 = 标识符集合,24,正规式与正规集的递归定义,(1) 和都是 上的正规式，它们所表示的正规集分别为

10、 和； (2) 任何a, a是上的一个正规式，它所表示的正规集为a； (3) 假定U和V都是上的正规式,它们所表示的正规集分别记为L(U)和L(V),那么,U|V、UV和U*也都是正规式,它们所表示的正规集分别为L(U)L(V)、 L(U)L(V)(连接积)和(L(U)*(闭包) 仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集，正规集也称为正规语言。,25,正规式定义,正规表达式 正规表达式对应的正规集 1. ， ， 2. a a 3. 若 r, s L( r ) , L(s) 则 选择 rs L( r ) L(s) 连接 r s L( r )

11、L(s) 闭包 r * ( L( r )* ( r ) L( r ) 运算优先级由高到低依次是: 闭包*、连接、选择|，括号最优先。注：有的书还引入了正则闭包，r+表示r作至少一次的任意有限次连接。,26,正规式与正规集: 例1,例1：=A,B,Z,a,b,z,0,1,9 正规式：A B . Z 正规集：L( A)L( B) L( Z) = A, B, , Z 正规式：0123456789 正规集：L(0) L(1) . L(9) = 0123456789 若 L A,B,Z,a,b,z, D 0,1,9 正规式：L(L|D)* 正规集： 标识符,27,正规式与正规集: 例2,例2: 设 =a

12、,b, 则正规式和正规集: ab a,b (ab)(ab) aa,ab,ba,bb a* ,a,aa,aaa,aaaa,= an | n0 (ab)* ,a,b,aa,ab,ba,bb,aaa,. = a, b* aab* a,ab,abb,abbb,abbbb,. = abn | n0,问：正规式 b(a|b)*a 表示的正规集是?,28,正规式与正规集: 例3.1,通过这一节的学习，要求能根据给出的简单正规式，会写出其表示的正规集。 例3.1 令=a,b,其正规式和正规集如下： 正规式 正规集 1. ba* 上所有以b为首后跟着 任意多个a的字。 2. a(a|b)* 上所有以a为首的字。

13、 3. (a|b)*(aa|bb)(a|b)* 上所有含有两 个相继的a或两个相继的b 的字。,29,正规式与正规集: 例3.2,例3.2: 令=A,B,0,1 , 则： 正规式 正规集 1. (A|B)(A|B|0|1)* 上的“标识符”的全体 =A,BA,B,0,1* 2. (0|1)(0|1)* 上“数”的全体 =0,10,1* 问: 正规式 , , 0 , 110 , 0|1 , 1* 表示的正规集是?,答: 正规集分别是 , , 0, 110, 0,1, ,1,11,111,=1* =1n | n0。,30,正规式的等价,若两个正规式U和V所表示的正规集相同，即L(U) =L(V)

14、，则认为二者等价，记为U=V 。 例1 ：b(ab)*=(ba)*b 因为: b(ab)*和 (ba)*b表示的正规集分别是: bab* ba*b = b,ab,abab, =,ba,baba,b = b,bab,babab, =b,bab,babab, 例2 ：00*=0*00*0* 正规集为 0n |n1 例3 : (a|b)*=(a*b*)* 正规集为 ,a,b,aa,ab,ba,bb,aaa,31,正规表达式的代数性质,注: 上述恒等式都表示两个正规式等价。 证明两个正规式等价: U=V L(U)=L(V),32,正规式等价的证明,例1. 证明 (V|W)U=VU|WU L(V|W)U) =L(V|W)L(U) = (L(V)L(W)L(U) = L(V)L(U)L(W)L(U) = L(VU)L(WU) = L(VU|WU) 例2. 证明 A*=|AA* L(|AA*)=L()L(A)