编译原理 第三章词法分析 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年3月
1 编译原理 第三章 词法分析 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年3月
本章目的 词法分析器从输入串中识别单词,编 译程序对源程序的分析由此开始。单词 构词规则可由状态转换图表示,手工编 程实现这些状态转换图,便可产生高效 的词法分析器。构词规则也可由正规式 表示,据此转换成识别单词的有限自动 机,这就得到了识别单词的状态转换图。 软件工具Lex能实现这种转换
2 本章目的 词法分析器从输入串中识别单词，编 译程序对源程序的分析由此开始。单词 构词规则可由状态转换图表示，手工编 程实现这些状态转换图，便可产生高效 的词法分析器。构词规则也可由正规式 表示，据此转换成识别单词的有限自动 机，这就得到了识别单词的状态转换图。 软件工具Lex能实现这种转换
第三章词法分析 §3.1构造一个简单的词法分析器 、词法分析器的功能 程序与由自然语言书写的文章一样,它是由 系列的句子组成的,而句子是由单词按一定规 则组成的,单词是由字符组成的,因此归根结 蒂源程序是由程序语言的字母表上的字符串组 成。词法分析就应从输入字符串中识别出一个 个单词,并对其中由用户定义的名字,在符号 表中予以登记
3 第三章 词法分析 §3.1 构造一个简单的词法分析器 一、词法分析器的功能 程序与由自然语言书写的文章一样，它是由一 系列的句子组成的，而句子是由单词按一定规 则组成的，单词是由字符组成的，因此归根结 蒂源程序是由程序语言的字母表上的字符串组 成。词法分析就应从输入字符串中识别出一个 个单词，并对其中由用户定义的名字，在符号 表中予以登记。
「例31有下列程序段: begin length:=length+l if length <20 then read (nextch) end: 它的输入字符串和识别出的单词流如图31(a) (b)所示。其中表示空白(空格)键,符号≌ 表示 RETURN键符, length和 nextel为程序中 定义的变量,它们在符号表中应予以记载 4
4 [例3.1]有下列程序段： begin length:=length+1； if length<20 then read (nextch) end； 它的输入字符串和识别出的单词流如图3.1(a)、 (b)所示。其中__表示空白（空格）键，符号↙ 表示RETURN键符，length和nextch为程序中 定义的变量，它们在符号表中应予以记载
词法分析与语法分析的关系 由词法分析识别出的单词流是语法分析的输入 语法分析据此判别它们是否构成合法句子。由 词法分析开始形成的符号表,在以后的编译各 阶段要频繁使用。 词法分析可以作为单独一遍,如图32(a)所示, 但由于词法分析比较简单,将它作为语法分析 的子程序,每当语法分析程序需要一单词时, 就调用词法分析子程序,从输入串中识别当前 单词,这是一种十分自然有效的工作方法,结 构如图32(b所示
5 词法分析与语法分析的关系： 由词法分析识别出的单词流是语法分析的输入， 语法分析据此判别它们是否构成合法句子。由 词法分析开始形成的符号表，在以后的编译各 阶段要频繁使用。 词法分析可以作为单独一遍，如图3.2(a)所示， 但由于词法分析比较简单，将它作为语法分析 的子程序，每当语法分析程序需要一单词时， 就调用词法分析子程序，从输入串中识别当前 单词，这是一种十分自然有效的工作方法，结 构如图3.2(b)所示。
输入串 ↓词法分析器 一法分析]一的法分析器取下 】符号表 法分析器 (a)词法分析为单独一遍 )词法分析器是一子程序 图3.2词法分析器与语法分析器的关系 6
6 词法分析器 语法分析器 输入串 单词流 图3.2 词法分析器与语法分析器的关系 (a) 词法分析为单独一遍 (b) 词法分析器是一子程序 语法分析器 词法分析器 符号表 输入串 取下一 单词 返回下 一单词
1.单词符号的种类 单词符号是程序语言最基本的语法符号,通常有五 种 (1)基本字。有的称关键字或保留字,如if、 while、 for、do、goto等,它们具标识符的特征,但它们 是由语言定义的,其意义是固定的。多数语言中 规定,它们不能作为标识符或标识符的前缀,用 户不能用它们来定义用户使用的名字,在这种情 况下,我们称它们为保留字,如 Pascal和C等。但 也有的语言允许将基本字作为标识符或标识符的 前缀,如 Fortran和PL/1; 7
7 1. 单词符号的种类 单词符号是程序语言最基本的语法符号,通常有五 种: (1)基本字。有的称关键字或保留字,如if、while、 for、do、goto等，它们具标识符的特征，但它们 是由语言定义的，其意义是固定的。多数语言中 规定，它们不能作为标识符或标识符的前缀，用 户不能用它们来定义用户使用的名字，在这种情 况下，我们称它们为保留字，如Pascal和C等。但 也有的语言允许将基本字作为标识符或标识符的 前缀，如Fortran和PL/1；
(2)标识符。用户用来命名程序中出现的变量、数 组、函数、过程、标号等,通常是 个字母开头的字母数字串;如 length, nextel等 (3)常数。包括各种类型的常数,如整型、实型、 布尔型、字符型常数,216、3.1416、TRUE alpha等。 (4)运算符。如+、=、*、/等 (5)界符。如;、:、(、)及双字符界符:=、/、* 及空白符等。 对于一个确定的程序语言来说,保留字(或基本字) 运算符、界符的数目是确定的,通常在几十个至 百余个之间。标识符、常数则由用户指定,如何 指定,使用多少个,程序语言均未加限制
8 (2)标识符。用户用来命名程序中出现的变量、数 组、函数、过程、标号等，通常是一 个字母开头的字母数字串；如length，nextch等； (3)常数。包括各种类型的常数，如整型、实型、 布尔型、字符型常数，216、3.1416、TRUE、 alpha等。 (4)运算符。如+、=、 * 、/等； (5)界符。如; 、: 、( 、)及双字符界符:= 、/* 、 */ 及空白符等。 对于一个确定的程序语言来说，保留字(或基本字)、 运算符、界符的数目是确定的，通常在几十个至 百余个之间。标识符、常数则由用户指定，如何 指定，使用多少个，程序语言均未加限制
2.单词的编码 识别出来的单词符号应采用某种中间表示,以便 为编译的后续阶段引用,其原则在于便以区别、 便于识别,表示方法可多种多样,以有利于编译 处理为准,通常单词符号可以用一个二元组来表 示: (单词类别,单词符号的属性值) 第一元用以区分单词符号所属的类,以整数编码。 第二元用以区分在该类中哪一个单词符号,即单 词符号的值,它的编码,随类别不同而不同
9 2. 单词的编码 识别出来的单词符号应采用某种中间表示，以便 为编译的后续阶段引用，其原则在于便以区别、 便于识别，表示方法可多种多样，以有利于编译 处理为准，通常单词符号可以用一个二元组来表 示： (单词类别，单词符号的属性值) 第一元用以区分单词符号所属的类，以整数编码。 第二元用以区分在该类中哪一个单词符号，即单 词符号的值，它的编码，随类别不同而不同
单词的三元组衔确定方法 有限类: 由于基本字,运算符,界符的数目有限,一般可 以对每个单词定义一个种别码,即一字一种,这 时,它的第二元就没有识别意义了,即一级编码 形式。显然以后对这类单词的识别十分简便。也 可以将关系运算符、≥、=、归为一类,则 第二元就应是区分为哪一个关系运算符的值了 无限类: 对于常数可以统归为一类,也可以按整型、实型、 布尔型、字符型分类。标识符类似处理,在这种 情况下每一类别中的常数或标识符将由单词符号 的属性值来区别是哪一个单词符号。通常将常数 表的入口指针作为常数的属性值,而将符号表的 入口指针作为标识符的属性值 10
10 单词的二元组的确定方法 •有限类： 由于基本字，运算符，界符的数目有限，一般可 以对每个单词定义一个种别码，即一字一种，这 时，它的第二元就没有识别意义了，即一级编码 形式。显然以后对这类单词的识别十分简便。也 可以将关系运算符、≥、=、归为一类，则 第二元就应是区分为哪一个关系运算符的值了。 •无限类： 对于常数可以统归为一类，也可以按整型、实型、 布尔型、字符型分类。标识符类似处理，在这种 情况下每一类别中的常数或标识符将由单词符号 的属性值来区别是哪一个单词符号。通常将常数 表的入口指针作为常数的属性值，而将符号表的 入口指针作为标识符的属性值