编译原理符号表的原理及典型实例

编译原理符号表的应用1. 什么是编译原理符号表编译原理中的符号表是一种数据结构，用于记录程序中各个符号的相关信息，包括变量名、函数名、常量等。

在编译过程中，符号表起着重要的作用，可以进行词法分析、语法分析和语义分析等过程中的变量和函数的命名检查、重名检查以及类型检查等功能。

2. 符号表的组织结构符号表可以采用不同的组织结构，最常见的有线性表、散列表和树等。

下面列举了几种常见的符号表组织结构：•线性表：符号表可以通过数组或链表等数据结构来表示。

•散列表：采用散列函数对符号进行映射，能够快速地查找符号。

•树：符号表可以用二叉搜索树、AVL树或红黑树等数据结构来表示，支持快速的查找、插入和删除操作。

3. 符号表在编译过程中的应用符号表在编译过程中扮演着重要的角色，下面介绍了符号表在不同阶段的应用：3.1 词法分析阶段在词法分析阶段，编译器通过符号表来记录程序中出现的各个标识符的信息，包括变量名、函数名和常量等。

符号表可以用来进行标识符的重名检查，以及维护标识符的属性信息，比如变量的类型、作用域和内存地址等。

3.2 语法分析阶段在语法分析阶段，编译器需要判断语法是否正确，并生成语法树。

符号表在此阶段可以用来进行各种类型的语法检查，比如检查函数参数的类型、检查类型转换的合法性等。

符号表还可以用来维护函数的参数表和局部变量表等信息。

3.3 语义分析阶段在语义分析阶段，编译器需要对代码进行语义检查，包括类型检查、作用域检查等。

符号表是进行这些检查的重要依据，通过符号表可以判断变量是否被定义、变量的作用域和类型是否匹配等。

3.4 中间代码生成阶段在中间代码生成阶段，编译器需要将源代码转换成中间代码，符号表可以用来生成中间表示时的参考依据。

符号表可以用来维护中间变量的属性信息，并生成中间代码时进行类型转换的判断。

3.5 代码优化和目标代码生成阶段在代码优化和目标代码生成阶段，符号表可以用来进行变量的寄存器分配和内存分配等操作。

编译原理符号表1. 引言编译原理是计算机科学领域中一个重要的研究方向，它研究的是将高级语言程序转化为机器语言的过程。

在编译器中，符号表是一种常用的数据结构，用于存储程序中的各种符号及其相关信息。

本文将深入探讨编译原理符号表的概念、作用、设计方法以及常见的符号表实现方式。

2. 符号表的概念和作用2.1 符号表的定义符号表是编译器中用于存储程序中各种符号信息的数据结构。

它一般由编译器自动生成和维护，用于支持语法分析、语义分析和代码生成等编译过程。

2.2 符号表的作用符号表在编译器的各个阶段都发挥着重要的作用：•语法分析阶段：符号表用于识别和存储各种变量、函数和类型的声明信息，以支持后续的语义分析过程。

•语义分析阶段：符号表用于检查变量和函数的引用是否合法，并记录其类型信息和作用域等属性，以支持类型检查和语义约束的验证。

•代码生成阶段：符号表用于存储中间代码和目标代码中的符号引用和符号定义的映射关系，以支持代码生成和目标代码优化等过程。

3. 符号表的设计方法3.1 符号表的数据结构符号表的数据结构通常由符号表项组成，每个符号表项用于存储一个符号及其相关信息。

常见的符号表项包括符号名称、符号类型、作用域、内存地址等。

3.2 符号表的组织方式符号表的组织方式可以有多种选择，常见的包括线性表、哈希表、树和图等。

选择合适的组织方式可以提高符号表的查询效率和插入删除的性能。

3.3 符号表的查询算法符号表的查询算法是指根据给定的符号名称，在符号表中进行查找并返回对应的符号表项。

常见的查询算法有线性搜索、二分搜索和哈希搜索等，选择合适的查询算法可以提高符号表的查询效率。

4. 常见的符号表实现方式4.1 线性表实现线性表实现是符号表最简单的一种实现方式，它可以使用数组或链表来存储符号表项。

线性表实现的优点是简单易懂，缺点是查询效率较低，随着符号表规模的增大，性能下降明显。

4.2 哈希表实现哈希表实现是一种常用的符号表实现方式，它通过哈希函数将符号名称映射到符号表项存储的位置。

确定符号表的组织方式，一般应包括名字栏和信息栏，其中名字栏作为关键字。

要考虑能够存储有关名字的信息，并可以高效地完成如下操作：1.查找：根据给定的名字，在符号表中查找其信息。

如果该名字在符号表中不测试范例：procedure test; var b,c,i:integer;begin b:=1; if a>b thenc:=a+b elsec:=a-b;for i:=0 to 3dobeginc:=i;end;end;符号表的结构#include<stdio.h>#include<string.h>#include<ctype.h>#include<stdlib.h>struct{ int m;char name[20]; char inf[20];}co[999]; int num;include 称为文件包含命令，其意义是把尖括号""或引号<>内指定的文件包含到本程序中，成为本程序的一部分。

被包含的文件通常是由系统提供的，其扩展名为.h 而stdio为standard input output的缩写，意为“标准输入输出” .。

#include<string,h>这是C语言/C++中的字符串处理函数的头文件。

#include <ctype.h>是用作字符处理的，#include <stdlib.h>是用于定义杂项函数及内存分配函数，最后是一个结构函数，分别定义了符号名，信息，个数等变量。

符号显示在C-Free中用了void display()，将已经输入进系统的符号全部都显示出来 3. 符号查找本符号表系统中用void find() ，并通过for循环将所要查找的符号及其信息全都显示出来。

如果查找的字符存在，则在显示之前，运用system(“cls”)进行了清屏，把之前屏幕上所显示的内容全部清除，同时，在显示完成以后，又用了if 语句判断是否要删除此符号及其信息。

编译原理符号表的作用一、引言编译器是将高级语言翻译成机器语言的程序，其主要功能是将源代码转换为可执行的目标代码。

在编译过程中，符号表是一个非常重要的数据结构，用于存储程序中出现的各种符号信息。

本文将介绍符号表的作用及其实现原理。

二、符号表的定义符号表是编译器中用于存储程序中出现的各种符号信息的数据结构，包括变量名、函数名、类型名等标识符及其属性信息。

它通常由一个哈希表和多个链表组成。

三、符号表的作用1. 语法分析阶段：在语法分析阶段，编译器会扫描源代码并生成相应的语法树。

同时，在扫描过程中，编译器会将每个标识符添加到符号表中，并记录其类型、作用域等属性信息。

这些信息可以在后续阶段中被使用。

2. 语义分析阶段：在语义分析阶段，编译器会对程序进行类型检查、作用域检查等操作。

这些操作需要使用到之前保存在符号表中的属性信息。

3. 代码生成阶段：在代码生成阶段，编译器会将源代码转换为目标代码。

在此过程中，编译器需要根据符号表中的信息生成目标代码中的符号表。

四、符号表的实现1. 哈希表：符号表通常由一个哈希表和多个链表组成。

哈希表用于快速查找标识符，并将其插入到相应的链表中。

2. 链表：每个链表对应一个作用域，用于存储该作用域中出现的所有标识符及其属性信息。

当进入一个新的作用域时，编译器会创建一个新的链表，并将其添加到符号表中。

当离开该作用域时，编译器会删除该链表。

3. 属性信息：在符号表中，每个标识符都有相应的属性信息，包括类型、作用域、地址等。

这些信息可以在后续阶段中被使用。

五、总结在编译过程中，符号表是一个非常重要的数据结构。

它可以存储程序中出现的各种标识符及其属性信息，并在后续阶段中被使用。

符号表通常由一个哈希表和多个链表组成，其中哈希表用于快速查找标识符，链表用于存储每个作用域中出现的所有标识符及其属性信息。

通过对符号表的实现和使用，编译器可以更加准确地将源代码转换为目标代码。

第八章符号表编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。

这些信息通常记录在一张或几张符号表中。

符号表的每一项包含两部分，一部分是名字（标识符），另一部分是此名字的有关信息。

每个名字的有关信息一般指种属（如简单变量、数组、过程等）、类型（如整、实、布尔等）等等。

这些信息将使用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。

编译过程中，每当扫描器识别出一个单词后，编译程序就查阅符号表，看它是否已在其中。

如果它是一个新名就将它填进表里。

它的有关信息将在词法分析和语法-语义分析过程中陆续填入。

符号表中所登记的信息在编译的不同阶段都要用到。

在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否相一致）和产生中间代码。

在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。

对于一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。

因为每遍所关心的信息各有差异。

本章重点：符号表的一般组织和使用方法。

第一节符号表的组织和使用信息栏通常包含许多子栏和标志位，用来记录相应名字的种种不同属性。

由于查填符号表一般都是通过匹配名字来实现的，因此，名字栏也称主栏。

主栏的内容称为关键字（key word）。

虽然原则上说，使用一张统一的符号表也就够了，但是，许多编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。

这是因为，不同种属名字的相应信息往往不同，并且信息栏的长度也各有差异的缘故。

因而，按不同种属建立不同的符号表在处理上常常是比较方便的。

对于编译程序的符号表来说，它所涉及的基本操作大致可归纳为五类：1、对给定名字，确定此名是否在有中；2、填入新名；3、对给定名字，访问它的有关信息；4、对给字名字，填写或更新它的某些信息；5、删除一个或一组无用的项。

不同种类的表格所涉及的操作往往也是不同的。

上述五方面只是一些基本的共同操作。

编译原理仅用于教学第10章 符号表第10章 符号表◆ 符号表的作用 ◆ 符号表的内容 ◆ 符号表的组织 ◆ 栈式符号表学习目标„ 掌握 „ 符号表的作用 „ 符号表的内容 „ 符号表的组织方法 „ 栈式符号表10.1 概述1．符号表的作用 符号表在整个编译期间的作用主要有两条：一是辅助语义的(即上下文有关的)正确性检查；二是辅助代码生成。

2．符号表的生存期 符号表的建立可以开始于词法分析阶段(有些内容初始建立)，也可以放到语法语义分析阶段，但符号表的使用， 有时会延续到目标代码的运行阶段(如运行时刻为了诊断的 需要，数组下标地址计算的需要等)。

10.2 符号表的内容◆ 标识符的名字 ◆ 与标识符有关的信息不同的标识符在符号表中具有不同的信息： ⅰ.数组——信息向量表(内情向量表) ⅱ.记录——域紧接着相应的记录变量名字相继存放 ⅲ.过程或函数——参数的个数、类型、次序、是否允 许递归等10.2 符号表的内容① 类型信息 包括种类(常量、变量、数组、标号、函数或过程等)与属性(整型、实型、字符型、布尔型等)。

② 地址码ⅰ.简单变量/常量——在数据区中的绝对或相对地址 ⅱ.数组——在数据区中的首地址 ⅲ.过程或函数——过程或函数的分程序入口地址 ③ 层次信息——标识符所属分程序(过程)的静态层次 ④ 行号信息——标识符在源程序中的行号(说明行与引用行)110.3 符号表的结构与组织1．符号表的结构 线性符号表、树结构、散列表或桶等。

2．符号表的组织 符号表的条目一般由两部分组成，即名字栏与信息栏。

通常，条目用连续的存储字构成的记录来实现。

为保持符号表条目记录的统一，往往把与名字相关联的构造类型等 信息保存在符号表的某处(如数组的信息向量表等)，而把相 应的指针或序号放在记录内。

10.3 符号表的结构与组织3．符号表的操作 大量的查找、填表与删除等操作。

10.4 栈式符号表——PASCAL符号表的设计1．语言的特点PASCAL按照最近嵌套作用域原则，一个名字的作用域 是那个包含了这个名字的说明的最小过程或函数。