编译原理 第五章 词法分析

第五章词法分析 词法分析的主要任务是对源程序进行扫描 从中识别出单词 它是编译过程的第一步 也是编译过程中不可缺少的部分 5 1词法分析概述 从左至右逐个字符地扫描源程序形式的字符流 将这些单个字符组合成一个个单词符号 把作为字符串的源程序转换成由单词符号串组成的中间语言程序供语法分析使用 因此 词法分析是编译程序的基础 一 词法分析的任务 1 词法分析器作为独立的一遍词法分析器可以单独作为一遍来实现 词法分析器是主程序 它输入的是用高级语言编写的源程序 输出的是由单词组成的与源程序等价的中间程序 并作为语法分析器的输入 2 词法分析器作为语法分析器的子程序有的编译程序将词法分析和语法分析安排在同一遍中 词法分析器作为语法分析器的一个子程序 每当语法分析器需要读入一个新的单词时 就调用词法反系器子程序 没调用一次 词法分析器就从源程序字符串中识别出一个具有独立意义的单词 并返回给语法分析器 直到分析结束 3 词法分析器和语法分析器作为协同程序如果两个或两个以上的程序 他们之间交叉执行 这些程序称为协同程序 词法分析器和语法分析器也可协工作的方式安排在同一遍中 以生产者和消费者的关系同步运行 二 词法分析器与语法分析器的关系 1 词法分析单独作为一遍 2 词法分析程序作为单独的子程序 S P 字符串 词法分析 S P 符号串 语法分析 第一遍 第二遍 单词串 优点 结构清晰 各遍功能单一缺点 效率低 三 分离词法分析的好处 可以简化设计 可以改进编译器的效率 可以加强编译器的可移植性 一 源程序的输入源程序的输入是词法分析器的一部分 用不同方法实现的词法分析器 其源程序的输入方法也不同 一般来讲 实现实现一个词法分析器有以下三种方法 1 利用词法分析器生成器 此时生成器将提供用于源程序字符流的读入和缓冲的若干子程序 2 利用传统的系统程序设计语言来编写词法分析器 此时要利用该语言所具有的输入 输出能力来处理读入操作 3 利用汇编语言来编写词法分析器 此时要直接管理源程序字符流的读入 二 源程序的预处理预处理工作包括 剔除无用的空白符 跳格 回车和换行等编辑性字符 将源程序的列表打印也放在预处理中进行 5 2词法分析器的输入和输出 词法分析器的结构 预处理子程序 扫描器 输入缓冲区 扫描缓冲区 单词符号 输入 列表 三 设置缓冲器的必要性之所以要设置缓冲器 是因为对于许多源程序而言 有时词法分析器为了得到某个单词符号的确切性质 只从该符号本身所含有的字符不能作出判定 还需要超前扫描若干字符之后 才能作出确切的分析 例如 有合法的Fortran语句 DO99K 1 10和DO99K 1 10前者是循环语句 后者是赋值语句 两者的区别在于等号后的第一个界符不同 前者是逗号 后者是句号 因此为了识别前者中的关键字 DO 必须超前扫描若干字符之后 才能作出确切的判定 四 配对缓冲器词法分析器对输入缓冲区进行扫描时 一般用两个指示器 分别是 起点指示器和搜索指示器 起点指示器用于指向当前正在识别的单词的开始位置 搜索指示器向前搜索 以寻找单词的终点 开始时 两个指示器都指向下一个要取的单词符号的第一个字符 搜索指示器向前扫描 直到把要取的符号确定为止 一旦符号被确定 搜索指示器置于该符号的右端 在此符号处理完后 让两个指示器都指向下一个字符 将程序输入到缓冲区中 不论输入的缓冲区定义得多大 都不能保证单词符号不会被它的边界所打断 所以把缓冲器分为两半 称之为配对缓冲区 若假定每半区可放80个字符 而这两个半区又是互补使用的 即每次输入都是80个字符 五 词法分析的输出词法分析器输出的是与源程序等价的单词序列 作为词法分析器的输出单词序列 可以有不同的具体内部表示形式 只有不同的单词有唯一的表示 能彼此区分开即可 通常一个单词采用以下二元式表示 单词类别 单词的属性 1 单词的类别关键字 运算符 界符 标识符 常数2 单词的属性单词的属性是用来区分该类单词中的哪一个单词 它是单词本身的机内编码 六 单词的描述与识别1 单词的描述正则表达式与正则文法都是用来描述程序设计语言的单词符号的 两者具有同样的表达能力 2 单词的识别利用状态转换图来识别单词 当词法分析在识别单词时 为了进一步判明情况 以确定下一步要作什么 常采用一种超前搜索的技术 所谓超前搜索 就是向前读取字符 并判别该字符是什么 当情况判明之后 再回来处理已读过的字符 例 识别标识符的状态转换图如下左图所示 其中0为初态 2为终态 它识别标识符的过程为 从初态0开始 若输入符号识一字母 则读进它 并转到状态1 在状态1下 若下一个输入符号是字母或数字则读进它 并重新进入状态1 重复这个过程 直至在状态1下发现读入的符号不再是字母或数字时 注意 此时该字符已被读出 就进入状态2 状态2是终态 它意指至此已识别出一个标识符 识别过程终止 若在状态0下输入符号不是字母 则意味着识别不出所给的输入串是一个标识符 七 词法分析器的实现及TINY扫描程序的实现 5 3词法分析器的自动生成 Lex工具是一种词法分析程序生成器 它可以根据词法规则说明书的要求来生成单词识别程序 由该程序识别出输入文本中的各个单词 Lex的流程如下图所示 一 LEX正则式约定 元字符表 二 lex源程序的结构 lex输入文件的格式 说明部分 定义部分 识别规则部分 辅助程序部分 用户子程序部分 其中规则部分是必须的 定义和辅助程序部分是任选的 如果没有辅助程序部分 则第二个分隔号 双百分号 可以省去 但由于第一个 用来指示规则部分的开始 故即使没有说明部分 也不能将其省去 1 说明部分它是C和Lex的全局声明 它的作用 在于对规则部分要引用的文件和变量进行说明 通常可包含头文件 常数定义 全局变量定义 正则式定义等 每一个正则式定义由分隔符 适当个数的空格或制表符 连接的正则式的名字和正则式表达式组成 即 DiRi其中 Di表示正则式的名字 Ri表示正则表达式 除正则式定义以外 定义部分的其余代码须用符号 和 括起来 其间可以是包括include语句 声明语句在内的C语句 例如 intwordCount 0 intnoCount 0 chars A za z numbers 0 9 words chars 注意 凡是对已经定义的正则表达式的名字的引用 都必须用花括号将它们括起来 在LEX源程序中 起标识作用的符号 以及 都必须处在所在行的最左字符位置 2 识别规则部分识别规则部分起始于 符号 终止于 符号 其间则是词法规则 词法规则由词形和动作两部分组成 即 Pi ACTIONi Pi词形部分可以由任意的正则表达式组成 ACTIONi动作部分是由C语言语句组成 这些语句用来对所匹配的词形进行相应处理 规则部分完全决定了词法分析程序的功能 它只能识别出词形中正则表达式所定义的单词 例如 words wordCount increasethewordcount numbers noCount increasethenumbercount n 3 辅助程序部分这部分包含了识别规则部分的动作代码段中所调用的各个局部函数 着写函数由用户用C语言编写的 这样就可以达到简化编程的目的 它们将由LEX系统直接拷贝到输出文件lex yy c中 例如 main yylex starttheanalysis printf Countofwords d n wordCount printf Countofnombers d n noCount LEX的变量和子程序 综合上述几个例子 我们可以编一个字 由字母组成的 和数字 由数字组成 的个数统计的词法分析器了 LEX输入源程序 intwordCount 0 noCount 0 chars A za z numbers 0 9 words chars words wordCount increasethewordcount numbers noCount increasethenumbercount n donothing donothing main yylex starttheanalysis printf Noofwords d n w