《第2章 词法分析.ppt》由会员分享，可在线阅读，更多相关《第2章 词法分析.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022/12/3112.1 词法分析器的设计考虑及词法分析器的设计考虑及手工构造手工构造词法分析任务：词法分析任务：从文件读入源程序，去除源程序中与编从文件读入源程序，去除源程序中与编译无关的编辑字符、注释等，由字符拼接译无关的编辑字符、注释等，由字符拼接单词。每当识别出一个单词，就用单词的单词。每当识别出一个单词，就用单词的内部码（单词二元式）替换。执行词法分内部码（单词二元式）替换。执行词法分析任务的程序称为词法分析器。析任务的程序称为词法分析器。2022/12/3122.1.1 单词类型及二元式编码单词类型及二元式编码单词类型单词类型 任何程序设计语言的单词都可将其分为任何程序设计语言
2、的单词都可将其分为任何程序设计语言的单词都可将其分为任何程序设计语言的单词都可将其分为5 5种类型，它们是：种类型，它们是：种类型，它们是：种类型，它们是：基本字基本字基本字基本字 realreal、integerinteger、标识符标识符标识符标识符 通常为以字母开始的数字字母串（简单变量、标号、通常为以字母开始的数字字母串（简单变量、标号、通常为以字母开始的数字字母串（简单变量、标号、通常为以字母开始的数字字母串（简单变量、标号、）常数常数常数常数整常数（整常数（整常数（整常数（123123）、实常数（）、实常数（）、实常数（）、实常数（123.456123.456）、）、）、）、运算符
3、运算符运算符运算符+、*、/、界符界符界符界符;、(、)、单词的性质单词的性质基本字、运算符和界符对于某一程序设计语言来说是确定基本字、运算符和界符对于某一程序设计语言来说是确定基本字、运算符和界符对于某一程序设计语言来说是确定基本字、运算符和界符对于某一程序设计语言来说是确定的，而源程序中的标识符和常数的个数是不确定的，随源程的，而源程序中的标识符和常数的个数是不确定的，随源程的，而源程序中的标识符和常数的个数是不确定的，随源程的，而源程序中的标识符和常数的个数是不确定的，随源程序而异。序而异。序而异。序而异。有些单词由单个字符构成，而有些单词由多个字符构成。有些单词由单个字符构成，而有些单
4、词由多个字符构成。有些单词由单个字符构成，而有些单词由多个字符构成。有些单词由单个字符构成，而有些单词由多个字符构成。2022/12/313单词二元式编码单词二元式编码 经词法分析后，单词用二元式经词法分析后，单词用二元式经词法分析后，单词用二元式经词法分析后，单词用二元式 (code,val)(code,val)表示。表示。表示。表示。codecode表示单词的种别，用整数码表示。单词种别表示单词表示单词的种别，用整数码表示。单词种别表示单词表示单词的种别，用整数码表示。单词种别表示单词表示单词的种别，用整数码表示。单词种别表示单词的语法特性，在语法分析时使用。的语法特性，在语法分析时使用。
5、的语法特性，在语法分析时使用。的语法特性，在语法分析时使用。valval表示单词的值，在本书中用字符串表示。单词值表示了表示单词的值，在本书中用字符串表示。单词值表示了表示单词的值，在本书中用字符串表示。单词值表示了表示单词的值，在本书中用字符串表示。单词值表示了单词的语义特性，在语义分析时使用。单词的语义特性，在语义分析时使用。单词的语义特性，在语义分析时使用。单词的语义特性，在语义分析时使用。编码原则编码原则通常将标识符归为一种，常数按类型分种，基本字、运算通常将标识符归为一种，常数按类型分种，基本字、运算通常将标识符归为一种，常数按类型分种，基本字、运算通常将标识符归为一种，常数按类型分
6、种，基本字、运算符及界符采用一符一种。符及界符采用一符一种。符及界符采用一符一种。符及界符采用一符一种。如果一个种别仅包含一个单词，那么单词种别就可代表该如果一个种别仅包含一个单词，那么单词种别就可代表该如果一个种别仅包含一个单词，那么单词种别就可代表该如果一个种别仅包含一个单词，那么单词种别就可代表该单词，无需给出单词值。为了输入和处理的方便，无意义的单词，无需给出单词值。为了输入和处理的方便，无意义的单词，无需给出单词值。为了输入和处理的方便，无意义的单词，无需给出单词值。为了输入和处理的方便，无意义的单词值用字符串单词值用字符串单词值用字符串单词值用字符串NULNUL表示。若一个种别含有
7、多个单词，除表示。若一个种别含有多个单词，除表示。若一个种别含有多个单词，除表示。若一个种别含有多个单词，除给出种别外，还需给出它的值。给出种别外，还需给出它的值。给出种别外，还需给出它的值。给出种别外，还需给出它的值。2022/12/314实例实例 设有某一程序设计语言，其部分单词二元式编码如下所示：设有某一程序设计语言，其部分单词二元式编码如下所示：设有某一程序设计语言，其部分单词二元式编码如下所示：设有某一程序设计语言，其部分单词二元式编码如下所示：单词单词单词单词 单词种别单词种别单词种别单词种别单词值单词值单词值单词值 integer integer a aNULNULrealrea
8、lc cNULNULbeginbegin NULNULendend NULNUL标识符标识符标识符标识符 i i字符串形式符号名字符串形式符号名字符串形式符号名字符串形式符号名 无符号整常数无符号整常数无符号整常数无符号整常数 x x字符串形式数字字符串形式数字字符串形式数字字符串形式数字 无符号实常数无符号实常数无符号实常数无符号实常数 y y字符串形式数字字符串形式数字字符串形式数字字符串形式数字 =NULNUL*NULNUL+NULNUL(NULNUL)NULNUL,NULNUL;NULNUL 计算园柱体表面积的源计算园柱体表面积的源计算园柱体表面积的源计算园柱体表面积的源程序（输入输出
9、略）如下程序（输入输出略）如下程序（输入输出略）如下程序（输入输出略）如下所示：所示：所示：所示：Begin/*S=2*3.14*R*R Begin/*S=2*3.14*R*R+2*3.14*R*H*/+2*3.14*R*H*/Real r,h,s;Real r,h,s;s=2*3.14*r*(r+h)s=2*3.14*r*(r+h)EndEnd 根据单词二元式编码，根据单词二元式编码，根据单词二元式编码，根据单词二元式编码，上述程序的单词二元式序上述程序的单词二元式序上述程序的单词二元式序上述程序的单词二元式序列应为：列应为：列应为：列应为：(,NUL)(,NUL)2022/12/3152.
10、1.2 源程序的输入及预处理源程序的输入及预处理 源程序的输入源程序的输入分段读入处理（早期）分段读入处理（早期）分段读入处理（早期）分段读入处理（早期）全部读入后处理全部读入后处理全部读入后处理全部读入后处理 源程序以文件形式存于外存，首先要将其读入内存才可进行词源程序以文件形式存于外存，首先要将其读入内存才可进行词源程序以文件形式存于外存，首先要将其读入内存才可进行词源程序以文件形式存于外存，首先要将其读入内存才可进行词法分析。早期计算机内存较小，只能在内存设置长度有限的缓冲法分析。早期计算机内存较小，只能在内存设置长度有限的缓冲法分析。早期计算机内存较小，只能在内存设置长度有限的缓冲法分
11、析。早期计算机内存较小，只能在内存设置长度有限的缓冲区，分段读入源程序进行处理。在编制程序时，必须考虑由于源区，分段读入源程序进行处理。在编制程序时，必须考虑由于源区，分段读入源程序进行处理。在编制程序时，必须考虑由于源区，分段读入源程序进行处理。在编制程序时，必须考虑由于源程序分段读入所产生的问题。例如，由多个字符构成的单词有可程序分段读入所产生的问题。例如，由多个字符构成的单词有可程序分段读入所产生的问题。例如，由多个字符构成的单词有可程序分段读入所产生的问题。例如，由多个字符构成的单词有可能被缓冲区边界所打断（留作习题）。目前计算机所使用的的内能被缓冲区边界所打断（留作习题）。目前计算机
12、所使用的的内能被缓冲区边界所打断（留作习题）。目前计算机所使用的的内能被缓冲区边界所打断（留作习题）。目前计算机所使用的的内存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，故源程序可一次全部读入内存进行处理。故源程序可一次全部读入内存进行处理。故源程序可一次全部读入内存进行处理。故源程序可一次全部读入内存进行处理。2022/12/316 设源程序如下所示，其中设源程序如下所示，其中设源程序如下所示，其中设源程序如
13、下所示，其中 为续行符。为续行符。为续行符。为续行符。B B e e g g i i n n/*S S=2 2*3 3.1 1 4 4*R R*R R+2 2*3 3.1 1 4 4*R R*HH*/nn t t R R e e a a l l r r,h h,s s;nnt t s s=2 2*3 3.nn 1 1 4 4*r r*(r r+h h)nn E E n n d dnn 00.00源程序读入后，输入缓冲区的内容如下所示：源程序读入后，输入缓冲区的内容如下所示：源程序读入后，输入缓冲区的内容如下所示：源程序读入后，输入缓冲区的内容如下所示：2022/12/317预处理预处理 词法分
14、析器通常由二个部分构成：词法分析器通常由二个部分构成：词法分析器通常由二个部分构成：词法分析器通常由二个部分构成：预处理程序预处理程序预处理程序预处理程序扫描器（单词识别程序）扫描器（单词识别程序）扫描器（单词识别程序）扫描器（单词识别程序）分成二部分的理由分成二部分的理由分成二部分的理由分成二部分的理由目前使用的程序设计语言大都采用自由格式书写，允许在单目前使用的程序设计语言大都采用自由格式书写，允许在单目前使用的程序设计语言大都采用自由格式书写，允许在单目前使用的程序设计语言大都采用自由格式书写，允许在单词之间存在多余的空格、换行和制表符（词之间存在多余的空格、换行和制表符（词之间存在多余
15、的空格、换行和制表符（词之间存在多余的空格、换行和制表符（TABTAB）。）。）。）。源程序通常带有注释，注释不是程序的必要组成部分。源程序通常带有注释，注释不是程序的必要组成部分。源程序通常带有注释，注释不是程序的必要组成部分。源程序通常带有注释，注释不是程序的必要组成部分。有些语言还提供续行功能（例有些语言还提供续行功能（例有些语言还提供续行功能（例有些语言还提供续行功能（例C C语言中的续行符语言中的续行符语言中的续行符语言中的续行符），当一），当一），当一），当一个单词过长（例字符串常数），可分多行列出。个单词过长（例字符串常数），可分多行列出。个单词过长（例字符串常数），可分多行列出
16、。个单词过长（例字符串常数），可分多行列出。对于对于对于对于FortranFortran和和和和CobolCobol之类语言，源程序还受到书写格式的之类语言，源程序还受到书写格式的之类语言，源程序还受到书写格式的之类语言，源程序还受到书写格式的限制。限制。限制。限制。词法分析器可在输入缓冲区上直接识别单词，但从程序设计的词法分析器可在输入缓冲区上直接识别单词，但从程序设计的词法分析器可在输入缓冲区上直接识别单词，但从程序设计的词法分析器可在输入缓冲区上直接识别单词，但从程序设计的角度来看，若把源程序预处理一下，则单词识别就比较容易。角度来看，若把源程序预处理一下，则单词识别就比较容易。角度来看
17、，若把源程序预处理一下，则单词识别就比较容易。角度来看，若把源程序预处理一下，则单词识别就比较容易。2022/12/318预处理主要工作预处理主要工作预处理主要工作预处理主要工作删除注释删除注释删除注释删除注释删除续行符，以及后续换行符删除续行符，以及后续换行符删除续行符，以及后续换行符删除续行符，以及后续换行符(0AH)(0AH)。换行符、换行符、换行符、换行符、TABTAB和空格具有界符作用，预处理时通常予以保留。和空格具有界符作用，预处理时通常予以保留。和空格具有界符作用，预处理时通常予以保留。和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在反而给后续的单词识
18、别在后面的分析中可以看到，它们的存在反而给后续的单词识别在后面的分析中可以看到，它们的存在反而给后续的单词识别在后面的分析中可以看到，它们的存在反而给后续的单词识别带来方便。为了简化判断，可在预处理时，将换行符和带来方便。为了简化判断，可在预处理时，将换行符和带来方便。为了简化判断，可在预处理时，将换行符和带来方便。为了简化判断，可在预处理时，将换行符和TABTAB统统统统一替换为空格。一替换为空格。一替换为空格。一替换为空格。大多数语言（除大多数语言（除大多数语言（除大多数语言（除C C语言）不区分大小写，可在预处理时，将语言）不区分大小写，可在预处理时，将语言）不区分大小写，可在预处理时，
19、将语言）不区分大小写，可在预处理时，将大写字母变换成小写字母，或相反，以方便后续处理。大写字母变换成小写字母，或相反，以方便后续处理。大写字母变换成小写字母，或相反，以方便后续处理。大写字母变换成小写字母，或相反，以方便后续处理。对于受书写格式限制的语言（例对于受书写格式限制的语言（例对于受书写格式限制的语言（例对于受书写格式限制的语言（例FortranFortran和和和和CobolCobol），还应识），还应识），还应识），还应识别标号区，正确给出语句标号。识别续行标志，把相继行捻接别标号区，正确给出语句标号。识别续行标志，把相继行捻接别标号区，正确给出语句标号。识别续行标志，把相继行捻接
20、别标号区，正确给出语句标号。识别续行标志，把相继行捻接在一起，给出语句结束符。在一起，给出语句结束符。在一起，给出语句结束符。在一起，给出语句结束符。b b e e g g i i n nr r e e a a l lr r,h h,s s;s s=2 2*3 3.1 1 4 4*r r*(r r+h h)e e n n d d00.00上述源程序经预处理后，扫描缓冲区中的内容如下所示：上述源程序经预处理后，扫描缓冲区中的内容如下所示：上述源程序经预处理后，扫描缓冲区中的内容如下所示：上述源程序经预处理后，扫描缓冲区中的内容如下所示：2022/12/319预处理例预处理例 用伪代码编写一个预处
21、理程序，要求如下：用伪代码编写一个预处理程序，要求如下：用伪代码编写一个预处理程序，要求如下：用伪代码编写一个预处理程序，要求如下：去除源程序中注释（源程序中的注释用去除源程序中注释（源程序中的注释用去除源程序中注释（源程序中的注释用去除源程序中注释（源程序中的注释用/*/*/标记，不允标记，不允标记，不允标记，不允许嵌套使用）许嵌套使用）许嵌套使用）许嵌套使用）去除源程序中续行符（去除源程序中续行符（去除源程序中续行符（去除源程序中续行符（）将将将将TABTAB和换行符替换为空格和换行符替换为空格和换行符替换为空格和换行符替换为空格将大写字母变换成小写将大写字母变换成小写将大写字母变换成小写
22、将大写字母变换成小写在源程序尾部添加字符在源程序尾部添加字符在源程序尾部添加字符在源程序尾部添加字符#，这是编译程序内部的一个特殊，这是编译程序内部的一个特殊，这是编译程序内部的一个特殊，这是编译程序内部的一个特殊的单词，以示源程序结束。的单词，以示源程序结束。的单词，以示源程序结束。的单词，以示源程序结束。每调用一次，将经预处理的源程序全部送入内存中的扫描每调用一次，将经预处理的源程序全部送入内存中的扫描每调用一次，将经预处理的源程序全部送入内存中的扫描每调用一次，将经预处理的源程序全部送入内存中的扫描缓冲区，供扫描器识别单词。缓冲区，供扫描器识别单词。缓冲区，供扫描器识别单词。缓冲区，供扫
23、描器识别单词。2022/12/3110算法说明算法说明算法说明算法说明用伪代码编写预处理程序，输入和预处理可同时进行，无用伪代码编写预处理程序，输入和预处理可同时进行，无用伪代码编写预处理程序，输入和预处理可同时进行，无用伪代码编写预处理程序，输入和预处理可同时进行，无需输入缓冲区，将读入后经预处理的源程序直接送扫描缓冲需输入缓冲区，将读入后经预处理的源程序直接送扫描缓冲需输入缓冲区，将读入后经预处理的源程序直接送扫描缓冲需输入缓冲区，将读入后经预处理的源程序直接送扫描缓冲区区区区buf1.nbuf1.n。定义布尔变量定义布尔变量定义布尔变量定义布尔变量 in_commentin_commen
24、t，记录当前处理字符是否处于，记录当前处理字符是否处于，记录当前处理字符是否处于，记录当前处理字符是否处于注释。注释。注释。注释。若若若若in_comment in_comment 的值为的值为的值为的值为falsefalse，则表示当前读入字符未处于，则表示当前读入字符未处于，则表示当前读入字符未处于，则表示当前读入字符未处于注释中，此时应将当前处理字符存入扫描缓冲区；若注释中，此时应将当前处理字符存入扫描缓冲区；若注释中，此时应将当前处理字符存入扫描缓冲区；若注释中，此时应将当前处理字符存入扫描缓冲区；若in_comment in_comment 的值为的值为的值为的值为truetrue，
25、则表示当前处理字符处于注释中，则表示当前处理字符处于注释中，则表示当前处理字符处于注释中，则表示当前处理字符处于注释中，此时无需将该字符存入此时无需将该字符存入此时无需将该字符存入此时无需将该字符存入bufbuf中，相当于掉弃。中，相当于掉弃。中，相当于掉弃。中，相当于掉弃。当读入当读入当读入当读入“/*/*/*/*”，布尔变量，布尔变量，布尔变量，布尔变量in_commentin_comment的值由的值由的值由的值由falsefalse变为变为变为变为truetrue；当读入；当读入；当读入；当读入“*/”，布尔变量布尔变量布尔变量布尔变量in_commentin_comment的值由的值
26、由的值由的值由truetrue变变变变为为为为falsefalse。可用变量。可用变量。可用变量。可用变量cur_ccur_c记录当前正在处理的字符，用记录当前正在处理的字符，用记录当前正在处理的字符，用记录当前正在处理的字符，用old_cold_c记录刚处理过的字符。记录刚处理过的字符。记录刚处理过的字符。记录刚处理过的字符。/*/*/in_comment:in_comment:f ff f/t tt t/f ff f2022/12/31110.procedure pro_process()0.procedure pro_process()/扫描缓冲区扫描缓冲区扫描缓冲区扫描缓冲区buf b
27、uf 和扫描缓冲区指针和扫描缓冲区指针和扫描缓冲区指针和扫描缓冲区指针i i1.1.old_cold_c0:in_commentfalse:0:in_commentfalse:cur_ccur_c文件第一个字符文件第一个字符文件第一个字符文件第一个字符:i1:i12.while not eof(“source.txt”)do 2.while not eof(“source.txt”)do/文件尚未处理完文件尚未处理完文件尚未处理完文件尚未处理完3.3.if not in_comment then if not in_comment then/当前字符未处于注释中当前字符未处于注释中当前字符未处
28、于注释中当前字符未处于注释中4.4.if if old_cold_c=/and=/and cur_ccur_c=*then=*then/进入注释进入注释进入注释进入注释5.5.ii-1:in_commenttrue ii-1:in_commenttrue6.6.else else7.7.if if old_cold_c=and=and cur_ccur_c=换行符换行符换行符换行符 then ii-1 then ii-1/是续行符是续行符是续行符是续行符8.8.elseelse9.9.if if cur_ccur_cA and A and cur_ccur_cZ then Z then cur
29、_ccur_ccur_ccur_c+32+3210.10.if if cur_ccur_c=制表符制表符制表符制表符 or or cur_ccur_c=换行符换行符换行符换行符 then then cur_ccur_c空格空格空格空格11.11.ii+1:bufi ii+1:buficur_ccur_c/送入扫描缓冲区送入扫描缓冲区送入扫描缓冲区送入扫描缓冲区12.12.end ifend if13.13.end if end if14.14.else else/当前字符处于注释中当前字符处于注释中当前字符处于注释中当前字符处于注释中15.15.if if old_cold_c=*and=*a
30、nd cur_ccur_c=/then in_commentfalse=/then in_commentfalse/离开注释离开注释离开注释离开注释16.16.end ifend if17.17.old_cold_ccur_c:cur_c:cur_ccur_c文件下一个字符文件下一个字符文件下一个字符文件下一个字符18.end while18.end while19.ii+1:bufi#19.ii+1:bufi#20.end procedure20.end procedure2022/12/31122.1.3 基本字的识别和超前搜索基本字的识别和超前搜索 程序设计语言单词以基本字识别最为困难，
31、原因如下：程序设计语言单词以基本字识别最为困难，原因如下：程序设计语言单词以基本字识别最为困难，原因如下：程序设计语言单词以基本字识别最为困难，原因如下：有些语言对基本字不加保护，用户可用作普通标识符。有些语言对基本字不加保护，用户可用作普通标识符。有些语言对基本字不加保护，用户可用作普通标识符。有些语言对基本字不加保护，用户可用作普通标识符。基本字、用户定义的标识符和常数之间可能没有分隔符。基本字、用户定义的标识符和常数之间可能没有分隔符。基本字、用户定义的标识符和常数之间可能没有分隔符。基本字、用户定义的标识符和常数之间可能没有分隔符。例标准例标准例标准例标准FortranFortran对
32、基本字不加保护，用户可以把它们用作普通标对基本字不加保护，用户可以把它们用作普通标对基本字不加保护，用户可以把它们用作普通标对基本字不加保护，用户可以把它们用作普通标识符。让我们来观察下面三个识符。让我们来观察下面三个识符。让我们来观察下面三个识符。让我们来观察下面三个FortranFortran语言语句。语言语句。语言语句。语言语句。IF(5.EQ.M)GOTO55IF(5.EQ.M)GOTO55逻辑逻辑逻辑逻辑IFIF，当，当，当，当MM等于等于等于等于5 5转标号为转标号为转标号为转标号为5555的语句。的语句。的语句。的语句。IF(5)=55IF(5)=55IFIF为数组名，为数组名，
33、为数组名，为数组名，IF(5)IF(5)为下标变量为下标变量为下标变量为下标变量IF(X+Y)110,120,130 IF(X+Y)110,120,130 算术算术算术算术IFIF，当，当，当，当X+Y0X+Y0X+Y0，转标号为，转标号为，转标号为，转标号为130130的语句的语句的语句的语句 显然仅根据显然仅根据显然仅根据显然仅根据IFIF无法判断其为何种单词，可能是基本字，也可能是无法判断其为何种单词，可能是基本字，也可能是无法判断其为何种单词，可能是基本字，也可能是无法判断其为何种单词，可能是基本字，也可能是标识符。标识符。标识符。标识符。2022/12/3113 解决办法是超前搜索，
34、一直扫描到右括号后面的字符。若该字解决办法是超前搜索，一直扫描到右括号后面的字符。若该字解决办法是超前搜索，一直扫描到右括号后面的字符。若该字解决办法是超前搜索，一直扫描到右括号后面的字符。若该字符为字母符为字母符为字母符为字母GG或或或或g g，则为逻辑，则为逻辑，则为逻辑，则为逻辑IFIF；若为数字，则为算术；若为数字，则为算术；若为数字，则为算术；若为数字，则为算术IFIF；若为；若为；若为；若为=，则为标识符。则为标识符。则为标识符。则为标识符。超前搜索导致词法分析器实现困难。为了降低词法分析器的复超前搜索导致词法分析器实现困难。为了降低词法分析器的复超前搜索导致词法分析器实现困难。为
35、了降低词法分析器的复超前搜索导致词法分析器实现困难。为了降低词法分析器的复杂性，避免超前搜索，在实际实现中，大多数语言的编译程序对杂性，避免超前搜索，在实际实现中，大多数语言的编译程序对杂性，避免超前搜索，在实际实现中，大多数语言的编译程序对杂性，避免超前搜索，在实际实现中，大多数语言的编译程序对用户采取了二条限制措施：用户采取了二条限制措施：用户采取了二条限制措施：用户采取了二条限制措施：所有基本字均为保留字，用户不得使用它们作为标识符。所有基本字均为保留字，用户不得使用它们作为标识符。所有基本字均为保留字，用户不得使用它们作为标识符。所有基本字均为保留字，用户不得使用它们作为标识符。将空格
36、、将空格、将空格、将空格、TABTAB和换行符视为界符。在基本字、用户定义的标和换行符视为界符。在基本字、用户定义的标和换行符视为界符。在基本字、用户定义的标和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或识符和常数之间，若没有运算符或界符，则至少用一个空格（或识符和常数之间，若没有运算符或界符，则至少用一个空格（或识符和常数之间，若没有运算符或界符，则至少用一个空格（或TABTAB、换行符）加以分隔。、换行符）加以分隔。、换行符）加以分隔。、换行符）加以分隔。这样空格、这样空格、这样空格、这样空格、TABTAB和换行符不再是没有意义的了，这也就
37、是为和换行符不再是没有意义的了，这也就是为和换行符不再是没有意义的了，这也就是为和换行符不再是没有意义的了，这也就是为什么在词法分析预处理中将空格、什么在词法分析预处理中将空格、什么在词法分析预处理中将空格、什么在词法分析预处理中将空格、TABTAB和换行符保留下来的原和换行符保留下来的原和换行符保留下来的原和换行符保留下来的原因。采用上述二条限制措施，对用户来讲是完全可接受的，并因。采用上述二条限制措施，对用户来讲是完全可接受的，并因。采用上述二条限制措施，对用户来讲是完全可接受的，并因。采用上述二条限制措施，对用户来讲是完全可接受的，并且已成为程序员进行程序设计的惯例。词法分析器对于所有单
38、且已成为程序员进行程序设计的惯例。词法分析器对于所有单且已成为程序员进行程序设计的惯例。词法分析器对于所有单且已成为程序员进行程序设计的惯例。词法分析器对于所有单词的识别，最多只要向前看一个字符就足够了。词的识别，最多只要向前看一个字符就足够了。词的识别，最多只要向前看一个字符就足够了。词的识别，最多只要向前看一个字符就足够了。2022/12/31142.1.4 遍遍遍的基本概念遍的基本概念 由外存获得前一遍的工作结果由外存获得前一遍的工作结果由外存获得前一遍的工作结果由外存获得前一遍的工作结果(对于第一遍而言，从外存获得源对于第一遍而言，从外存获得源对于第一遍而言，从外存获得源对于第一遍而言
39、，从外存获得源程序程序程序程序)，完成它所含的有关阶段工作之后，再把结果存于外存。，完成它所含的有关阶段工作之后，再把结果存于外存。，完成它所含的有关阶段工作之后，再把结果存于外存。，完成它所含的有关阶段工作之后，再把结果存于外存。遍引入的历史背景遍引入的历史背景 早期的计算机内存较小，编译程序相对而言体积较大。使用遍早期的计算机内存较小，编译程序相对而言体积较大。使用遍早期的计算机内存较小，编译程序相对而言体积较大。使用遍早期的计算机内存较小，编译程序相对而言体积较大。使用遍技术的优点在于，可根据当前遍的工作，装入相应的工作程序。技术的优点在于，可根据当前遍的工作，装入相应的工作程序。技术的
40、优点在于，可根据当前遍的工作，装入相应的工作程序。技术的优点在于，可根据当前遍的工作，装入相应的工作程序。当一遍工作完之后，内存空间大部分被释放。当下一遍进入后，当一遍工作完之后，内存空间大部分被释放。当下一遍进入后，当一遍工作完之后，内存空间大部分被释放。当下一遍进入后，当一遍工作完之后，内存空间大部分被释放。当下一遍进入后，几乎可以使用全部存储空间。遍数多一点还有一个好处，即整个几乎可以使用全部存储空间。遍数多一点还有一个好处，即整个几乎可以使用全部存储空间。遍数多一点还有一个好处，即整个几乎可以使用全部存储空间。遍数多一点还有一个好处，即整个编译程序的逻辑结构较为清晰。但是，遍数多势必增
41、加输入输出编译程序的逻辑结构较为清晰。但是，遍数多势必增加输入输出编译程序的逻辑结构较为清晰。但是，遍数多势必增加输入输出编译程序的逻辑结构较为清晰。但是，遍数多势必增加输入输出所耗费的时间。所耗费的时间。所耗费的时间。所耗费的时间。遍和编译程序的结构遍和编译程序的结构 遍决定了编译程序的结构。在本书中，词法分析器是以函数形遍决定了编译程序的结构。在本书中，词法分析器是以函数形遍决定了编译程序的结构。在本书中，词法分析器是以函数形遍决定了编译程序的结构。在本书中，词法分析器是以函数形式书写的，函数的返回值是一个单词的二元式。式书写的，函数的返回值是一个单词的二元式。式书写的，函数的返回值是一个
42、单词的二元式。式书写的，函数的返回值是一个单词的二元式。词法分析不作为独立一遍词法分析不作为独立一遍词法分析不作为独立一遍词法分析不作为独立一遍 词法分析作为独立一遍（本书采用）词法分析作为独立一遍（本书采用）词法分析作为独立一遍（本书采用）词法分析作为独立一遍（本书采用）2022/12/31152.1.5 状态转换图和词法分析器手工构造状态转换图和词法分析器手工构造 引入状态转换图的必要性引入状态转换图的必要性 若不考虑科学计数法形式，程序设计语言的无符号实型常数有若不考虑科学计数法形式，程序设计语言的无符号实型常数有若不考虑科学计数法形式，程序设计语言的无符号实型常数有若不考虑科学计数法形
43、式，程序设计语言的无符号实型常数有三种书写形式，它们是：三种书写形式，它们是：三种书写形式，它们是：三种书写形式，它们是：无小数部分形式无小数部分形式无小数部分形式无小数部分形式134.134.无整数部分形式无整数部分形式无整数部分形式无整数部分形式.12.12完全形式完全形式完全形式完全形式3.143.14 如果考虑科学计数法形式，则无符号实型常数识别更复杂。如果考虑科学计数法形式，则无符号实型常数识别更复杂。如果考虑科学计数法形式，则无符号实型常数识别更复杂。如果考虑科学计数法形式，则无符号实型常数识别更复杂。直接编写识别无符号实型常数的程序有一定难度，状态转换图是直接编写识别无符号实型常
44、数的程序有一定难度，状态转换图是直接编写识别无符号实型常数的程序有一定难度，状态转换图是直接编写识别无符号实型常数的程序有一定难度，状态转换图是构造单词识别程序（扫描器）的一种较好工具。构造单词识别程序（扫描器）的一种较好工具。构造单词识别程序（扫描器）的一种较好工具。构造单词识别程序（扫描器）的一种较好工具。状态转换图基本概念及应用状态转换图基本概念及应用状态转换图是一个有向图。在状态转换图中，结点代表状态，状态转换图是一个有向图。在状态转换图中，结点代表状态，状态转换图是一个有向图。在状态转换图中，结点代表状态，状态转换图是一个有向图。在状态转换图中，结点代表状态，用园圈表示。状态之间用箭
45、弧连接。箭弧上的标记代表在射出结用园圈表示。状态之间用箭弧连接。箭弧上的标记代表在射出结用园圈表示。状态之间用箭弧连接。箭弧上的标记代表在射出结用园圈表示。状态之间用箭弧连接。箭弧上的标记代表在射出结状态下可能出现的合法的输入字符。状态下可能出现的合法的输入字符。状态下可能出现的合法的输入字符。状态下可能出现的合法的输入字符。2022/12/3116一个状态转换图包含若干个状态一个状态转换图包含若干个状态一个状态转换图包含若干个状态一个状态转换图包含若干个状态（结点），其中有一个是初态，用符（结点），其中有一个是初态，用符（结点），其中有一个是初态，用符（结点），其中有一个是初态，用符号号号号
46、指示，是识别字符串的起点。状指示，是识别字符串的起点。状指示，是识别字符串的起点。状指示，是识别字符串的起点。状态转换图至少有一个终态，表示已识态转换图至少有一个终态，表示已识态转换图至少有一个终态，表示已识态转换图至少有一个终态，表示已识别出一个字符串（单词），终态用双别出一个字符串（单词），终态用双别出一个字符串（单词），终态用双别出一个字符串（单词），终态用双圈表示。圈表示。圈表示。圈表示。例，识别标识符的状态转换图如下例，识别标识符的状态转换图如下例，识别标识符的状态转换图如下例，识别标识符的状态转换图如下所示：所示：所示：所示：其中其中其中其中0 0为初态，为初态，为初态，为初态，2
47、 2为终态。为终态。为终态。为终态。2022/12/3117若当前状态是若当前状态是若当前状态是若当前状态是1 1，只有当输入字符为非字母数字，才可能到达，只有当输入字符为非字母数字，才可能到达，只有当输入字符为非字母数字，才可能到达，只有当输入字符为非字母数字，才可能到达状态状态状态状态2 2，显然多读了一个字符，这就是终态结，显然多读了一个字符，这就是终态结，显然多读了一个字符，这就是终态结，显然多读了一个字符，这就是终态结2 2上星号上星号上星号上星号*的含的含的含的含义，它并不是正在识别的标识符的组成部分。此时应将其退回，义，它并不是正在识别的标识符的组成部分。此时应将其退回，义，它并
48、不是正在识别的标识符的组成部分。此时应将其退回，义，它并不是正在识别的标识符的组成部分。此时应将其退回，下次识别单词从该字符开始。下次识别单词从该字符开始。下次识别单词从该字符开始。下次识别单词从该字符开始。单词的尾部空格作为单词的结束标志，单词的前导空格在识别单词的尾部空格作为单词的结束标志，单词的前导空格在识别单词的尾部空格作为单词的结束标志，单词的前导空格在识别单词的尾部空格作为单词的结束标志，单词的前导空格在识别单词前滤去，所以在初态单词前滤去，所以在初态单词前滤去，所以在初态单词前滤去，所以在初态0 0有一个标记为空格的自回路。有一个标记为空格的自回路。有一个标记为空格的自回路。有一
49、个标记为空格的自回路。在词法分析预处理中，空格作为界符被保留下来。由于空格不在词法分析预处理中，空格作为界符被保留下来。由于空格不在词法分析预处理中，空格作为界符被保留下来。由于空格不在词法分析预处理中，空格作为界符被保留下来。由于空格不是任何单词的组成部分（除字符串常数），故在识别单词前，应是任何单词的组成部分（除字符串常数），故在识别单词前，应是任何单词的组成部分（除字符串常数），故在识别单词前，应是任何单词的组成部分（除字符串常数），故在识别单词前，应将单词的前导空格滤去。由于空格的特殊性，状态转换图中用虚将单词的前导空格滤去。由于空格的特殊性，状态转换图中用虚将单词的前导空格滤去。由于
50、空格的特殊性，状态转换图中用虚将单词的前导空格滤去。由于空格的特殊性，状态转换图中用虚线表示（若当前输入字符是空格，重新进入线表示（若当前输入字符是空格，重新进入线表示（若当前输入字符是空格，重新进入线表示（若当前输入字符是空格，重新进入1 1状态）。在识别标状态）。在识别标状态）。在识别标状态）。在识别标识符的过程中，当读入的字符不是字母或数字，可能是空格，说识符的过程中，当读入的字符不是字母或数字，可能是空格，说识符的过程中，当读入的字符不是字母或数字，可能是空格，说识符的过程中，当读入的字符不是字母或数字，可能是空格，说明当前正在识别的单词已完全读入。为程序处理方便起见，不管明当前正在识