编译原理第二章词法分析.ppt

2020 3 18 编译原理 1 第二章词法分析 主要内容 词法分析过程涉及的几个问题模式的形式化描述 正规式与正规集记号的识别 有限自动机从正规式到词法分析器词法分析器生成器简介 2020 3 18 编译原理 2 一 词法分析过程涉及的几个问题 词法分析是编译过程中的第一个阶段 执行词法分析的程序称为词法分析程序 也称为词法分析器或扫描器 任务是 从左至右逐个字符地对源程序进行扫描 产生一个个单词符号 把字符串形式的源程序改造成为单词符号串形式的中间程序 功能是输入源程序 输出单词符号 并检查词法错误 2020 3 18 编译原理 3 词法分析器作为主程序 词法分析器作为子程序 并行工作方式 1 词法分析器的三种工作方式 2020 3 18 编译原理 4 图2 1作为子程序的词法分析器 图2 2词法分析器进行单独一遍扫描 2020 3 18 编译原理 5 图2 3并行工作模式 2020 3 18 编译原理 6 2 单词符号的分类 单词符号分类 词法分析程序简单地说就是读单词程序 该程描用高级语言编写的源程序 将源程序中由单词符号组成的字符串分解出一个个单词来 因此 单词符号是程序语言的基本语法单位 具有确定的语法意义 程序语言的单词符号通常可分为下面五种 2020 3 18 编译原理 7 1 保留字 也称基本字 如C语言中的if else while和do等 这些字保留了语言所规定的含义 是编译程序识别各类语法成分的依据 几乎所有程序语言都限制用户使用保留字来作为标识符 2 标识符 用来标记常量 数组 类型 变量 过程或函数名等 通常由用户自己定义 3 常数 包括各种类型的常数 如整型常数386 实型常数0 618 布尔型常数TRUE等 4 运算符 如 等 5 界符 在语言中是作为语法上的分界符号使用的 如 等 2020 3 18 编译原理 8 注意 一个程序语言的保留字 运算符和界符的个数是确定的 而标识符或常数的使用则不限定个数 将产生和识别单词的规则称为模式 patten 按照某个模式 规则 识别出的元素称为记号 token 单词 lexeme 一词是指被识别出元素自身的值 2020 3 18 编译原理 9 词法分析程序的输入是源程序字符串 而输出是与源程序等价的单词符号序列 并且所输出的单词符号通常表示成如下的二元式 单词种别 单词自身的值 词法分析器输出单词的形式 3 词法分析器输出单词的形式 2020 3 18 编译原理 10 1 单词种别 单词种别表示单词的种类 它是语法分析所需要的信息 一个语言的单词符号如何划分种类 分为几类 如何编码都属于技术性问题 主要取决于处理上的方便 通常让每种单词对应一个整数码 这样可最大限度地把各个单词区别开来 对于保留字 可将其全体视为一种 也可一字一种 采用一字一种的分类方法处理起来比较方便 标识符一般统归为一种 常数可统归为一种 也可按整型 实型 布尔型等分为几种 运算符和界符可采用一符一种的分法 也可统归为一种 2020 3 18 编译原理 11 2 单词自身的值 单词自身的值是编译中其它阶段所需要的信息 对于单词符号来说 如果一个种别只含有一个单词符号 那么对于这个单词符号 其种别编码就完全代表了它自身的值 如果一个种别含有多个单词符号 那么对于它的每个单词符号 除了给出种别编码之外还应给出单词符号自身的值 以便把同一种类的单词区别开来 注意 标识符自身的值就是标识符自身的字符串 而常数自身的值是常数本身的二进制数值 此外 我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词 例如 对于标识符 可以用它在符号表的入口指针作为它自身的值 而常数也可用它在常数表的入口指针作为它自身的值 2020 3 18 编译原理 12 二 模式的形式化描述 正规式与正规集 1 字符串与语言从词法分析的角度看 程序设计语言是由记号组成的集合 每个记号又是由若干字母按照一定规则组成的字符串 2020 3 18 编译原理 13 定义2 1语言L是有限字母表 上有限长度字符串的集合 定义2 1明确指出 语言是一个集合 集合中的元素是字符串 并且强调了两个有限 字母表是有限的 即字母表中元素是有限多个 字符串的长度是有限的 即字符串中字符个数是有限多个 这是由于计算机所能表示的字符个数和字符串的长度都是有限的 2020 3 18 编译原理 14 字符串的基本概念 2020 3 18 编译原理 15 字符串集合上的基本运算 2020 3 18 编译原理 16 2 正规式与正规集 定义2 2令 是一个有限字母表 则 上的正规式及其表示的集合递归定义如下 是正规式 它表示集合L 若a是 上的字符 则a是正规式 它表示集合L a 若正规式r和s分别表示集合L r 和L s 则 a r s是正规式 表示集合L r L s b rs是正规式 表示集合L r L s c r 是正规式 表示集合 L r d r 是正规式 表示的集合仍然是L r 可用正规式描述的语言称为正规语言或正规集 2020 3 18 编译原理 17 定义2 2中 和 规定了正规式的基本操作数或基本正规式 定义2 2的 给出了正规式上的三种运算 a 或运算 b 连接运算和 c 闭包运算 对于由多个操作数和多个操作符组成的正规式 可以利用 d 所给的括号规定运算的先后次序 如果对或 连接和闭包运算进行如下约定 三种运算均具有左结合性质 运算的优先级从高到低顺序排列为 闭包运算 连接运算 或运算 则正规式中不必要的括号可以被省略 例如 a b c 可以简化成a b c 2020 3 18 编译原理 18 正规集是一个集合 而正规式是表示正规集的一种方法 不同正规式也可以表示同一个正规集 即正规式与正规集之间是多对一的关系 定义2 3若正规式P和Q表示了同一个正规集 则称P和Q是等价的 记为P Q 正规式之间的一些恒等运算 被称为正规式的代数性质 表2 6给出了正规式的若干代数性质 利用这些性质 可以对复杂的正规式进行化简 使得可以用最简单形式的正规式表示一个集合 而简单的正规式意味着其所对应的识别器的构造也是简单的 2020 3 18 编译原理 19 正规式的代数性质 2020 3 18 编译原理 20 3 记号的说明 用自然语言对模式进行了非形式化的描述 例如标识符模式的非形式化描述是 以字母打头的字母数字串 这一描述很不精确 存在一些问题 如哪些符号是字母 哪些符号是数字 字母数字串的长度可以是多少等等 正规式是严格的数学表达式 采用正规式来描述模式 解决了精确描述模式的问题 另外 从词法分析器的角度上看程序设计语言 用正规式说明的记号是一个正规集 用正规式说明记号的公式为 记号 正规式 可以读作为 左边 记号定义为 右边 正规式 或者 记号是正规式 通常 在不引起混淆的情况下 也把说明记号的公式简称为正规式 或者规则 2020 3 18 编译原理 21 例2 5表2 1中的记号relation id和num分别是Pascal的关系运算符 标识符和无符号数 它们的正规式表示如下所示 relation id a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 2020 3 18 编译原理 22 num 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 E 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 上述正规式给出了标识符的精确定义 用自然语言可以描述为 字母是英文26个字母大小写中任何一个 数字是十进制阿拉伯数字中的任何一个 标识符是以字母打头的 其后可跟随0个或若干个字母或数字的字符串 2020 3 18 编译原理 23 a 简化正规式描述为了简化正规式的描述 通常可以采用如下的几种正规式的缩写形式 1 正闭包 若r是表示L r 的正规式 则r 是表示 L r 的正规式 且下述等式成立 r rr r r r r 与 具有相同的运算优先级和结合性 2 可缺省 若r是正规式 则 r 是表示L r 的正规式 且下述等式成立 r r 2020 3 18 编译原理 24 3 字符组 字符组是或关系的缩写形式 它把所有存在或关系的字符集中在 里面 其中的字符可以有如下两种书写方式 枚举方式 如 abc 它等价于a b c分段方式 如 0 9a z 它等价于 0123456789abcdefghijklmnopqrstuvwxyz 2020 3 18 编译原理 25 4 非字符组 若 r 是一个字符组形式的正规式 则 r 是表示 L r 的正规式 例如 若 则L abc d e f g 5 串 若r是字符连接运算的正规式 则串 r 与r等价 即r r 特别地 a a 引入串的表示可以避免与正规式中运算符的冲突 例如 a b a b a b 2020 3 18 编译原理 26 b 引入辅助定义式引入辅助定义式的主要目的是为较复杂 但需要重复书写的正规式命名 并在定义式之后的引用中 用名字代替相应的正规式 所以 辅助定义式实质上仍然是正规式 唯一的区别是正规式与外部模式匹配 而辅助定义式不与任何模式匹配 2020 3 18 编译原理 27 例2 6引入正规式的缩写形式和辅助定义式后 id和num的正规式可重写如下 char a zA Z digit 0 9 digits digit optional fraction digits optional exponent E digits id char char digit num digitsoptional fractionoptional exponent 2020 3 18 编译原理 28 词法错误校正 词法错误种类 语言不允许的符号 括号类配对错误 单词的后继符错 偶尔 词法错误校正 a删除已被读过的字符 并重新扫描未被读过的字符b删除已读过的第一个字符 重新扫描它的后继部分的字符 校正后的标示