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

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

第二章 词法分析

第二章

词法分析

主要内容: 主要内容: 词法分析过程涉及的几个问题 模式的形式化描述模式的形式化描述-正规式与正规集 记号的识别记号的识别-有限自动机 从正规式到词法分析器 词法分析器生成器简介

2010-7-22

编译原理

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

第二章 词法分析

一,词法分析过程涉及的几个问题词法分析是编译过程中的第一个阶段. 词法分析是编译过程中的第一个阶段. 执行词法分析的程序称为词法分析程序, 执行词法分析的程序称为词法分析程序,也称 为词法分析器或扫描器. 为词法分析器或扫描器. 任务是 任务是:从左至右逐个字符地对源程序进行扫 产生一个个单词符号, 描,产生一个个单词符号,把字符串形式的源 程序改造成为单词符号串形式的中间程序. 程序改造成为单词符号串形式的中间程序. 功能是输入源程序 输出单词符号, 是输入源程序, 功能是输入源程序,输出单词符号,并检查词 法错误. 法错误.2010-7-22 编译原理 2

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

第二章 词法分析

1,词法分析器的三种工作方式: ,词法分析器的三种工作方式:

词法分析器作为主程序; 词法分析器作为主程序; 词法分析器作为子程序; 词法分析器作为子程序; 并行工作方式

2010-7-22

编译原理

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

第二章 词法分析

图2.1 作为子程序的词法分析器

图2.2 词法分析器进行单独一遍扫描

2010-7-22

编译原理

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

第二章 词法分析

图2.3 并行工作模式

2010-7-22

编译原理

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

第二章 词法分析

2,单词符号的分类 ,

单词符号分类: 词法分析程序简单地说就是读单词程序,该程 描用高级语言编写的源程序,将源程序中由单 词符号组成的字符串分解出一个个单词来.因 此,单词符号是程序语言的基本语法单位 基本语法单位,具 基本语法单位 有确定的语法意义. 程序语言的单词符号通常可分为下面五种:

2010-7-22

编译原理

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

第二章 词法分析

(1) 保留字 也称基本字 :如C语言中的if,else,while 保留字(也称基本字 也称基本字): 和do等,这些字保留了语言所规定的含义,是编译程 序识别各类语法成分的依据.几乎所有程序语言都限 制用户使用保留字来作为标识符. (2) 标识符:用来标记常量,数组,类型,变量,过程 标识符: 或函数名等,通常由用户自己定义. (3) 常数:包括各种类型的常数,如整型常数386,实 常数: 型常数0.618,布尔型常数TRUE等. (4) 运算符:如"+","?","*","/",">", 运算符: "<"等. (5) 界符:在语言中是作为语法上的分界符号使用的, 界符: 如",",";","(",")"等.

2010-7-22

编译原理

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

第二章 词法分析

注意:一个程序语言的保留字,运算符和 保留字, 保留字 界符的个数是确定的,而标识符或常数 界符 的使用则不限定个数. 将产生和识别单词的规则

称为模式 模式 (patten). 按照某个模式(规则)识别出的元素称为记 记 号(token). 单词(lexeme)一词是指被识别出元素自 身的值.2010-7-22 编译原理 8

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

第二章 词法分析

3,词法分析器输出单词的形式 ,

词法分析程序的输入是源程序字符串, 而输出是与源程序等价的单词符号序列, 词法分析器输出单词的形式 并且所输出的单词符号通常表示成如下 的二元式: 单词种别,单词自身的值) (单词种别,单词自身的值)

2010-7-22

编译原理

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

第二章 词法分析

(1) 单词种别. 单词种别. 单词种别表示单词的种类,它是语法分析所需要的信息. 单词种别表示单词的种类,它是语法分析所需要的信息. 一个语言的单词符号如何划分种类,分为几类, 一个语言的单词符号如何划分种类,分为几类,如何编码都属于技术性 问题,主要取决于处理上的方便. 问题,主要取决于处理上的方便. 通常让每种单词对应一个整数码, 通常让每种单词对应一个整数码,这样可最大限度地把各个单词区别开 来. 对于保留字,可将其全体视为一种,也可一字一种, 对于保留字,可将其全体视为一种,也可一字一种,采用一字一种的分 类方法处理起来比较方便; 类方法处理起来比较方便; 标识符一般统归为一种; 标识符一般统归为一种; 常数可统归为一种,也可按整型,实型,布尔型等分为几种; 常数可统归为一种,也可按整型,实型,布尔型等分为几种; 运算符和界符可采用一符一种的分法,也可统归为一种. 运算符和界符可采用一符一种的分法,也可统归为一种.

2010-7-22

编译原理

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

第二章 词法分析

(2) 单词自身的值. 单词自身的值. 单词自身的值是编译中其它阶段所需要的信息. 单词自身的值是编译中其它阶段所需要的信息. 对于单词符号来说: 对于单词符号来说: 如果一个种别只含有一个单词符号,那么对于这个单词符号, 如果一个种别只含有一个单词符号,那么对于这个单词符号,其 种别编码就完全代表了它自身的值. 种别编码就完全代表了它自身的值. 如果一个种别含有多个单词符号,那么对于它的每个单词符号, 如果一个种别含有多个单词符号,那么对于它的每个单词符号, 除了给出种别编码之外还应给出单词符号自身的值, 除了给出种别编码之外还应给出单词符号自身的值,以便把同一 种类的单词区别开来. 种类的单词区别开来. 注意:标识符自身的值就是标识符自身的字符串, 注意:标识符自身的值就是标识符自身的字符串,而常数自身的 值是常数本身的二进制数值.此外, 值是常数本身的二进制数值.此外,我们也可用指向某类表格中 一个特定项目的指针来区分同类中的不同单词. 一个特定项目的指针来区分同类中的不同单词.

例如,对于标识符, 例如,对于标识符,可以用它在符号表的入口指针作为它自身的 而常数也可用它在常数表的入口指针作为它自身的值. 值;而常数也可用它在常数表的入口指针作为它自身的值.

2010-7-22

编译原理

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

第二章 词法分析

二,模式的形式化描述-正规式与正规集 模式的形式化描述-

1,字符串与语言 , 从词法分析的角度看,程序设计语言 是由记号组成的集合,每个记号又是由 若干字母按照一定规则组成的字符串.

2010-7-22

编译原理

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

第二章 词法分析

定义2.1 语言 是有限字母表 上有限长度字 语言L是有限字母表 是有限字母表∑上有限长度字 定义 符串的集合. 符串的集合. 定义2.1明确指出,语言是一个集合,集 明确指出, 定义 明确指出 语言是一个集合, 合中的元素是字符串,并且强调了两个有限: 合中的元素是字符串,并且强调了两个有限 字母表是有限的, ① 字母表是有限的,即字母表中元素是 有限多个; 有限多个; 字符串的长度是有限的, ② 字符串的长度是有限的,即字符串中 字符个数是有限多个. 字符个数是有限多个. 这是由于计算机所能表示的字符个数和 字符串的长度都是有限的. 字符串的长度都是有限的.

2010-7-22

编译原理

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

第二章 词法分析

字符串的基本概念: 字符串的基本概念:

2010-7-22

编译原理

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

第二章 词法分析

字符串集合上的基本运算

2010-7-22

编译原理

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

第二章 词法分析

2,正规式与正规集 正规式与正规集定义2.2 令∑是一个有限字母表,则∑上的正规式及其 是一个有限字母表, 定义 是一个有限字母表 上的正规式及其 表示的集合递归定义如下: 表示的集合递归定义如下 是正规式, ① ε是正规式,它表示集合 是正规式 它表示集合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)是正规式,表示的集合仍然是 是正规式, 是正规式 表示的集合仍然是L(r). . 可用正规式描述的语言称为正规语言或正规集. 可用正规式描述的语言称为正规语言或正规集.

2010-7-22

编译原理

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

第二章 词法分析

定义2.2中①和②规定了正规式的基本操作数或基本正规 中 定义 式. 定义2.2的③给出了正规式上的三种运算 (a)或运算, 或运算, 定义 的 给出了正规式上的三种运算: 或运算 (b)连接运算和 闭包运算.

连接运算和(c)闭包运算 连接运算和 闭包运算. 对于由多个操作数和多个操作符组成的正规式, 对于由多个操作数和多个操作符组成的正规式,可以 利用(d)所给的括号规定运算的先后次序. 所给的括号规定运算的先后次序. 利用 所给的括号规定运算的先后次序 如果对或,连接和闭包运算进行如下约定: 如果对或,连接和闭包运算进行如下约定 三种运算均具有左结合性质; ① 三种运算均具有左结合性质; 运算的优先级从高到低顺序排列为: 闭包运算, ② 运算的优先级从高到低顺序排列为 闭包运算, 连接运算,或运算. 连接运算,或运算. 则正规式中不必要的括号可以被省略.例如, 则正规式中不必要的括号可以被省略.例如, (a)|((b)*(c))可以简化成 可以简化成a|b*c. 可以简化成 .

2010-7-22

编译原理

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

第二章 词法分析

正规集是一个集合, 正规集是一个集合,而正规式是表示正规集的一种方 法. 不同正规式也可以表示同一个正规集, 不同正规式也可以表示同一个正规集,即正规式与正 规集之间是多对一的关系. 规集之间是多对一的关系. 定义2.3 若正规式 和Q表示了同一个正规集,则称 若正规式P和 表示了同一个正规集 则称P 表示了同一个正规集, 定义 和Q是等价的,记为P=Q. 是等价的,记为 . 是等价的 正规式之间的一些恒等运算, 正规式之间的一些恒等运算,被称为正规式的代 数性质. 给出了正规式的若干代数性质. 数性质.表2.6给出了正规式的若干代数性质.利用这 给出了正规式的若干代数性质 些性质,可以对复杂的正规式进行化简, 些性质,可以对复杂的正规式进行化简,使得可以用 最简单形式的正规式表示一个集合. 最简单形式的正规式表示一个集合.而简单的正规式 意味着其所对应的识别器的构造也是简单的. 意味着其所对应的识别器的构造也是简单的.

2010-7-22

编译原理

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

第二章 词法分析

正规式的代数性质

2010-7-22

编译原理

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

第二章 词法分析

3,记号的说明 记号的说明用自然语言对模式进行了非形式化的描述, 用自然语言对模式进行了非形式化的描述,例如标识符模式的非形 式化描述是"以字母打头的字母数字串" 这一描述很不精确, 式化描述是"以字母打头的字母数字串".这一描述很不精确,存在一 些问题,如哪些符号是字母,哪些符号是数字, 些问题,如哪些符号是字母,哪些符号是数字,字母数字串的长度可以 是多少等等. 是多少等等. 正规式是严格的数学表达式,采用正规式来描述模式,解决了精确 正规式是严格的数学表达式,采用正规式来描述模式, 描述模式的问题.另外,从词法分析器的角度上看程序设计语言, 描述模式的问题.另外,从词法分析器的角度上看程

序设计语言,用正 规式说明的记号是一个正规集. 规式说明的记号是一个正规集. 用正规式说明记号的公式为: 正规式,可以读作为" 左边 左边) 用正规式说明记号的公式为:记号 = 正规式,可以读作为"(左边 记号定义为(右边 正规式 记号定义为 右边)正规式",或者"记号是正规式".通常,在不引起 右边 正规式" 或者"记号是正规式" 通常, 混淆的情况下,也把说明记号的公式简称为正规式,或者规则. 混淆的情况下,也把说明记号的公式简称为正规式,或者规则.

2010-7-22

编译原理

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

第二章 词法分析

中的记号relation,id和num分别是 分别是Pascal的关系运 例2.5 表2.1中的记号 中的记号 , 和 分别是 的关系运 算符,标识符和无符号数,它们的正规式表示如下所示: 算符,标识符和无符号数,它们的正规式表示如下所示: 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)*2010-7-22 编译原理 21