编译原理-词法分析.ppt

1 本章在编译程序中的地位 表 格 管 理 词法分析器 语法分析器 语义分析与中间代码产生 优化器 目标代码生成器 源程序 单词符号 语法单位 中间代码 中间代码 目标代码 出 错 处 理 2 词法分析 n任务：从左到右一个字符一个字符地读入源程 序，对构成源程序的字符流进行扫描和分解， 从而识别出一个个单词符号。 逻辑上紧密相连的一组字符， 这些字符具有集体含义。 n单词：标识符，保留字，常数，算符，界符 n词法分析阶段的工作所依循的是语言的词法规 则。描述词法规则的有效工具是正规式和有限 自动机。 3 3.1 对词法分析器的要求 3.1.1 词法分析器的功能和输出形式 n输入源程序，扫描识别, 输出单词符号 n程序语言的单词符号一般分为五种： n关键字(保留字或基本字)：如 begin,end,if,then,else,while,do等 n标识符：用来表示各种名字，如 X1 n字面常数：如 256，3.14，true,abc n运算符：如 、*、/ 等等 n分界符：如 逗号，分号，冒号等 4 n单词符号的内部表示是二元式： (词类种别编码, 单词符号自身的属性值) n1. 词类种别编码提供给语法分析程序 使用； n2.单词自身的属性值提供给语义分析 程序使用。 n3. 具体的分类设计方法以方便语法分 析程序使用为原则。 单词符号的内部表示 5 例子 n考虑下述C语言代码段： while (i=j) i- - ; 经词法分析器处理后，它将转换为如下的单 词符号序列： = , - 100 i 地址类型名字 符号表 10 如标识符单词 i 对 应的二元组(6, 10) 6 3.1.2 词法分析器作为独立子程序 n把词法分析设计成一个独立程序，每当语法分 析器需要一个单词符号时就调用这个子程序。 n每一次调用，词法分析器从源程序字符串中识 别出一个单词符号，并把它的内部表示二元组 交给语法分析器处理。如图所示： 词法分 析器 语法分析器 语义分析和 中间代码生成器 源程序 中间代码 7 输入、预处理：词法分析第一步 扫描缓冲区 预处理程序 预处理 扫描识别 输入缓冲区 内存 源程序 文本 外存 读入 词法分析程序 扫描识别 预处理用于删除空白符、回车符、换行符及注释等。 2）相关问题 n词法分析器可以作为一个独立的子程序， 也可以作为一遍独立的扫描来安排。 n扫描缓冲区 双缓冲区 搜索 起点 指示器 指示器 起点 搜索 指示器 指示器 8 9 关键字的识别(1)、超前搜索 n像FORTRAN这样的语言，关键字的识 别甚为麻烦。因为 n1. 关键字不加保护（只要不引起矛盾，用 户可以用它们作为普通标识符）。 n2. 关键字和用户自定义的标识符或标号之 间没有特殊的界符作间隔。 10 关键字的识别(2) n下面是几个FORTRAN的正确语句，空白可有 可无，不作分隔符： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55 n语句1和2分别是DO和IF语句，它们都是以某 关键字开头的。 n语句3和4是赋值语句，它们都是以用户自定 义的标识符开头的。 11 标识符、常数的识别 n标识符的识别 n是字母开头的字母数字串，后跟算符或界 符，识别不困难，例如 DO99K=1.10 n常数的识别 n算术常数的识别: 多数语言很直接，有的须 采用超前搜索，如FORTRAN语言中： IF(5.EQ.M)GOTO55 - 5.E08 n逻辑(布尔)常数的识别: 比较容易 nFORTRAN文字常数的识别: 麻烦, 须作特 殊处理 12 算符、界符的识别 n算符的识别 n单个字符构成的算符的识别较容易 如 i+j n多个字符构成的算符的识别须使用超前搜 索 如 i+界符的识别 n界符的识别比较简单 13 3.2.3 状态转换图 n状态转换图用来： n描述单词符号的结构 n识别单词符号串 n是设计词法分析器的工具 n手工生成词法分析器的方法: 转换 实现 词法分析程序 构造识别单词符号的状态转换图 14 状态转换图 n状态转换图是一张有限方向图，只包含有限 个状态，即有限个结点。 n1. 结点代表状态，用圆圈表示 n2. 终止状态用双圈表示 n3. 初始状态前标记符号“ ”来表示 n4. 状态之间用箭弧连结 n5. 箭弧上的标记代表在射出结点即箭弧始 结点状态下可能出现的输入字符或字符类 ，箭弧标记表示状态转换的条件。 2 3 1 Y X 15 状态转换图：例 n在状态1下，若输入字符为 X，则读进X，并转换到状 态2。 n若输入字符为y，则读进y， 并转换到状态3。 n若输入字符非x和非y，则此 转换图不工作。 2 3 1 Y X 一个状态转换图可用于识别一定的字符串 16 状态转换图识别字符串：例1 n识别标识符的状态转换图。其中0为初态，2为 终态。 n这个转换图识别标识符的过程是: 从初态0开 始，若在状态0下输入字符是字母，则读进它 ，并转入状态1。在状态1之下，若输入字符为 字母或数字，则读进它，并重新进入状态1。 一直重复这个过程直到发现输入字符不再是字 母或数字时(这个字符已经被读进)就进入状态 2。 12 字母或数字 0 *其他字母 17 状态转换图识别字符串: 例 n识别标识符的状态转换图。其中0为初态，2为 终态。 n状态2是终态，它意味着到此已经识别出一个 标识符。终态上打个*号，表示多读进了一个 不属于标识符部分的字符，应把它退还给输入 串。如果在状态0时输入字符不为“字母”，则 意味着这个转换图不工作。 12 字母或数字 0 *其他字母 18 状态转换图识别字符串: 例2 n例2 是识别整数的转换图。其中0为初态，2 为终态, 打了*号。 n识别的过程类似前例。 1 2 数字 0 * 其他 数字 19 例3 是一个识别 FORTRAN实型常数的 转换图。其中0为初态 ，7为终态。 状态转换图识别字符串: 例3 该转换图可以识别下面 形式的一些实数: 123. , .123, 123E3 ,123.456 .123E+10, 123.456E-3 等 5 其他 数字 6 17 数字 0 * 234 其他 E或D . E或D+或-数字 数字 . 数字数字数字 某简单语言的单词符号编码 单词符号种别编码内部值助记符 DIM1$DIM IF2$IF DO3$DO STOP4$STOP END5$END 标识符6内部符号串$IDN 整数7标准二进制$ INT =8$ASG +9$PLUS *10$STAR *11$POWER ，12$COMMA （13$SLP ）14$SRP 状态图状态图 letter,digit letter （IDN，入口） digit digit (其它) (其它)（NUM，值） （ASG，_） = * （STAR，_） s s * （POWER，_ ） 其它 IDNIDNletter(letter|digit)* NUMNUMdigit(digit)* ASGASG= POWERPOWER*STARSTAR* 空白 21 22 3.3 正规表达式与有限自动机 n为了更好地使用状态转换图构造词法分 析器，为了讨论词法分析器的自动生成 ，还需要将转换图的概念形式化。 n本节主要讨论词法分析器自动产生所需 要的工具, 引入：正规式，正规集，有 限自动机等概念。 n本节是本章的重点和难点。 23 3.3.1 正规式与正规集 n对于字母表，有符号串集合*和+, 我们感兴 趣的是它的一些特殊的子集，即所谓正规集。 n使用正规式这个概念来描述正规集。 n例如, =a,b,c,z,0,1,2,9 * =所有字母数字串 我们对如下子集感兴趣 : 字母开头的字母数字串 = 标识符集合 正规式表示: L(L|D)* 一个正规集 即一个正规语言 24 正规式与正规集的递归定义 n(1) 和都是 上的正规式，它们所表示的正规集分 别为 和； n(2) 任何a, a是上的一个正规式，它所表示的正 规集为a； n(3) 假定U和V都是上的正规式,它们所表示的正规 集分别记为L(U)和L(V),那么,U|V、UV和U*也都是 正规式,它们所表示的正规集分别为L(U)L(V)、 L(U)L(V)(连接积)和(L(U)*(闭包) n仅由有限次使用上述三步骤而得到的表达式才是 上的正规式。仅由这些正规式所表示的字集才是 上的正规集，正规集也称为正规语言。 25 正规式定义 正规表达式 正规表达式对应的正规集 1. ， ， 2. a a 3. 若 r, s L( r ) , L(s) 则 选择 rs L( r ) L(s) 连接 r s L( r ) L(s) 闭包 r * ( L( r )* ( r ) L( r ) n运算优先级由高到低依次是: 闭包*、连接、选择|， 括号最优先。注：有的书还引入了正则闭包，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 n例2: 设 =a,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 n通过这一节的学习，要求能根据给出的简单 正规式，会写出其表示的正规集。 n例3.1 令=a,b,其正规式和正规集如下： 正规式 正规集 1. ba* 上所有以b为首后跟着 任意多个a的字。 2. a(a|b)* 上所有以a为首的字。 3. (a|b)*(aa|bb)(a|b)* 上所有含有两 个相继的a或两个相继的b 的字。 29 正规式与正规集: 例3.2 n例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 正规式的等价 n若两个正规式U和V所表示的正规集相同，即 L(U) =L(V) ，则认为二者等价，记为U=V 。 n例1 ：b(ab)*=(ba)*b 因为: b(ab)*和 (ba)*b表示的正规集分别是: bab* ba*b = b,ab,abab, =,ba,baba,b = b,bab,babab, =b,bab,babab, n例2 ：00*=0*00*0* 正规集为 0n |n1 n例3 : (a|b)*=(a*b*)* 正规集为 ,a,b,aa,ab,ba,bb,aaa, 31 正规表达式的代数性质 n注: 上述恒等式都表示两个正规式等价。 n证明两个正规式等价: U=V L(U)=L(V) 恒等式说明 r|s=s|r“|”是可交换的 (r|s)|t=r|(s|t)“|”是可结合的 (rs)t=r(st)连接是可结合的 r(s|t)=rs|rt , (s|t) r=sr|tr分配律 r=r, r=r 是连接的单位元素 r*=(r|)*“*”和之间的关系 r*=r*“*”是幂等的 32 正规式等价的证明 n例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(V