编译原理基础(刘坚)第2章.ppt

《编译原理基础(刘坚)第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章词法分析2.1词法分析中的若干问题2.2模式的形式化描述2.3记号的识别——有限自动机2.4从正规式到词法分析器2.5本章小结2.1词法分析中的若干问题2.1.1记号、模式与单词自然语言中的句子通常由一个个单词和标点符号组成，可以根据其在句子中的作用，将它们划分为动词、名词、形容词、标点符号等不同的种类。程序设计语言与此相类似，组成语句的基本单元也可根据其在句子中的作用分类。最基本分类有四类：(1)关键字(保留字)：这类单词在程序设计语言中有固定的意义，如begin、end、while等。若在程序设计语言中不允许用它们再表示其他的意思，则这类单词也被称为保留字。(2)标识符：标识符

2、是程序设计语言中最大的一个类别，它的作用是为某个实体起一个名字，以便于今后称呼(引用)，如draw_line、sort等。可以用标识符来命名的实体包括类型、变量、过程、常量、类、对象、程序包、标号等，即类型名、变量名、过程名、常量名等。(3)字面量：字面量是指直接以其字面所表示的常量，如25、true、"Thisisastring"等。值得注意的是，字面量与常量是两个不同的概念，常量可以是一个字面量(直接表示)，也可以是一个常量名(命名表示)。例如可以在Pascal中声明：constmax_length=25，显然25是一个常量，max_length也是一个常量，我们称25为字面量，而不

3、称max_length为字面量。根据字面量的内容，可以将它们再进行更细的划分，如常数字面量(包括整型字面量、实型字面量、枚举字面量等)、字符串字面量等。(4)特殊符号：程序设计语言中的特殊符号，类似于自然语言中的标点符号，每个符号在程序设计语言中均有特殊用途。可以根据它们的用途，再细分为算符(如+、、*、/等)、分隔符(如；、”、“等)。显然，一个单词究竟是标识符、关键字，还是特殊符号，需要根据一定的构词规则来产生和识别。我们将产生和识别单词的规则称为模式(patten)，按照某个模式(规则)识别出的元素称为记号(token)，而单词(lexeme)一词是指被识别出元素自身的值。例2.1

4、对于语句：position:=initial+rate*60，可以识别出下述序列：标识符特殊符号标识符特殊符号标识符特殊符号数字字面量其中position、initial、rate均被识别为标识符，因为它们均符合同一条规则，即以字母打头的字母数字串。记号至少含有两个信息：一个是记号的类别，如“标识符”；另一个是记号的值，如“position”。显然，如果把记号看作是一个类型的话，则单词就是一个类型中的实例。由于我们总是说识别出一个标识符，而不说识别出一个position或rate，因而将词法分析器识别出的序列称为记号流。记号的类别、模式以及单词三者之间的关系可以用表2.1加以说明。其中，

5、const和if分别是被细分的关键字，它们的特点是一个记号类别仅对应一个单词；relation表示关系运算符；id表示标识符；num表示数字字面量；literal表示字符串字面量；comment表示注释，它们的特点是一个记号类别可以对应若干个单词。由于语法分析及其后的阶段并不对注释进行分析，因而可在词法分析阶段中滤掉注释，即词法分析器可以不向语法分析器返回comment。而其他的记号，均是源程序中的有效成分，需要返回给语法分析器。表2.1记号、模式与单词2.1.2记号的属性从例2.1中已经知道，记号至少包含两个部分：记号类别和记号的其他信息。可以看出，记号的类别唯一标识一类记号，例如所有

6、的关系运算符均可以由relation来标识，而所有字符串字面量均可以由literal来标识。所以，记号的类别可以被认为是记号的名字或记号的代表，在不引起混淆的情况下，将记号的类别简称为记号。记号的其他信息被称为记号的属性。例如，num可以取值3.1416，则称3.1416是num的属性，而literal可以取值“coredumped”(不含引号)，则称“coredumped”是literal的属性。由此可见，记号的类别标识一类记号，而记号的类别加属性标识一个记号实例。在计算机内部，可以有不同的方式来表示记号的类别和属性。一般情况下，记号的类别可以用整型编码或枚举类型表示，如表2.1中每个

7、记号类别可以用括号中的整型编码表示，如01表示const，82表示id等。根据记号类别的不同，记号的属性的值可以有不同的表示方法。relation的属性值是一个有限可枚举集合，可以用每个属性值在集合中的位置来表示它，如1表示<，2表示<=，依此类推。id的属性值是一个无限可枚举集合，因此，只能用每个标识符的原始输入形式(字符串)来表示，如pi、draw_line等。字面量的属性根据情况，其表示方式也不同，如数字字面量可由转义后的实际