编译原理 第2章 词法分析.ppt

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

1、第2章词法分析2.1词法分析器的设计考虑及手工构造2.1.1单词类型及二元式编码2.1.2源程序的输入及预处理2.1.3基本字的识别和超前搜索2.1.4遍2.1.5状态转换图和词法分析器的手工构造2.2正规式、自动机及词法分析器的自动生成2.2.1基本概念2.2.2正规式与正规集2.2.3确定有限自动机（DFA）2.2.4非确定有限自动机（NFA）2.2.5正规式与确定有限自动机的等价性2.3词法分析器的自动生成12.1词法分析器的设计考虑及手工构造词法分析任务：从文件读入源程序，去除源程序中与编译无关的编辑字符

2、、注释等，由字符拼接单词。每当识别出一个单词，就用单词的内部码（单词二元式）替换。执行词法分析任务的程序称为词法分析器。22.1.1单词类型及二元式编码㈠单词类型任何程序设计语言的单词都可将其分为5种类型，它们是：基本字real、integer、……标识符通常为以字母开始的数字字母串（简单变量、标号、……）常数整常数（123）、实常数（123.456）、……运算符+、*、/、……界符;、(、)、……㈡单词的性质基本字、运算符和界符对于某一程序设计语言来说是确定的，而源程序中的标识符和常数的个数是不确定的，随源程序而

3、异。有些单词由单个字符构成，而有些单词由多个字符构成。3㈢单词二元式编码经词法分析后，单词用二元式(code,val)表示。code表示单词的种别，用整数码表示。单词种别表示单词的语法特性，在语法分析时使用。val表示单词的值，在本书中用字符串表示。单词值表示了单词的语义特性，在语义分析时使用。㈣编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。如果一个种别仅包含一个单词，那么单词种别就可代表该单词，无需给出单词值。为了输入和处理的方便，无意义的单词值用字符串"NUL"表示。若一个种别

4、含有多个单词，除给出种别外，还需给出它的值。4㈤实例设有某一程序设计语言，其部分单词二元式编码如下所示：单词单词种别单词值integeraNULrealcNULbegin{NULend}NUL标识符i字符串形式符号名无符号整常数x字符串形式数字无符号实常数y字符串形式数字==NUL**NUL++NUL((NUL))NUL,,NUL;;NUL计算园柱体表面积的源程序（输入输出略）如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/Realr,h,s;s=2*3.14*r*(r+h)End根据单词

5、二元式编码，上述程序的单词二元式序列应为：('{',"NUL")…………52.1.2源程序的输入及预处理㈠源程序的输入分段读入处理（早期）全部读入后处理源程序以文件形式存于外存，首先要将其读入内存才可进行词法分析。早期计算机内存较小，只能在内存设置长度有限的缓冲区，分段读入源程序进行处理。在编制程序时，必须考虑由于源程序分段读入所产生的问题。例如，由多个字符构成的单词有可能被缓冲区边界所打断（留作习题）。目前计算机所使用的的内存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，故源程序可一次全部读入内存进行处

6、理。6设源程序如下所示，其中''为续行符。Begin/*S=2*3.14*R*R+2*3.14*R*H*/tRealr,h,s;ts=2*3.14*r*(r+h)End......源程序读入后，输入缓冲区的内容如下所示：7㈡预处理词法分析器通常由二个部分构成：预处理程序扫描器（单词识别程序）①分成二部分的理由目前使用的程序设计语言大都采用自由格式书写，允许在单词之间存在多余的空格、换行和制表符（TAB）。源程序通常带有注释，注释不是程序的必要组成部分。有些语言还提供续行功能（例C

7、语言中的续行符''），当一个单词过长（例字符串常数），可分多行列出。对于Fortran和Cobol之类语言，源程序还受到书写格式的限制。词法分析器可在输入缓冲区上直接识别单词，但从程序设计的角度来看，若把源程序预处理一下，则单词识别就比较容易。8②预处理主要工作删除注释删除续行符，以及后续换行符(0AH)。换行符、TAB和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在反而给后续的单词识别带来方便。为了简化判断，可在预处理时，将换行符和TAB统一替换为空格。大多数语言（除C语言）不区分大

8、小写，可在预处理时，将大写字母变换成小写字母，或相反，以方便后续处理。对于受书写格式限制的语言（例Fortran和Cobol），还应识别标号区，正确给出语句标号。识别续行标志，把相继行捻接在一起，给出语句结束符。beginrealr,h,s;s=2*3.14*r*(r+h)end...上述源程序经预处理后，扫描缓冲区中的内容如下所示：9㈢预处理例用伪