《04词法分析.ppt》由会员分享，可在线阅读，更多相关《04词法分析.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 词法分析概概 述述编译程序需要在单词级别上来分析和翻译源程编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词。序，所以首先要识别出单词。词法分析的任务是：词法分析的任务是：从左至右扫描源程序的字符串，按照词法规则从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。交给语法分析使用。因此，词法分析是编译的基础。执行词法分析因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。的程序称为词法分析器
2、。源程序源程序词法分析程序词法分析程序单词序列单词序列2两种两种词法词法分析分析程序程序不包括处理说明部分：不包括处理说明部分：仅读单词并仅读单词并转换成属性字，而不把单词的全转换成属性字，而不把单词的全部属性都识别出来。部属性都识别出来。包括处理说明部分：包括处理说明部分：把单词的全部把单词的全部属性都识别出来属性都识别出来 本章叙述的词法分析程序是处理了说明部分的词本章叙述的词法分析程序是处理了说明部分的词本章叙述的词法分析程序是处理了说明部分的词本章叙述的词法分析程序是处理了说明部分的词法分析程序，也即一个源程序经过词法分析程序分析法分析程序，也即一个源程序经过词法分析程序分析法分析程序
3、，也即一个源程序经过词法分析程序分析法分析程序，也即一个源程序经过词法分析程序分析处理后，将被改造成为由属性字组成的不含有静态说处理后，将被改造成为由属性字组成的不含有静态说处理后，将被改造成为由属性字组成的不含有静态说处理后，将被改造成为由属性字组成的不含有静态说明部分的中间程序明部分的中间程序明部分的中间程序明部分的中间程序3（1 1 1 1）把词法分析工作单独作为一趟）把词法分析工作单独作为一趟）把词法分析工作单独作为一趟）把词法分析工作单独作为一趟词法分析是主程序词法分析是主程序词法分析是主程序词法分析是主程序源程序源程序源程序源程序词法分析词法分析词法分析词法分析L L1 1程序程序
4、程序程序符号表符号表符号表符号表字符字符字符字符单词单词单词单词 输入流是用高级语言编写的由字符组成的源程序，输入流是用高级语言编写的由字符组成的源程序，输入流是用高级语言编写的由字符组成的源程序，输入流是用高级语言编写的由字符组成的源程序，输出流是由属性字组成的与源程序等价的程序，称之输出流是由属性字组成的与源程序等价的程序，称之输出流是由属性字组成的与源程序等价的程序，称之输出流是由属性字组成的与源程序等价的程序，称之为用第一级中间语言写的程序，简称为用第一级中间语言写的程序，简称为用第一级中间语言写的程序，简称为用第一级中间语言写的程序，简称L1L1程序。程序。程序。程序。词法分析的两种
5、处理结构词法分析的两种处理结构4把词法分析工作单独作为一趟的好处可使整个编译程序的结构更简洁、清晰和条理可使整个编译程序的结构更简洁、清晰和条理化：化：词法分析比语法分析要简单得多，可用更有效的词法分析比语法分析要简单得多，可用更有效的词法分析比语法分析要简单得多，可用更有效的词法分析比语法分析要简单得多，可用更有效的特殊方法和工具进行出理。有些语言的词法分析特殊方法和工具进行出理。有些语言的词法分析特殊方法和工具进行出理。有些语言的词法分析特殊方法和工具进行出理。有些语言的词法分析工作比较别扭，如工作比较别扭，如工作比较别扭，如工作比较别扭，如FORTRANFORTRAN这种受书写格式限这种
6、受书写格式限这种受书写格式限这种受书写格式限制的语言，识别其单词符号便甚为曲折和费时，制的语言，识别其单词符号便甚为曲折和费时，制的语言，识别其单词符号便甚为曲折和费时，制的语言，识别其单词符号便甚为曲折和费时，把词法分析作为一趟独立出来就有利于集中力量把词法分析作为一趟独立出来就有利于集中力量把词法分析作为一趟独立出来就有利于集中力量把词法分析作为一趟独立出来就有利于集中力量考虑这些枝节问题。考虑这些枝节问题。考虑这些枝节问题。考虑这些枝节问题。5增强编译程序的可移植增强编译程序的可移植在同一个语言的不同实现中，或多或少会涉及到在同一个语言的不同实现中，或多或少会涉及到在同一个语言的不同实现
7、中，或多或少会涉及到在同一个语言的不同实现中，或多或少会涉及到与设备有关的特征，如采用与设备有关的特征，如采用与设备有关的特征，如采用与设备有关的特征，如采用ASCIIASCII还是其它的字符还是其它的字符还是其它的字符还是其它的字符编码，可置于词法分析程序中解决而不会影响编编码，可置于词法分析程序中解决而不会影响编编码，可置于词法分析程序中解决而不会影响编编码，可置于词法分析程序中解决而不会影响编译程序其它成分的设计。译程序其它成分的设计。译程序其它成分的设计。译程序其它成分的设计。编译程序的效率会得到改进编译程序的效率会得到改进编译程序的大部分时间是花费在扫描字符以把单编译程序的大部分时间
8、是花费在扫描字符以把单编译程序的大部分时间是花费在扫描字符以把单编译程序的大部分时间是花费在扫描字符以把单词符号分离出来，若把词法分析独立出来，则可词符号分离出来，若把词法分析独立出来，则可词符号分离出来，若把词法分析独立出来，则可词符号分离出来，若把词法分析独立出来，则可采用专门的读字符和分离单词的技术可提高编译采用专门的读字符和分离单词的技术可提高编译采用专门的读字符和分离单词的技术可提高编译采用专门的读字符和分离单词的技术可提高编译速度，而且可建立词法分析程序的自动构造工具速度，而且可建立词法分析程序的自动构造工具速度，而且可建立词法分析程序的自动构造工具速度，而且可建立词法分析程序的自
9、动构造工具这并不意味着必须要把词法分析工作单独作为这并不意味着必须要把词法分析工作单独作为一趟一趟6 每当语法分析器需要一个单词符号时就调用词法分每当语法分析器需要一个单词符号时就调用词法分析子程序。每一次调用，词法分析器就从输入串中识析子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号交给语法分析器。别出一个单词符号交给语法分析器。源程序源程序源程序源程序词法分析词法分析词法分析词法分析语法分析语法分析语法分析语法分析符号表符号表符号表符号表字符字符字符字符单词单词单词单词回送回送回送回送单词单词单词单词 语法分析是主程序语法分析是主程序 由于后一种方式不需要在内存中构造和保存中间
10、文件而常常被由于后一种方式不需要在内存中构造和保存中间文件而常常被采用。采用。把词法分析工作作为子程序7实验一实验一 词法分析词法分析实验目的：实验目的：编制一个读单词过程，从输入的源程序中，识别编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。出各个单词的内部编码及单词符号自身值。估计实验时间：估计实验时间：课余准备课余准备15小时小时上机二次上机二次4小时；小时；完成实验报告完成实验报告5小时。
11、小时。8如源程序为如源程序为C语言。输入如下一段：语言。输入如下一段：main()int a=-5,b=4,j;if(a=b)j=a-b;else j=b-a;要求输出如图：要求输出如图：（2，”main”）（5，”（”）（5，”）”）（5，”）（1，”int”）（2，”a”）（4，”=”）（3，”-5”）（5，”,”）（2，”b”）（4，”=”）（3，”4”）（5，”,”）（2，”j”）（5，”;”）（1，”if”）（5，”（”）（2，”a”）（4，”=”）（2，”b”）（5，”）”）（2，”j”）（4，”=”）（2，”a”）（4，”-”）（2，”b”）（5，”;”）（1，”else”）（2
12、，”j”）（4，”=”）（2，”b”）（4，”-”）（2，”a”）（5，”;”）（5，”）9一、识别各种单词符号一、识别各种单词符号程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：关键字（保留字关键字（保留字/基本字）基本字）if、while、begin标识符：常量名、变量名标识符：常量名、变量名常数：常数：34、56.78、true、a、运算符：运算符：+、-、*、/、and、or、.界限符：，界限符：，；（）/*识别单词：掌握单词的构成规则很重要识别单词：掌握单词的构成规则很重要标识符的识别：字母标识符的识别：字母|下划线下划线+(字母字母/数字数字/下划线下划线)关键字的
13、识别：与标识符相同，最后查表关键字的识别：与标识符相同，最后查表常数的识别常数的识别界符和算符的识别界符和算符的识别 10单词的构成规则用单词的构成规则用状态转换图状态转换图表示表示012字母字母字母或数字字母或数字其它其它识别标识符的转换图识别标识符的转换图012数字数字数字数字其它其它识别整数的转换图识别整数的转换图大多数程序设计语言的单词符号都可以用转换大多数程序设计语言的单词符号都可以用转换图来识别图来识别11状态转换图的实状态转换图的实现：使用一个现：使用一个switch case switch case 语语句：每条分支对句：每条分支对应一个应一个casecase语句语句段段12词
14、法分析器的输出形式词法分析器的输出形式词法分析器输出的单词符号常常表示为二元式：词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）（单词种别，单词符号的属性值）单词种别通常用整数编码，如单词种别通常用整数编码，如1代表关键字，代表关键字，2代代表标识符等表标识符等关键字可视其全体为一种，也可以一字一种。采关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起来较为方便。用一字一种得分法实际处理起来较为方便。标识符一般统归为一种标识符一般统归为一种常数按类型（整、实、布尔等）分种常数按类型（整、实、布尔等）分种运算符可采用一符一种的方法。运算符可采用一符一种的
15、方法。界符一般一符一种的分法。界符一般一符一种的分法。本实验采用一类符号一种别码本实验采用一类符号一种别码13二、二、超前搜索方法超前搜索方法词法分析时，常常会用到超前搜索方法。词法分析时，常常会用到超前搜索方法。如当前待分析字符串为如当前待分析字符串为“a+”，当前字符为，当前字符为“”，此时，分析器倒底是将其分析为大于关系运算符，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？还是大于等于关系运算符呢？显然，只有知道下一个字符是什么才能下结论。于显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符是分析器读入下一个字符+，这时可知应将，这时可知应将解释为大
16、于运算符。但此时，超前读了一个解释为大于运算符。但此时，超前读了一个字符字符+，所以要回退一个字符，词法分析器才，所以要回退一个字符，词法分析器才能正常运行。又比如：能正常运行。又比如：+分析为正号还是加法分析为正号还是加法符号符号14三、预处理三、预处理预处理工作包括对空白符、跳格符、回车符和预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。换行符等编辑性字符的处理，及删除注解等。由一个预处理子程序来完成。由一个预处理子程序来完成。15词法分析器的设计词法分析器的设计设计方法：设计方法：写出该语言的词法规则。写出该语言的词法规则。把词法规则转换为相应的状态转换图
17、。把词法规则转换为相应的状态转换图。把各转换图的初态连在一起，构成识别该语言的把各转换图的初态连在一起，构成识别该语言的自动机自动机设计扫描器设计扫描器把扫描器作为语法分析的一个过程，当语法分把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。析需要一个单词时，就调用扫描器。扫描器从初态出发，当识别一个单词后便进入终扫描器从初态出发，当识别一个单词后便进入终态，送出二元式态，送出二元式16开始开始读标识符读标识符是字母是字母掠过空格和回车符掠过空格和回车符查保留字表查保留字表是否查到是否查到换成属性字换成属性字结束结束是数字是数字是特殊符号是特殊符号error取数取数换成属
18、性字换成属性字换成属性字换成属性字换成属性字换成属性字YNYYYNNN取单词程序框图17void main()if(fp=fopen(“example.c”,“r”)=NULL)/*只读方式打开一个文件只读方式打开一个文件*/printf(error);else cbuffer=fgetc(fp);/*fgetc()函数：从磁盘文件读取一个字符函数：从磁盘文件读取一个字符*/while(cbuffer!=EOF)if(cbuffer=|cbuffer=n)/*掠过空格和回车符掠过空格和回车符*/cbuffer=fgetc(fp);else if(isalpha(cbuffer)cbuffer=
19、alphaprocess(cbuffer);else if(isdigit(cbuffer)cbuffer=digitprocess(cbuffer);else cbuffer=otherprocess(cbuffer);18char alphaprocess(char buffer)int atype;/*保留字数组中的位置保留字数组中的位置*/int i=-1;char alphatp20;while(isalpha(buffer)|(isdigit(buffer)|buffer=_)alphatp+i=buffer;/*读一个完整的单词放入读一个完整的单词放入alphatp数组中数组中*
20、/alphatpi+1=0;atype=search(alphatp,1);/*对此单词调用对此单词调用search函数判断类型函数判断类型*/if(atype!=0)printf(%s,(1,%d)n,alphatp,atype-1);id=1;else printf(%s,2)n,alphatp);id=2;19FILE*fp;char cbuffer;char*key8=if,else,for,while,do,return,break,continue;int atype,id=4;int search(char searchchar,int wordtype)/*判断单词是保留字还是
21、标识符判断单词是保留字还是标识符*/int i=0;int p;switch(wordtype)case 1:for(i=0;i=7;i+)if(strcmp(keyi,searchchar)=0)p=i+1;break;/*是保留字则是保留字则p为非为非0且不重复的整数且不重复的整数*/else p=0;/*不是保留字则用于返回的不是保留字则用于返回的p=0*/return(p);20char digitprocess(char buffer)int i=-1;char digittp20;while(isdigit(buffer)digittp+i=buffer;buffer=fgetc(
22、fp);digittpi+1=0;printf(%s,3)n,digittp);id=3;return(buffer);21char otherprocess(char buffer)char ch20;ch0=buffer;ch1=0;if(ch0=,|ch0=;|ch0=|ch0=|ch0=(|ch0=)printf(%s,5)n,ch);buffer=fgetc(fp);id=4;return(buffer);if(ch0=*|ch0=/)printf(%s,4)n,ch);buffer=fgetc(fp);id=4;return(buffer);22if(ch0=|ch0=!|ch0=
23、)buffer=fgetc(fp);if(buffer=)ch1=buffer;ch2=0;printf(%s,4)n,ch);else printf(%s,4)n,ch);id=4;return(buffer);buffer=fgetc(fp);id=4;return(buffer);23if(ch0=+|ch0=-)if(id=4)/*在当前符号以前是运算符，则此时为正负号在当前符号以前是运算符，则此时为正负号*/buffer=fgetc(fp);ch1=buffer;ch2=0;printf(%s,3)n,ch);id=3;buffer=fgetc(fp);return(buffer);
24、ch1=0;printf(%s,4)n,ch);buffer=fgetc(fp);id=4;return(buffer);24 5.5 词法分析器的自动生成一般来说，在各种不同的高级程序设计语言中，一般来说，在各种不同的高级程序设计语言中，单词的总体结构基本相同，从而人们总希望对单词的总体结构基本相同，从而人们总希望对所有的高级程序设计语言设计一个词法分析程所有的高级程序设计语言设计一个词法分析程序的自动生成程序（生产器）。只要给出某种序的自动生成程序（生产器）。只要给出某种高级语言的单词描述，便能经过这样的自动生高级语言的单词描述，便能经过这样的自动生成程序自动产生相应的词法分析程序，这就是
25、成程序自动产生相应的词法分析程序，这就是词法分析程序的自动生成问题词法分析程序的自动生成问题这里只介绍一个词法分析程序的生成程序这里只介绍一个词法分析程序的生成程序 Lex25 Lex是一种描述词法分析程序的语言，它由一组正是一种描述词法分析程序的语言，它由一组正则表达式以及与之相伴的代码则表达式以及与之相伴的代码(动作动作)组成，每组成，每个动作指出相应的正则表达式所要完成的任务个动作指出相应的正则表达式所要完成的任务,也即当按该正则表达式识别出某单词后应执行也即当按该正则表达式识别出某单词后应执行的操作。的操作。一个一个Lex程序被编译后所得的结果程序程序被编译后所得的结果程序(记为记为L
26、),其作用就如同一个有效自动机一样，可用其作用就如同一个有效自动机一样，可用来识别和产生单词符号。来识别和产生单词符号。结果程序结果程序L含有一张状态转换矩阵和一个控制含有一张状态转换矩阵和一个控制程序。程序。26 LEXLEX源程序源程序源程序源程序 LEXLEX 编译程序编译程序编译程序编译程序 词法词法词法词法分析器分析器分析器分析器L L 输入串输入串输入串输入串 词法词法词法词法分析器分析器分析器分析器L L 单词单词单词单词符号串符号串符号串符号串 LEXLEX编译系统的作用编译系统的作用编译系统的作用编译系统的作用27一一 Lex源程序辅助定义辅助定义转换规则转换规则代码代码28
27、 辅助定义辅助定义 辅助定义部分由以下形式的一串辅助定义部分由以下形式的一串辅助定义部分由以下形式的一串辅助定义部分由以下形式的一串LexLexLexLex语句组成语句组成语句组成语句组成D D1 1RR1 1 D D2 2RR2 2 D Dn nRRn nR Ri i(i(i=1,2,n)=1,2,n)是一个正则表达式是一个正则表达式是一个正则表达式是一个正则表达式,D Di i是是是是代表此正则表达式代表此正则表达式代表此正则表达式代表此正则表达式R Ri i的名字的名字的名字的名字,并限定并限定并限定并限定R Ri i=V=Vt t(D(D1 1,D,D2 2,D,Di-1i-1)D D
28、i i一般用小写英文字母串表示一般用小写英文字母串表示一般用小写英文字母串表示一般用小写英文字母串表示标识符的辅助定义标识符的辅助定义标识符的辅助定义标识符的辅助定义 letterAletterAZ Za az z identident letter(letter letter(letterdigit)digit)*例例例例:整常数的辅助定义整常数的辅助定义整常数的辅助定义整常数的辅助定义 digit0digit01 19 9 integer digit(digit)integer digit(digit)*与文法一致与文法一致与文法一致与文法一致29也称识别规则也称识别规则也称识别规则也称识
29、别规则,由下列形式的一串由下列形式的一串由下列形式的一串由下列形式的一串LexLexLexLex语句组成语句组成语句组成语句组成P P1 1A A1 1P P2 2A A2 2 P PmmA Amm P Pi i(i=1,2,m)(i=1,2,m)是是是是定义在定义在定义在定义在V Vt t(D(D1 1,D,D2 2,D Dn n)上的上的上的上的正则正则正则正则表达式表达式表达式表达式,称为词型称为词型称为词型称为词型,它描述了单词的形式它描述了单词的形式它描述了单词的形式它描述了单词的形式.A Ai i(i=1,2,m)(i=1,2,m)是是是是一个动作一个动作一个动作一个动作,每个动作
30、是一个可以每个动作是一个可以每个动作是一个可以每个动作是一个可以执行的代码序列执行的代码序列执行的代码序列执行的代码序列,并用并用并用并用括括括括起来起来起来起来,它指出在识别出它指出在识别出它指出在识别出它指出在识别出词型为词型为词型为词型为P Pi i的的的的单词后单词后单词后单词后,词法分析器应采取的动作词法分析器应采取的动作词法分析器应采取的动作词法分析器应采取的动作 转换规则转换规则30digit(digit)*例例例例 整常数的转换规则整常数的转换规则整常数的转换规则整常数的转换规则 val:=int(id);return(16);return(val)求整型求整型求整型求整型值值
31、值值,并执行有关子程序并执行有关子程序并执行有关子程序并执行有关子程序,查填常量表等查填常量表等查填常量表等查填常量表等函数函数int(idint(id)是求数字串是求数字串idid的数值，子程序的数值，子程序returnreturn及其参数与整个转换规则的统一要求有关。及其参数与整个转换规则的统一要求有关。31将源程序翻译成语法分析程序的程序将源程序翻译成语法分析程序的程序过程过程转换规则转换规则(P Pi i)状态转换图状态转换图(NFA)状态转换矩阵状态转换矩阵简化简化(NFADFA)词法分析程序词法分析程序二、Lex编译程序32 .三 词法分析程序Lex源程序经源程序经Lex编译程序编
32、译后得到的编译程序编译后得到的Lex目目标程序叫词法分析程序标程序叫词法分析程序工作过程工作过程Lex目标程序目标程序(L)逐一扫描输入串的每个字符，寻逐一扫描输入串的每个字符，寻找一个最长的子串匹配某个找一个最长的子串匹配某个Pi i，把该子串截下来放，把该子串截下来放在一个缓冲区在一个缓冲区TOKEN中中然后然后L就调用动作子程序就调用动作子程序Ai i,当当Ai i完成后，完成后，L就把得就把得到的单词符号交给词法分析程序到的单词符号交给词法分析程序当当L重新被调用时重新被调用时,就从输入串中继上次截出的位就从输入串中继上次截出的位置之后识别下一个单词符号置之后识别下一个单词符号33匹配
33、时有两种：匹配时有两种：输入串找不到任何词型输入串找不到任何词型Pi i与之相匹配与之相匹配L应报告输入应报告输入串有错误串有错误输入串可以匹配若干个不同的输入串可以匹配若干个不同的Pi i以以Lex程序中出现程序中出现在最前面的在最前面的Pi i为准为准34 与每个词型与每个词型Pi相应的动作相应的动作Ai的基本组成成分是的基本组成成分是“返回返回”Pi定义的单词属性定义的单词属性”。对于大多数单词，词法分析。对于大多数单词，词法分析程序返回的属性就是该单词的内部编码。但是诸如常程序返回的属性就是该单词的内部编码。但是诸如常数、标识符、字符串常数单词，除了返回内部编码以数、标识符、字符串常数单词，除了返回内部编码以外，还要分别返回常数的值、标识符本身和字符串在外，还要分别返回常数的值、标识符本身和字符串在串表中的起始位置和长度。另外，必须把保留字从标串表中的起始位置和长度。另外，必须把保留字从标识符中区别出，这可以通过查找预先设置的保留字表识符中区别出，这可以通过查找预先设置的保留字表来实现。来实现。35