词法分析1上课讲义.ppt

《词法分析1上课讲义.ppt》由会员分享，可在线阅读，更多相关《词法分析1上课讲义.ppt（27页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章 词法分析词法分析1第二章 词法分析图2.1 作为子程序的词法分析器 图2.2 词法分析器进行单独一遍扫描2022/11/252编译原理编译原理第二章 词法分析图2.3 并行工作模式2022/11/253编译原理编译原理第二章 词法分析2、单词符号的分类、单词符号的分类单词符号分类：词法分析程序简单地说就是读单词程序，该程描用高级语言编写的源程序，将源程序中由单词符号组成的字符串分解出一个个单词来。因此，单词符号是程序语言的基本语法单位基本语法单位，具有确定的语法意义。程序语言的单词符号通常可分为下面五种：2022/11/254编译原理编译原理第二章 词法分析n(1)保留字保留字(也称基

2、本字也称基本字)：如C语言中的if、else、while和do等，这些字保留了语言所规定的含义，是编译程序识别各类语法成分的依据。几乎所有程序语言都限制用户使用保留字来作为标识符。n(2)标识符：标识符：用来标记常量、数组、类型、变量、过程或函数名等，通常由用户自己定义。n(3)常数：常数：包括各种类型的常数，如整型常数386、实型常数0.618、布尔型常数TRUE等。n(4)运算符：运算符：如“+”、“?”、“*”、“/”、“”、“”等。n(5)界符：界符：在语言中是作为语法上的分界符号使用的，如“，”、“；”、“（”、“）”等。2022/11/255编译原理编译原理第二章 词法分析注意：一

3、个程序语言的保留字、运算符和保留字、运算符和界符界符的个数是确定的，而标识符或常数的使用则不限定个数。n将产生和识别单词的规则称为模式模式(patten)。n按照某个模式(规则)识别出的元素称为记记号号(token)。n单词(lexeme)一词是指被识别出元素自身的值。2022/11/256编译原理编译原理第二章 词法分析n词法分析程序的输入是源程序字符串，而输出是与源程序等价的单词符号序列，并且所输出的单词符号通常表示成如下的二元式：（单词种别，单词自身的值）（单词种别，单词自身的值）词法分析器输出单词的形式3、词法分析器输出单词的形式、词法分析器输出单词的形式2022/11/257编译原理

4、编译原理第二章 词法分析(1)单词种别。单词种别。n单词种别表示单词的种类，它是语法分析所需要的信息。单词种别表示单词的种类，它是语法分析所需要的信息。n一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性一个语言的单词符号如何划分种类、分为几类、如何编码都属于技术性问题，主要取决于处理上的方便。问题，主要取决于处理上的方便。n通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开通常让每种单词对应一个整数码，这样可最大限度地把各个单词区别开来。来。n对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分对于保留字，可将其全体视为一种，也可一字一种，采用一字一种的分类

5、方法处理起来比较方便；类方法处理起来比较方便；n标识符一般统归为一种；标识符一般统归为一种；n常数可统归为一种，也可按整型、实型、布尔型等分为几种；常数可统归为一种，也可按整型、实型、布尔型等分为几种；n运算符和界符可采用一符一种的分法，也可统归为一种。运算符和界符可采用一符一种的分法，也可统归为一种。2022/11/258编译原理编译原理第二章 词法分析n(2)单词自身的值。单词自身的值。n单词自身的值是编译中其它阶段所需要的信息。单词自身的值是编译中其它阶段所需要的信息。n对于单词符号来说：对于单词符号来说：n如果一个种别只含有一个单词符号，那么对于这个单词符号，其如果一个种别只含有一个单

6、词符号，那么对于这个单词符号，其种别编码就完全代表了它自身的值。种别编码就完全代表了它自身的值。n如果一个种别含有多个单词符号，那么对于它的每个单词符号，如果一个种别含有多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外还应给出单词符号自身的值，以便把同一除了给出种别编码之外还应给出单词符号自身的值，以便把同一种类的单词区别开来。种类的单词区别开来。n注意：标识符自身的值就是标识符自身的字符串，而常数自身的注意：标识符自身的值就是标识符自身的字符串，而常数自身的值是常数本身的二进制数值。此外，我们也可用指向某类表格中值是常数本身的二进制数值。此外，我们也可用指向某类表格中一个特定项目

7、的指针来区分同类中的不同单词。一个特定项目的指针来区分同类中的不同单词。n例如，对于标识符，可以用它在符号表的入口指针作为它自身的例如，对于标识符，可以用它在符号表的入口指针作为它自身的值；而常数也可用它在常数表的入口指针作为它自身的值。值；而常数也可用它在常数表的入口指针作为它自身的值。2022/11/259编译原理编译原理第二章 词法分析二、模式的形式化描述二、模式的形式化描述-正规式与正规集正规式与正规集1、字符串与语言、字符串与语言 从词法分析的角度看，程序设计语言是由记号组成的集合，每个记号又是由若干字母按照一定规则组成的字符串。2022/11/2510编译原理编译原理第二章 词法分

8、析n定义定义2.1 语言语言L是有限字母表是有限字母表上有限长度字上有限长度字符串的集合。符串的集合。n 定义定义2.1明确指出，语言是一个集合，集明确指出，语言是一个集合，集合中的元素是字符串，并且强调了两个有限合中的元素是字符串，并且强调了两个有限:n 字母表是有限的，即字母表中元素是字母表是有限的，即字母表中元素是有限多个；有限多个；n 字符串的长度是有限的，即字符串中字符串的长度是有限的，即字符串中字符个数是有限多个。字符个数是有限多个。n 这是由于计算机所能表示的字符个数和字这是由于计算机所能表示的字符个数和字符串的长度都是有限的。符串的长度都是有限的。2022/11/2511编译原

9、理编译原理第二章 词法分析字符串的基本概念：字符串的基本概念：2022/11/2512编译原理编译原理第二章 词法分析字符串集合上的基本运算字符串集合上的基本运算2022/11/2513编译原理编译原理第二章 词法分析2、正规式与正规集正规式与正规集n定义定义2.2 令令是一个有限字母表，则是一个有限字母表，则上的正规式及其上的正规式及其表示的集合递归定义如下表示的集合递归定义如下:n 是正规式，它表示集合是正规式，它表示集合L()=；n 若若a是是上的字符，则上的字符，则a是正规式，它表示集合是正规式，它表示集合L(a)=；n 若正规式若正规式r和和s分别表示集合分别表示集合L(r)和和L(

10、s)，则，则n (a)r|s是正规式，表示集合是正规式，表示集合L(r)L(s)；n (b)rs是正规式，表示集合是正规式，表示集合L(r)L(s)；n (c)r*是正规式，表示集合是正规式，表示集合(L(r)*；n (d)(r)是正规式，表示的集合仍然是是正规式，表示的集合仍然是L(r)。n可用正规式描述的语言称为正规语言或正规集。可用正规式描述的语言称为正规语言或正规集。2022/11/2514编译原理编译原理第二章 词法分析n定义定义2.2中中和和规定了正规式的基本操作数或基本正规定了正规式的基本操作数或基本正规式。规式。n 定义定义2.2的的给出了正规式上的三种运算给出了正规式上的三种

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

12、b)*(c)可以简化成可以简化成a|b*c。2022/11/2515编译原理编译原理第二章 词法分析n正规集是一个集合，而正规式是表示正规集的一种方正规集是一个集合，而正规式是表示正规集的一种方法。法。n不同正规式也可以表示同一个正规集，即正规式与正不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。规集之间是多对一的关系。n定义定义2.3 若正规式若正规式P和和Q表示了同一个正规集，则称表示了同一个正规集，则称P和和Q是等价的，记为是等价的，记为P=Q。n 正规式之间的一些恒等运算，被称为正规式的代正规式之间的一些恒等运算，被称为正规式的代数性质。表数性质。表2.6给出了正

13、规式的若干代数性质。利用这给出了正规式的若干代数性质。利用这些性质，可以对复杂的正规式进行化简，使得可以用些性质，可以对复杂的正规式进行化简，使得可以用最简单形式的正规式表示一个集合。而简单的正规式最简单形式的正规式表示一个集合。而简单的正规式意味着其所对应的识别器的构造也是简单的。意味着其所对应的识别器的构造也是简单的。2022/11/2516编译原理编译原理第二章 词法分析正规式的代数性质正规式的代数性质2022/11/2517编译原理编译原理第二章 词法分析3、记号的说明记号的说明 用自然语言对模式进行了非形式化的描述，例如标识符模式的非形用自然语言对模式进行了非形式化的描述，例如标识符

14、模式的非形式化描述是式化描述是“以字母打头的字母数字串以字母打头的字母数字串”。这一描述很不精确，存在一。这一描述很不精确，存在一些问题，如哪些符号是字母，哪些符号是数字，字母数字串的长度可以些问题，如哪些符号是字母，哪些符号是数字，字母数字串的长度可以是多少等等。是多少等等。正规式是严格的数学表达式，采用正规式来描述模式，解决了精确正规式是严格的数学表达式，采用正规式来描述模式，解决了精确描述模式的问题。另外，从词法分析器的角度上看程序设计语言，用正描述模式的问题。另外，从词法分析器的角度上看程序设计语言，用正规式说明的记号是一个正规集。规式说明的记号是一个正规集。用正规式说明记号的公式为：

15、记号用正规式说明记号的公式为：记号=正规式，可以读作为正规式，可以读作为“(左边左边)记号定义为记号定义为(右边右边)正规式正规式”，或者，或者“记号是正规式记号是正规式”。通常，在不引起混。通常，在不引起混淆的情况下，也把说明记号的公式简称为正规式，或者规则。淆的情况下，也把说明记号的公式简称为正规式，或者规则。2022/11/2518编译原理编译原理第二章 词法分析n例例2.5 表表2.1中的记号中的记号relation、id和和num分别是分别是Pascal的关系运的关系运算符、标识符和无符号数，它们的正规式表示如下所示：算符、标识符和无符号数，它们的正规式表示如下所示：n relati

16、on=|=|=|=n 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|zn|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)n (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|zn|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)*2022/11/2519编译原理编译原理第二章 词法分析num=(0|1|2|3|4|5|6|7|8|

17、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个或若干个字母或数字的字符串个或

18、若干个字母或数字的字符串”。2022/11/2520编译原理编译原理第二章 词法分析a简化正规式描述简化正规式描述 为了简化正规式的描述，通常可以采用如下的几种正规式的缩写形式。(1)正闭包。若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式，且下述等式成立:r+=rr*=r*r，r*=r+|+与*具有相同的运算优先级和结合性。(2)可缺省。若r是正规式，则(r)?是表示L(r)的正规式，且下述等式成立:r?=r|2022/11/2521编译原理编译原理第二章 词法分析(3)字符组。字符组是或关系的缩写形式，它把字符组。字符组是或关系的缩写形式，它把所有存在或关系的字符集中在所有存在

19、或关系的字符集中在 里面。其中的字里面。其中的字符可以有如下两种书写方式符可以有如下两种书写方式:枚举方式枚举方式:如如abc，它等价于它等价于a|b|c 分段方式分段方式:如如0-9a-z，它等价于：它等价于：0123456789abcdefghijklmnopqrstuvwxyz2022/11/2522编译原理编译原理第二章 词法分析(4)非字符组。若非字符组。若r是一个字符组形式的正规式，则是一个字符组形式的正规式，则r是表示是表示L(r)的正规式。例如，若的正规式。例如，若=，则，则L(abc)=d,e,f,g。(5)串。若串。若r是字符连接运算的正规式，则串是字符连接运算的正规式，则

20、串r与与r等价，等价，即即r=r。特别地，特别地，=,?a=a。引入串的表示可以避引入串的表示可以避免与正规式中运算符的冲突。例如：免与正规式中运算符的冲突。例如：a|b=a|ba|b。2022/11/2523编译原理编译原理第二章 词法分析b引入辅助定义式引入辅助定义式 引入辅助定义式的主要目的是为较复杂、但需引入辅助定义式的主要目的是为较复杂、但需要重复书写的正规式命名，并在定义式之后的引用要重复书写的正规式命名，并在定义式之后的引用中，用名字代替相应的正规式。所以，辅助定义式中，用名字代替相应的正规式。所以，辅助定义式实质上仍然是正规式，唯一的区别是正规式与外部实质上仍然是正规式，唯一的

21、区别是正规式与外部模式匹配，而辅助定义式不与任何模式匹配。模式匹配，而辅助定义式不与任何模式匹配。2022/11/2524编译原理编译原理第二章 词法分析例例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 =digits optional_fraction optional_exponent 2022/11/2525编

22、译原理编译原理第二章 词法分析词法错误校正词法错误校正n词法错误种类：词法错误种类：n 语言不允许的符号：语言不允许的符号：#n 括号类配对错误：括号类配对错误：n 单词的后继符错（偶尔）：单词的后继符错（偶尔）：n词法错误校正：词法错误校正：n a a 删除已被读过的字符，并重新扫删除已被读过的字符，并重新扫n 描未被读过的字符描未被读过的字符n b b 删除已读过的第一个字符，重新删除已读过的第一个字符，重新n 扫描它的后继部分的字符。扫描它的后继部分的字符。n校正后的标示校正后的标示2022/11/2526编译原理编译原理第二章 词法分析此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢