第四章 词法分析.doc

第四章 词法分析器与单词符号第四章 词法分析1、教学目的及要求：词法分析的主要任务是对源程序进行扫描，从中识别出单词，它是编译过程的第一步，也是编译过程中不可缺少的部分。明确词法分析在编译过程所处的阶段和作用。 掌握词法分析程序的手工实现方法。 理解通常的单词分类和构词规则。 会使用单词的描述和识别机制。 掌握词法分析程序的自动构造原理。2、教学内容：本章介绍词法分析程序的手工构造和自动构造原理。3、教学重点：重点：词法分析器的任务与设计。4、教学难点： 如何设计和实现词法分析程序。5、课前思考 词法分析程序的功能是什么？ PL/0词法分析程序识别哪几种单词？ 画出PL/0词法分析程序的流程图。 C语言，PASCAL语言的标识符和数的表示分别有什么规定？ 编写一个程序（C的，或PASCAL的）识别C+语言的标识符。6、章节内容第一节 词法分析器与单词符号第二节 扫描程序的设计第三节 标识符的处理第四节设计词法分析程序的直接方法4.1 词法分析器与单词符号一、词法分析器词法分析器：编译程序中完成词法分析任务的程序段称为词法分析器。扫描器：词法分析器负责对源程序进行扫描，从中识别出一个个的单词符号，因此词法分析器又称为扫描器。词法分析的任务：从左至右逐个字符地扫描源程序形式的字符流，将这些单个字符组合成一个个单词符号，把作为字符串的源程序转换成由单词符号串组成的中间语言程序供语法分析使用。因此，词法分析是编译程序的基础。词法分析阶段的必要性 ：描述单词结构的语法比其它语法结构简单得多，仅用3型文法就足够，把单词的识别从整个语法识别中划分出来，可以使我们采用更有效的方法和工具，如状态转移图、有穷自动机等，同时还可利用这些工具建立词法分析程序的自动生成器。对不设键字的语言如某些非标准Fortran，其中某些标识符的识别需超前扫描，分析上下文才能准确识别，将这种特殊地方分离出来，有利于保证语法分析方式的一致性。词法分析与语法分析分离，可使整个编译程序的各部分功能更加单一，编译程序结构更加清晰，有利于编译程序的维护。可以把词法分析程序作为独立的一遍去编写，实现源程序的全部词法分析工作，并将转换后的内部形式的源程序传递给语法分析程序。也可将它设计成一个子程序。二、 单词符号单词符号是语言的基本符号，它具有独立的意义且是不可再分的。程序语言中的大部分单词符号都属于下述几类之一。 标识符。用以表示各种名字，如变量名，过程名等等。 保留字。如if，goto，begin，end等等。 常数。125，3.8，0，1等等； 运算符。如，*，/，等等。 分界符。如逗号、分号和括号等等。例：识别标识符的状态转换图如下图所示： 识别标识符的过程为： 从初态0开始，若输入符号是一字母，则读进它，并转到状态1；在状态1下，若下一个输入符号是字母或数字则读进它，并重新进入状态1； 重复这个过程，直至在状态1下发现读入的符号不再是字母或数字时(注意，此时该字符已被读出)，就进入状态2。 状态2是终态，至此已识别出一个标识符，识别过程终止。若在状态0下输入符号不是字母，则意味着识别不出所给的输入串是一个标识符。4.2 扫描程序的设计一、源程序的输入为节省内存，通常在内存开辟一个大小适宜的输入缓冲区，将源程序分批读入缓冲区。词法分析程序从缓冲区中读取字符。预处理：剔除空白符、跳格符、回车、换行和注释等非程序的必要部分；将相继的若干个空白符合成一个。 超前搜索：一般高级语言不必超前搜索，每个单词间有明确的界符。某些语言的单词间没有明确的界符，究竟起什么作用，要在上下文环境中才能识别。在读到一个单词后，在输入缓冲区或扫描缓冲区上做个标记，然后继续向前读，直到明确了刚才单词的含义之后，再退回到标记处重新分析，这个过程就是超前搜索。超前搜索举例(FORTRAN语句)：(1)IF(M) 10,20,30 算术条件语(2)IF(5.EQ.M) GOTO 50 逻辑条件语句(3)IF=100 简单变量赋值(4)If(100)=ABC 下标变量赋值*当读到IF时不能区分IF做什么，需要超前搜索。 *单词起点指示器搜索指示器源程序输入缓冲区： 将源程序输入到缓冲区中，不论缓冲区多大，均不能避免单词符号不被其边界打断。为解决该问题，可将缓冲区分成相等的两个区。二、状态转换图语言的词法规则满足正规式要求，可以构造出它的状态转换图。 将终结符和非终结符用相应的缩写符号代替。 所有的规则用相应的状态转换图表示，再将各个状态转换图的初态连在一起，就成了识别一门语言的FA。 扫描器从初态出发，当识别一个单词后便进入终态，同时送出二元式。 三、根据状态图设计词法分析程序状态转换图实质上就是词法分析程序的流程图，根据它可以很容易编写出对应的词法分析程序。根据画出的识别单词的状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。词法分析程序的输出为单词符号的内部表示二元式。4.3 标识符的处理在词法分析中，标识符的处理比其它单词的处理复杂得多，且涉及面也很广，因此在编译程序中，标识符的处理占有极为重要的位置。标识符的处理主要包括其语义表示、作用域处理、符号表构造以及内存单元分配等工作。标识符处理的难易程度依赖于语言的数据结构的复杂程度。一般来说数据结构越复杂，标识符的处理也就越复杂。一、类型的机内表示标识符的类型在机内采用位向量的形式表示。如下图所示。其中，vector.v=1表示简单变量 vector.a=1表示数组vector.i=1表示整数 vector.r=1表示实型vector.b=1表示布尔型 vector.c=1表示字符型二、标识符的语义表示标识符一旦被赋予各种不同的语义，就可以用来标识变量、数组、函数、过程等。标识符的语义信息可用一个机器字（机内符）来存放，如果信息过多，一个机内符存放不下，可在此机内符中存放部分语义信息，其余语义信息则存放在一个信息表区中。三、符号表（标识符表）在编译过程中，源程序中的标识符及其语义属性都要记录在表格符号表中，这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等，对于过程标识符，还有参数信息，包括参数的个数及类型，参数传递的方式以及返回的类型等。标识符的全部属性是在编译程序的各个阶段逐步获得。在编译程序的各个阶段，不仅要用获取的标识符信息去更新符号表中的内容，添加新的标识符及其属性，而且需要去查找符号表，引用符号表中的信息。符号表在编译过程中使用频繁，是影响编译速度的主要因素，因此，对符号表的组织要求考虑存储与查找的效率。四、标识符处理的基本思想程序中标识符分为定义性标识符和使用性标识符两大类，前者是指在说明部分出现的标识符，后者是指在语句部分出现的标识符。例：VAR integer a,b; Procedure p(x,y)real x,y;其中的标识符a,b,p,x,y都是定义性标识符。y:=3.14*r*r其中标识符y和r都是使用性标识符。标识符处理的基本思想：1、当遇到定义性标识符时，先查找符号表 若此标识符已在符号表中登记过，则表明该标识符被重复申明，应作出错处理； 若未登记过，则构造此标识符的机内符，并在符号表中进行登记。2、当遇到使用性标识符时，也查找符号表 若找到，则获取此标识符相应的机内符； 若未找到，则表明该标识符未定义，应作出错处理。4.4 设计词法分析程序的直接方法一、由正规文法设计词法分析程序正规文法NFADFADFA化简词法分析程序二、由正规表达式设计词法分析程序正规表达式NFADFADFA化简词法分析程序本章小结1、词法分析是编译过程的第一阶段，是编译过程的基础。它负责对源程序扫描，从中识别出一个个的单词。 2、单词是程序设计语言的基本语法单位和最小的语义单位。单