编译原理第3章.ppt

《编译原理第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章词法分析这一章将讨论词法分析程序的构造。词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。前一部分讨论手工构造方法，后一部分讨论自动构造方法。3.1对于词法分析器的要求词法分析器的功能和输出形式词法分析器的功能是输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列五种。(1)关键字（保留字或基本字）(2)标识符(3)常数（整型、实型、布尔型、文字型等）(4)运算符(5)界符(逗号、分号、括号、／*，

2、*／等)词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）考虑下述c＋＋代码段：while（i＞=j）i--;经词法分析器处理后，它将被转换为如下的单词符号序列：＜while，-＞＜（，-＞＜id，指向i的符号表项的指针＞＜＞＝，-＞＜id,指向j的符号表项的指针＞＜），-＞＜id，指向i的符号表项的指针>＜--，-＞＜；，-＞词法分析器作为一个独立子程序可使整个编译程序的结构更简洁、清晰和条理化。也可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调

3、用，词法分析器就从输人串中识别出一个单词符号，把它交给语法分析器。3.2词法分析器的设计输入、预处理词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。起点指示器搜索指示器超前扫描关健字的识别：（如FORTRAN语言)1D099K＝1，102IF（5．EQ．M）I=103D099K＝1．104IF(5)＝55标识符的识别常数的识别算符和界符的识别状

4、态转换图转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是初态，而且实际上至少要有一个终态（用双圈表示）。一个状态转换图可用于识别（或接受）一定的字符串。123XY012字母字母或数字其它012数字数字其它06123457.数字数字数字数字数字数字数字E或DE或D+或-其它*其它.状态转换图的实现(1)ch字符变量，存放最新读进的源程序字符。

5、(2)strToken字符数组，存放构成单词符号的字符串。(3)GetChar子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。(4)GetBC子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符(5)Concat子程序过程，将ch中的字符连接到strToken之后。(6)IsLetter和IsDigit布尔函数过程，它们分别判断ch中的字符是否为字母和数字。(7)Reserve整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，

6、否则返回0值（假定0不是保留字的编码）。(8)Retract子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。(9)InsertId整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。(10）InsertConst整型函数过程，将strToken中的常数插入常数表，返回常数表指针。对于不含回路的分叉结点来说，可让它对应一个switch语句或一组if...then...else语句。例如，下图状态结点i所对应的程序段可表示为：GetChar(）；if（IsLetter（））{…状态J的对应程序

7、段…；｝elseif（IsDigit（））{…状态k的对应程序段…；｝elseif（ch＝‘／’）{…状态I的对应程序段…；｝else{…错误处理…；｝ijkl字母数字/对于含回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段。例如，下图的状态结点i所对应的程序段可为：GetChar(）；while（IsLetter(）orIsDigit(））GetChar（）；…状态j的对应程序段…ij字母或数字其它终态结点一般对应一个形如return（code，value）的语句。其中，code为单词种别编码；

8、value或是单词符号的属性值，或无定义。3.3正规表达式与有限自动机正规式与正规集正规式和正规集的递归定义：（1）ε和φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和φ(2)任何a€Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；(3)假定U和V都是Σ上的正规式，它们所表示的正规集分别记为L(U)和L(V)