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

编译原理 第二章 词法分析 主要内容： 词法分析过程涉及的几个问题 模式的形式化描述-正规式与正规集 记号的识别-有限自动机 从正规式到词法分析器 词法分析器生成器简介 一、词法分析过程涉及的几个问题 词法分析是编译过程中的第一个阶段。 执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。 任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。 功能是输入源程序，输出单词符号，并检查词法错误。 词法分析器作为主程序； 词法分析器作为子程序； 并行工作方式 2、单词符号的分类 单词符号分类： 词法分析程序简单地说就是读单词程序，该程描用高级语言编写的源程序，将源程序中由单词符号组成的字符串分解出一个个单词来。因此，单词符号是程序语言的基本语法单位，具有确定的语法意义。 程序语言的单词符号通常可分为下面五种： (1) 保留字(也称基本字)：如C语言中的if、else、while和do等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。 (2) 标识符：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。 (3) 常数：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。 (4) 运算符：如“+”、“?”、“*”、“/”、“”、“”等。 (5) 界符：在语言中是作为语法上的分界符号使用的，如“，”、“；”、“（”、“）”等。 注意：一个程序语言的保留字、运算符和界符的个数是确定的，而标识符或常数的使用则不限定个数。 将产生和识别单词的规则称为模式(patten)。 按照某个模式(规则)识别出的元素称为记号(token)。 单词(lexeme)一词是指被识别出元素自身的值。 词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式： （单词种别，单词自身的值） (1) 单词种别。 单词种别表示单词的种类，它是语法分析所需要的信息。 一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。 通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。 对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分类方法处理起来比较方便； 标识符一般统归为一种； 常数可统归为一种，也可按整型、实型、布尔型等分为几种； 运算符和界符可采用一符一种的分法，也可统归为一种。 (2) 单词自身的值。 单词自身的值是编译中其它阶段所需要的信息。 对于单词符号来说： 如果一个种别只含有一个单词符号，那么对于这个单词符号，其种别编码就完全代表了它自身的值。 如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外还应给出单词符号自身的值，以便把同一种类的单词区别开来。 注意：标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。 例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。 二、模式的形式化描述-正规式与正规集 1、字符串与语言 从词法分析的角度看，程序设计语言是由记号组成的集合，每个记号又是由若干字母按照一定规则组成的字符串。 定义2.1 语言L是有限字母表∑上有限长度字符串的集合。 定义2.1明确指出，语言是一个集合，集合中的元素是字符串，并且强调了两个有限: ① 字母表是有限的，即字母表中元素是有限多个； ② 字符串的长度是有限的，即字符串中字符个数是有限多个。 这是由于计算机所能表示的字符个数和字符串的长度都是有限的。 字符串的基本概念： 字符串集合上的基本运算 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)。 可用正规式描述的