《编译原理-词法分析》由会员分享，可在线阅读，更多相关《编译原理-词法分析（33页珍藏版）》请在金锄头文库上搜索。
1、1本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2词法分析n任务：从左到右一个字符一个字符地读入源程 序，对构成源程序的字符流进行扫描和分解， 从而识别出一个个单词符号。逻辑上紧密相连的一组字符， 这些字符具有集体含义。n单词：标识符，保留字，常数，算符，界符n词法分析阶段的工作所依循的是语言的词法规 则。描述词法规则的有效工具是正规式和有限 自动机。33.1 对词法分析器的要求3.1.1 词法分析器的功能和输出形式n输入源程序，扫描识别, 输出单词符号n程序语言的单词符号一般分为五种：n关键字
2、(保留字或基本字)：如 begin,end,if,then,else,while,do等 n标识符：用来表示各种名字，如 X1n字面常数：如 256，3.14，true,abcn运算符：如 、*、/ 等等n分界符：如 逗号，分号，冒号等4n单词符号的内部表示是二元式：(词类种别编码, 单词符号自身的属性值)n1. 词类种别编码提供给语法分析程序 使用；n2.单词自身的属性值提供给语义分析 程序使用。n3. 具体的分类设计方法以方便语法分 析程序使用为原则。单词符号的内部表示5例子n考虑下述C语言代码段： while (i=j) i- - ;经词法分析器处理后，它将转换为如下的单 词符号序列：=
3、 , - 100 i地址类型名字符号表10如标识符单词 i 对 应的二元组(6, 10)63.1.2 词法分析器作为独立子程序n把词法分析设计成一个独立程序，每当语法分 析器需要一个单词符号时就调用这个子程序。n每一次调用，词法分析器从源程序字符串中识 别出一个单词符号，并把它的内部表示二元组 交给语法分析器处理。如图所示：词法分 析器语法分析器语义分析和 中间代码生成器源程序中间代码7输入、预处理：词法分析第一步扫描缓冲区预处理程序预处理扫描识别输入缓冲区内存源程序 文本外存读入词法分析程序扫描识别预处理用于删除空白符、回车符、换行符及注释等。2）相关问题n词法分析器可以作为一个独立的子程序
4、， 也可以作为一遍独立的扫描来安排。n扫描缓冲区 双缓冲区 搜索 起点 指示器 指示器 起点 搜索 指示器 指示器89关键字的识别(1)、超前搜索n像FORTRAN这样的语言，关键字的识 别甚为麻烦。因为n1. 关键字不加保护（只要不引起矛盾，用 户可以用它们作为普通标识符）。n2. 关键字和用户自定义的标识符或标号之 间没有特殊的界符作间隔。10关键字的识别(2)n下面是几个FORTRAN的正确语句，空白可有 可无，不作分隔符：1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.14 IF(5)=55n语句1和2分别是DO和IF语句，它们都是以某 关键字开头的。n
5、语句3和4是赋值语句，它们都是以用户自定 义的标识符开头的。11标识符、常数的识别n标识符的识别 n是字母开头的字母数字串，后跟算符或界 符，识别不困难，例如 DO99K=1.10n常数的识别n算术常数的识别: 多数语言很直接，有的须 采用超前搜索，如FORTRAN语言中：IF(5.EQ.M)GOTO55 - 5.E08n逻辑(布尔)常数的识别: 比较容易nFORTRAN文字常数的识别: 麻烦, 须作特 殊处理12算符、界符的识别n算符的识别n单个字符构成的算符的识别较容易如 i+jn多个字符构成的算符的识别须使用超前搜 索如 i+界符的识别 n界符的识别比较简单133.2.3 状态转换图n状
6、态转换图用来：n描述单词符号的结构n识别单词符号串n是设计词法分析器的工具n手工生成词法分析器的方法: 转换 实现词法分析程序构造识别单词符号的状态转换图14状态转换图n状态转换图是一张有限方向图，只包含有限 个状态，即有限个结点。n1. 结点代表状态，用圆圈表示n2. 终止状态用双圈表示n3. 初始状态前标记符号“ ”来表示n4. 状态之间用箭弧连结n5. 箭弧上的标记代表在射出结点即箭弧始 结点状态下可能出现的输入字符或字符类 ，箭弧标记表示状态转换的条件。231 YX15状态转换图：例n在状态1下，若输入字符为 X，则读进X，并转换到状 态2。n若输入字符为y，则读进y， 并转换到状态3
7、。n若输入字符非x和非y，则此 转换图不工作。231 YX 一个状态转换图可用于识别一定的字符串16状态转换图识别字符串：例1n识别标识符的状态转换图。其中0为初态，2为 终态。n这个转换图识别标识符的过程是: 从初态0开 始，若在状态0下输入字符是字母，则读进它 ，并转入状态1。在状态1之下，若输入字符为 字母或数字，则读进它，并重新进入状态1。 一直重复这个过程直到发现输入字符不再是字 母或数字时(这个字符已经被读进)就进入状态 2。12字母或数字0*其他字母17状态转换图识别字符串: 例n识别标识符的状态转换图。其中0为初态，2为 终态。n状态2是终态，它意味着到此已经识别出一个 标识符
8、。终态上打个*号，表示多读进了一个 不属于标识符部分的字符，应把它退还给输入 串。如果在状态0时输入字符不为“字母”，则 意味着这个转换图不工作。12字母或数字0*其他字母18状态转换图识别字符串: 例2n例2 是识别整数的转换图。其中0为初态，2 为终态, 打了*号。n识别的过程类似前例。12数字0*其他数字19例3 是一个识别 FORTRAN实型常数的 转换图。其中0为初态 ，7为终态。状态转换图识别字符串: 例3 该转换图可以识别下面 形式的一些实数:123. , .123, 123E3 ,123.456 .123E+10, 123.456E-3 等5其他数字617数字0*234其他E或
9、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,digitletter （IDN，入口）digitdigit(其它) (其它)（NUM，值）（ASG，_） =*（STAR，_）s s*（POWER，_ ）其它IDNIDNletter(letter|digit)*NUMN
10、UMdigit(digit)*ASGASG=POWERPOWER*STARSTAR*空白21223.3 正规表达式与有限自动机n为了更好地使用状态转换图构造词法分 析器，为了讨论词法分析器的自动生成 ，还需要将转换图的概念形式化。n本节主要讨论词法分析器自动产生所需 要的工具, 引入：正规式，正规集，有 限自动机等概念。n本节是本章的重点和难点。233.3.1 正规式与正规集n对于字母表，有符号串集合*和+, 我们感兴 趣的是它的一些特殊的子集，即所谓正规集。n使用正规式这个概念来描述正规集。n例如, =a,b,c,z,0,1,2,9* =所有字母数字串我们对如下子集感兴趣 :字母开头的字母数
11、字串 = 标识符集合正规式表示: 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正规式定义正规表达式 正规表
12、达式对应的正规集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) = 0123
13、456789 若 L A,B,Z,a,b,z, D 0,1,9正规式：L(L|D)* 正规集： 标识符27正规式与正规集: 例2n例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.1n通过这一节的学习，要求能根据给出的简单 正规式，会写出其表示的正规集。n例3.1 令=a
14、,b,其正规式和正规集如下：正规式 正规集1. ba* 上所有以b为首后跟着任意多个a的字。2. a(a|b)* 上所有以a为首的字。3. (a|b)*(aa|bb)(a|b)* 上所有含有两个相继的a或两个相继的b 的字。29正规式与正规集: 例3.2n例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) ，则认
