CH3词法分析.ppt

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

1、第三章第三章 词法分析词法分析 程程 序序 设设 计计 语语 言言 2023/1/21Ch3.词法分析本章在编译程序中的地位本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2回顾回顾:词法分析词法分析n任任务务：从从左左到到右右一一个个字字符符一一个个字字符符地地读读入入源源程程序序，对对构构成成源源程程序序的的字字符符流流进进行行扫扫描描和和分分解解，从而识别出一个个从而识别出一个个单词单词符号符号。逻辑上紧密相连的一组字符，逻辑上紧密相连的一组字符，这些字符具有集体含义。这些字符具有集体含义。

2、n单词单词：标识符，保留字，常数，算符，界符标识符，保留字，常数，算符，界符n词词法法分分析析阶阶段段的的工工作作所所依依循循的的是是语语言言的的词词法法规规则则。描描述述词词法法规规则则的的有有效效工工具具是是正正规规式式和和有有限限自动机自动机。3CH.3 CH.3 词法分析词法分析n掌掌握握：正正规规式式、状状态态转转换换图图、有有限限自自动动机机的的概概念念,将将NFANFA转转换换为为DFADFA、DFADFA的的化化简简、正正规规式式与与有有限限自自动动机机间间的的转转换换、正正规规文文法法与与有有穷穷自自动动机机间间的的转转换换，词词法法分分析析程程序序的的功功能能和和设设计方法

3、。计方法。n了解了解理解理解：词法分析器的自动产生工具词法分析器的自动产生工具LEXLEX。n主要教学内容：主要教学内容：n3.1 词法分析器的功能、输出形式和结构词法分析器的功能、输出形式和结构n3.2 词法分析程序的设计方法词法分析程序的设计方法-重点重点 n3.3 正规表达式与有穷状态自动机正规表达式与有穷状态自动机-重点难点重点难点n3.4 词法分析器的自动产生词法分析器的自动产生 4 词法分析涉及的概念及关系词法分析涉及的概念及关系扫描识别扫描识别,依据构词规依据构词规则则源程序源程序(字符串字符串)单词符号串单词符号串词法分析程序词法分析程序(扫描器扫描器)输入输入输出输出输入输入

4、,扫描扫描 (3.2)预处理预处理,超前搜索超前搜索单词分类单词分类 (3.1)内部表示内部表示手工生成手工生成(3.2)自动生成自动生成(3.3)等等价价状态转换图状态转换图用程序实现用程序实现,即扫描器即扫描器正规式正规式,正规集正规集有限自动机有限自动机 DFA NFA自动生成工具自动生成工具LEX,用正规式描述用正规式描述,扫扫描器象描器象FA一样工作一样工作(3.4)生成生成描述描述工具工具等价等价53.1 3.1 对词法分析器的要求对词法分析器的要求3.1.1 3.1.1 词法分析器的词法分析器的功能和输出形式功能和输出形式n输入源程序，扫描识别输入源程序，扫描识别,输出单词符号输

5、出单词符号n程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：n关关 键键 字字(保保 留留 字字 或或 基基 本本 字字)：如如 begin,end,if,then,else,while,dobegin,end,if,then,else,while,do等等 n标识符标识符：用来表示各种名字，如：用来表示各种名字，如 X1X1n字面字面常数常数：如：如 256 256，3.143.14，true,true,abcabcn运算符运算符：如：如 、*、/等等等等n分分界符界符：如：如 逗号，分号，冒号等逗号，分号，冒号等6while ij do if ij then i:ij el

6、se j:=ji;例例词法分析器词法分析器输入输入输出输出while i j do if i j then i :=i jelse j :=j i ;7n单词符号的单词符号的内部表示是二元式内部表示是二元式：(词类种别编码词类种别编码,单词符号自身的属性值单词符号自身的属性值)n1.1.词词类类种种别别编编码码提提供供给给语语法法分分析析程程序序使用；使用；n2.2.单单词词自自身身的的属属性性值值提提供供给给语语义义分分析析程序使用。程序使用。n3.3.具具体体的的分分类类设设计计方方法法以以方方便便语语法法分分析程序使用为原则。析程序使用为原则。单词符号的内部表示单词符号的内部表示2023

7、/1/28Ch3.词法分析n单词种别单词种别通常用整数编码。通常用整数编码。n一一个个语语言言的的单单词词符符号号如如何何分分种种，分分成成几几种种，怎怎样样编码，取决于处理上的方便。编码，取决于处理上的方便。n标识符标识符一般统归为一种。一般统归为一种。n常数常数则宜按类型（整、实、布尔等）分种。则宜按类型（整、实、布尔等）分种。n关关键键字字可可视视其其全全体体为为一一种种，也也可可以以一一字字一一种种。采采用一字一种的分法实际处理起来较为方便。用一字一种的分法实际处理起来较为方便。n运运算算符符可可采采用用一一符符一一种种的的分分法法，但但也也可可以以把把具具有有一定共性的运算符视为一种

8、。一定共性的运算符视为一种。n界符界符一般采用一符一种的分法。一般采用一符一种的分法。n例例:参见参见P42.P42.表表3.1 3.1 单词符号及种别编码单词符号及种别编码单词符号：种别编码单词符号：种别编码9单词符号：单词自身属性值单词符号：单词自身属性值n单词符号的属性是指单词符号的单词符号的属性是指单词符号的特征值特征值 。n如如果果一一个个种种别别只只含含有有一一个个单单词词符符号号，那那么么对对于于这这个个单单词词符符号号，种种别别编编码码就就完完全全代代表表它它自自身了，因而不需要属性值。身了，因而不需要属性值。n若若一一个个种种别别含含有有多多个个单单词词符符号号，那那么么，对

9、对于于它它的的每每个个单单词词符符号号，除除了了给给出出种种别别编编码码之之外外，还应给出有关单词符号的还应给出有关单词符号的属性值属性值。n例例如如，对对于于标标识识符符，可可将将它它的的符符号号表表项项指指针针作作为为其其属属性性值值；对对于于常常数数，可可将将它它的的常常数数表表项指针作为其属性值。项指针作为其属性值。n例例:参见参见P42.P42.表表3.1 3.1 单词符号及属性值单词符号及属性值10例子例子n考虑下述考虑下述C+C+代码段：代码段：while(i=j)i-;while(i=j)i-;经经词词法法分分析析器器处处理理后后，它它将将转转换换为为如如下下的的单单词符号序列

10、：词符号序列：id,id,指向指向i i的符号表项的指针的符号表项的指针 =,-=,-100 i地址地址名字名字符号表符号表10如标识符单词如标识符单词 i 对对应的二元组应的二元组(6,10)113.1.2 3.1.2 词法分析器作为独立子程序词法分析器作为独立子程序n把把词词法法分分析析设设计计成成一一个个独独立立程程序序，每每当当语语法法分分析器需要一个单词符号时就调用这个子程序。析器需要一个单词符号时就调用这个子程序。n每每一一次次调调用用，词词法法分分析析器器从从源源程程序序字字符符串串中中识识别别出出一一个个单单词词符符号号，并并把把它它的的内内部部表表示示二二元元组组交给语法分析

11、器处理。交给语法分析器处理。如图所示：如图所示：词法分词法分析器析器语法分析器语法分析器语义分析和语义分析和中间代码生成器中间代码生成器源源程程序序中中间间代代码码123.2 3.2 词法分析器的设计词法分析器的设计n3.2.1 输入、预处理输入、预处理 处理源程序输入的技术处理源程序输入的技术n3.2.2 单词符号的识别：超前搜索单词符号的识别：超前搜索 识别单词符号的技术识别单词符号的技术n3.2.3 状态转换图状态转换图 单词符号结构的一种图形表示方法单词符号结构的一种图形表示方法 识别单词符号的一种方法识别单词符号的一种方法n3.2.4 状态转换图的实现状态转换图的实现 词法分析程序的

12、一种手工构造方法词法分析程序的一种手工构造方法 状态转换图状态转换图 词法分析程序词法分析程序133.2.1 3.2.1 输入、预处理输入、预处理n词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。n输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。词词法法分分析析器器的的工工作作可可以以直直接接在在输输入入缓缓冲冲区区中中进进行行。但但在在许许多多情情况况下下，可以先预处理输入串，识别工作将更方便。可以先预处理输入串，识别工作将更方便。n预预处处理理工工作作包包括括对对空空白白符符、跳跳格格符符、回回车车符符和和换换行行符符等编辑性字符的处理，及删除

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

14、识别扫描识别输入缓冲区输入缓冲区内存内存源程序源程序文本文本外存外存读入读入词法分析程序词法分析程序扫描识别扫描识别15扫描缓冲区的结构扫描缓冲区的结构n词词法法分分析析器器对对扫扫描描缓缓冲冲区区进进行行扫扫描描时时一一般般使使用用两两个个指指示示器器，一一个个指指向向当当前前正正在在识识别别的的单单词词的的开开始始位位置置,即即指指向向新新单单词词的的首首字字符符;另另一个用于向前搜索以寻找单词的终点。一个用于向前搜索以寻找单词的终点。n不不论论扫扫描描缓缓冲冲区区设设得得多多大大都都不不能能保保证证单单词词符符号号不不会会被被缓缓冲冲区区的的边边界界所所打打断断。因因此此，扫扫描描缓冲区

15、最好使用如下缓冲区最好使用如下一分为二的区域一分为二的区域：起点指示器起点指示器搜索指示器搜索指示器2023/1/216Ch3.词法分析在扫描缓冲区中扫描在扫描缓冲区中扫描n假假定定每每个个半半个个区区可可容容120120个个字字符符，而而这这两两个个半半区又是区又是互补互补的。的。n如如果果搜搜索索指指示示器器从从单单词词起起点点出出发发搜搜索索到到一一个个半半区区的的边边缘缘但但尚尚未未达达到到单单词词的的终终点点，那那么么就就调调用用预预处处理理子子程程序序，令令其其把把后后续续的的120120个个字字符符装装入入另一个半区。另一个半区。n认认定定在在另另一一半半区区一一定定可可以以达达

16、到到单单词词的的终终点点。这这意意味味着着对对标标识识符符和和常常数数的的长长度度实实际际上上必必须须加加以以限制，否则即使缓冲区再大也无济于事。限制，否则即使缓冲区再大也无济于事。23：=100；begin .ab1 起点起点搜索搜索17n下面通过单词符号：下面通过单词符号：n关键字的识别关键字的识别n标识符的识别标识符的识别n常数的识别常数的识别n算符的识别算符的识别n界符的识别界符的识别n介介绍绍单单词词符符号号识识别别的的一一个个简简单单方方法法-超超前前搜搜索索3.2.2 3.2.2 单词符号的识别：超前搜索单词符号的识别：超前搜索2023/1/218Ch3.词法分析关键字的识别关键

17、字的识别(1)n像像FORTRAN这这样样的的语语言言，关关键键字字的的识识别甚为麻烦。因为别甚为麻烦。因为n1.关关键键字字不不加加保保护护（只只要要不不引引起起矛矛盾盾，用用户可以用它们作为普通标识符）。户可以用它们作为普通标识符）。n2.关关键键字字和和用用户户自自定定义义的的标标识识符符或或标标号号之之间没有特殊的界符作间隔间没有特殊的界符作间隔。2023/1/219Ch3.词法分析关键字的识别关键字的识别(2)n下下面面是是几几个个FORTRAN的的正正确确语语句句，空空白白可可有有可无，不作分隔符可无，不作分隔符：1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO

18、99K=1.1 4 IF(5)=55n语语句句1和和2分分别别是是DO和和IF语语句句，它它们们都都是是以以某某关键字开头的。关键字开头的。n语语句句3和和4是是赋赋值值语语句句，它它们们都都是是以以用用户户自自定定义的标识符开头的。义的标识符开头的。20关键字的识别关键字的识别(3)1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55n为为了了从从语语句句1 1、2 2中中识识别别出出关关键键字字DODO和和IFIF，必必须要能够区别语句须要能够区别语句1 1、3 3和区别语句和区别语句2 2、4 4。n语语句句1 1、3 3的的区区别别在

19、在于于等等号号之之后后的的第第一一个个界界符符：一个为逗号，另一个为点符。一个为逗号，另一个为点符。n语语句句2 2、4 4的的主主要要区区别别在在于于右右括括号号后后的的第第一一个个字字符符：一一个个为为字字母母，另另一一个个为为等等号号。这这就就是是说说，为为了了识识别别 1 1、2 2句句中中的的关关键键字字，必必须须超超前前扫扫描描许许多多个个字字符符，超超前前到到能能够够肯肯定定词词性性的的地地方为止。方为止。21n对对于于1 1、3 3来来说说，尽尽管管都都以以DODO两两个个字字母母开开头头，但但不不能能一一见见DODO就就认认定定是是DODO语语句句。必必须须超超前前搜搜索索，

20、跳跳过过所所有有的的字字母母和和数数字字，看看看看是是否否有有等等号号。如如果果有有，再再向向前前搜搜索索。若若下下一一个个界界符符是是逗逗号号，则则可可以以肯肯定定DODO应应为为关关键键字字。否否则则，DODO不不构构成成关关键键字字，它它只只是是用用户户标标识识符符的的头头两两个个字字母母。所所以以为为了了区区别别1 1和和3 3，必必须须超超前扫描到等号后的第一个界符处前扫描到等号后的第一个界符处。n 对对于于2 2和和4 4来来说说，必必须须超超前前扫扫描描到到与与IFIF后后的的左左括括号号相相对对应应的的那那个个右右括括号号之之后后的的第第一一个个字字符符为为止止。若若此此字字符

21、符是是字字母母，则则得得逻逻辑辑IFIF。若若此此字字符符为为数数字字，则则得得算算术术IFIF。否否则则，应应认认为为是是用户自定义标识符用户自定义标识符IFIF。关键字的识别关键字的识别(4)22标识符、常数的识别标识符、常数的识别n标识符标识符的识别的识别 (参考参考P40,P41)n是是字字母母开开头头的的字字母母数数字字串串，后后跟跟算算符符或或界界符，识别不困难，例如符，识别不困难，例如 DO99K=1.10n常数常数的识别的识别n算算术术常常数数的的识识别别:多多数数语语言言很很直直接接，有有的的须须采用超前搜索，如采用超前搜索，如FORTRAN语言中：语言中：IF(5.EQ.M

22、)GOTO55-5.E08n逻辑逻辑(布尔布尔)常数的识别常数的识别:比较容易比较容易nFORTRAN文文字字常常数数的的识识别别:麻麻烦烦,须须作作特特殊处理殊处理23算符、界符的识别算符、界符的识别 (参考参考P40,P41)n算符算符的识别的识别n单个字符构成的算符的识别较容易单个字符构成的算符的识别较容易 如如 i*jn多多个个字字符符构构成成的的算算符符的的识识别别须须使使用用超超前前搜搜索索 如如 i*j界符的识别界符的识别 n界符界符的识别比较简单的识别比较简单2023/1/224Ch3.词法分析3.2.3 状态转换图状态转换图n状态转换图状态转换图用来：用来：n描述单词符号的结

23、构描述单词符号的结构n识别单词符号串识别单词符号串n是设计词法分析器的工具是设计词法分析器的工具n手工生成词法分析器的方法手工生成词法分析器的方法:转换转换 实现实现词法分析程序词法分析程序构造识别单词符号的状态转换图构造识别单词符号的状态转换图25状态转换图状态转换图n状状态态转转换换图图是是一一张张有有限限方方向向图图，只只包包含含有有限限个状态，个状态，即有限个结点。即有限个结点。n1.结点代表结点代表状态状态，用，用圆圈圆圈表示表示n2.终止状态终止状态用用双圈双圈表示表示n3.初始状态初始状态前标记符号前标记符号“”来表示来表示n4.状态之间用状态之间用箭弧箭弧连结连结n5.箭箭弧弧

24、上上的的标标记记代代表表在在射射出出结结点点即即箭箭弧弧始始结结点点状状态态下下可可能能出出现现的的输输入入字字符符或或字字符符类类，箭弧标记表示箭弧标记表示状态转换的条件状态转换的条件。2023/1/226Ch3.词法分析状态转换图：例状态转换图：例n例例 P41.图图3.2(a)表示：表示：n在在状状态态1下下，若若输输入入字字符符为为X，则则读读进进X，并并转转换换到到状状态态2。n若若输输入入字字符符为为y，则则读读进进y，并转换到状态并转换到状态3。n若若输输入入字字符符非非x和和非非y，则则此此转换图不工作。转换图不工作。231Y YX X一个状态转换图可用于识别一定的字符串一个状

25、态转换图可用于识别一定的字符串27状态转换图识别字符串：例状态转换图识别字符串：例1n例例1 1 P41.P41.图图3.2(3.2(b)b)，识识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态，为初态，2 2为终态。为终态。n这这个个转转换换图图识识别别标标识识符符的的过过程程是是:从从初初态态0 0开开始始，若若在在状状态态0 0下下输输入入字字符符是是字字母母，则则读读进进它它，并并转转入入状状态态1 1。在在状状态态1 1之之下下，若若输输入入字字符符为为字字母母或或数数字字，则则读读进进它它，并并重重新新进进入入状状态态1 1。一一直直重重复复这这个个过过程程直直到到

26、发发现现输输入入字字符符不不再再是是字字母母或数字时或数字时(这个字符已经被读进这个字符已经被读进)就进入状态就进入状态2 2。12字母或数字字母或数字0*其他其他字母字母28状态转换图识别字符串状态转换图识别字符串:例例n例例1 1 P41.P41.图图3.2(3.2(b)b)，识识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态，为初态，2 2为终态。为终态。n状状态态2 2是是终终态态，它它意意味味着着到到此此已已经经识识别别出出一一个个标标识识符符。终终态态上上打打个个*号号，表表示示多多读读进进了了一一个个不不属属于于标标识识符符部部分分的的字字符符，应应把把它它退退还

27、还给给输输入入串串。如如果果在在状状态态0 0时时输输入入字字符符不不为为“字字母母”，则意味着这个转换图不工作。则意味着这个转换图不工作。12字母或数字字母或数字0*其他其他字母字母29状态转换图识别字符串状态转换图识别字符串:例例2 2n例例2 P41.图图3.2(c)是是识识别别整整数数的的转转换换图图。其其中中0为初态，为初态，2为终态为终态,打了打了*号。号。n识别的过程类似前例。识别的过程类似前例。1 12 2数字数字0 0*其他其他数字数字2023/1/230Ch3.词法分析例例3 P41.图图3.2(d)是是一个一个识别识别FORTRAN实实型常数型常数的转换图。其中的转换图。

28、其中0为初态，为初态，7为终态。为终态。状态转换图识别字符串状态转换图识别字符串:例例3 3该转换图可以识别下面该转换图可以识别下面形式的一些实形式的一些实数数:123.,.123,123E3,123.456.123E+10,123.456E-3 等等5其他其他数字数字617数字数字0*234其他其他E或或D.E或或D+或或-数字数字数字数字.数字数字数字数字数字数字31状态转换图识别字符串状态转换图识别字符串:综合例综合例n一一个个非非常常重重要要的的事事实实是是，大大多多数数程程序序语语言言的的单词符号都可以用状态转换图予以识别单词符号都可以用状态转换图予以识别。n作作为为一一个个综综合合

29、例例子子，教教材材P42.46.构构造造了了一一个个识识别别某某个个简简单单语语言言的的所所有有单单词词符符号号的的状状态态转换图，并给出了对应的词法分析程序。转换图，并给出了对应的词法分析程序。n希希望望同同学学们们好好好好读读一一下下。要要求求完完成成的的第第一一个个实实验验-设设计计并并实实现现一一个个小小语语言言的的词词法法分分析析程程序序,可以以这个例子做参考。可以以这个例子做参考。2023/1/232Ch3.词法分析一个简单语言的词法分析一个简单语言的词法分析nP42.表表3.1 简简单单语语言言的的单单词词符符号号及及内内部部表表示示(种种别别码码,内内部部值值)，注注意意这这个

30、个简简单单语语言言有有哪哪些些单词符号及单词符号内部表示形式是什么。单词符号及单词符号内部表示形式是什么。nP42.对对简简单单语语言言的的几几点点限限制制 为为了了简简化化问问题题，使多数单词符号的识别使多数单词符号的识别可以不用超前搜索可以不用超前搜索:n 关键字是保留字，不能作标识符。关键字是保留字，不能作标识符。n 关关键键字字视视为为特特殊殊的的标标识识符符，不不专专设设转转换换图图来来识识别别；但但要要设设保保留留字字表表，当当识识别别出出一一个个标标识识符符以以后要进一步确认是关键字还是真的标识符。后要进一步确认是关键字还是真的标识符。n 关关键键字字、标标识识符符、常常数数之之

31、间间必必须须有有间间隔隔，用用算符、界符、空白符等分隔。算符、界符、空白符等分隔。33识别简单语言单词符号的转换图识别简单语言单词符号的转换图n参见参见P43.图图3.37非非*+312字母字母0*非字母与数字非字母与数字字母或数字字母或数字=数字数字数字数字空白空白*4*非数字非数字568*9*13其它其它2态：识别标识态：识别标识符和关键字符和关键字4态：识别整常数态：识别整常数8态：识别态：识别*9态：识别态：识别*13态：识别错误态：识别错误5态：识别态：识别=6态：识别态：识别+34 3.2.4 状态转换图的实现状态转换图的实现n状状态态转转换换图图容容易易用用程程序序实实现现，即即

32、容容易易由由转转换换图图编写词法分析程序。编写词法分析程序。n最最简简单单的的办办法法是是让让每每个个状状态态结结点点对对应应一一小小段段程程序序。根根据据画画出出的的识识别别单单词词的的状状态态转转换换图图构构造造词词法法分分析析程程序序，每每个个状状态态对对应应一一段段程程序序，完完成成到到达达此此状状态态的的工工作作；词词法法分分析析程程序序的的控控制制程程序序模模拟拟状态转换图的状态转换。状态转换图的状态转换。n在在识识别别标标识识符符的的过过程程中中，要要把把标标识识符符拼拼写写出出来来，并并和和关关键键字字区区别别开开来来；在在识识别别常常数数的的过过程程中中，要把它转换成机器表示

33、以作为属性值。要把它转换成机器表示以作为属性值。35 状态转换图与程序流图状态转换图与程序流图n状状态态转转换换图图实实质质上上就就是是一一个个抽抽象象的的程程序序流流程程图图。转转换换图图忽忽略略了了程程序序的的实实现现细细节节，着着力力刻刻画画了了单单词符号识别的本质。词符号识别的本质。n转转换换图图与与程程序序结结构构之之间间存存在在下下述述对对应应关关系系，并并可以据此构造相应的程序：可以据此构造相应的程序：n初态初态对应程序的开始；对应程序的开始；n终终态态对对应应程程序序的的结结束束，一一般般是是一一条条返返回回语语句句，且不同的终态对应不同的返回语句；，且不同的终态对应不同的返回

34、语句；n状态转移分叉状态转移分叉对应分情况或者对应分情况或者条件语句条件语句；n转换图中的转换图中的环环对应程序中的对应程序中的循环语句循环语句；36n在编制程序的过程中引进了在编制程序的过程中引进了一组全局变量一组全局变量和过程和过程。将它们作为实现转换图即词法分。将它们作为实现转换图即词法分析程序的基本成分。析程序的基本成分。参见参见P44.1.1.Ch Ch 字符字符变量，存放最新读入的源程序字符变量，存放最新读入的源程序字符2.2.strTokenstrToken 字符数组，存放构成单词符号的字符字符数组，存放构成单词符号的字符串串3.3.GetcharGetchar 过程，将下一个输

35、入字符读到过程，将下一个输入字符读到chch中，搜中，搜索指示器前移一个字符位置索指示器前移一个字符位置4.4.GetBCGetBC 过程，判过程，判chch中的字符是否空白，若是，则中的字符是否空白，若是，则调用调用GetcharGetchar，直到直到chch中进入一个非空白字符中进入一个非空白字符5.5.ConcatConcat 过程，拼接单词，把过程，拼接单词，把chch中的字符放到中的字符放到strTokenstrToken中中设定一组全局变量和过程设定一组全局变量和过程(1)376.6.IsLetterIsLetter,IsDigitIsDigit 布尔函数，分别判断布尔函数，分别

36、判断chch中的中的字符是否字母或数字。字符是否字母或数字。7.7.ReserveReserve 整型函数整型函数,对对strTokenstrToken中的字符串查保中的字符串查保留字表留字表,若它是关键字则返回它的编码若它是关键字则返回它的编码,否则返回否则返回0 0值值(假定假定0 0不是关键字的编码不是关键字的编码),),表示是标识符。表示是标识符。8.8.RetractRetract 过程，将搜索指示器回调一个字符位置，过程，将搜索指示器回调一个字符位置，将将chch置为空白字符。置为空白字符。9.9.InsertIdInsertId 整型函数，将整型函数，将strTokenstrTo

37、ken中的标识符插中的标识符插入符号表，返回符号表指针。入符号表，返回符号表指针。10.10.InsertConstInsertConst 整型函数，将整型函数，将strTokenstrToken中的常数中的常数插入常数表，返回常数表指针。插入常数表，返回常数表指针。设定一组全局变量和过程设定一组全局变量和过程(2)38 状态结对应程序段的编写状态结对应程序段的编写(1)n不含回路的分叉结不含回路的分叉结对应条件语句或情形语句对应条件语句或情形语句n状态结状态结 i 对应的程序段对应的程序段:Getchar();If(IsLetter()状态状态j的对应程的对应程 序序段段;Else if(I

38、sDigit()状态状态k的对的对 应应 程程 序序 段段;Else if(ch=/)状态状态l的对应程的对应程 序序段段;Else 错误处理程序段错误处理程序段 或接其他状态图的程序或接其他状态图的程序;j数字i/字母klP45.图图3.4(a)的状态结的状态结 i39 状态结对应程序段的编写状态结对应程序段的编写(2)n含回路的状态结含回路的状态结 对应循环语句对应循环语句n状态结状态结 i i 对应的程序段对应的程序段:GetcharGetchar();();While(While(IsLetterIsLetter()or()or IsDigitIsDigit()()Begin Begi

39、n concatconcat();();GetcharGetchar();();End;End;状态状态j j的对应程序段的对应程序段;其它ij字母或数字 P45.图图3.4(b)的状态结的状态结 i40 状态结对应程序段的编写状态结对应程序段的编写(3)n终终态态结结(如如图图3.33.3中中的的状状态态5 5、6 6、9 9、1010、1111、1212、13)13)对对应应return(Code,Value)return(Code,Value)语语句句,返返回回单词符号的内部表示二元式给语法分析器。单词符号的内部表示二元式给语法分析器。n带带*号号的的终终态态结结(如如图图3.33.3中

40、中的的状状态态2 2、4 4、8)8)多多读读进进了了一一个个不不属属于于现现行行单单词词符符号号的的字字符符,这这个个字字符符应应退退回回,即即搜搜索索指指示示器器要要回回调调一一个个字字符符位位置置,这这时时除除了了ReturnReturn外外，还还要要调调用用RetractRetract过过程程来完成这项工作。来完成这项工作。2023/1/241Ch3.词法分析 状态结对应程序段的编写状态结对应程序段的编写(4)n多多种种单单词词出出口口的的终终态态结结，如如图图3.33.3中中的的状状态态2 2，既既是是标标识识符符的的出出口口又又是是关关键键字字的的出出口口，为为了了确确认认到到底底

41、是是关关键键字字还还是是用用户户自自定定义义的的标标识识符符，需需要要对对strTokenstrToken查查询询 保保 留留 字字 表表，这这 由由 整整 型型 函函 数数 过过 程程ReserveReserve来来完完成成。若若函函数数值值为为0 0，则则表表示示strTokenstrToken中中的的字字符符串串是是一一个个标标识识符符；否否则，表示是关键字编码。则，表示是关键字编码。2023/1/242Ch3.词法分析 状态结对应程序段的编写状态结对应程序段的编写(5)n初初态态结结(如如图图3.33.3中中的的状状态态0)0)，要要作作一一些些初初始始化化的的工工作作,比比如如：设设

42、置置指指示示器器的的值值，对对chch，strTokenstrToken等进行初始化。等进行初始化。n对对于于某某些些状状态态(如如图图3.33.3中中的的状状态态1 1、3)3)，需需要要将将chch的的内内容容送送进进strTokenstrToken拼拼接接单单词词，则还要调用则还要调用ConcatConcat过程。过程。2023/1/243Ch3.词法分析 构造图构造图3.3的词法分析程序的词法分析程序(1)n0 0状态状态对应的程序段：整个程序从开始到结束对应的程序段：整个程序从开始到结束n是初态：作初始化工作是初态：作初始化工作n有分叉：对应整个程序的有分叉：对应整个程序的 ifel

43、se ifelse ifelse ifelse 结构结构n含回路：有循环，用过程含回路：有循环，用过程GetBCGetBC()()实现实现n1 1状状态态含含回回路路，对对应应P45.P45.的的if(if(IsLetterIsLetter()()分分支中的循环语句支中的循环语句 While(While(IsLetterIsLetter()or()or IsDigitIsDigit()()2023/1/244Ch3.词法分析 构造图构造图3.3的词法分析程序的词法分析程序(2)n2 2状状态态 对对应应P45.P45.语语句句Retract()Retract()开开始始到到P46.P46.语语

44、句句Else if(Else if(IsDigitIsDigit()()之前之前n是带是带*号的终态号的终态:调用了调用了Retract()Retract()过程过程n是是标标识识符符和和关关键键字字的的识识别别态态:调调用用了了ReserveReserve()()n是是 终终 态态:用用 Return($IDReturn($ID,value)value)或或Return(code,_)Return(code,_)返返回回标标识识符符或或关关键键字字的的内内部表示部表示n3 3状状态态 含含回回路路，对对应应P46.P46.的的else else if(if(IsDigitIsDigit()(

45、)分分支中的循环语句支中的循环语句 While(While(IsDigitIsDigit()()45 构造图构造图3.3的词法分析程序的词法分析程序(3)n4状态状态 带带*号的终态，整常数的识别态，对应号的终态，整常数的识别态，对应P46.语语句句else if(IsDigit()分支中的分支中的Retract()到到Return($INT,value)n5状态状态 识别识别“=”号号,对应对应P46.语句语句Return($ASSIN,_)n6状态状态 识别识别“+”号号,对应对应P46.语句语句Return($PLUS,_)n7状态状态 分叉分叉,对应对应P46.语句语句 Getchar

46、();if(ch=*)n8状态状态 识别识别“*”号号,对应对应P46.语句语句Return($STAR,_)n9状态状态 识别识别“*”号号,对应对应P46.语句语句Return($POWER,_)n说明说明:这段程序执行一次这段程序执行一次,只能识别出一个单词符号只能识别出一个单词符号,它作为语法分析器调用的一个子程序。它作为语法分析器调用的一个子程序。46 3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n为为了了更更好好地地使使用用状状态态转转换换图图构构造造词词法法分分析析器器，为为了了讨讨论论词词法法分分析析器器的的自自动动生生成成，还需要还需要将转换图的概念形式化将转

47、换图的概念形式化。n本本节节主主要要讨讨论论词词法法分分析析器器自自动动产产生生所所需需要要的的工工具具,引引入入：正正规规式式，正正规规集集，有有限自动机等概念。限自动机等概念。n本节是本章的本节是本章的重点和难点重点和难点。2023/1/247Ch3.词法分析 本节内容及关系本节内容及关系单词符号结单词符号结构的描述构的描述状态转换图状态转换图词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现正规表达正规表达式式E(3.3.1)用用正规集正规集L(E)(3.3.1)表示表示,值集值集正规文法正规文法G正规语言正规语言L(G)用用产生产生有限自动机有限自动机 FA M单词符号集单词符号

48、集L(M)形式化形式化识别识别,接受接受DFA(3.3.2)最少化最少化(3.3.6)NFA(3.3.3)确定化确定化(3.3.3)三者相同三者相同等价等价等价等价(3.3.4)等价等价(3.3.5)2023/1/248Ch3.词法分析3.3.1 正规式与正规集正规式与正规集n对对于于字字母母表表，有有符符号号串串集集合合*和和+,我我们们感感兴兴趣的是它的一些趣的是它的一些特殊的子集特殊的子集，即所谓正规集。，即所谓正规集。n使用正规式这个概念来描述正规集。使用正规式这个概念来描述正规集。n例如例如,=a,b,c,z,0,1,2,9a,b,c,z,0,1,2,9 *=所有字母数字串所有字母数

49、字串 我们对如下子集感兴趣我们对如下子集感兴趣:字母开头的字母数字串字母开头的字母数字串 =标识符集合标识符集合正规式表示正规式表示:l(l|d)l(l|d)*一个正规集一个正规集即一个正规语言即一个正规语言49正规式与正规集的递归定义正规式与正规集的递归定义(P4647)n(1)和和 都都是是 上上的的正正规规式式，它它们们所所表表示示的的正正规规集集分分别为别为 和和；n(2)任任何何a,a是是上上的的一一个个正正规规式式，它它所所表表示示的的正正规集为规集为a；n(3)假假定定U和和V都都是是上上的的正正规规式式,它它们们所所表表示示的的正正规规集集分分别别记记为为L(U)和和L(V),

50、那那么么,U|V、U.V和和U*也也都都是是正正规规式式,它它们们所所表表示示的的正正规规集集分分别别为为L(U)L(V)、L(U)L(V)(连接积连接积)和和(L(U)*(闭包闭包)n仅仅由由有有限限次次使使用用上上述述三三步步骤骤而而得得到到的的表表达达式式才才是是上上的的正正规规式式。仅仅由由这这些些正正规规式式所所表表示示的的字字集集才才是是上的上的正规集，正规集也称为正规语言正规集，正规集也称为正规语言。50正规式定义正规式定义 正规表达式正规表达式 正规表达式对应的正规表达式对应的正规集正规集 1.，2.a a 3.若若 r,s L(r),L(s)则则 选择选择 r s L(r)L