编译原理_第二章词法分析(1)

1、编译原理_第二章 词法分析(1) 编译原理_其次章 词法分析(1) 其次章 词法分析 其次章 词法分析 主要内容: 主要内容: 词法分析过程涉及的几个问题 模式的形式化描述模式的形式化描述-正规式与正规集 记号的识别记号的识别-有限自动机 从正规式到词法分析器 词法分析器生成器简介 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 一,词法分析过程涉及的几个问题词法分析是编译过程中的第一个阶段. 词法分析是编译过程中的第一个阶段. 执行词法分析的程序称为词法分析程序, 执行词法分析的程序称为词法分析程序,也称 为词法分析器或扫描器. 为词法分析器或扫描器. 任务

2、是 任务是:从左至右逐个字符地对源程序进行扫 产生一个个单词符号, 描,产生一个个单词符号,把字符串形式的源 程序改造成为单词符号串形式的中间程序. 程序改造成为单词符号串形式的中间程序. 功能是输入源程序 输出单词符号, 是输入源程序, 功能是输入源程序,输出单词符号,并检查词 法错误. 法错误.2021-7-22 编译原理 2 编译原理_其次章 词法分析(1) 其次章 词法分析 1,词法分析器的三种工作方式: ,词法分析器的三种工作方式: 词法分析器作为主程序; 词法分析器作为主程序; 词法分析器作为子程序; 词法分析器作为子程序; 并行工作方式 2021-7-22 编译原理 编译原理_其

3、次章 词法分析(1) 其次章 词法分析 图2.1 作为子程序的词法分析器 图2.2 词法分析器进行单独一遍扫描 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 图2.3 并行工作模式 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 2,单词符号的分类 , 单词符号分类: 词法分析程序简洁地说就是读单词程序,该程 描用高级语言编写的源程序,将源程序中由单 词符号组成的字符串分解出一个个单词来.因 此,单词符号是程序语言的基本语法单位 基本语法单位,具 基本语法单位 有确定的语法意义. 程序语言的单词符号通常可分为下面五种: 20

4、21-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 (1) 保留字 也称基本字 :如c语言中的if,else,while 保留字(也称基本字 也称基本字): 和do等,这些字保留了语言所规定的含义,是编译程 序识别各类语法成分的依据.几乎全部程序语言都限 制用户使用保留字来作为标识符. (2) 标识符:用来标记常量,数组,类型,变量,过程 标识符: 或函数名等,通常由用户自己定义. (3) 常数:包括各种类型的常数,如整型常数386,实 常数: 型常数0.618,布尔型常数true等. (4) 运算符:如+,?,*,/, 运算符: 等. (5) 界符:在语言中是作为语

5、法上的分界符号使用的, 界符: 如,;,(,)等. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 留意:一个程序语言的保留字,运算符和 保留字, 保留字 界符的个数是确定的,而标识符或常数 界符 的使用则不限定个数. 将产生和识别单词的规章 称为模式 模式 (patten). 根据某个模式(规章)识别出的元素称为记 记 号(token). 单词(lexeme)一词是指被识别出元素自 身的值.2021-7-22 编译原理 8 编译原理_其次章 词法分析(1) 其次章 词法分析 3,词法分析器输出单词的形式 , 词法分析程序的输入是源程序字符串, 而输出是与源程

6、序等价的单词符号序列, 词法分析器输出单词的形式 并且所输出的单词符号通常表示成如下 的二元式: 单词种别,单词自身的值) (单词种别,单词自身的值) 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 (1) 单词种别. 单词种别. 单词种别表示单词的种类,它是语法分析所需要的信息. 单词种别表示单词的种类,它是语法分析所需要的信息. 一个语言的单词符号如何划分种类,分为几类, 一个语言的单词符号如何划分种类,分为几类,如何编码都属于技术性 问题,主要取决于处理上的便利. 问题,主要取决于处理上的便利. 通常让每种单词对应一个整数码, 通常让每种单词对应一个整数

7、码,这样可最大限度地把各个单词区分开 来. 对于保留字,可将其全体视为一种,也可一字一种, 对于保留字,可将其全体视为一种,也可一字一种,采纳一字一种的分 类方法处理起来比较便利; 类方法处理起来比较便利; 标识符一般统归为一种; 标识符一般统归为一种; 常数可统归为一种,也可按整型,实型,布尔型等分为几种; 常数可统归为一种,也可按整型,实型,布尔型等分为几种; 运算符和界符可采纳一符一种的分法,也可统归为一种. 运算符和界符可采纳一符一种的分法,也可统归为一种. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 (2) 单词自身的值. 单词自身的值. 单词自

8、身的值是编译中其它阶段所需要的信息. 单词自身的值是编译中其它阶段所需要的信息. 对于单词符号来说: 对于单词符号来说: 假如一个种别只含有一个单词符号,那么对于这个单词符号, 假如一个种别只含有一个单词符号,那么对于这个单词符号,其 种别编码就完全代表了它自身的值. 种别编码就完全代表了它自身的值. 假如一个种别含有多个单词符号,那么对于它的每个单词符号, 假如一个种别含有多个单词符号,那么对于它的每个单词符号, 除了给出种别编码之外还应给出单词符号自身的值, 除了给出种别编码之外还应给出单词符号自身的值,以便把同一 种类的单词区分开来. 种类的单词区分开来. 留意:标识符自身的值就是标识符

9、自身的字符串, 留意:标识符自身的值就是标识符自身的字符串,而常数自身的 值是常数本身的二进制数值.此外, 值是常数本身的二进制数值.此外,我们也可用指向某类表格中 一个特定项目的指针来区分同类中的不同单词. 一个特定项目的指针来区分同类中的不同单词. 例如,对于标识符, 例如,对于标识符,可以用它在符号表的入口指针作为它自身的 而常数也可用它在常数表的入口指针作为它自身的值. 值;而常数也可用它在常数表的入口指针作为它自身的值. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 二,模式的形式化描述-正规式与正规集 模式的形式化描述- 1,字符串与语言 , 从

10、词法分析的角度看,程序设计语言 是由记号组成的集合,每个记号又是由 若干字母根据肯定规章组成的字符串. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 定义2.1 语言 是有限字母表 上有限长度字 语言l是有限字母表 是有限字母表上有限长度字 定义 符串的集合. 符串的集合. 定义2.1明确指出,语言是一个集合,集 明确指出, 定义 明确指出 语言是一个集合, 合中的元素是字符串,并且强调了两个有限: 合中的元素是字符串,并且强调了两个有限 字母表是有限的, 字母表是有限的,即字母表中元素是 有限多个; 有限多个; 字符串的长度是有限的, 字符串的长度是有限的

11、,即字符串中 字符个数是有限多个. 字符个数是有限多个. 这是由于计算机所能表示的字符个数和 字符串的长度都是有限的. 字符串的长度都是有限的. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 字符串的基本概念: 字符串的基本概念: 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 字符串集合上的基本运算 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 2,正规式与正规集 正规式与正规集定义2.2 令是一个有限字母表,则上的正规式及其 是一个有限字母表, 定义 是一个有限字母表 上的正规式及其

12、表示的集合递归定义如下: 表示的集合递归定义如下 是正规式, 是正规式,它表示集合 是正规式 它表示集合l()=; ; 上的字符, 是正规式, 若a是上的字符,则a是正规式,它表示集合 是 上的字符 是正规式 l(a)=; ; 若正规式r和 分别表示集合 分别表示集合l(r)和l(s),则 若正规式 和s分别表示集合 和 , (a) r|s是正规式,表示集合 是正规式, 是正规式 表示集合l(r)l(s); ; (b) rs是正规式,表示集合 是正规式, 是正规式 表示集合l(r)l(s); ; (c) r*是正规式,表示集合 是正规式, 是正规式 表示集合(l(r)*; ; (d) (r)是

13、正规式,表示的集合仍旧是 是正规式, 是正规式 表示的集合仍旧是l(r). . 可用正规式描述的语言称为正规语言或正规集. 可用正规式描述的语言称为正规语言或正规集. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 定义2.2中和规定了正规式的基本操作数或基本正规 中 定义 式. 定义2.2的给出了正规式上的三种运算 (a)或运算, 或运算, 定义 的 给出了正规式上的三种运算: 或运算 (b)连接运算和 闭包运算. 连接运算和(c)闭包运算 连接运算和 闭包运算. 对于由多个操作数和多个操作符组成的正规式, 对于由多个操作数和多个操作符组成的正规式,可以 利

14、用(d)所给的括号规定运算的先后次序. 所给的括号规定运算的先后次序. 利用 所给的括号规定运算的先后次序 假如对或,连接和闭包运算进行如下商定: 假如对或,连接和闭包运算进行如下商定 三种运算均具有左结合性质; 三种运算均具有左结合性质; 运算的优先级从高到低挨次排列为: 闭包运算, 运算的优先级从高到低挨次排列为 闭包运算, 连接运算,或运算. 连接运算,或运算. 则正规式中不必要的括号可以被省略.例如, 则正规式中不必要的括号可以被省略.例如, (a)|(b)*(c)可以简化成 可以简化成a|b*c. 可以简化成 . 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章

15、 词法分析 正规集是一个集合, 正规集是一个集合,而正规式是表示正规集的一种方 法. 不同正规式也可以表示同一个正规集, 不同正规式也可以表示同一个正规集,即正规式与正 规集之间是多对一的关系. 规集之间是多对一的关系. 定义2.3 若正规式 和q表示了同一个正规集,则称 若正规式p和 表示了同一个正规集 则称p 表示了同一个正规集, 定义 和q是等价的,记为p=q. 是等价的,记为 . 是等价的 正规式之间的一些恒等运算, 正规式之间的一些恒等运算,被称为正规式的代 数性质. 给出了正规式的若干代数性质. 数性质.表2.6给出了正规式的若干代数性质.利用这 给出了正规式的若干代数性质 些性质

16、,可以对简单的正规式进行化简, 些性质,可以对简单的正规式进行化简,使得可以用 最简洁形式的正规式表示一个集合. 最简洁形式的正规式表示一个集合.而简洁的正规式 意味着其所对应的识别器的构造也是简洁的. 意味着其所对应的识别器的构造也是简洁的. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 正规式的代数性质 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 3,记号的说明 记号的说明用自然语言对模式进行了非形式化的描述, 用自然语言对模式进行了非形式化的描述,例如标识符模式的非形 式化描述是以字母打头的字母数字串 这一描述很不

17、精确, 式化描述是以字母打头的字母数字串.这一描述很不精确,存在一 些问题,如哪些符号是字母,哪些符号是数字, 些问题,如哪些符号是字母,哪些符号是数字,字母数字串的长度可以 是多少等等. 是多少等等. 正规式是严格的数学表达式,采纳正规式来描述模式,解决了精确 正规式是严格的数学表达式,采纳正规式来描述模式, 描述模式的问题.另外,从词法分析器的角度上看程序设计语言, 描述模式的问题.另外,从词法分析器的角度上看程 序设计语言,用正 规式说明的记号是一个正规集. 规式说明的记号是一个正规集. 用正规式说明记号的公式为: 正规式,可以读作为 左边 左边) 用正规式说明记号的公式为:记号 = 正

18、规式,可以读作为(左边 记号定义为(右边 正规式 记号定义为 右边)正规式,或者记号是正规式.通常,在不引起 右边 正规式 或者记号是正规式 通常, 混淆的状况下,也把说明记号的公式简称为正规式,或者规章. 混淆的状况下,也把说明记号的公式简称为正规式,或者规章. 2021-7-22 编译原理 编译原理_其次章 词法分析(1) 其次章 词法分析 中的记号relation,id和num分别是 分别是pascal的关系运 例2.5 表2.1中的记号 中的记号 , 和 分别是 的关系运 算符,标识符和无符号数,它们的正规式表示如下所示: 算符,标识符和无符号数,它们的正规式表示如下所示: relation = |