Ch3词法分析课件

1、Ch3词法分析1第二章第二章 词法分析词法分析 Ch3词法分析2本章在编译程序中的地位本章在编译程序中的地位表表格格管管理理词法分析器词法分析器语法分析器语法分析器语义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码出出错错处处理理Ch3词法分析3P8. P8. 词法分析概述词法分析概述n任务任务：从左到右逐个字符地对源程序扫描，产生出：从左到右逐个字符地对源程序扫描，产生出一个个一个个单词符号单词符号。n输入输入：源程序。：源程序。n输出输出：单词符号。：单词符号。n单

2、词符号单词符号：保留字、标识符、常数、算符、界符。：保留字、标识符、常数、算符、界符。n词法分析依循的是词法分析依循的是语言的构词规则语言的构词规则。n描述词法规则的工具是描述词法规则的工具是正规表达式正规表达式和和有限自动机有限自动机。n词法分析器词法分析器(扫描器扫描器)可以采用两种处理结构：可以采用两种处理结构：nP8.图图2-1(a) 作为独立的主程序；作为独立的主程序；nP8.图图2-1(b) 作为语法分析程序调用的子程序。作为语法分析程序调用的子程序。Ch3词法分析4教学内容教学内容n2.1 词法分析器设计方法词法分析器设计方法 P8.11.n单词符号的分类、词法分析器的输出形式单

3、词符号的分类、词法分析器的输出形式n状态转换图状态转换图n2.2 一个简单的词法分析器示例一个简单的词法分析器示例 P11.15.nC语言子集的单词符号、状态转换图及其实现语言子集的单词符号、状态转换图及其实现 n2.3 正规表达式与有限状态自动机正规表达式与有限状态自动机 P15.19.n正规表达式正规表达式 、正规集、正规集、 NFA、 DFAn2.4 正规式到有限自动机的构造正规式到有限自动机的构造 P19.27.n正规式正规式 NFA DFA 最简最简DFAn2.5 词法分析器的自动生成工具词法分析器的自动生成工具LEX P27.29.重点难点掌握重点难点掌握重点掌握重点掌握重点掌握重

4、点掌握Ch3词法分析5词法分析词法分析涉及的概涉及的概念及关系念及关系读扫描分解识别读扫描分解识别, 构词规则构词规则源程序源程序(字符串字符串)单词符号串单词符号串词法分析程序词法分析程序(扫描器扫描器)输入输入输出输出输入输入, 扫描扫描 (2.1)单词分类及其单词分类及其内部表示内部表示(2.1)自动生成工具自动生成工具LEX，用正规式描述单，用正规式描述单词词, 扫描器象有限自动机一样工作扫描器象有限自动机一样工作(2.5)生成生成描述描述工具工具手工生成手工生成(2.1，2.2)状态转换图状态转换图用程序实现用程序实现, 即扫描器即扫描器自动生成自动生成(2.3，2.4) 正规式正规

5、式, 正规集正规集有限自动机有限自动机 DFA NFACh3词法分析62.1 2.1 词法分析器的设计方法词法分析器的设计方法-输入、预处理输入、预处理n词法分析器工作的第一步是输入源程序。词法分析器工作的第一步是输入源程序。n输入串一般放在一个输入串一般放在一个输入缓冲区输入缓冲区中。词法分析器的中。词法分析器的工作可以直接在输入缓冲区中进行。但在许多情况工作可以直接在输入缓冲区中进行。但在许多情况下，可以先预处理输入串，识别工作将更方便。下，可以先预处理输入串，识别工作将更方便。n预处理工作预处理工作包括对空白符、跳格符、回车符和换行包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，

6、及删除注解等。符等编辑性字符的处理，及删除注解等。n可以构造一个可以构造一个预处理子程序预处理子程序完成上面的工作。每当完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入指定的缓冲区字符，并将其装入指定的缓冲区 - 扫描缓冲区扫描缓冲区中。中。n这样分析器就可以在扫描缓冲区中直接进行单词符这样分析器就可以在扫描缓冲区中直接进行单词符号的识别工作。号的识别工作。Ch3词法分析7输入、预处理：词法分析第一步输入、预处理：词法分析第一步扫描缓冲区扫描缓冲区预处理程序预处理程序预处理预处理扫描识别扫描识别输入缓冲区输入缓冲区内存

7、内存源程序源程序文本文本外存外存读入读入词法分析程序词法分析程序扫描识别扫描识别Ch3词法分析8扫描缓冲区的结构扫描缓冲区的结构n词法分析器对扫描缓冲区进行扫描时一般词法分析器对扫描缓冲区进行扫描时一般使用两个使用两个指示器指示器，一个指向当前正在识别的单词的开始位置，一个指向当前正在识别的单词的开始位置 (首字符首字符)，另一个用于向前搜索以寻找单词的终点。，另一个用于向前搜索以寻找单词的终点。 ab123:=100； begin . 起点起点 搜索搜索n扫描缓冲区使用互补的两个半区，每个半区假设扫描缓冲区使用互补的两个半区，每个半区假设120个字符。个字符。n如果搜索指示器从单词起点出发搜

8、索到一个半区的如果搜索指示器从单词起点出发搜索到一个半区的边缘但尚未达到单词的终点，那么就调用预处理子边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的程序，令其把后续的120个字符装入另一个半区，搜个字符装入另一个半区，搜索指示器在另半区继续搜索。认定在另一半区一定索指示器在另半区继续搜索。认定在另一半区一定可以达到单词的终点，即对单词限定了长度。可以达到单词的终点，即对单词限定了长度。Ch3词法分析92.1.1 2.1.1 单词符号的分类和输出形式单词符号的分类和输出形式nP8. P8. 词法分析程序的功能：词法分析程序的功能：n输入源程序，扫描识别分解，输出单词符号输入源程序

9、，扫描识别分解，输出单词符号n程序语言的单词符号一般分为程序语言的单词符号一般分为5 5类：类：n(1) 保留字保留字 (也称关键字、基本字也称关键字、基本字)： 如如C语言中的语言中的 int，if，while，for 等。这些字保等。这些字保留了语言所规定的语义，是编译程序识别各类语留了语言所规定的语义，是编译程序识别各类语法成分的依据法成分的依据n(2) 标识符标识符：用来标记各种名字：常量、数组、：用来标记各种名字：常量、数组、类型、变量、过程、函数等，如变量名类型、变量、过程、函数等，如变量名 abc12 等等 问题：问题：标识符和名字的区别？标识符和名字的区别？Ch3词法分析101

10、. 1. 单词符号的分类单词符号的分类nP9.P9.程序语言的单词符号一般分为程序语言的单词符号一般分为5 5类：类：n(3) 常数常数：包括各种类型的常数，如：包括各种类型的常数，如 256，3.14，true,abc 等等n(4) 运算符运算符：如：如 、*、/ 、= 等等n(5) 分界符分界符：在语言中作为语法上的分界符使用，：在语言中作为语法上的分界符使用，如如 逗号，分号，冒号，圆括号，空白符号等逗号，分号，冒号，圆括号，空白符号等n注意：注意：一个程序语言的保留字、运算符和界一个程序语言的保留字、运算符和界符的个数是确定的；而标识符和常数的使用符的个数是确定的；而标识符和常数的使用

11、则不限定个数。则不限定个数。Ch3词法分析11nP9. P9. 单词符号的内部表示是单词符号的内部表示是二元式二元式： n单词种别单词种别通常用整数编码通常用整数编码n单词种别码提供给语法分析程序使用。单词种别码提供给语法分析程序使用。n一个语言的单词符号如何分种，分成几种，怎一个语言的单词符号如何分种，分成几种，怎样编码，取决于处理上的方便。样编码，取决于处理上的方便。n单词符号自身的属性值也称内码值单词符号自身的属性值也称内码值 指单词符指单词符号的特征值，号的特征值，是编译中其他阶段如语义分析是编译中其他阶段如语义分析阶段所需要的信息。阶段所需要的信息。2. 单词符号的输出形式单词符号的

12、输出形式Ch3词法分析12nP9.P9.单词种别如何编码？单词种别如何编码？n标识符标识符一般统归为一种。一般统归为一种。n常数常数则宜按类型（整、实、布尔等）分种。则宜按类型（整、实、布尔等）分种。n保留字保留字可视其全体为一种，也可以一字一种。采可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。用一字一种的分法实际处理起来较为方便。n运算符运算符可采用一符一种的分法，但也可以把具有可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。一定共性的运算符视为一种。n界符界符一般采用一符一种的分法。一般采用一符一种的分法。n例例: P11.: P11.表表2.1

13、2.1 C C语言子集的单词种别编码语言子集的单词种别编码单词符号的种别编码单词符号的种别编码Ch3词法分析13单词符号自身的属性值单词符号自身的属性值nP9.P9.单词符号自身的属性值规定：单词符号自身的属性值规定： n如果一个种别只含如果一个种别只含一个一个单词符号，那么种别编码单词符号，那么种别编码就完全代表了这个单词符号，因而不需要属性值。就完全代表了这个单词符号，因而不需要属性值。n如果一个种别含有如果一个种别含有多个多个单词符号，那么对于它的单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应给每个单词符号，除了给出种别编码之外，还应给出有关单词符号的出有关单词符号的属性

14、值属性值，以便把同一种别的单，以便把同一种别的单词区分开来。词区分开来。n注意：标识符的属性值注意：标识符的属性值可以是标识符自身的字符可以是标识符自身的字符串，也可以是指向符号表入口的指针；串，也可以是指向符号表入口的指针；常数的属常数的属性值性值可以是常数本身的二进制数值，也可以是指可以是常数本身的二进制数值，也可以是指向常数表入口的指针。向常数表入口的指针。n例例: P11.: P11.表表2.1 2.1 C C语言子集的单词内码值语言子集的单词内码值Ch3词法分析14单词符号的分类和输出形式：单词符号的分类和输出形式：例子例子nC C代码段：代码段： while (i=10) i- -

15、;while (i=10) i- -;经词法分析器处理后，它将转换为如下的单词符经词法分析器处理后，它将转换为如下的单词符号二元式序列：号二元式序列：如标识符单词如标识符单词 i 对对应的二元组应的二元组 100 i地址地址名字名字符号表符号表5 = , _ 见见P11.表表2.1，使用了助记符，使用了助记符Ch3词法分析152.1.2 状态转换图状态转换图(P9.)n在词法分析中，在词法分析中，状态转换图状态转换图用来：用来：n描述单词符号的结构描述单词符号的结构n识别单词符号识别单词符号n是设计词法分析器的重要工具是设计词法分析器的重要工具n手工生成词法分析程序的方法手工生成词法分析程序的

16、方法: 转换转换 实现实现得到：词法分析程序得到：词法分析程序先构造：识别单词符号的状态转换图先构造：识别单词符号的状态转换图Ch3词法分析16状态转换图状态转换图nP9.P9.状态转换图是一张状态转换图是一张有限方向图有限方向图，只包含有，只包含有限个状态，即有限个结点。限个状态，即有限个结点。n结点代表结点代表状态状态，用，用圆圈圆圈表示表示n终止状态终止状态用用双圈双圈表示表示n初始状态初始状态前标记符号前标记符号“ ”来表示来表示n状态之间用状态之间用箭弧箭弧连结连结n箭弧上的箭弧上的标记标记代表在射出结点即箭弧始结点状态代表在射出结点即箭弧始结点状态下可能出现的输入字符或字符类，箭弧

17、标记可看下可能出现的输入字符或字符类，箭弧标记可看成成状态转换的条件状态转换的条件。Ch3词法分析17状态转换图例：状态转换图例： P9.图图2-2n该状态转换图表示该状态转换图表示, , 在状态在状态1 1下下: :n若输入字符为若输入字符为x，则读进，则读进x，并转，并转换到状态换到状态2。n若输入字符为若输入字符为y，则读进，则读进y，并转，并转换到状态换到状态3。n若输入字符非若输入字符非x和非和非y，则此转换，则此转换图不工作。图不工作。231y yx x状态转换图的作用：状态转换图的作用：描述单词符号的结构，描述单词符号的结构，识别单词符号。识别单词符号。Ch3词法分析18状态转换

18、图识别标识符：状态转换图识别标识符：P10.P10.图图2-3(a)2-3(a)n该状态转换图描述了单词符号该状态转换图描述了单词符号“标识符标识符”的结构。的结构。标识符标识符是字母打头的字母数字串。是字母打头的字母数字串。n该该转换图识别标识符的过程转换图识别标识符的过程是是: 从初态从初态0开始，若在开始，若在状态状态0下输入字符是字母，则读进它，并转入状态下输入字符是字母，则读进它，并转入状态1。在状态在状态1之下，若输入字符为字母或数字，则读进它，之下，若输入字符为字母或数字，则读进它，并重新进入状态并重新进入状态1。一直重复这个过程直到发现输入。一直重复这个过程直到发现输入字符不再

19、是字母或数字时字符不再是字母或数字时(该字符已被读进该字符已被读进)就进入终就进入终态态2，识别结束。，识别结束。12字母或数字字母或数字0*其他其他字母字母Ch3词法分析19状态转换图识别标识符状态转换图识别标识符: 续续n识别标识符识别标识符的状态转换图的状态转换图2-3(a)中，状态中，状态2是终态，是终态，它意味着到此已经识别出一个标识符。它意味着到此已经识别出一个标识符。n终态上打个终态上打个*号号，表示多读进了一个不属于标识符部，表示多读进了一个不属于标识符部分的其他字符，应把它退还给输入串。分的其他字符，应把它退还给输入串。n如果在状态如果在状态0时输入字符不为时输入字符不为“字

20、母字母”，则意味着这，则意味着这个转换图不工作。个转换图不工作。12字母或数字字母或数字0*其他其他字母字母考虑，如何识别考虑，如何识别 abc123x:=10中的标识符中的标识符abc123xCh3词法分析20状态转换图识别无符号整数：状态转换图识别无符号整数：P10.P10.图图2-3(b)2-3(b)n该状态转换图描述了单词符号该状态转换图描述了单词符号“无符号整数无符号整数”的结的结构。构。无符号整数无符号整数是不带是不带+、-符号的由符号的由09数字构成的数字构成的数字串，如数字串，如 123456 等。等。n识别无符号整数识别无符号整数的转换图中，的转换图中，0为初态，为初态，2为

21、终态，为终态，打了打了*号。号。n识别的过程识别的过程类似于识别标识符。类似于识别标识符。1 12 2数字数字0 0* *其他其他数字数字Ch3词法分析21状态转换图识别状态转换图识别无符号数：无符号数：P10.P10.图图2-3(c)2-3(c)5其他其他数字数字617数字数字0*234其他其他 E. E+或或-数字数字数字数字.数字数字数字数字数字数字n该状态转换图可以该状态转换图可以识别下面形式的一些无符号数识别下面形式的一些无符号数: 123.，.123， 123.456， 123.E3，123.456E-3 等等等等n识别的过程识别的过程类似于识别标识符。类似于识别标识符。Ch3词法

22、分析22 状态转换图的实现状态转换图的实现nP10. P10. 状态转换图容易用程序实现状态转换图容易用程序实现。n办法是让办法是让每个状态结点对应一段程序每个状态结点对应一段程序。n转换图与程序结构之间存在下述对应关系：转换图与程序结构之间存在下述对应关系：n 初态初态对应程序的开始；对应程序的开始；n 终态终态对应程序的结束，一般是一条对应程序的结束，一般是一条返回语句返回语句，不同的终态对应不同的返回语句；不同的终态对应不同的返回语句；n 分叉状态分叉状态对应对应情形情形或者或者条件语句条件语句；n 转换图中的转换图中的环环对应程序中的对应程序中的循环语句循环语句；n状态转换图可看成一个

23、抽象的程序流程图。状态转换图可看成一个抽象的程序流程图。Ch3词法分析23 状态结对应程序段的编写状态结对应程序段的编写(1)nP10.P10.不含回路的分叉结不含回路的分叉结对应条件或情形语句对应条件或情形语句n状态结状态结 i i 对应的程序段对应的程序段: : s=getchar( ); 读当前字符到变量读当前字符到变量s if( IsLetter(s) 状态状态j对应的程序段对应的程序段 else if(IsDigit(s) 状态状态k对应的对应的 程序段程序段 else 错误处理程序段错误处理程序段 或接其他状态图的程序或接其他状态图的程序 n参见参见P10. SwitchP10.

24、Switch语句的程序段语句的程序段 j数字数字i字母字母kP11.图图2-4(a)的状态结的状态结 iCh3词法分析24 状态结对应程序段的编写状态结对应程序段的编写(2)nP10.P10.含回路的状态结含回路的状态结 对应循环语句对应循环语句n状态结状态结 i i 对应的程序段对应的程序段: : s=getchar( ); 读当前字符到变量读当前字符到变量s while(IsLetter(s) | IsDigit(s) concatenation(s); 拼接单词拼接单词 s=getchar( ); ; 状态状态 j 对应的程序段对应的程序段;n参见参见P11. whileP11. whi

25、le语句的程序段语句的程序段 其它其它ij字母或字母或数字数字 P11.图图2-4(b)的状态结的状态结 iCh3词法分析25 状态结对应程序段的编写状态结对应程序段的编写(3)n初态结初态结(如如P12.图图2-5中的状态中的状态0)，要作一些初始化要作一些初始化的工作的工作，比如：设置指示器的值，对变量进行初始，比如：设置指示器的值，对变量进行初始化等。化等。nP11. P11. 终态结终态结对应对应return(Code,Value)语句语句，返回单，返回单词符号的内部表示二元式给语法分析器。词符号的内部表示二元式给语法分析器。n带带* *号的终态结号的终态结多读进了一个不属于现行单词符

26、多读进了一个不属于现行单词符号的字符，这个字符应退回输入串，即搜索指示器号的字符，这个字符应退回输入串，即搜索指示器要回调一个字符位置，这时除了要回调一个字符位置，这时除了Return外，还要将外，还要将搜索指示器回调一个字符位置，这可以由一个搜索指示器回调一个字符位置，这可以由一个过程过程来完成。来完成。Ch3词法分析26 状态结对应程序段的编写状态结对应程序段的编写(4)n多种单词出口的终态结多种单词出口的终态结，如，如P12.图图2-5中的状态中的状态2，既是标识符的出口又是保留字的出口，为了确认到既是标识符的出口又是保留字的出口，为了确认到底是保留字还是用户自定义的标识符，需要对识别底

27、是保留字还是用户自定义的标识符，需要对识别出的单词符号查询保留字表，这可以由一个出的单词符号查询保留字表，这可以由一个整型函整型函数过程数过程来完成。若函数值为来完成。若函数值为0，则表示是一个标识，则表示是一个标识符；否则，表示是保留字的种别编码。符；否则，表示是保留字的种别编码。n在在识别标识符识别标识符的过程中，要把标识符拼写出的过程中，要把标识符拼写出来，并和保留字区别开来；在来，并和保留字区别开来；在识别常数识别常数的过的过程中，要把它转换成机器表示以作为属性值。程中，要把它转换成机器表示以作为属性值。Ch3词法分析272.2 2.2 一个简单的词法分析器示例一个简单的词法分析器示例

28、nP11. P11. 一个非常重要的事实是，一个非常重要的事实是，大多数程序语大多数程序语言的单词符号都可以用状态转换图予以识别言的单词符号都可以用状态转换图予以识别。n作为一个综合例子，作为一个综合例子，教材教材P11.15.构造了一构造了一个识别简单语言个识别简单语言(是是C语言子集语言子集)的所有单词符的所有单词符号的状态转换图，并给出了对应的词法分析号的状态转换图，并给出了对应的词法分析程序。程序。n希望同学们好好读一下这个例子。要求完成希望同学们好好读一下这个例子。要求完成的第一个实验的第一个实验 - 设计并实现一个小语言的设计并实现一个小语言的词法分析程序词法分析程序，就可以以这个

29、例子作参考。，就可以以这个例子作参考。Ch3词法分析282.2.1 C2.2.1 C语言子集的单词符号表示语言子集的单词符号表示nP11.表表2.1 C语言子集的单词符号及内部表示语言子集的单词符号及内部表示 注意：注意：定义有哪些单词符号及怎么编码的？定义有哪些单词符号及怎么编码的？n为了简化问题，对为了简化问题，对C语言子集作语言子集作几点限制几点限制: n 保留字不能作标识符。保留字不能作标识符。n 保留字视为特殊的标识符，不专设状态转换保留字视为特殊的标识符，不专设状态转换图来识别；但要图来识别；但要设保留字表设保留字表( (表表2.12.1中的前中的前5 5项项) )，当识别出一个标

30、识符以后要进一步确认是保留字当识别出一个标识符以后要进一步确认是保留字还是用户定义的标识符。还是用户定义的标识符。n 保留字、标识符、常数之间必须有间隔，用保留字、标识符、常数之间必须有间隔，用运算符、界符、空白符等分隔。运算符、界符、空白符等分隔。Ch3词法分析292.2.2 C2.2.2 C语言子集对应的状态转换图语言子集对应的状态转换图P12.图图2-5*7=-312字母字母0非字母与数字非字母与数字字母或数字字母或数字+数字数字数字数字空白空白*4非数字非数字569*10其他其他15其它其它8* 问题：问题：各个终各个终态识别什么单态识别什么单词符号？词符号？ 终态终态2识别识别 终态

31、终态4识别识别 终态终态5识别识别 终态终态9识别识别 终态终态10识别识别 终态终态15识别识别Ch3词法分析30 2.2.3 2.2.3 状态转换图的实现状态转换图的实现nP13. P13. 容易由状态转换图容易由状态转换图编写词法分析程序，编写词法分析程序，办办法是让法是让每个状态结点对应一段程序每个状态结点对应一段程序。nP13. P13. 在编制程序的过程中需要引进了在编制程序的过程中需要引进了一组全局一组全局变量和过程变量和过程，将它们作为实现转换图即词法分，将它们作为实现转换图即词法分析程序的基本成分。析程序的基本成分。 1. character 字符变量字符变量, 存放最新读入

32、的源程序字符。存放最新读入的源程序字符。 2. token 字符数组，存放构成单词符号的字符串。字符数组，存放构成单词符号的字符串。 3. Getbe( ) 过程，若过程，若character中的字符为空白，则调中的字符为空白，则调用用getchar，直到，直到character为非空白字符。为非空白字符。Ch3词法分析31 4. Concatenation( ) 过程，将过程，将token中的字符串与中的字符串与character中的字符连接并作为中的字符连接并作为token中新的字符串。中新的字符串。P13. 设定一组全局变量和过程设定一组全局变量和过程(1) 5. Letter( ) 和

33、和 Digit( ) 布尔函数，分别判断布尔函数，分别判断character中的字符是否为字母或数字，是则返回中的字符是否为字母或数字，是则返回True, 否则返否则返回回False。 6. Reserve( ) 整型函数整型函数, 对对Token中的字符串查保留字中的字符串查保留字表表, 若它是保留字则返回其编码若它是保留字则返回其编码, 否则返回否则返回0值值(假定假定0不是保留字的编码不是保留字的编码), 表示是标识符。表示是标识符。 思考：思考：怎么连接？怎么连接？ 思考：思考：怎么设计保留字表的结构？怎么设计保留字表的结构？Ch3词法分析32 7. Retract( ) 过程，将搜索

34、指示器回调一个字符位置，过程，将搜索指示器回调一个字符位置，同时将同时将character置为空白字符。置为空白字符。 8. Buildlist( ) 整型函数，将整型函数，将Token中的标识符或常数中的标识符或常数登录到符号表或常数表，返回符号表或常数表指针。登录到符号表或常数表，返回符号表或常数表指针。P13. 设定一组全局变量和过程设定一组全局变量和过程(2) 思考：思考：符号表或常数表的结构符号表或常数表的结构？ 9. Error( ) 整型函数，出现非法字符，显示出错信息。整型函数，出现非法字符，显示出错信息。 10. Getchar( ) 过程，将下一个输入字符读到过程，将下一个

35、输入字符读到character中，搜索指示器前移一个字符位置。中，搜索指示器前移一个字符位置。Ch3词法分析33 构造图构造图2-5对应的词法分析程序对应的词法分析程序(P13.)n0 0状态状态对应的程序段：整个程序从开始到结束对应的程序段：整个程序从开始到结束n是初态：作初始化工作是初态：作初始化工作 token=; s=getchar( );n有分叉：对应整个程序的分支结构有分叉：对应整个程序的分支结构 switchcasecasedefaultn含回路：有循环，用过程含回路：有循环，用过程Getbe( )实现实现n1 1状态状态含回路，对应含回路，对应P13.P13.的的case a:

36、 case z: 分支中的循环语句分支中的循环语句 While(Letter( ) | Digit( ) Ch3词法分析34 图图2-5对应的词法分析程序对应的词法分析程序(P13.)n2 2状态状态 对应对应P13.P13.语句语句Retract( )Retract( )开始到开始到P14.P14. 语语句句case 0:case 0:之前的部分之前的部分n是带是带*号的终态号的终态: 调用了调用了Retract( )过程回调指针过程回调指针n是标识符和保留字的识别态是标识符和保留字的识别态: 调用了调用了Reserve( )函函数并且作判断数并且作判断 if (c = = 0) build

37、list( ); n是终态是终态: 用用Return( id, 指向指向id的符号表入口指针的符号表入口指针)返回标识符的内部表示，用返回标识符的内部表示，用Return(保留字码保留字码, null)返回保留字的内部表示返回保留字的内部表示n3 3状态状态 含回路，对应含回路，对应P14.P14.的的case 0: case 9：分支中的循环语句分支中的循环语句 While(Digit( ) Ch3词法分析35 构造图构造图2-52-5对应的词法分析器对应的词法分析器(P14.)(P14.)n4 4状态状态 带带*号的终态，整常数的识别态，对应号的终态，整常数的识别态，对应P14. case

38、 0: case 9：分支中的语句：分支中的语句 Retract( )；buildlist( ); Return(num,num的常数表入口指针的常数表入口指针)； n1515状态状态 识别错误识别错误, 对应对应P15. default: 分支中的语句分支中的语句error( )n说明说明: 这段程序执行一次这段程序执行一次, 只能识别出一个单词符号只能识别出一个单词符号, 它作为语法分析器调用的一个子程序。它作为语法分析器调用的一个子程序。n思考：思考：如果作为一个独立执行的程序，要求把源程如果作为一个独立执行的程序，要求把源程序的单词符号都输出来，该怎么办？序的单词符号都输出来，该怎么办

39、？Ch3词法分析36 2.3 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介n为了更好地使用状态转换图构造词法分析器，为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生成，还需要为了讨论词法分析器的自动生成，还需要将将状态转换图的概念形式化状态转换图的概念形式化。n2.32.3节主要讨论词法分析器自动产生所需要的节主要讨论词法分析器自动产生所需要的工具工具, , 将引入：正规表达式，正规集，有限将引入：正规表达式，正规集，有限自动机等概念。自动机等概念。n2.42.4节讨论正规表达式与有限自动机的等价性。节讨论正规表达式与有限自动机的等价性。n2.32.3节及节及

40、 2.42.4节是本章的节是本章的重点和难点重点和难点。Ch3词法分析37 2.3 2.3节与节与2.42.4节的主要概念及关系节的主要概念及关系单词符号的单词符号的结构结构状态转换图状态转换图描述描述词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现正规表达式正规表达式 E 表示表示 (2.3.1)用用正规集正规集L(E)(2.3.1)表达式表达式 值的集值的集有限自动机有限自动机 FA M单词符号集单词符号集L(M)形式化形式化识别识别,接受接受DFA(2.3.2)最少化最少化(2.4.3)NFA (2.3.2)确定化确定化 (2.4.2)两者相同两者相同等价等价(2.4.1，2.4

41、.4)Ch3词法分析38字母表与符号（字母表与符号（参见参见P16.P16.）n在引入正规表达式之前先介绍几个关于字母在引入正规表达式之前先介绍几个关于字母表、符号、符号串、符号串集合、符号串集表、符号、符号串、符号串集合、符号串集合的运算等概念。合的运算等概念。n字母表字母表 是元素的非空是元素的非空有穷集合。有穷集合。n字母表记为字母表记为 。n例如，由例如，由26个英文字母组成的集合是一个字母表。个英文字母组成的集合是一个字母表。n字母表字母表 的每个元素称为一个的每个元素称为一个符号符号。n例如，例如，26个英文字母中的个英文字母中的a、b、c等都称为符号。等都称为符号。Ch3词法分析

42、39符号串及其集合符号串及其集合n 上的一个上的一个符号串符号串(也称也称字字)是指由是指由 中的符号所构中的符号所构成的有穷序列。成的有穷序列。n例如，字母表例如，字母表 中的符号组成的序列中的符号组成的序列compiler、string、symbol等都是符号串。等都是符号串。n 不包含任何符号的符号串称为不包含任何符号的符号串称为空符号串空符号串(也称也称空空字字)，记为，记为 。n 用用 *表示表示 上的所有符号串的全体上的所有符号串的全体(符号串集合，符号串集合， 的闭包的闭包)，空字，空字 也包括在其中。也包括在其中。 用用 +表示表示 上的所有符号串的全体上的所有符号串的全体(符

43、号串集合，符号串集合， 的正闭包的正闭包)，空字，空字 不包括在其中。不包括在其中。Ch3词法分析40n用用 表示不含任何元素的空集合表示不含任何元素的空集合 。n注意注意 、 和和 的区别的区别。n例例1 1：令：令=a,b, =a,b, 则则*=, a, b, aa, ab, ba, bb, aaa, +=a, b, aa, ab, ba, bb, aaa, aab, n例例2: 2: 令令=0,1,2,3,4,5,6,7,8,9, =0,1,2,3,4,5,6,7,8,9, 则则 * = 0 9 构成的所有数字串构成的所有数字串 + = 0 9 构成的所有数字串构成的所有数字串 符号串集

44、合：例符号串集合：例Ch3词法分析41n 符号串集合的乘积符号串集合的乘积 *的子集的子集R和和S的的(连接连接)乘积乘积定义为定义为: R S= R & S 即集合即集合R S中的符号串是由中的符号串是由R和和S的符号串连接而的符号串连接而成，成， 号可以省略。号可以省略。 一般一般 RS SR，但，但(RS)W=R(SW)。n 符号串集合的方幂符号串集合的方幂 R自身的自身的n次连接积次连接积( n次方幂次方幂)记为：记为： Rn = R R R (n个个R的积的积) 规定规定 R0 = 。符号串集的运算（符号串集的运算（1）Ch3词法分析42n 符号串集合的符号串集合的自反闭包自

45、反闭包( (闭包闭包) )R* * R* = R0 R1 R2 n 符号串集合的符号串集合的正则闭包正则闭包( (正闭包正闭包) )R+ + R+ = R1 R2 R3 n显然：显然：R+ = RR* = R*R R* = R+ = R+ nR*、R+中的每个符号串都是由中的每个符号串都是由R中的符号串经中的符号串经有限次连接而成的。有限次连接而成的。符号串集的运算（符号串集的运算（2）Ch3词法分析43n设字母表设字母表=a,b,0,1令令 *的子集的子集 R=10,ab, S=001 计算计算 RS，SR，RS，R2，R0，S * ，S + 。 符号串集运算：例及练习符号串集运算：例及练习

46、n解：解：RS=10001, ab001 SR=00110, 001ab RS=10, ab, 001 R2 =1010, 10ab, ab10, abab R0 = S * =, 001, 001001, 001001001, S + = 001, 001001, 001001001, Ch3词法分析442.3.1 2.3.1 正规表达式与正规集正规表达式与正规集nP15.P15.正规表达式正规表达式，简称，简称正规式正规式。n它是状态转换图的一种形式化表示方法它是状态转换图的一种形式化表示方法n它可以描述单词符号的结构它可以描述单词符号的结构n它能精确地定义单词符号集它能精确地定义单词符号

47、集 - 称称正规集正规集n本小节主要内容本小节主要内容n正规式与正规集的定义正规式与正规集的定义n正规式的等价及判断正规式的等价及判断n由正规式写正规集由正规式写正规集n由正规集写正规式由正规集写正规式Ch3词法分析45P15. 正规式与正规集的递归定义正规式与正规集的递归定义 . . 正规表达式正规表达式 正规式表示的正规式表示的正规集正规集 . . (1). ， ， (2). a a (3). 若若 R, S L( R ) , L(S) 则则 选择选择 R S L( R ) L( S ) 连接连接 R.S L( R ) . L( S ) 闭包闭包 R * ( L( R ) )* 括号括号

48、( R ) L( R ) (4).Ch3词法分析46正规式运算符的优先级正规式运算符的优先级nP16.P16.正规式运算符优先级正规式运算符优先级由高到低依次是由高到低依次是: :n括号最优先括号最优先n闭包闭包 * R*表示表示R作任意有限次作任意有限次(包括包括0次次)的连接的连接n连接连接 n选择选择 |n注：注：还可以引入还可以引入正则闭包正则闭包+ +，R R+ +表示表示R R作任意作任意有限次有限次( (至少一次至少一次) )的连接。的连接。nR R+ += R R= R R* *n R R* *= = R R+ +Ch3词法分析47正规式等价的定义和性质正规式等价的定义和性质n

49、P16. 若两个正规式若两个正规式R和和S所表示的正规集相同，所表示的正规集相同，即即L(R) =L(S) ，则认为二者，则认为二者等价等价，记为，记为R=S。n正规式的性质：正规式的性质：恒等式恒等式(等价式等价式)说明说明R|S=S|R“|”是可交换的是可交换的(R|S)|T=R|(S|T)“|”是可结合的是可结合的(RS)T=R(ST)连接是可结合的连接是可结合的R(S|T)=RS|RT (R|S)T=RT|ST分配律分配律R=R R=R同一律同一律Ch3词法分析48由正规式写正规集由正规式写正规集: 例例2.1nP16.P16. 令令=a=a，bb，设，设R=a(a|b)R=a(a|b

50、)* *是是上的上的正正规式，试求其表示的正规集。规式，试求其表示的正规集。n解：解： L(R) = L(a(a|b)*) = L(a)(L(a|b)* = L(a)(L(a) L(b)*=a(a b)* = aa,b* = a, a, b, aa, ab, ba, bb, aaa, = a, aa, ab, aaa, aab, aba, abb, aaaa, 注意：注意：符是些集合符是些集合的运算和变换！的运算和变换！Ch3词法分析49由正规式写正规集例：设由正规式写正规集例：设 = a,b 正规式正规式 正规集正规集 . a b a, b (a b)(a b) aa, ab, ba, bb

51、 a* , a, aa, aaa, aaaa, = an | n0 (a b)* , a, b, aa, ab, ba, bb, aaa,. = a, b* ba* 上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字的字 (a|b)*a 上所有以上所有以a为尾的字为尾的字 (a|b)*(aa|bb)(a|b)* 上所有含有两上所有含有两个相继的个相继的a 或两个相继的或两个相继的b 的字的字Ch3词法分析50由正规式写正规集由正规式写正规集: : 练习练习n 令令=A, B, 0, 1 , 问问: 正规式正规式 , , 0 , 110 , 0|1 , 1*，(A|B)(A|B|0|1

52、)* 和和 (0|1)(0|1)*表示的正规集分别是什表示的正规集分别是什么么?解答解答: 正规式正规式 , , 0 , 110 , 0|1 , 1* 表示的表示的正规集分正规集分别是别是 , , 0, 110, 0,1, , 1, 11, 111, =1* =1n | n0。 正规式正规式 (0|1)(0|1)*表示的正规集是表示的正规集是上上“数数”的全体的全体 =0, 1.0, 1* 正规式正规式 (A|B)(A|B|0|1)*表示的正规集是表示的正规集是上的上的“标识标识符符”的全体的全体 =A, B.A, B, 0, 1*Ch3词法分析51正规式等价的判断和证明：例正规式等价的判断和

53、证明：例2.2nP16. P16. 判断下述正规式之间是否等价判断下述正规式之间是否等价n(1) (a|b)*与与a*|b* 不等价不等价 因为因为 (a|b)*对应的正规集为对应的正规集为 a, b*； 而而 a*|b*对应的正规集为对应的正规集为 a* b*。n(2) (ab)*与与a*b* 不等价不等价 因为因为 (ab)*对应的正规集为对应的正规集为 ab*； 而而 a*b*对应的正规集为对应的正规集为 a* b*。n(3) (a|b)*与与(a*b*)* 等价等价 因为因为 (a|b)*对应的正规集为对应的正规集为 a, b*； 而而 (a*b*)*对应的正规集也为对应的正规集也为

54、a, b*。Ch3词法分析52正规式等价的证明：例正规式等价的证明：例2.3nP17. P17. 设设L(a+)=a*-，则有，则有a+=aa*。n证明：证明： 要证明要证明a+=aa*，只要证明，只要证明L(a+)=L(aa*)nL(a+) = a*- = , a, a2, a3, - = a, a2 ,a3 , = a , a, a2 , = a a* = L(a) L(a*) = L(aa*)n证明两个正规式等价的方法证明两个正规式等价的方法：用定义：正规用定义：正规集相等；集相等； 正规式对应的有限自动机相同。正规式对应的有限自动机相同。Ch3词法分析53写正规表达式写正规表达式: 例

55、例 1. 给出下列在字母表给出下列在字母表0, 1上的正规式：上的正规式：n所有以所有以00结束的串的集合。结束的串的集合。 n由正规集写正规式的方法：由正规集写正规式的方法：分析正规集中符分析正规集中符号串的结构特点号串的结构特点, , 试着写出正规式；试着写出正规式； 验证是否验证是否能表示符号串能表示符号串, , 不断调整正规式直到正确。不断调整正规式直到正确。 2. 写字母表写字母表a, b上的正规式：每个上的正规式：每个a都至少有一个都至少有一个b直接跟在其右边。直接跟在其右边。n 所有具有三个所有具有三个0的串的集合。的串的集合。解解: (0|1)*00解解: 1*01*01*01

56、*解解: b*(abb*)* 或或 b*(ab+)* Ch3词法分析54写正规表达式写正规表达式: 练习练习n1. 1.给出下列在字母表给出下列在字母表a,ba,b上的正规式：以上的正规式：以b b开开头，后跟若干个头，后跟若干个( (至少至少1 1个个)ab)ab的符号串的集合。的符号串的集合。 解解: bab(ab)* 或或 b(ab)+解解: a(aa)*bb(bb)*a(aa)* n2. 2. P29.P29.题题2.5(1).2.5(1).写出描述语言写出描述语言 L(G)= aL(G)= a2n+12n+1b b2m2ma a2p+12p+1|n|n 0, p0, p 0, m0,

57、 m 1 1 的正规式。的正规式。Ch3词法分析552.3.2 有限自动机有限自动机(FA)n有限自动机有限自动机是描述符号串处理的强有力工具，是描述符号串处理的强有力工具，是研究词法分析器的重要基础。是研究词法分析器的重要基础。n有限自动机有限自动机(FA)(FA)分为分为确定有限自动机确定有限自动机(DFA)(DFA) 和和不确定有限自动机不确定有限自动机(NFA)(NFA) 。n本小节主要内容本小节主要内容nDFA、NFA的定义及区别的定义及区别nFA M 表示为状态转换图和状态转换矩阵表示为状态转换图和状态转换矩阵nFA M 识别字、空字识别字、空字、识别的语言、识别的语言 L(M)C

58、h3词法分析56 1. 确定有限自动机确定有限自动机(DFA Md)nP17. 一个确定有限自动机一个确定有限自动机 DFA Md是一个五元组：是一个五元组： Md= (S, , f, s0 , Z) (1) S 有限状态集。有限状态集。 (2) 有穷有穷字母表字母表，输入字符集，输入字符集。 (3) f 状态转换函数；状态转换函数；从从 S 至至 S 的单值映射的单值映射。 f (si, a)= sj 表示：当现行状态为表示：当现行状态为 si, 输入字符为输入字符为 a时，时，将转换到下一个状态将转换到下一个状态 sj 。称。称 sj为为 si的后继状态。的后继状态。DFA的的后继状态是唯

59、一确定的后继状态是唯一确定的, 故称为确定有限自动机故称为确定有限自动机。 (4) s0 S，唯一的初态。，唯一的初态。 (5) Z S，终态集，终态集(可空可空)。n例：例：P17. 图图2-6，DFA Md的的状态转换函数。的的状态转换函数。Ch3词法分析572. 非确定有限自动机非确定有限自动机(NFA)nP17.一个非确定有限自动机一个非确定有限自动机NFA Mn是一个五元组：是一个五元组： Mn= ( S，f，Q，Z ) (1) S 同同 DFA ，有限状态集。，有限状态集。 (2) 同同 DFA，有穷字母表，输入字符集。，有穷字母表，输入字符集。 (3) f 状态转换函数：从状态转

60、换函数：从 S* 到到 S 的子集的映射的子集的映射 即即 f：S*2s 意味着意味着 f (si,)= s1, s2, , sm ，可以是空字可以是空字。 (4) Q S，非空的初态集。，非空的初态集。 (5) Z S，终态集，终态集(可空可空)。n例：例：P18. 图图2-7，NFA Mn的状态转换函数。的状态转换函数。Ch3词法分析58P17. DFA与与NFA的联系与区别的联系与区别nDFA是是NFA的特例的特例。nDFA与与NFA的区别的区别: n 初态初态数目，是否是集合数目，是否是集合n 状态转换函数状态转换函数f：DFA： S S f (si, a)= sj a是一个符号是一个符号NF