第三章词法分析精选PPT.ppt
《第三章词法分析精选PPT.ppt》由会员分享,可在线阅读,更多相关《第三章词法分析精选PPT.ppt(54页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第三章词法分析第1页,本讲稿共54页源程序扫描器scanner1 1、关键字、关键字词法分析器的词法分析器的功能功能如下图所示:如下图所示:2 2、标识符、标识符5 5、界符、界符4 4、运算符、运算符3 3、常数、常数由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如:Pascal中的begin,end,if等。界符:如逗号、分号、括号、/*,*/等。它是确定的。运算符:如+、-、*、/等。它是确定的。常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。用来表示各种名字,如变量名、数组名、过程名等。它是不限的。第2页,本讲稿共54页词法分析器的词法分析器的功能功能:输入
2、源程序,输出单词符号。:输入源程序,输出单词符号。单词符号单词符号:一个程序语言的基本语法符号。分为以下:一个程序语言的基本语法符号。分为以下5 5种。种。1 1、关键字关键字:由程序语言定义的具有固定意义的标识符。也:由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如:可称为保留字或基本字。例如:PascalPascal中的中的beginbegin,endend,ifif等。它是等。它是确定确定的。的。2 2、标识符标识符:用来表示各种名字,如变量名、数组名、过程:用来表示各种名字,如变量名、数组名、过程名等。它是名等。它是不限不限的。的。3 3、常数常数:常数的类型一般有整
3、型、实型、布尔型、文字型:常数的类型一般有整型、实型、布尔型、文字型等。它是等。它是不限不限的。的。4 4、运算符运算符:如:如+、-、*、/等。它是等。它是确定确定的。的。5 5、界符界符:如逗号、分号、括号、:如逗号、分号、括号、/*/*,*/等。它是等。它是确定确定的。的。第3页,本讲稿共54页单词符号的表示形式单词符号的表示形式:词法分析器所输出的单词符号常常表示成:词法分析器所输出的单词符号常常表示成 二元式(单词种别,单词自身的值)二元式(单词种别,单词自身的值)。单词种别单词种别可以用以下形式表示:可以用以下形式表示:1 1、一类单词统一用一个整数值代表其属性。例如:、一类单词统
4、一用一个整数值代表其属性。例如:1 1代表关键字,代表关键字,2 2代表标识符等。代表标识符等。2 2、每一个单词一个类别。例如:、每一个单词一个类别。例如:1 1代表代表BEGINBEGIN,2 2代表代表ENDEND等。等。单词自身的值单词自身的值可以表示成:常量的二进制表示;常量、变量等在符号表可以表示成:常量的二进制表示;常量、变量等在符号表种的地址码,等等。种的地址码,等等。注意:注意:一个语言的单词符号如何分种,分几种,怎样编码,是一个技术问题。标识符一般同归为一种。常数则宜按类型(整、实、布尔)分。关键字可以将其全体视为一种,也可一字一种一字一种。运算符可采用一符一种,但也可把具
5、有一定共性的视为一种。界符则一般采用一符一种一符一种。如何进行分种主要取决于处理上的方便。若是一符一种分种,单词自身值就不需要了。否则,要查符号表。第4页,本讲稿共54页例例3-13-1:151151FORTRANFORTRAN编译程序的词法分析器在扫描输入串编译程序的词法分析器在扫描输入串 IF(5EQIF(5EQM)GOTO 100M)GOTO 100 后,它输出的后,它输出的单词符号串单词符号串是:是:逻辑逻辑IF IF (3434,_ _)左括号左括号 (2 2,_ _)整常数整常数 (2020,55的二进制表示)的二进制表示)等号等号 (6 6,_ _)标识符标识符 (2626,MM
6、)右括号右括号 (1616,_ _)GOTO GOTO (3030,_ _)标号标号 (1919,100100的二进制表示)的二进制表示)IFIF为关键字,种别编码为关键字,种别编码3434,采用一,采用一符一种的编码方式。符一种的编码方式。常数类型,种别编码常数类型,种别编码2020,单词自身的值,单词自身的值为为55的二进制表示。的二进制表示。(为界符,种别编码为界符,种别编码2 2,采用一符,采用一符一种的编码方式。一种的编码方式。等号为运算符,种别编码等号为运算符,种别编码6 6,采用,采用一符一种的编码方式。一符一种的编码方式。M M为标识符,种别编码为标识符,种别编码2626,单词
7、自,单词自身值为身值为MM。)为界符,种别编码为界符,种别编码1616,采用,采用一符一种的编码方式。一符一种的编码方式。GOTOGOTO为关键字,种别编码为关键字,种别编码3030,采用一,采用一符一种的编码方式。符一种的编码方式。100100为标号,种别编码为标号,种别编码1919,单词内部,单词内部的值用的值用100100的二进制表示。的二进制表示。第5页,本讲稿共54页例例3-2 3-2:下述:下述C+C+代码段:代码段:while(i=j)i-while(i=j)i-;经词法分析器处理以后,它将被转换为如下的经词法分析器处理以后,它将被转换为如下的单词符号串单词符号串 (while(
8、while,_)_)(,_)_)(id(id,指向,指向i i的符号表指针的符号表指针 )(=(=,_)_)(id(id,指向,指向j j的符号表指针的符号表指针 )()(),_)_)(id(id,指向,指向i i的符号表指针的符号表指针 )(-(-,_ _)(;,_)_)第6页,本讲稿共54页1 1、把词法分析从语法分析中脱离出来的、把词法分析从语法分析中脱离出来的优点优点:使编译程序的使编译程序的结构结构更加简洁、清晰和条理化。更加简洁、清晰和条理化。词法分析和语法分析词法分析和语法分析方法方法不同,词法分析可以使用正则文法自动构造不同,词法分析可以使用正则文法自动构造scannersca
9、nner简单。简单。有利于提高语法分析的有利于提高语法分析的效率效率。可以改善词法分析的细节,甚至于一个语法分析配几个可以改善词法分析的细节,甚至于一个语法分析配几个scannerscanner,把不同,把不同的输入变成一种内部表示。的输入变成一种内部表示。2 2、把词法分析作为独立的一、把词法分析作为独立的一遍遍scannerscanner当作一遍。当作一遍。把把scannerscanner当作子程序。当作子程序。外存外存scannerscanner语法分析语法分析源程序单词符号scannerscanner作为一遍作为一遍语法语法分析分析scannerscanner源程序源程序scanner
10、scanner作为子程序作为子程序第7页,本讲稿共54页设计前提设计前提:把把scannerscanner作为一个独立的子程序;作为一个独立的子程序;词法分析器的任务为输出单词符号。词法分析器的任务为输出单词符号。必要性必要性:编辑性字符如空白符、回车符等,除了出现在文字和编辑性字符如空白符、回车符等,除了出现在文字和 常数中以外,在别处出现都没有意义。常数中以外,在别处出现都没有意义。功功 能能:剔除无用字符。剔除无用字符。实实 现现:预处理子程序。预处理子程序。输入列表预处理预处理子程序子程序扫描器扫描器扫描缓冲区扫描缓冲区输入缓冲区输入缓冲区单词符号图图3.1 3.1 词法分析器词法分析
11、器语法分析器语法分析器预预处处理理部部分分扫扫描描器器第8页,本讲稿共54页若若识别识别输入语句输入语句 IF(5.EQ.M)GOTO 100,若缓冲区情况如下所示:,若缓冲区情况如下所示:IF(5.EQ.M)GO 起点指示器起点指示器 搜索指示器搜索指示器输入缓冲区输入缓冲区 TO 100 IF(5.EQ.M)GO 起点指示器起点指示器 搜索指示器搜索指示器输入缓冲区输入缓冲区TO 100 IF(5.EQ.M)GO 起点指示器起点指示器搜索指示器搜索指示器两两 个个 互互 补补 输输 入入 缓缓 冲冲 区区120个字符个字符扫描缓冲区的扫描缓冲区的结构结构:缓冲区大小缓冲区大小:120120
12、个字符。个字符。采用两个采用两个指示器指示器:起点指示器、搜索指示器。:起点指示器、搜索指示器。两个互补区两个互补区。第9页,本讲稿共54页单词符号识别的简单方法:单词符号识别的简单方法:超前搜索。关键字识别关键字识别:例如:在标准例如:在标准FORTRANFORTRAN中中 1 1、DO99KDO99K=1,10=1,10 2 2、IFIF(5.EQ.M)I=10(5.EQ.M)I=10 3 3、DO99KDO99K=1.10=1.10 4 4、IFIF(5)=55(5)=55 其中的其中的DODO、IFIF为关键字为关键字其中的其中的DODO、IFIF为标识符的为标识符的一部分一部分第10
13、页,本讲稿共54页标识符的识别标识符的识别 多数语言的标识符是字母开头的多数语言的标识符是字母开头的“字母字母/数字数字”串,串,而且在程序中标识符的出现后都跟着算符或界符。因此,而且在程序中标识符的出现后都跟着算符或界符。因此,不难识别。不难识别。常数的识别常数的识别 对于某些语言的常数的识别也需要使用超前搜索。对于某些语言的常数的识别也需要使用超前搜索。算符和界符的识别算符和界符的识别 对于诸如对于诸如C+C+语言中的语言中的“+”+”、“-”-”,这种复,这种复合成的算符,需要超前搜索。合成的算符,需要超前搜索。第11页,本讲稿共54页转换图转换图:是一张有限方向图。在状态转换图中,:是
14、一张有限方向图。在状态转换图中,结点结点代表代表 状态状态,用圆圈表示。状态之间用,用圆圈表示。状态之间用箭弧箭弧连接。箭弧上连接。箭弧上的的标记(字符)标记(字符)代表在射出结状态下可能出现的输代表在射出结状态下可能出现的输入字符或字符类。入字符或字符类。状态转换图的功能状态转换图的功能:用于识别一定的字符串。用于识别一定的字符串。初态初态:一张转换图的启动条件,至少有一个:一张转换图的启动条件,至少有一个,用圆圈表示。用圆圈表示。终态终态:一张转换图的结束条件,至少有一个,用双圈表示。:一张转换图的结束条件,至少有一个,用双圈表示。*:表示多读进了一个字符。:表示多读进了一个字符。第12页
15、,本讲稿共54页1 12 23 3XY(a)(a)转换图示例转换图示例2 20 01 1字母字母其他其他字母或数字字母或数字*(b b)识别标识符的转换图)识别标识符的转换图其他其他2 20 01 1数字数字数字数字*(c c)识别整数的转换图)识别整数的转换图例例3-33-3:简单的状态转换图示例:简单的状态转换图示例:初态初态终态终态从从0 0状态到状态到1 1状态可状态可能出现字母能出现字母第13页,本讲稿共54页图图3.2 3.2 状态转换图状态转换图7 7*6 65 5数字数字1 10 01 1数字数字数字数字2 2数字数字3 3E E 或或 D D+或或数字数字其他其他E E 或或
16、 D D数字数字其他其他数字数字例例3-43-4:识别:识别FORTRANFORTRAN实型常数实型常数的转换图:的转换图:例如下列实型常数可以例如下列实型常数可以被以下转换图识别:被以下转换图识别:1.23E+41.23E+4 .56E-7 .56E-7第14页,本讲稿共54页单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND 5$END标识符标识符6$ID常数(整)常数(整)7$INT内部字符串内部字符串8$ASSIGN标准二进制形式标准二进制形式 9$PLUS*10$STAR*11$POWER,12$COMMA(13
17、$LPAR)14$RPAR例例3-53-5:综合实例:综合实例做出识别下表所示的小语言的做出识别下表所示的小语言的单词符号单词符号的状态转换图的状态转换图第15页,本讲稿共54页*1 12 20 0字母字母非字母与数字非字母与数字字母或数字字母或数字*空白空白5 54 43 3数字数字数字数字非数字非数字*6 610101111131312127 7*8 89 9*非*,()其他其他。右图即为对上页所示右图即为对上页所示的简单语言进行的简单语言进行词法词法分析分析的状态转换图。的状态转换图。第16页,本讲稿共54页1、CHARCHAR 字符变量,存放最新读进的源程序字符。字符变量,存放最新读进
18、的源程序字符。2 2、TOKENTOKEN 字符数组,存放构成单词的字符串。字符数组,存放构成单词的字符串。3 3、GETCHARGETCHAR 过程,将下一输入字符读入过程,将下一输入字符读入CHARCHAR,搜索指示器前移一个字符。,搜索指示器前移一个字符。4 4、GETBCGETBC 过程,检查过程,检查CHARCHAR中的字符是否为空白。若是,则调用中的字符是否为空白。若是,则调用GETCHARGETCHAR 直至直至CHARCHAR中进入一个非空白字符。中进入一个非空白字符。5 5、CONCAT CONCAT 过程,把过程,把CHARCHAR中的字符连接到中的字符连接到TOKENTO
19、KEN之后。之后。6 6、LETTERLETTER 布尔函数过程,它们分别判断布尔函数过程,它们分别判断CHARCHAR中的字符是数字或是字母,中的字符是数字或是字母,DIGITDIGIT 从而给出真假值从而给出真假值TRUETRUE、FALSEFALSE。7 7、RESERVERESERVE 整型函数过程,用整型函数过程,用TOKENTOKEN中的字符串查保留字表,若是一个保留中的字符串查保留字表,若是一个保留 字则给予编码,否则回送字则给予编码,否则回送0 0值(假定值(假定0 0不是保留字的编码)。不是保留字的编码)。8 8、RETRACTRETRACT 过程,把搜索指示器回调一个字节,
20、把过程,把搜索指示器回调一个字节,把CHARCHAR中的字符置为空白。中的字符置为空白。第17页,本讲稿共54页 以上函数和子程序过程都不难编制,使用它们能够方便以上函数和子程序过程都不难编制,使用它们能够方便的构造状态转换图的对应程序。一般,我们可以让每的构造状态转换图的对应程序。一般,我们可以让每一个状一个状态结态结对应对应一个程序段一个程序段。例如:我们可以让不含回路的分叉结,对应一个例如:我们可以让不含回路的分叉结,对应一个CASE CASE 语语句,或者是一组句,或者是一组IFTHENELSEIFTHENELSE语句。具体见后面实例。语句。具体见后面实例。终态结终态结一般对应一个一般
21、对应一个RETURN(C,VAL)RETURN(C,VAL)语句。其中语句。其中C C为单词为单词种别编码;种别编码;VALVAL是字符数组的是字符数组的TOKEN TOKEN,或者是一个整数值,或,或者是一个整数值,或者无定义。具体见后面实例。者无定义。具体见后面实例。第18页,本讲稿共54页 为了把为了把状态转换图状态转换图转化成转化成程序程序,每个,每个状态状态要建立一段要建立一段程序程序,它要做的工作如下:,它要做的工作如下:第一步第一步:从输入缓冲区中取一个字符。为此,我们使用函:从输入缓冲区中取一个字符。为此,我们使用函数数GETCHARGETCHAR,每次调用它,推进先行指针,送
22、回一,每次调用它,推进先行指针,送回一个字符。个字符。第二步第二步:确定在本状态下,哪一条箭弧是用刚刚来的输入:确定在本状态下,哪一条箭弧是用刚刚来的输入字符标识的。如果找到,控制就转到该弧所指向字符标识的。如果找到,控制就转到该弧所指向的状态;若找不到,那么寻找该单词的企图就失的状态;若找不到,那么寻找该单词的企图就失败了。败了。失失 败败:先行指针必须:先行指针必须重新回到重新回到开始指针处,并用另一状开始指针处,并用另一状态图来搜索态图来搜索另一另一单词。如果所有的状态转换图都单词。如果所有的状态转换图都试过之后,还没有匹配的,就表明这是一个词法试过之后,还没有匹配的,就表明这是一个词法
23、错误,此时,调用错误校正程序。错误,此时,调用错误校正程序。GETCHAR是过程,将是过程,将下一输入字符读入下一输入字符读入CHAR,搜索指示器,搜索指示器前移一个字符。前移一个字符。第19页,本讲稿共54页例例3 36 6:以下:以下CASECASE语句段对应的状态图语句段对应的状态图:state istate i:GETCHARGETCHAR;CASE CASE CHARCHAR OF OF A.Z A.Z:state j state j ;0.90.9:state k state k ;/:state l state l ;ENDEND;FAILFAIL数字数字i ij jk kl l
24、字母字母 /字符变量,存放最新字符变量,存放最新读进的源程序字符。读进的源程序字符。过程,将下一输入字符读过程,将下一输入字符读入入CHARCHAR,搜索指示器前,搜索指示器前移一个字符。移一个字符。第20页,本讲稿共54页对于如上的状态转换图,对于如上的状态转换图,状态状态0 0的代码如下所示:的代码如下所示:state 0state 0:C:=C:=GETCHAR GETCHAR;if if LETTER(C)LETTER(C)then goto state 1 then goto state 1 else else FAIL()FAIL()2 20 01 1字母字母其他其他字母或数字字母
25、或数字LETTER()是布尔函数是布尔函数过程,当且仅当过程,当且仅当C中的中的字符是字母,它返回字符是字母,它返回真假值真假值TRUE。FAIL()是例子程序,它移是例子程序,它移回回先行指针先行指针(lookahead pointer),开始下一状态开始下一状态转换图,或调用出错程序。转换图,或调用出错程序。例例3-73-7:示例:示例如何把如何把状态结状态结对应于一段对应于一段程序程序:*第21页,本讲稿共54页对于如上的状态转换图,对于如上的状态转换图,状态状态1 1的代码如下所示:的代码如下所示:state 1state 1:C:=C:=GETCHAR GETCHAR;if if L
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 词法 分析 精选 PPT
限制150内