第三章词法分析 词法分析是编译的第一个阶段,它的主要任务是从左至 有逐个字符地对源程序进行扫描,产生一个个单词序列,用 以语法分析。执行词法分析的程序称为词法分析程序或扫描 程序。y 3.1词法分析的基本概念 31.1词法分析的意义 词法分析程序完成的是编译第一阶段的王作。词法分析 工作可以是独立的一遍,把字符流的源程序变为单同序列, 输出在一个中间文件上,这个文件做为语法分析程序的输入 而继续编译过程、为减少与外存储器交换数据,将词法分析 程序设计成一个子程序,每当语法分析程序需要一个单词时 则调用该子程序。词法分析程序每得到一次调用,便从
第三章 词法分析 词法分析是编译的第一个阶段，它的主要任务是从左至 右逐个字符地对源程序进行扫描，产生一个个单词序列，用 以语法分析。执行词法分析的程序称为词法分析程序或扫描 程序。 3.1 词法分析的基本概念 3.1.1 词法分析的意义 词法分析程序完成的是编译第一阶段的工作。词法分析 工作可以是独立的一遍，把字符流的源程序变为单同序列， 输出在一个中间文件上，这个文件做为语法分析程序的输入 而继续编译过程、为减少与外存储器交换数据，将词法分析 程序设计成一个子程序，每当语法分析程序需要一个单词时， 则调用该子程序。词法分析程序每得到一次调用，便从
源程序文件中读入一些字符,直到识别出一个单词。停留在空 格、回车、制表符或下一单词的第一个字符为止。这样把词法 分析程序和语法分析程序是放在同一遍里,而省掉了中间文件 节省了运行时间。 正如前面所说,正则文法是上下文无关文法的特例,也就 是说,词法分析可以看作语法分析的的一部分,词法描述完全 可以归并到语法描述中去,。那么为什么将词法分析做为 独立的阶段?为什么把编译过程的分析上作划分成词法分析和 语法分析两个阶段?主要的考虑因素为 1.使整个编译程序的结构更简洁、清晰和条理化。词法分析 比语法分析简单的多,由于源程序结构上的一些细节,常使得 识别单词的工作交给语法分析处理比较曲折和费时。例如,空 白和注释的处理;早期的 FORTRAN受书写格式限制,需在 别单词时进行特殊处理等等。如果这些工作都在语法分析时 并考虑,显然会使得分析程序的结构变得十分复杂
源程序文件中读入一些字符，直到识别出一个单词。停留在空 格、回车、制表符或下一单词的第一个字符为止。这样把词法 分析程序和语法分析程序是放在同一遍里，而省掉了中间文件， 节省了运行时间。 正如前面所说，正则文法是上下文无关文法的特例，也就 是说，词法分析可以看作语法分析的的一部分，词法描述完全 可以归并到语法描述中去，。那么为什么将词法分析做为一个 独立的阶段？为什么把编译过程的分析上作划分成词法分析和 语法分析两个阶段？主要的考虑因素为： 1．使整个编译程序的结构更简洁、清晰和条理化。词法分析 比语法分析简单的多，由于源程序结构上的一些细节，常使得 识别单词的工作交给语法分析处理比较曲折和费时。例如，空 白和注释的处理；早期的FORTRAN受书写格式限制，需在识 别单词时进行特殊处理等等。如果这些工作都在语法分析时一 并考虑，显然会使得分析程序的结构变得十分复杂
2.编译程序的工作效率也是要考虑的。正则文法和上下文 无关文法采用的识别器是不同的,把词法分析从语法分析独立 出来,采用专门的读字符和分离单词的技术可大大加快编译速 度。由于单词的结构可采用与正则文法对应的有限自动机进行 识别,进而可建立词法分析程序的自动构造工具。 3.可增强编译程序的可移植性。在同一个语言的不同实现 中,或多或少地会涉及到与设备有关的特征,比如采用ASC 还是 EBCDIC字符编码。另外语言的字符集的特殊性的处理, 些专用符号,如 PASCAL中的“↑”的表示等等,都可置于 词法分析程序中解决而不影响编译程序其它成分的设计
2．编译程序的工作效率也是要考虑的。正则文法和上下文 无关文法采用的识别器是不同的，把词法分析从语法分析独立 出来，采用专门的读字符和分离单词的技术可大大加快编译速 度。由于单词的结构可采用与正则文法对应的有限自动机进行 识别，进而可建立词法分析程序的自动构造工具。 3．可增强编译程序的可移植性。在同一个语言的不同实现 中，或多或少地会涉及到与设备有关的特征，比如采用 ASCII 还是 EBCDIC字符编码。另外语言的字符集的特殊性的处理， 一些专用符号，如 PASCAL中的“↑”的表示等等，都可置于 词法分析程序中解决而不影响编译程序其它成分的设计
同法分析程序的主要功能是从字符流的源程序中识别单词, 它要从左至右逐个字符地扫描源程序,有时还可完成其它一些 任务。如:,滤掉源程序中的注释和空自(由空格,制表或回车 换行字符引起的空白)、为了使编译程序能将发现的错误信息 与源程序的出错位置联系起来,同法分析程序负责记录新读入 的字符行的行号,以便行号与出错信息相联:在支持宏处理功 能的源请自中,可以词法分析程席完成基预处理等等。也可
词法分析程序的主要功能是从字符流的源程序中识别单词， 它要从左至右逐个字符地扫描源程序，有时还可完成其它一些 任务。如：滤掉源程序中的注释和空白（由空格，制表或回车 换行字符引起的空白）、为了使编译程序能将发现的错误信息 与源程序的出错位置联系起来，同法分析程序负责记录新读入 的字符行的行号，以便行号与出错信息相联；在支持宏处理功 能的源语自中，可以由词法分析程序完成其预处理等等。也可 完成一些语法分析的工作，如：说明部分的处理
3.1.2词法分析的输入输出 词法分析程序的功能是读入源程序,输出单词符号。词法 分析是读入文本文件的源程序,读入文本文件可采用从文件中逐 个读入符号,或者建立一个缓冲区,先将字符读入缓冲区,然后从 缓冲区中读入字符,使用缓冲区也可以采用双区域方式,即将 缓冲区分成二部分一部分在分析时,更换另一部数据,从而提 词法分析的效率。 单词符号是一个程序设计语言的基本语法符号。程序设计 语言的单同符号大致可分成5种: 1基本字,也称关键字,如 PASCAL语言中的 begin,end, if; while和var等。 2标识符,用来表示各种名字,如常量名、变量名、类型名、 函数名和过程名等。 3.常数,各种类型的常数,如25,3.1415,TRUE和“ABC” 等
3.1.2词法分析的输入输出 词法分析程序的功能是读入源程序，输出单词符号。词法 分析是读入文本文件的源程序,读入文本文件可采用从文件中逐 个读入符号,或者建立一个缓冲区,先将字符读入缓冲区,然后从 缓冲区中读入字符，使用缓冲区也可以采用双区域方式，即将 缓冲区分成二部分一部分在分析时，更换另一部数据，从而提 高词法分析的效率。 单词符号是一个程序设计语言的基本语法符号。程序设计 语言的单同符号大致可分成5种： 1.基本字，也称关键字，如 PASCAL语言中的 begin，end， if；while和 var等。 2.标识符，用来表示各种名字，如常量名、变量名、类型名、 函数名和过程名等。 3.常数，各种类型的常数，如 25，3.1415，TRUE和“ABC” 等
4运算符,如+,-,*,,<=等 5界符,如逗点,分号,括号,冒号等 词法分析程序所输出的单词符号常常采用以下二元式表示 (单词种别,单词自身的值)。单词的种别是语法分析需要的 信息,而单词自身的值则是编译其它阶段需要的信息。比如在 PASCAL的语句 const E=25,yes=1;中的单词25和1的种别 都是常数,常数的值25和1;对于代码生成来说,是必不可少 的、有时,对某些单词来说,不仅仅需要它的值还需要其它 些信息以便编译的进行。比如,对于标识符来说,还需要记载 它的类别。层次还有其它属性,如果这些属性统统收集在符号 表中,那么可以将单词的二元式表示设计成如下形式(标识符, 指向该标识符所在符号表中位置的指什),如上述语句中的单 词和yes的表示为:
4.运算符，如+,-,*,/,<=等。 5.界符，如逗点，分号，括号,冒号等。 词法分析程序所输出的单词符号常常采用以下二元式表示 （单词种别，单词自身的值）。单词的种别是语法分析需要的 信息，而单词自身的值则是编译其它阶段需要的信息。比如在 PASCAL的语句 const i=25， yes=1；中的单词 25和 1的种别 都是常数，常数的值25和1；对于代码生成来说，是必不可少 的、有时，对某些单词来说，不仅仅需要它的值,还需要其它一 些信息以便编译的进行。比如，对于标识符来说，还需要记载 它的类别。层次还有其它属性，如果这些属性统统收集在符号 表中，那么可以将单词的二元式表示设计成如下形式（标识符, 指向该标识符所在符号表中位置的指什），如上述语句中的单 词i和yes的表示为：
(标识符,指向i的表项的指针) (标识符,指向yes的表项的指针) 单词的种别可以用整数编码表示,设标识符编码为1,常数为 2,保留字为3,运算符为4,界符为5 这种码称为机内码。 例:写出程序段i=5 then x=y; 在经词法分析器扫描后输出的单词符号和它们的表示
（标识符，指向i的表项的指针） （标识符，指向yes的表项的指针） 单词的种别可以用整数编码表示，设标识符编码为1，常数为 2，保留字为3，运算符为4，界符为5. 这种码称为机内码。 例：写出程序段if i=5 then x:=y; 在经词法分析器扫描后输出的单词符号和它们的表示
答: 保留字i(3,‘if) 标识符i(1,指向符号表入口) 等号 (4, 常数5(2.“5) 保留字then(3,‘then') 标识符x(1,指向x的符号表入口) 赋值号:=(4:=”) 标识符y(1,指向y的符号表入口) 分号 (5, 综上所述可以把单词表示为:(内部码,属性)的二元式
答： 保留字if （3，‘if’） 标识符i （1，指向i的符号表入口） 等号= （4，‘=’） 常数5 （2．‘5’） 保留字then （3，‘then’） 标识符x （1，指向x的符号表入口） 赋值号:= （4‘:=’） 标识符y （1，指向y的符号表入口） 分号； （5，‘；’） 综上所述可以把单词表示为：（内部码，属性）的二元式
3.1.3词法分析的实现方法 词法分析的实现主要有二种方法,一是将词法分析单独写 成一个独立的程序,其工作作为独立的一遍,把字符流的源程 序变为单同序列,输出在一个某个中间文件上(也可直接存放 在内存中),另一种方法是将词法分析程序设计成一个子程序, 每当语法分析程序需要一个单词时,则调用该子程序。词法分 析程序每得到一次调用,便从源程序文件中读入一些字符,直 到识别出一个单词。停留在空格、回车、制表符或下一单词的 第一个字符为止。这样把词法分析程序和语法分析程序是放在 同一遍里,而省掉了中间文件,节省了运行时间
3.1.3 词法分析的实现方法 词法分析的实现主要有二种方法，一是将词法分析单独写 成一个独立的程序，其工作作为独立的一遍，把字符流的源程 序变为单同序列，输出在一个某个中间文件上（也可直接存放 在内存中），另一种方法是将词法分析程序设计成一个子程序， 每当语法分析程序需要一个单词时，则调用该子程序。词法分 析程序每得到一次调用，便从源程序文件中读入一些字符，直 到识别出一个单词。停留在空格、回车、制表符或下一单词的 第一个字符为止。这样把词法分析程序和语法分析程序是放在 同一遍里，而省掉了中间文件，节省了运行时间
32正规式自动机和状态图 321正规式的表示 在编译程序设计时,应尽量减少语法规则,从而提高编译 程序的效率,那么如何使设计的正规规则最少,或者当一个语 言较复杂时,怎样能够判定它是否能用正规文法表示,以及如 何自动生词法分析程序等到,都需要用一种新的表示方法,为 些引进了正规式和正则集。在这里可以用正规式来描述单词符 号语言中的基本语法符号,井且基于正规式这类描述工具,可 以建立词法分析技术,进而可以建立词法分析程序的自动构造 方法
3.2 正规式自动机和状态图 3.2.1正规式的表示 在编译程序设计时，应尽量减少语法规则，从而提高编译 程序的效率，那么如何使设计的正规规则最少，或者当一个语 言较复杂时，怎样能够判定它是否能用正规文法表示，以及如 何自动生词法分析程序等到，都需要用一种新的表示方法，为 些引进了正规式和正则集。在这里可以用正规式来描述单词符 号语言中的基本语法符号，井且基于正规式这类描述工具，可 以建立词法分析技术，进而可以建立词法分析程序的自动构造 方法