1、程序设计语言与编译 主要内容主要内容1.介绍词法分析的过程2.讨论词法分析器的设计与实现3.介绍实现词法分析器的主要工具：程序设计语言与编译第一节第一节 词法分析概述词法分析概述一一.词法分析的功能词法分析的功能1.1.功能功能扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误,则输出有关的错误信息。程序设计语言与编译功能：输入源程序，输出单词符号。单词功能：输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。符号是一个程序语言的基本语法符号。3 3程序设计语言与编译词法分析器的词法分析器的功能功能：输入源程序，输出单词符号。：输入源程序，输出单词
2、符号。单词符号单词符号：一个程序语言的基本语法符号。分为以下：一个程序语言的基本语法符号。分为以下5 5种。种。1 1、保留字保留字(关键字关键字)：由程序语言定义的具有固定意义的标：由程序语言定义的具有固定意义的标识符。也可称为保留字或基本字。例如：识符。也可称为保留字或基本字。例如：PascalPascal中的中的beginbegin，endend，ifif等。它是等。它是确定确定的。的。2 2、标识符标识符：用来表示各种名字，如变量名、数组名、过程：用来表示各种名字，如变量名、数组名、过程名等。它是名等。它是不限不限的。的。3 3、常数常数：常数的类型一般有整型、实型、布尔型、文字型：常
3、数的类型一般有整型、实型、布尔型、文字型等。它是等。它是不限不限的。的。4 4、运算符运算符：如：如+、-、*、/等。它是等。它是确定确定的。的。5 5、界符界符：如逗号、分号、括号、：如逗号、分号、括号、/*，*/等。它是等。它是确定确定的。的。确定确定不限不限二二.词法分析器的输出形式词法分析器的输出形式程序设计语言与编译5 5程序设计语言与编译 (单词类别,单词的属性)区分单词所属的类区分单词所属的类(整数编码整数编码)单词的值单词的值2.2.单词的输出形式单词的输出形式(1)(1)二元式二元式 单词符号的表示形式单词符号的表示形式：词法分析器所输出的单词符号常常表示成：词法分析器所输出
4、的单词符号常常表示成 二元式（单词种别，单词自身的值）二元式（单词种别，单词自身的值）。单词种别单词种别可以用以下形式表示：可以用以下形式表示：1 1、一类单词统一用一个整数值代表其属性。例如：、一类单词统一用一个整数值代表其属性。例如：1 1代表关键字，代表关键字，2 2代表标识符等。代表标识符等。2 2、每一个单词一个类别。例如：、每一个单词一个类别。例如：1 1代表代表BEGINBEGIN，2 2代表代表ENDEND等。等。单词自身的值单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表可以表示成：常量的二进制表示；常量、变量等在符号表种的地址码，等等。种的地址码，等等。程序设
5、计语言与编译（2 2）单词类别的划分）单词类别的划分基本字、运算符、界符基本字、运算符、界符:一字一码一字一码标识符标识符:单列一种单列一种常数常数:按类型分类按类型分类 程序设计语言与编译一个例子A:=B50+10；的输出为：（标识符的编码，A）（:=的编码，）（标识符的编码，B50）（的编码，）（整数的编码，10）（；的编码，）程序设计语言与编译注意：注意：一个语言的单词符号如何分种，分几种，怎一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型（整、实、布尔）分。关键字可以常数则宜按类型（整、实、
6、布尔）分。关键字可以将其全体视为一种，也可将其全体视为一种，也可一字一种一字一种。运算符可采用运算符可采用一符一种，但也可把具有一定共性的视为一种。界一符一种，但也可把具有一定共性的视为一种。界符则一般采用符则一般采用一符一种一符一种。如何进行分种主要取决于。如何进行分种主要取决于处理上的方便。处理上的方便。若是一符一种分种，单词自身值就不需要了若是一符一种分种，单词自身值就不需要了。否则，要查符号表。否则，要查符号表。程序设计语言与编译例：例：151151FORTRANFORTRAN编译程序的词法分析器在扫描输入串编译程序的词法分析器在扫描输入串 IF(5EQIF(5EQM)GOTO 100
7、M)GOTO 100 后，它输出的后，它输出的单词符号串单词符号串是：是：逻辑逻辑IF IF （3434，_ _）左括号左括号 （2 2，_ _）整常数整常数 （2020，55的二进制表示）的二进制表示）等号等号 （6 6，_ _）标识符标识符 （2626，MM）右括号右括号 （1616，_ _）GOTO GOTO （3030，_ _）标号标号 （1919，100100的二进制表示）的二进制表示）IFIF为关键字，种别编码为关键字，种别编码3434，采用一符一种的编码方式。采用一符一种的编码方式。常数类型，种别编码常数类型，种别编码2020，单词自，单词自身的值为身的值为55的二进制表示。的二
8、进制表示。(为界符，种别编码为界符，种别编码2 2，采，采用一符一种的编码方式。用一符一种的编码方式。等号为运算符，种别编码等号为运算符，种别编码6 6，采用一符一种的编码方式。采用一符一种的编码方式。M M为标识符，种别编码为标识符，种别编码2626，单，单词自身值为词自身值为MM。)为界符，种别编码为界符，种别编码1616，采用一符一种的编码方式。采用一符一种的编码方式。GOTOGOTO为关键字，种别编码为关键字，种别编码3030，采用一符一种的编码方式。采用一符一种的编码方式。100100为标号，种别编码为标号，种别编码1919，单词，单词内部的值用内部的值用100100的二进制表示。的
9、二进制表示。程序设计语言与编译例例 ：下述：下述C+C+代码段：代码段：while(i=j)i-while(i=j)i-；经词法分析器处理以后，它将被转换为如下的经词法分析器处理以后，它将被转换为如下的单词符号串单词符号串 (while(while，_)_)(，_)_)(id(id，指向，指向i i的符号表指针的符号表指针 )(=(=，_)_)(id(id，指向，指向j j的符号表指针的符号表指针 )()()，_)_)(id(id，指向，指向i i的符号表指针的符号表指针 )(-(-，_ _)(；，_)_)程序设计语言与编译词法分析程序的实现方式词法分析程序的实现方式u完全独立方式完全独立方式
10、：词法分析程序作为：词法分析程序作为单独一趟单独一趟来来实现。词法分析程序读入整个源程序，它的输实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。出作为语法分析程序的输入。u相对独立方式相对独立方式：把词法分析程序作为语法分析：把词法分析程序作为语法分析程序的一个独立程序的一个独立子程序子程序。语法分析程序需要新。语法分析程序需要新符号时调用这个子程序。符号时调用这个子程序。2.词法分析器作为一个独立子程序词法分析器作为一个独立子程序1212程序设计语言与编译完全独立方式完全独立方式u采用词法分析工作完全独立的原因：采用词法分析工作完全独立的原因：简化设计，降低语法分析的复杂性
11、简化设计，降低语法分析的复杂性提高编译效率提高编译效率增加编译系统的可移植性增加编译系统的可移植性 源程序词法分析程序语法分析程序属性字序列属性字序列.1313程序设计语言与编译相对独立方式相对独立方式u当采用递归下降分析等技术实现一趟编译程当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。序时常采用这种方式。词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.1414程序设计语言与编译设计前提设计前提：把把scannerscanner作为一个独立的子程序；作为一个独立的子程序；词法分析器的任务为输出单词符号。词法分析器的任务为输出单词
12、符号。必要性必要性：编辑性字符如空白符、回车符等，除了出现在文字和编辑性字符如空白符、回车符等，除了出现在文字和 常数中以外，在别处出现都没有意义。常数中以外，在别处出现都没有意义。功功 能能：剔除无用字符。剔除无用字符。实实 现现：预处理子程序。预处理子程序。程序设计语言与编译输入列表预处理预处理子程序子程序扫描器扫描器扫描缓冲区扫描缓冲区输入缓冲区输入缓冲区单词符号图图 词法分析器词法分析器语法分析器语法分析器预预处处理理部部分分扫扫描描器器程序设计语言与编译一一.扫描缓冲区扫描缓冲区1.1.输入缓冲区输入缓冲区：源程序输入缓冲区2.2.预处理程序：预处理程序：取消注解，剔除无用的空白、跳
13、格、回车、换行等 程序设计语言与编译3.3.扫描缓冲区扫描缓冲区：从输入缓冲区输入固定长度的字符串到另一个缓冲区（扫描缓冲区），词法分析可以直接在此缓冲区中进行符号识别。扫描缓冲区的结构：扫描缓冲区的结构：用来指示正在扫描的单词的起点；：用于向前搜索，寻找单词的结束；：设置左右两个缓冲区，当左缓冲区读完后，新读入的字符存入右缓冲区；反之，存放在左缓冲区；左缓冲区左缓冲区右缓冲区右缓冲区起点指示器起点指示器搜索指示器搜索指示器 程序设计语言与编译u扫描缓冲区的大小扫描缓冲区的大小应当保证单词符号不被缓冲区的边界打断应当保证单词符号不被缓冲区的边界打断扫描缓冲区使用一个一分为二的区域 使用循环链表
14、实现使用循环链表实现规定单词符号的大小不超过整个链表的容量规定单词符号的大小不超过整个链表的容量起始指针起始指针搜索指针搜索指针1919程序设计语言与编译二二.符号的识别符号的识别根据语言规定的词法规则，进行识别；对不同类型的单词符号，有不同的识别要求。超前搜索超前搜索 词法分析程序在读取单词时，为了判断词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来取向前多读取字符并通过读取的字符来判别，即所谓判别，即所谓超前搜索技术超前搜索技术。程序设计语言与编译 例如：在标准例如：在标准FORTRANFORTRAN中
15、中 1 1、DO99KDO99K=1,10=1,10 2 2、IFIF(5.EQ.M)I=10(5.EQ.M)I=10 3 3、DO99KDO99K=1.10=1.10 4 4、IFIF(5)=55(5)=55 其中的其中的DODO、IFIF为关键字为关键字其中的其中的DODO、IFIF为标识符为标识符的一部分的一部分程序设计语言与编译（2）标识符的识别：多数语言的标识符是字母开头的多数语言的标识符是字母开头的“字字母母/数字数字”串，而且在程序中标识符的出现后都跟着算符或界符。因此，串，而且在程序中标识符的出现后都跟着算符或界符。因此，不难识别。不难识别。（3）常数的识别：根据常数的格式；大
16、多数常数后都有运算根据常数的格式；大多数常数后都有运算符或界符。如符或界符。如FORTRANFORTRAN的的5.E085.E08与与5.EQ.M5.EQ.M也必须超前搜索。也必须超前搜索。（4）运算符的识别：需要超前搜索，需要超前搜索，对于诸如对于诸如C+C+语言中的语言中的“+”+”、“-”-”，这种复合成的算符，需要超前搜索。，这种复合成的算符，需要超前搜索。（5）界符的识别：需要超前搜索，如需要超前搜索，如/*程序设计语言与编译是设计词法分析器的有效工具。是设计词法分析器的有效工具。转换图：转换图：是一张有限方向图。在状态转换图中，是一张有限方向图。在状态转换图中，结点结点代表代表 状
17、态，状态，用圆圈表示。状态之间用用圆圈表示。状态之间用箭弧箭弧连接。箭弧上连接。箭弧上的的标记（字符）标记（字符）代表在射出结状态下可能出现的输代表在射出结状态下可能出现的输入字符或字符类。入字符或字符类。状态转换图的功能状态转换图的功能:用于识别一定的字符串。用于识别一定的字符串。初态初态：一张转换图的启动条件，至少有一个：一张转换图的启动条件，至少有一个,用圆圈表示。用圆圈表示。终态终态：一张转换图的结束条件，至少有一个，用双圈表示。：一张转换图的结束条件，至少有一个，用双圈表示。*：表示多读进了一个字符。：表示多读进了一个字符。程序设计语言与编译 (node)：圆圈表示结点，代表状态（s
18、tate）（弧）:连接结点，边上的标记字符表示该状态下可能接收或识别的字符；1 12 23 3x xy y有限的有向图有向边上标记字符唯一初态若干终态（至少一个）程序设计语言与编译1 12 23 3XY(a)(a)转换图示例转换图示例2 20 01 1字母字母其他其他字母或数字字母或数字*（b b）识别标识符的转换图）识别标识符的转换图其他其他2 20 01 1数字数字数字数字*（c c）识别整数的转换图）识别整数的转换图简单的状态转换图示例：简单的状态转换图示例：初态初态终态终态从从0 0状态到状态到1 1状态状态可能出现字母可能出现字母程序设计语言与编译7 7*6 65 5数字数字1 10
19、 01 1数字数字数字数字2 2数字数字3 3E E 或或 D D+或或数字数字其他其他E E 或或 D D数字数字其他其他数字数字例：识别例：识别FORTRANFORTRAN实型常数实型常数的转换图：的转换图：例如下列实型常数可以例如下列实型常数可以被以下转换图识别：被以下转换图识别：1.23E+41.23E+4 .56E-7 .56E-7程序设计语言与编译第四章设计的语言允许下述单词：标识符、数字串、begin、end、integer、if、then、else、function、read、write、-、*、=、=、=、:=、；、（、）词法分析器的设计与实现词法分析器的设计与实现一一.单词
20、符号单词符号 程序设计语言与编译 单词符号 种别编码助忆符内码值begin01$BEGIN-end02$END-integer03$INTEGER-if04$IF-then05$THEN-else06$ELSE-function07$FUNCTION-read08$READ-write09$WRITE-单词符号 种别编码助忆符内码值标识符10$ID字符串常数11$INT二进制值=12$EQ-13$NE-=14$LE-=16$GE17$GT-程序设计语言与编译 单词符号 种别编码助忆符内码值-18$SUB-*19$MUL-:=20$ASSIGN-(21$LPAR-)22$RPAR-;23$SEM
21、-程序设计语言与编译 0 01 12 2字母字母字母字母/数字数字其它字符其它字符3 34 4数字数字数字数字非数字非数字5 5=6 67 7 10101111 非非=1212=1313-1414*15151616:=1717非非=1818(1919)2020;2121其他其他退一字符；查保留字表；退一字符；查保留字表；若是，返回若是，返回若不是，返回若不是，返回退一字符；退一字符；返回返回返回返回返回返回，退一字符，退一字符返回返回返回返回返回返回，退一字符，退一字符返回返回返回返回返回返回返回返回出错处理出错处理返回返回返回返回返回返回ERRORERROR，非法字符，非法字符二二.状态转换
22、图状态转换图*程序设计语言与编译 为了把为了把状态转换图状态转换图转化成转化成程序程序，每个，每个状态状态要建立一段要建立一段程序程序，它要做的工作如下：，它要做的工作如下：第一步第一步：从输入缓冲区中取一个字符。为此，我们使用函：从输入缓冲区中取一个字符。为此，我们使用函数数GETCHARGETCHAR，每次调用它，推进先行指针，送回一，每次调用它，推进先行指针，送回一个字符。个字符。第二步第二步：确定在本状态下，哪一条箭弧是用刚刚来的输入：确定在本状态下，哪一条箭弧是用刚刚来的输入字符标识的。如果找到，控制就转到该弧所指向字符标识的。如果找到，控制就转到该弧所指向的状态；若找不到，那么寻找
23、该单词的企图就失的状态；若找不到，那么寻找该单词的企图就失败了。败了。失失 败败：先行指针必须：先行指针必须重新回到重新回到开始指针处，并用另一状开始指针处，并用另一状态图来搜索态图来搜索另一另一单词。如果所有的状态转换图都单词。如果所有的状态转换图都试过之后，还没有匹配的，就表明这是一个词法试过之后，还没有匹配的，就表明这是一个词法错误，此时，调用错误校正程序。错误，此时，调用错误校正程序。GETCHAR是过程，是过程，将下一输入字符读入将下一输入字符读入CHAR，搜索指示器，搜索指示器前移一个字符。前移一个字符。程序设计语言与编译每个状态结对应一小段程序 分支状态分支状态if或case语句
24、 循环状态循环状态while语句 终态终态return语句三三.实现方法实现方法 程序设计语言与编译3333状态转换图的实现状态转换图的实现u思想：每个状态结思想：每个状态结点点对应一小段程序。对应一小段程序。u做法做法:1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASE语句或语句或一组一组IF-THEN-ELSE语句实现语句实现GetChar();GetChar();if(IsLetter()if(IsLetter()状态状态j j的对应程序段的对应程序段;else if(IsDigit()else if(IsDigit()状态状态k k的对应程序段的对应程序段;else
25、if(ch=/)else if(ch=/)状态状态l l的对应程序段的对应程序段;else else 错误处理错误处理;ijkl字母字母数字数字/程序设计语言与编译34342)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILE结构和结构和IF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段3)3)终态结终态结点表示识别出某种单词符号点表示识别出某种单词符号，因此，因此，对应语句为对应语句为 RETURN(CRETURN(C，VAL)
26、VAL)其中，其中，C C为单词种别，为单词种别，VALVAL为单词自身值为单词自身值.程序设计语言与编译锻炼锻炼012字母字母其它字符其它字符字母或数字字母或数字*数字数字23*其它符号其它符号 入口字母？取字符字母？数字？出口出口否是是否是否程序设计语言与编译 9.查保留字子程序reserve10.语句return(c,val)11.二进制转换子程序dtb12.标识符存符号表子程序id13.指针变量val14.错误处理子程序error1.字符串变量char2.字符数组token3.读一字符子程序getchar4.删除空白子程序getnbc5.连接字符串子程序concat6.判定字母函数le
27、tter7.判定数字函数digit8.回退一字符子程序retract全局量及过程全局量及过程:用来存放最新读入的字符用来存放最新读入的字符用来存放单词符号用来存放单词符号从扫描缓冲区读一个字符进入char，并将搜索指针移向下一个字符检查检查charchar中字符是否为中字符是否为空白；若是，调用空白；若是，调用getchargetchar，直到，直到charchar中中的字符不是空白符的字符不是空白符把把charchar中的字符连接到中的字符连接到tokentoken布尔函数；若布尔函数；若charchar中的中的字符为字母，返回真；字符为字母，返回真；否则，为假；否则，为假；布尔函数；若布尔
28、函数；若charchar中的中的字符为数字，返回真；字符为数字，返回真；否则，为假；否则，为假；将搜索指针回退一个字将搜索指针回退一个字符，并把已读入符，并把已读入charchar的的字符用空白代替。字符用空白代替。用用tokentoken中的字符串查中的字符串查保留字表，若查到，则保留字表，若查到，则返回该保留字的种别编返回该保留字的种别编码；否则返回码；否则返回0 0值值其中其中c c是种别编码，是种别编码，valval或者是或者是tokentoken在符号表中在符号表中位置，或者是在常数表位置，或者是在常数表中的位置，或者无定义中的位置，或者无定义将将token中的数字串转中的数字串转换
29、成二进制值，并存入换成二进制值，并存入常数表中常数表中将将tokentoken中的字符串存中的字符串存入符号表中入符号表中存放标识符在符号表中存放标识符在符号表中的位置，或常数在常数的位置，或常数在常数表中的位置表中的位置处理出现的词法错误处理出现的词法错误程序设计语言与编译start:token:=;getchar;getnb;case character of az:begin while letter or digit do begin concatenate;getchar end;retract;c:=reserve;if c=0 then begin buildlist;retur
30、n($ID,val)end else return(c,)end;09:begin while digit do begin concatenate;getchar end;retract;dtb;return($INT,val)end;=:return($EQ,);-:return($SUB,);*:return($MUL,);(:return($LPAR,);):return($RPAR,);程序设计语言与编译 then return($NE,);retract;return($LT,)end;:begin getchar;if character=then return($GE,);re
31、tract;return($GT,)end;:begin getchar;if character=then return($ASSIGN,)else error end;:return($SEM,)other:errorend of case;goto start;程序设计语言与编译u将词法分析器实现为一个函数将词法分析器实现为一个函数uLexAnalyze()，函数每执行一次，函数每执行一次，就会从输入字符串中识别出一个单就会从输入字符串中识别出一个单词符号并按二元式形式词符号并按二元式形式返回返回。程序设计语言与编译u实际词法分析中，可连续调用该函实际词法分析中，可连续调用该函数，将输入
32、字符串中的所有单词符数，将输入字符串中的所有单词符号识别出来，并输出相应的二元式号识别出来，并输出相应的二元式序列；序列；u也可将其作为语法分析程序的一个也可将其作为语法分析程序的一个子程序，当语法分析需要下一个新子程序，当语法分析需要下一个新单词时，就调用该函数，从输入字单词时，就调用该函数，从输入字符串中识别一个单词后返回。符串中识别一个单词后返回。程序设计语言与编译4242编译过程中编译程序需要不断汇集和反复查编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有证出现在源程序中各种名字的属性和特征等有关信息。这些信息通常记录在一张或多张符号关信息。这些信息通常记
33、录在一张或多张符号表中，每一项分两部分：名字表中，每一项分两部分：名字(标识符标识符)和此名和此名字的有关信息。每个名字的有关信息一般指种字的有关信息。每个名字的有关信息一般指种属属(如简单变量、数组、过程等如简单变量、数组、过程等)、类型、类型(如整、如整、实、布尔等实、布尔等)等等。这些信息将用于语义检查、等等。这些信息将用于语义检查、产生中间代码以及最终生成目标代码等阶段。产生中间代码以及最终生成目标代码等阶段。程序设计语言与编译4343u在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。在词法分析及语法在分析过程中不断积累和更 新表
34、中的信息，并在词法分析到代码生成的各阶段，按各自的需要从表中获取不同的属性信息。不论编译策略是否分趟，符号表的作用和地位是完全一致的。收集符号属性收集符号属性 上下文语义的合法性检查的依据上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 程序设计语言与编译4444u 收集符号属性收集符号属性 u编译程序扫描说明部分收集有关标识符的属性，并在符号表中建立符号的相应属性信息。例如，编译程序分析到下述两个说明语句int A;float B5;程序设计语言与编译4545u上下文语义的合法性检查的依据上下文语义的合法性检查的依据u 同一个标识符可能在程序
35、的不同地方出现，而有关该符号的属性是在这些不同情况下收集的。特别是在多趟编译及程序分段编译（在PASCAL及C中以文件为单位）的情况下，更需检查标识符属性在上下文中的一致性和合法性。通过符号表中属性记录可进行相应上下文的语义检查。例如，在一个C语言程序中出现int i 3,5;/定义整型数组ifloat i4,2;/定义实型数组i,重定义冲突int i 3,5;/定义整型数组i,重定义冲突 程序设计语言与编译4646u 作为目标代码生成阶段地址分配的依据作为目标代码生成阶段地址分配的依据 u每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）。u首先要确定其被分配的区域。在
36、C语言中首先要确定该符号变量是分配在公共区（extern）、文 件静态区（extern static）、函数静态区（函数中static）、还是函数运行时的动态区（auto）等。u其次是根据变量出现的次序决定该变量在某个区 中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中。程序设计语言与编译4747在编译的各个分析阶段，每当遇到一个名在编译的各个分析阶段，每当遇到一个名字都要查找符号表。若是新名字或发现已有名字都要查找符号表。若是新名字或发现已有名字的新信息，则要加入字的新信息，则要加入(填入填入)。因此
37、，合理。因此，合理组织符号表，使其存储占用最少，同时提高编组织符号表，使其存储占用最少，同时提高编译期间对符号表的访问效率，至关重要。译期间对符号表的访问效率，至关重要。一、符号表的作用一、符号表的作用程序设计语言与编译4848概括地说，符号表的每一项概括地说，符号表的每一项(或称入口或称入口)包含包含两大栏两大栏(或称区段、字域或称区段、字域)，即，即名字栏名字栏和和信息栏信息栏。表格的形式如下：表格的形式如下：第第1项项(入口入口1)第第2项项(入口入口2)第第n项项(入口入口n)名字栏(NAME)信息栏(INFORMATION)程序设计语言与编译4949信息栏包含许多子栏和标志位，记录相
38、应信息栏包含许多子栏和标志位，记录相应名字的种种不同属性。由于查填符号表一般是名字的种种不同属性。由于查填符号表一般是通过匹配名字来实现的，故名字栏也称通过匹配名字来实现的，故名字栏也称主栏主栏，其内容称为其内容称为关键字关键字(keyword)。符号表中每一项都是关于名字的说明。因符号表中每一项都是关于名字的说明。因为所保存的关于名字的信息取决于名字的用途，为所保存的关于名字的信息取决于名字的用途，所以各表项的格式不一定统一，为使表中的每所以各表项的格式不一定统一，为使表中的每个记录格式统一，可采用指针技术，在记录中个记录格式统一，可采用指针技术，在记录中设置指针，把某些信息放在表的外边，用
39、指针设置指针，把某些信息放在表的外边，用指针指向存放另外信息的空间。指向存放另外信息的空间。程序设计语言与编译5050对符号表的操作大致可以分为五类：对符号表的操作大致可以分为五类：查询某个名字是否已在表中。查询某个名字是否已在表中。填入一个新的名字。填入一个新的名字。添加或更新某个名字的某些信息。添加或更新某个名字的某些信息。删除一个或一组无用的项。删除一个或一组无用的项。访问某个名字的某些信息。访问某个名字的某些信息。程序设计语言与编译5151u对符号表进行操作的时机：对符号表进行操作的时机：定义性出现定义性出现使用性出现使用性出现u按名字的不同种属建立多张符号表，如常按名字的不同种属建立
40、多张符号表，如常数表、变量名表、过程名表、数表、变量名表、过程名表、u符号的组织方式符号的组织方式:1.1.安排各项各栏的存储单元为固定长度安排各项各栏的存储单元为固定长度2.2.用间接方式安排各栏存储单元用间接方式安排各栏存储单元程序设计语言与编译5252最简单的组织方式：各项各栏长度固定最简单的组织方式：各项各栏长度固定易于组织、填写和查找。这种表格，每一栏易于组织、填写和查找。这种表格，每一栏的内容可直接填写在有关的区段内。的内容可直接填写在有关的区段内。例如，例如，对于名字栏，其大小可按标识符最对于名字栏，其大小可按标识符最大允许长度来确定。如标准大允许长度来确定。如标准FORTRAN
41、语言规语言规定每一标识符不得超过定每一标识符不得超过6个字符，因此就可用个字符，因此就可用6个字符的空间作为名字栏的长度。若标识符长个字符的空间作为名字栏的长度。若标识符长度不足度不足6个字符，则以空白符补齐。个字符，则以空白符补齐。二、符号表的组织方式二、符号表的组织方式程序设计语言与编译5353但是，有许多语言对标识符的长度几乎不但是，有许多语言对标识符的长度几乎不加以限制，或者说，标识符的长度范围很宽。加以限制，或者说，标识符的长度范围很宽。比如说，最长可允许由比如说，最长可允许由100个字符组成的名字。个字符组成的名字。此时，如果名字栏的长度设为此时，如果名字栏的长度设为100个字符，
42、则势个字符，则势必会大量浪费存储空间。因此，最好采用指针必会大量浪费存储空间。因此，最好采用指针技术。用另外一独立的字符串数组，把所有标技术。用另外一独立的字符串数组，把所有标识符都存放其中。在符号表的主栏放一指示器识符都存放其中。在符号表的主栏放一指示器和一整数，或仅放一指示器，同时在标识符前和一整数，或仅放一指示器，同时在标识符前放一个整数。指示器指出标识符在字符串数组放一个整数。指示器指出标识符在字符串数组中的位置；整数代表此标识符的长度。中的位置；整数代表此标识符的长度。程序设计语言与编译5454SAMPLELOOPINFORMATIONNAME，6，4在符号表的主栏放一指示器和一整数
43、在符号表的主栏放一指示器和一整数程序设计语言与编译5555INFORMATIONNAME6SAMPLE4LOOP在符号表的主栏放一指示器，同时在标识在符号表的主栏放一指示器，同时在标识符前放一个整数符前放一个整数程序设计语言与编译5656 类似地，如果各种名字所需的信息空间长类似地，如果各种名字所需的信息空间长短不一，则将共同属性直接登记在信息栏中，而短不一，则将共同属性直接登记在信息栏中，而特殊属性登记在别的地方。在信息栏中附设一指特殊属性登记在别的地方。在信息栏中附设一指示器，指向存放特殊属性的地方。示器，指向存放特殊属性的地方。例如对于数组标识符，需存储的信息包含例如对于数组标识符，需存
44、储的信息包含维数等，如果将它们与其它名字全部集中在一张维数等，如果将它们与其它名字全部集中在一张符号表中，处理起来很不方便。因此，常另辟一符号表中，处理起来很不方便。因此，常另辟一个信息表区，称个信息表区，称数组信息表数组信息表(或内情向量表或内情向量表)，用来保存数组的有关信息。在符号表的地址栏内用来保存数组的有关信息。在符号表的地址栏内存入符号表与内情向量表连接的入口地址。当填存入符号表与内情向量表连接的入口地址。当填写或查询数组有关信息时，通过符号表来访问此写或查询数组有关信息时，通过符号表来访问此内情向量表。内情向量表。程序设计语言与编译5757 对对过程名过程名以及以及其它一些含信息
45、较多的名其它一些含信息较多的名字字，都可类似地开辟专用信息表，存放那些，都可类似地开辟专用信息表，存放那些不宜全部存放在符号表中的信息，而在符号不宜全部存放在符号表中的信息，而在符号表中保留与信息表相联系的地址信息。表中保留与信息表相联系的地址信息。程序设计语言与编译5858 一张可容纳一张可容纳 N 项的符号表在存储器中可用下项的符号表在存储器中可用下述两种不同方式之一表示述两种不同方式之一表示(假定每项需用假定每项需用K个字个字)(1)把每一项置于连续的把每一项置于连续的 K个字中。个字中。K*N个字个字表示。表示。(2)分成分成 M 个子表个子表T1，T2，Tm。每个子表。每个子表含含
46、N 项。假定子表项。假定子表 Ti 的每一项所需的字数为的每一项所需的字数为 Ki，则则 K=K1+K2 +Km 。对于任何。对于任何i,T1i,T2i,Tmi的并置就构成了符号表第的并置就构成了符号表第i项的全部内容。项的全部内容。程序设计语言与编译5959 编译过程中，每一遍所用的符号表可能编译过程中，每一遍所用的符号表可能略有差别。一般说来，主栏和某些基本属性略有差别。一般说来，主栏和某些基本属性栏大多不会改变，但另外一些信息栏可能在栏大多不会改变，但另外一些信息栏可能在不同阶段有不同的内容，为了合理使用存储不同阶段有不同的内容，为了合理使用存储空间，特别是重新利用那些已经过时的信息空间
47、，特别是重新利用那些已经过时的信息栏所占用的空间，最好采用第栏所占用的空间，最好采用第二种存储表示二种存储表示方式方式。若用高级语言实现的话，用记录数组或若用高级语言实现的话，用记录数组或变体记录的数组来实现是比较合适的。变体记录的数组来实现是比较合适的。程序设计语言与编译6060 在编译时，虽然从原则上说，使用一张统在编译时，虽然从原则上说，使用一张统一的符号表就够了。但许多编译程序按名字的一的符号表就够了。但许多编译程序按名字的不同种属分别使用许多符号表。如常数表、变不同种属分别使用许多符号表。如常数表、变量名表、过程名表等等。这是因为，不同种属量名表、过程名表等等。这是因为，不同种属名字
48、的相应信息往往不同，信息栏的长度也各名字的相应信息往往不同，信息栏的长度也各有差异。因而，按不同种属建立不同的符号表有差异。因而，按不同种属建立不同的符号表在处理上常常是比较方便的。在处理上常常是比较方便的。程序设计语言与编译6161PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.程序设计语
49、言与编译6262PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.程序设计语言与编译6363PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K
50、:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.程序设计语言与编译6464PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER;K:INTEGER;BEGINBEGINSTART:START:K:=M+1;K:=M+1;M:=N+4;M:=N+4;N:=K;N:=K;END.END.程序设计语言与编译6565PROCEDURE INCWAP(MP
