《编译原理(冯博琴_版)》由会员分享,可在线阅读,更多相关《编译原理(冯博琴_版)(54页珍藏版)》请在金锄头文库上搜索。
1、第三章 词法分析,词法分析的任务:,从左至右逐个字符地扫描源程序,产生一个个的单词符号,把作为字符串的源程序改造成为单词符号串的中间程序。,词法分析器/扫描器:执行词法分析的程序。,源程序,扫描器 scanner,1、关键字,词法分析器的功能如下图所示:,2、标识符,5、界符,4、运算符,3、常数,由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如:Pascal中的begin,end,if等。,界符:如逗号、分号、括号、/*,*/ 等。它是确定的。,运算符:如+、-、*、/ 等。它是确定的。,常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。,用来表示各种名字,如变量名
2、、数组名、过程名等。它是不限的。,3.1对词法分析器的要求,3.1.1词法分析器的功能和输出形式,词法分析器的功能:输入源程序,输出单词符号。 单词符号:一个程序语言的基本语法符号。分为以下5种。 1、关键字:由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如:Pascal中的begin,end,if等。它是确定的。 2、标识符:用来表示各种名字,如变量名、数组名、过程名等。它是不限的。 3、常数:常数的类型一般有整型、实型、布尔型、文字型等。它是不限的。 4、运算符:如+、-、*、/ 等。它是确定的。 5、界符:如逗号、分号、括号、/*,*/ 等。它是确定的。,确定,不限,单
3、词符号的表示形式:词法分析器所输出的单词符号常常表示成 二元式(单词种别,单词自身的值)。 单词种别可以用以下形式表示: 1、一类单词统一用一个整数值代表其属性。例如:1代表关键字,2代表标识符等。 2、每一个单词一个类别。例如:1代表BEGIN,2代表END等。 单词自身的值可以表示成:常量的二进制表示;常量、变量等在符号表种的地址码,等等。,注意:一个语言的单词符号如何分种,分几种,怎样编码,是一个技术问题。标识符一般同归为一种。常数则宜按类型(整、实、布尔)分。关键字可以将其全体视为一种,也可一字一种。运算符可采用一符一种,但也可把具有一定共性的视为一种。界符则一般采用一符一种。如何进行
4、分种主要取决于处理上的方便。 若是一符一种分种,单词自身值就不需要了。否则,要查符号表。,例3-1:151FORTRAN编译程序的词法分析器在扫描输入串 IF (5EQM) GOTO 100 后,它输出的单词符号串是:,逻辑IF (34,_) 左括号 (2,_) 整常数 (20,5的二进制表示) 等号 (6,_) 标识符 (26,M) 右括号 (16,_) GOTO (30,_) 标号 (19,100的二进制表示),IF为关键字,种别编码34,采用一符一种的编码方式。,常数类型,种别编码20,单词自身的值为5的二进制表示。,(为界符,种别编码2,采用一符一种的编码方式。,等号为运算符,种别编码
5、6,采用一符一种的编码方式。,M为标识符,种别编码26,单词自身值为M。,)为界符,种别编码16,采用一符一种的编码方式。,GOTO为关键字,种别编码30,采用一符一种的编码方式。,100为标号,种别编码19,单词内部的值用100的二进制表示。,例3-2 :下述C+代码段:while ( i = j ) i - -; 经词法分析器处理以后,它将被转换为如下的单词符号串,( while ,_ ) ( ( ,_ ) ( id ,指向i的符号表指针 ) ( = ,_ ) ( id ,指向j的符号表指针 ) ( ) ,_ ) ( id ,指向i的符号表指针 ) ( - - ,_ ) ( ; ,_ ),
6、3.1.2词法分析与语法分析的关系,1、把词法分析从语法分析中脱离出来的优点: 使编译程序的结构更加简洁、清晰和条理化。 词法分析和语法分析方法不同,词法分析可以使用正则文法自动构造scanner简单。 有利于提高语法分析的效率。 可以改善词法分析的细节,甚至于一个语法分析配几个scanner,把不同的输入变成一种内部表示。 2、把词法分析作为独立的一遍 scanner当作一遍。 把scanner当作子程序。,3.2词法分析器的设计,设计前提: 把scanner作为一个独立的子程序; 词法分析器的任务为输出单词符号。,3.2.1预处理,必要性:编辑性字符如空白符、回车符等,除了出现在文字和 常
7、数中以外,在别处出现都没有意义。 功 能: 剔除无用字符。 实 现: 预处理子程序。,若识别输入语句 IF (5.EQ.M) GOTO 100,若缓冲区情况如下所示:,扫描缓冲区的结构: 缓冲区大小:120个字符。 采用两个指示器:起点指示器、搜索指示器。 两个互补区。,3.2.2单词符号的识别超前搜索,单词符号识别的简单方法:超前搜索。 关键字识别: 例如:在标准FORTRAN中 1、DO99K = 1,10 2、IF(5.EQ.M)I = 10 3、DO99K = 1.10 4、IF(5) = 55,其中的DO、IF为关键字,其中的DO、IF为标识符的一部分,标识符的识别 多数语言的标识符
8、是字母开头的“字母/数字”串,而且在程序中标识符的出现后都跟着算符或界符。因此,不难识别。 常数的识别 对于某些语言的常数的识别也需要使用超前搜索。 算符和界符的识别 对于诸如C+语言中的“+ +”、“- -”,这种复合成的算符,需要超前搜索。,3.2.3状态转换图,转换图:是一张有限方向图。在状态转换图中,结点代表 状态,用圆圈表示。状态之间用箭弧连接。箭弧上的标记(字符)代表在射出结状态下可能出现的输入字符或字符类。 状态转换图的功能:用于识别一定的字符串。 初态:一张转换图的启动条件,至少有一个,用圆圈表示。 终态:一张转换图的结束条件,至少有一个,用双圈表示。 * :表示多读进了一个字
9、符。,2,0,1,字母,其他,字母或数字,*,(b)识别标识符的转换图,例3-3:简单的状态转换图示例:,初态,终态,从0状态到1状态可能出现字母,例3-4:识别FORTRAN实型常数的转换图:,例如下列实型常数可以被以下转换图识别: 1.23E+4 .56E-7,例3-5:综合实例做出识别下表所示的小语言的单词符号的状态转换图,右图即为对上页所示的简单语言进行词法分析的状态转换图。,3.2.4状态转换图的实现,1、CHAR 字符变量,存放最新读进的源程序字符。 2、TOKEN 字符数组,存放构成单词的字符串。 3、GETCHAR 过程,将下一输入字符读入CHAR,搜索指示器前移一个字符。 4
10、、GETBC 过程,检查CHAR中的字符是否为空白。若是,则调用GETCHAR 直至CHAR中进入一个非空白字符。 5、CONCAT 过程,把CHAR中的字符连接到TOKEN之后。 6、LETTER 布尔函数过程,它们分别判断CHAR中的字符是数字或是字母, DIGIT 从而给出真假值TRUE、FALSE。 7、RESERVE 整型函数过程,用TOKEN中的字符串查保留字表,若是一个保留 字则给予编码,否则回送0值(假定0不是保留字的编码)。 8、RETRACT 过程,把搜索指示器回调一个字节,把CHAR中的字符置为空白。,以上函数和子程序过程都不难编制,使用它们能够方便的构造状态转换图的对应
11、程序。一般,我们可以让每一个状态结对应一个程序段。 例如:我们可以让不含回路的分叉结,对应一个CASE 语句,或者是一组IFTHENELSE语句。具体见后面实例。 终态结一般对应一个RETURN(C,VAL)语句。其中C为单词种别编码;VAL是字符数组的TOKEN ,或者是一个整数值,或者无定义。具体见后面实例。,为了把状态转换图转化成程序,每个状态要建立一段 程序,它要做的工作如下: 第一步:从输入缓冲区中取一个字符。为此,我们使用函数GETCHAR,每次调用它,推进先行指针,送回一个字符。 第二步:确定在本状态下,哪一条箭弧是用刚刚来的输入字符标识的。如果找到,控制就转到该弧所指向的状态;
12、若找不到,那么寻找该单词的企图就失败了。 失 败:先行指针必须重新回到开始指针处,并用另一状态图来搜索另一单词。如果所有的状态转换图都试过之后,还没有匹配的,就表明这是一个词法错误,此时,调用错误校正程序。,GETCHAR是过程,将下一输入字符读入CHAR,搜索指示器前移一个字符。,例36:以下CASE语句段对应的状态图: state i: GETCHAR; CASE CHAR OF AZ: state j ; 09: state k ; / : state l ; END; FAIL,字符变量,存放最新读进的源程序字符。,过程,将下一输入字符读入CHAR,搜索指示器前移一个字符。,对于如上的
13、状态转换图,状态0的代码如下所示: state 0: C := GETCHAR ; if LETTER(C) then goto state 1 else FAIL( ),LETTER( )是布尔函数过程,当且仅当C中的字符是字母,它返回真假值TRUE。,FAIL( )是例子程序,它移回先行指针(lookahead pointer), 开始下一状态转换图,或调用出错程序。,例3-7:示例如何把状态结对应于一段程序:,*,对于如上的状态转换图,状态1的代码如下所示: state 1: C := GETCHAR ; if LETTER( C) or DIGIT(C) then goto state
14、 1 else if DELIMITER(C) then goto state 2 else FAIL( ),DIGIT( )是布尔函数过程,当且仅当C中的字符是数字,它返回真假值TRUE。,DELIMITER(C)是过程,只要碰到标识符后的分界符,它返回TRUE。分界符一般为:空格、算术、逻辑符号,括号、;、. 、,。,*,对于如上的状态转换图,终态状态2的代码如下所示: state 2: RETRACT( ) ; RETURN($id ,INSTALL( ) ),RETRACT( )是过程,由于分界符不属于标识符,所以我们要把先行指针回调一个字符。,INSTALL( )是过程,如我们识别出
15、的标识符不在符号表中,我们把它装入符号表。我们还要给语法分析程序返回一个二元式。,*,如果同时识别 标识符和定义符, 则需要修改为 State2:,修改之后,状态2的代码如下所示: state 2: RETRACT( ) ; c := RESERVE( ); if c = 0 then RETURN($id ,INSTALL ) else RETURN(C , _ ),RESERVE( ) 整型函数过程,针对TOKEN中的字符串进行查找,看其是否是保留字,是保留字给出它的编码,否则回送0(假定0不是保留字编码)。,例38:以下程序段对应的状态图 state i:GETCHAR; WHILE L
16、ETTER OR DIGIT DO GETCHAR; state j:,布尔函数过程,它们分别判断CHAR中的字符是数字或是字母,从而给出真假值TRUE、FALSE。,例39:以下程序段对应的状态图 0 9:BEGIN WHILE DIGIT DO BEGIN CONCAT;GETCHAR END; RETRACT; RETURN($INT,DTB) ; END;,RETURN 语句,对应终态结,其中$INT为种别编码,DTB为一个把十进制转换到二进制的转换函数。它把TOKEN中的数字译成标准二进制码,并以此为函数值返回。,正规式与正规集的递归定义: 1、和都是字母表上的正规式,它们所表示的正规集分别为和; 2、任何a,a是上的一个正规式,它所表示的正规集为a; 3、 正规式 正规集 正规式 正