词法分析1上课讲义

词法分析1图2.1作为子程序的词法分析器图2.2词法分析器进行单独一遍扫描2023/1/132编译原理图2.3并行工作模式2023/1/133编译原理2、单词符号的分类单词符号分类：词法分析程序简单地说就是读单词程序，该程描用高级语言编写的源程序，将源程序中由单词符号组成的字符串分解出一个个单词来。因此，单词符号是程序语言的基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：2023/1/134编译原理(1)保留字(也称基本字)：如C语言中的if、else、while和do等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。(2)

标识符：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。(3)常数：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。(4)运算符：如“+”、“?”、“*”、“/”、“>”、“<”等。(5)界符：在语言中是作为语法上的分界符号使用的，如“，”、“；”、“（”、“）”等。2023/1/135编译原理注意：一个程序语言的保留字、运算符和界符的个数是确定的，而标识符或常数的使用则不限定个数。将产生和识别单词的规则称为模式(patten)。按照某个模式(规则)识别出的元素称为记号(token)。单词(lexeme)一词是指被识别出元素自身的值。2023/1/136编译原理词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式：

（单词种别，单词自身的值）词法分析器输出单词的形式3、词法分析器输出单词的形式2023/1/137编译原理(1)单词种别。单词种别表示单词的种类，它是语法分析所需要的信息。一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分类方法处理起来比较方便；标识符一般统归为一种；常数可统归为一种，也可按整型、实型、布尔型等分为几种；运算符和界符可采用一符一种的分法，也可统归为一种。2023/1/138编译原理(2)单词自身的值。单词自身的值是编译中其它阶段所需要的信息。对于单词符号来说：如果一个种别只含有一个单词符号，那么对于这个单词符号，其种别编码就完全代表了它自身的值。如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外还应给出单词符号自身的值，以便把同一种类的单词区别开来。注意：标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目的指针来区分同类中的不同单词。例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。2023/1/139编译原理二、模式的形式化描述-正规式与正规集1、字符串与语言从词法分析的角度看，程序设计语言是由记号组成的集合，每个记号又是由若干字母按照一定规则组成的字符串。2023/1/1310编译原理定义2.1语言L是有限字母表∑上有限长度字符串的集合。定义2.1明确指出，语言是一个集合，集合中的元素是字符串，并且强调了两个有限:①字母表是有限的，即字母表中元素是有限多个；②字符串的长度是有限的，即字符串中字符个数是有限多个。这是由于计算机所能表示的字符个数和字符串的长度都是有限的。2023/1/1311编译原理字符串的基本概念：2023/1/1312编译原理字符串集合上的基本运算2023/1/1313编译原理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)。可用正规式描述的语言称为正规语言或正规集。2023/1/1314编译原理定义2.2中①和②规定了正规式的基本操作数或基本正规式。定义2.2的③给出了正规式上的三种运算:(a)或运算、(b)连接运算和(c)闭包运算。对于由多个操作数和多个操作符组成的正规式，可以利用(d)所给的括号规定运算的先后次序。如果对或、连接和闭包运算进行如下约定:①三种运算均具有左结合性质；②运算的优先级从高到低顺序排列为:闭包运算、连接运算、或运算。则正规式中不必要的括号可以被省略。例如，(a)|((b)*(c))可以简化成a|b*c。2023/1/1315编译原理正规集是一个集合，而正规式是表示正规集的一种方法。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。定义2.3若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。正规式之间的一些恒等运算，被称为正规式的代数性质。表2.6给出了正规式的若干代数性质。利用这些性质，可以对复杂的正规式进行化简，使得可以用最简单形式的正规式表示一个集合。而简单的正规式意味着其所对应的识别器的构造也是简单的。2023/1/1316编译原理正规式的代数性质2023/1/1317编译原理3、记号的说明用自然语言对模式进行了非形式化的描述，例如标识符模式的非形式化描述是“以字母打头的字母数字串”。这一描述很不精确，存在一些问题，如哪些符号是字母，哪些符号是数字，字母数字串的长度可以是多少等等。正规式是严格的数学表达式，采用正规式来描述模式，解决了精确描述模式的问题。另外，从词法分析器的角度上看程序设计语言，用正规式说明的记号是一个正规集。用正规式说明记号的公式为：记号=正规式，可以读作为“(左边)记号定义为(右边)正规式”，或者“记号是正规式”。通常，在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。2023/1/1318编译原理例2.5

表2.1中的记号relation、id和num分别是Pascal的关系运算符、标识符和无符号数，它们的正规式表示如下所示：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)*2023/1/1319编译原理num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)上述正规式给出了标识符的精确定义，用自然语言可以描述为“字母是英文26个字母大小写中任何一个，数字是十进制阿拉伯数字中的任何一个，标识符是以字母打头的、其后可跟随0个或若干个字母或数字的字符串”。2023/1/1320编译原理a．简化正规式描述为了简化正规式的描述，通常可以采用如下的几种正规式的缩写形式。(1)正闭包。若r是表示L(r)的正规式，则r+是表示(L(r))+的正规式，且下述等式成立:r+=rr*=r*r，r*=r+|ε+与*具有相同的运算优先级和结合性。(2)可缺省。若r是正规式，则(r)?是表示L(r)∪ε的正规式，且下述等式成立:r?=r|ε2023/1/1321编译原理(3)字符组。字符组是或关系的缩写形式，它把所有存在或关系的字符集中在[]里面。其中的字符可以有如下两种书写方式:枚举方式:如[abc]，它等价于a|b|c

分段方式:如[0-9a-z]，它等价于：[0123456789abcdefghijklmnopqrstuvwxyz]2023/1/1322编译原理(4)非字符组。若[r]是一个字符组形式的正规式，则[^r]是表示∑L(r)的正规式。例如，若∑=，则L([^abc])={d,e,f,g}。(5)串。若r是字符连接运算的正规式，则串"r"与r等价，即r="r"。特别地，ε="",?a="a"。引入串的表示可以避免与正规式中运算符的冲突。例如："a|b"=a"|"b≠a|b。2023/1/1323编译原理b．引入辅助定义式引入辅助定义式的主要目的是为较复杂、但需要重复书写的正规式命名，并在定义式之后的引用中，用名字代替相应的正规式。所以，辅助定义式实质上仍然是正规式，唯一的区别是正规式与外部模式匹配，而辅助定义式不与任何模式匹配。2023/1/1324编译原理例2.6引入正规式的缩写形式和辅助定义式后，id和num的正规式可重写如下。

char =[a-zA-Z]digit =[0-9]digits =digit+optional_fraction =(.digits)?optional_exponent =(E(+|)?digits)?id =char(char|digit)*num =digitsoptional_fra