《第2讲--词法分析》由会员分享，可在线阅读，更多相关《第2讲--词法分析（78页珍藏版）》请在金锄头文库上搜索。
1、第二讲 词法分析,词法分析器的构造 正规表达式与有穷自动机 词法分析器的自动产生,CompilerPrinciples,2,1.词法分析器的构造,编译程序首先在单词级别上来分析和翻译源程序。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，即把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器(通常又称为扫描器,scanner）。,CompilerPrinciples,3,一、一般考虑：,1.词法分析程序的主要任务： 读入字符串形式的源程序输入 剔除非单词符号空格、换行，注释 宏展开， 拼单词符号*、:=、FOR
2、、BEGIN等 源程序的列表输出 行号,CompilerPrinciples,4,2.词法分析器的输入和输出形式 输入字符串形式的源程序 输出单词符号串。 程序语言的单词符号一般分为五种： 关键字、运算符、界符、标识符、常数 词法分析器输出的单词符号常常表示为二元式： （单词种类编号，单词符号的属性值）,CompilerPrinciples,5,单词种类编号 一个语言的单词符号分成几种，怎样编码是一个技术性问题，它取决于处理上的方便。 标识符一般归为一种。常数则宜按类型（整、实、布尔、字符等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符
3、一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。,CompilerPrinciples,6,单词符号的属性值 如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因此属性值就没有意义了。若同一个种别含有多个单词符号，那麽对于它的每个单词符号，除了给出种别编码之外，还应给出各有关单词符号的属性信息。 属性值是反映特性或特征的值。例如，对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个字符串常量，则将该串的首地址指针作为其属性值。,CompilerPrinciples,7,作为例子考虑下述C+语句： while
4、(i=j) i- -; 若while种别为01,(种别为11,标识符种别为20,=种别为12,)种别为13,种别为14,;种别为30,则经词法分析器处理后，它将被转换为如下的单词符号序列： ( 01, ) ( 11, ) ( 20 ,指向i的符号表项的指针 ) ( 12 , ) ( 20 ,指向j的符号表项的指针 ) ( 13 , ) ( 20 ,指向i的符号表项的指针 ) ( 14 , ) ( 30 , ),CompilerPrinciples,8,3.词法分析器与语法分析器的衔接 通常把词法分析器安排成一个独立子程序，而不是单独的一遍。这样一来，就无须在存储器中保留整个单词符号串，而是每当
5、语法分析器需要单词符号时就调用这个子程序。每一次调用，词法分析器就从源程序字符串中识别出一个（一批）单词符号，把它交给语法分析器。这样做的好处是： 压缩编译时扫描字符的时间 词法规则描述简单，也便于独立处理； 使得语法分析获得更多信息（上下文环境）； 便于处理同一语言的几种不同表示形式（扩展）；,CompilerPrinciples,9,由以上考虑，可以初步设计为：,CompilerPrinciples,10,二、进一步考虑： 1. 输入、预处理 输入串一般放在一个缓冲区中，这个缓冲区称源程序输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号
6、的识别工作将是比较方便的。 预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注释等。于是可以设想构造一个预处理子程序，它完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接而方便地进行单词符号的识别工作。,CompilerPrinciples,11,2.对半互补缓冲区 分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识别单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。 但是不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区
7、的边界所打断。 因此，扫描缓冲区最好使用一分为二的区域，并使两区首尾相接，形成一个对半互补缓冲区。,CompilerPrinciples,12,例如：,。W h i l e。,起点指针,搜索指针,CompilerPrinciples,13,综上所述，预处理子程序、扫描器和语法分析器相互之间的关系及工作情况可图示如下：,CompilerPrinciples,14,3. 单词符号识别超前搜索技术 问题发生在对基本字不加任何保护的语言中，基本字及用户自定义的标识符或标号之间无特殊分界符，这使得关键字的识别甚为麻烦。 请看下面的例子： 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 D
8、O99K=1.10 4 IF(5)=55 这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以某基本字开头的。语句3和4是赋值语句，它们都是以用户自定义的标识符开头的。,CompilerPrinciples,15,为了从1、2中识别出关键字DO和IF，我们必须要能够区别1、3和区别2、4。语句1、3的区别在于等号之后的第一个界符：一个为逗号，另一个为小数点，语句2、4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了识别 1、2句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。 这种向前扫描若干字符直到找到能区分单词
9、的字符为止的技术就叫超前搜索。,CompilerPrinciples,16,单一符号运算符和复合运算符：,CompilerPrinciples,17,CompilerPrinciples,18,4. 词法错误 如果没有其他组件的帮助，词法分析器很难发现源代码中的错误。,CompilerPrinciples,19,例在TurboC下运行下面的C程序 1 int main() 2 int x = 3 ; 3 if( x%2 = 0 ) /* even number */ 4 return 0 ; 5 else /* odd number */ 6 return 1 ; 7 ,CompilerPri
10、nciples,20,如果把 if 写成 iif ，则编译得到以下2条错误信息： Error4: Statement missing ; in function main. Error5: Misplaced else in function main. 如果把 else 写成 els ，则编译得到以下3条错误信息： Error6: Undefined symbol els in function main. Warning6: Code has no effect in function main. Error6: Statement missing ; in function main.,
11、CompilerPrinciples,21,现在有关扫描器的输入、处理、输出等问题都清楚了，可以进行扫描器的设计了。为此，引入一种新的图形工具-状态转换图。 1. 状态转换图是一张有限个结点的有向图，结点代表状态，用圆圈表示，状态之间用带标识的箭弧连结，箭弧上的标识代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。,三、状态转换图,CompilerPrinciples,22,如右图所示： 在状态1下，若输入字符为a，则读进a，并转换到状态2。若输入字符为b，则读进b，并转换到状态3。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用
12、双圈表示），图中3为终态。,状态转换图,a,b,CompilerPrinciples,23,2.状态转换图可用来识别一定的字符串 例如： 字母|字母|数字 数字|数字 终态上打个*号，表示多读进了一个不属于该标识符或数字部分的字符，应把它退还给输入串。,CompilerPrinciples,24,*,0,1,2,3,4,5,6,数字,数字,数字,E或D,E或D,+或-,数字,数字,数字,数字,其它,其它,上图是识别Fortran实常数的转换图,CompilerPrinciples,25,3.状态转换图可以用来识别程序语言的单词符号,例：假设某程序语言只有前述的五类单词符号，运算符只有+、*、=
13、，界符只有#、(、)，那么就可以用左边的状态转换图来识别其所有单词符号。 012识别的串是基本字还是标识符，要查保留字表区分。 当然，还要加上两个限制： (1)所有基本字都是保留的； (2)所有单词间若无明显分界，则用空格分开；,空白,字母或数字,*,*,CompilerPrinciples,26,4.状态转换图的程序实现-为每个状态编写一小段程序即可,例：使用如下一组全局变量和过程，作为实现状态转换图的基本部分： CHAR：字符变量，存放最新读进的源程序字符； Token：字符数组，存放构成单词符号的符号串； GetChar：取字符过程，将下一个输入字符读到CHAR中，并把搜索指示器的指针前
14、移一个字符位置； GetBC：检查CHAR中的字符是否为空白，若是则调用GetChar直至CHAR中进入一个非空白字符； ConCat：拼单词过程，每调用一次就将CHAR中的字符连接到Token之后；,CompilerPrinciples,27, IsLetter和IsDigit：两个布尔函数，分别判断CHAR中的字符为字母或是数字而返回真假值； Reserve：整型函数，对Token中的字符串查保留字表，查到则返回该保留字的整型编码，否则返回0值； Retract：回退子程序，专门用来把搜索指示器回调一个字符位置，并置CHAR为空； Error：出错处理子程序； DTB：类型转换函数，将To
15、ken中的十进制数转换为二进制数； 于是，可编出如下程序： Start: Token:= ; GetChar ; GetBC ;,CompilerPrinciples,28,CASE CHAR OF Az: BEGIN WHILE IsLetter OR IsDigit DO BEGIN ConCat; GetChar END; Retract; C:=Reserve; IF C=0 THEN Return($ID,Token) ELSE Return(C,) END; 09: BEGIN WHILE IsDigit DO BEGIN ConCat ; GetChar END; Retract; Return($INT, DTB) END; =: Return($ASSIGN, ) ; +: Return($PLUS, ) ; *: Return($START, ) ; (: Return($LPAR, ) ; ): Return($RPAR, ) ; #: Return($ , ) ; END OF CASE; DealError; Goto Start;,CompilerPrinciples,29,2.正规表达式与有穷自动机 Regular Expression and Finite Automata,上一节我们讨论了扫描器的手工编制，是在讨论了Scanner的主要
