实验一：词法分析器编制实验一教学重点与实现的关键技术1.1词法分析概述人们理解一篇文章(或解析一个程序)起码是在单词级别上来思考的。
同样，编译程序也是在单词的级别上来分析和翻译源程序的。
词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号（token），把作为字符串的源程序改造成单词符号串的中间程序。
因此，词法分析是编译的基础。
执行词法分析的程序称为词法分析器。
构造词法分析器的方法分为手工编制和自动生成（如用著名的词法分析器的自动生成工具Lex自动为某种语言的编译构造词法分析器）两种，本实验要求学生利用所学习掌握的知识手工编制一个小型的词法分析器。
1.2词法分析器的设计要求1.2.1词法分析器的功能和输出形式词法分析器的功能是输入源程序，输出单词符号。
单词符号是一个程序语言的基本语法符号。
程序语言的单词符号一般可分为下列五种。
（1）关键字是由程序语言定义的具有固定意义的标志符。
有时称这些标志符为保留字或基本字。
例如，Pascal中的begin，end，if，while都是保留字。
这些字通常不用作一般标志符。
（2）标识符用来表示各种名字，如变量名、数组名、过程名等等。
（3）常数常数的类型一般有整型、实型、布尔型、文字型等等。
例如，100，3.14159，TRUE，‘Sample’。
（4）运算符如+、-、*、/等等（5）界符如逗号、分号、括号、/*，*/等等。
一个程序语言的关键字、运算符和界符都是确定的，一般只有几十个或上百个。
而对于标识符或常数的使用通常都不加什么限制。
词法分析器所输出的单词符号常常表示成如下的二元式：（单词种别，单词符号的属性值）单词种别通常用整数编码。
一个语言的单词符号如何分种，分成几种，怎么编码，是一个技术性的问题。
它主要取决于处理上的方便。
标识符一般统归为一种。
常数则宜按类型（整、实、布尔等）分种。
关键字可将其全体视为一种，也可以一字一种。
采用一字一种的分法实际处理起来较为方便。
运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。
至于界符一般用一符一种的分法。
如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。
若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。
单词符号的属性是指单词符号的特性或特征。
属性值则是反映特性或特征的值。
例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。
在这里，我们给出一种编码方法（以FORTRAN语言为例）：单词符号编码举例单词符号种别编码内部值助记符DIM1$DIMIF2$IF DO3$DO STOP4$STOP END5$END标识符6内部符号串$IDN整数7标准二进制$INT=8$ASG+9$PLUS*10$STAR**11$POWER，12$COMMA（13$SLP）14$SRP1.2.2词法分析器作为一个独立子程序为何将词法分析作为一个独立阶段呢？是否还应该将它安排为独立的一遍呢？把词法分析安排为一个独立阶段的好处是，它可使整个编译程序的结构更简洁、清晰和条理化。
词法分析比语法分析要简单得多，可用更有效的特殊方法和工具进行处理。
但是，这并不意味着我们也必须把词法分析作为独立的一遍。
当然，也可以把词法分析安排成独立的一遍。
让它把整个源程序翻译成一连串的单词符号存放于文件中。
待语法分析器进入工作是在对从文件输进的这些单词符号进行分析。
这种做法意味着必须在文件中保存整个源程序的内码形式，这似乎是没有必要的。
我们可以把词法分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。
每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。
这样，把词法分析器安排成一个子程序就比较自然。
1.3 词法分析器的实现技术在以下的讨论中，我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。
1.3.1 输入、预处理词法分析器工作的第一步是输入源程序文本。
输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。
词法分析的工作可以直接在这个缓冲区中进行。
但在很多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。
对于许多程序语言来说，空白符、跳格符、回车符和换行符等编辑性字符除了出现在文字常数中之外，在别处的任何出现都没有意义。
对于它们，预处理时可以将其剔掉。
我们可以设想构造一个预处理子程序来完成预处理功能。
每当词法分析器调用它时，它就处理出一串确定长度的输入字符，并将其装进词法分析器所指定的缓冲区中（称为扫描缓冲区）。
这样，分析器就可以在此缓冲区中直接进行单词符号的识别，而不必照管其它繁琐事务。
分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。
不论扫描缓冲区设的多大都不能保证单词符号不会被他的边界所打断。
因此，扫描缓冲区最好使用一个如下所示的一分为二的区域，即著名的双缓冲区设计。
具体的操作步骤如下图所示：1.3.2 单词符号的识别：状态转换图使用状态转换图是设计词法分析器的一种好途径。
转换图是一张有限方向图（有向图）。
在状态转换图中，结点代表状态，用圆圈表示。
状态之间用箭弧连接。
箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。
举例：对于正规式IDN→letter(letter|digit)*描述的标识符，其状态图如下所示：letter,digit，_）INC→++ADD→+1.3.3 利用状态转换图识别单词（Token）的步骤1. 从初态出发2. 读入一字符3. 按当前字符转入下一状态4. 重复2,3 直到无法继续转移注：在遇到读入的字符是Token的分割符时，若当前状态是终止状态，说明读入的字符组成一单词；否则，说明输入不符合词法规则。
1.3.4算法描述★子程序scan( )⏹输入：字符流⏹输出：⏹Symbol(Code) :单词种别⏹Attr(value):属性（全局变量）★数据结构与子例程⏹数据结构⏹ch 当前输入字符⏹token 输入缓冲区(字符数组)⏹symbol 单词种别（子程序的返回值）⏹attr 属性（全局变量）⏹子例程⏹Lookup(token):将token 存入符号表，返回入口指针⏹isKeyword(token):判别token是关键字？返回关键字种别或-1⏹getchar():从输入缓冲区中读入一个字符放入ch⏹isdigit() isalpha()★该例的实现算法1. getchar()2. WHILE ch 是空格//跳过空格2.1 DO getchar();3. CASE ch OF4. isdigit(ch) :4.1 ch→token; getchar();4.2 WHILE isdigit(ch) DOch→token; getchar();4.3 输入指针回退一个字符；4.4 将token中的字符串变成数值→attr4.5 返回NUM5. isalpha(ch) :5.1 ch→token; getchar();5.2 WHILE isalpha(ch) OR isdigit(ch)DO ch→token; getchar();5.3输入指针回退一个字符;5.4 key = isKeyword(token);5.5 IF key≥0 THEN 返回key5.6 Lookup(token)→attr;5.7 返回IDN6 ':' : getchar();6.1 IF ch等于'=' THEN 返回ASG6.2 出错处理7 '+' : 返回ADD8 '-' : 返回SUB9 '*' : 返回MUL10 '/' : 返回DIV11 '=' : 返回EQ12 '>' : 返回GT13 '<' : 返回LT14 '(' : 返回LP15 ')' : 返回RP16 ';' : 返回SEMI17 其它: 出错处理18 END OF CASE1.4实现的关键技术提示除了前述的双缓冲区设计、识别单词的状态转换图等，符号表的组织与实现也是不容忽视的一项关键技术。
但由于学生初次接触编译系统的设计，往往忽略符号表的设计，即使想到了也无从下手。
有的学生甚至认为标识符表既是符号表的全部——编译的运行环境只需要（也只能有）一张标识符表。
这种理解上的偏差正是由于对符号表的作用（特别是对标识符表的特定用途）理解不够，而多数教科书在这个问题上往往只是给出一些宏观上的引导所至。
下面将分别对符号表的作用与具体实现进行阐述。
1.4.1 符号表的作用为了检查语义的正确性和生成代码，编译程序需要知道用户源程序中所使用的各种标识符的属性，这些属性信息常常由编译程序集中起来并存放于一张标识符表或符号表中。
符号表用于存放程序中出现的有关各种名字的属性信息，以反应名字的语义特征，编译的各阶段均涉及符号表的操作。
符号表的作用主要有以下几个方面：1)收集符号的各种属性。
如名字、类型、定义的层次等。
2)作为语义的合法性检查的依据。
如引用时类型是否一致、层次是否得当等。
3)作为目标代码生成阶段地址分配的依据。
如根据符号表中该变量的特性可为其在适当的存储区域分配大小合适的存储空间。
1.4.2 符号表的建立符号表一般在编译程序的开始阶段（词法分析或语法分析阶段）就建立了，其内容的填写一般在词法分析、语法分析、语义分析阶段陆续填入，而它的使用与管理则贯穿于整个编译程序工作的各个阶段。
1.4.3 符号表的内容符号表的每一项（也称入口）由若干域构成，存放一个符号的所有属性信息。
程序设计语言中的符号一般分为两大部分：固定部分和非固定部分。
（1）固定部分符号表固定部分包括符号的名字域和种属域。
（2）非固定部分符号表的非固定部分包括符号的各种信息域。
不同种属的符号有不同的信息域，如简单变量有类型、地址、存储类别、作用域等信息域，数组名可有类型、内情向量地址等信息域，过程名、函数名可有参数个数、参数表地址、入口地址等信息域。
1.4.4 符号表的组织符号表的组织直接关系到语义功能的实现和语义处理的时空效率。
★符号表的总体组织所谓符号表的总体组织就是构造多少张符号表，以及哪些符号放在同一张表中，一般可选以下三种方式之一：1）将属性完全相同的符号（即同一种属的符号）组织在一起构成一张符号表，从而编译程序将使用多张符号表。