编译原理是计算机专业的一门重要专业课,通过对这门课程的学习,不仅可以掌握编译理论和方法方面的基本知识,而且能获得设计、实现、分析和移植编译程序方面的初步能力。第一视频教程推荐的这部编译原理教程是一部非常不错的教程。有意学习编译原理相关知识的朋友不妨仔细观看一下!
编译原理一直是计算机学习的必修课。当然,由编译器的阶段使用的算法与支持这些阶段的数据结构
关注公众号:diyijc_com
问题反馈
编译原理是计算机专业的一门重要专业课,通过对这门课程的学习,不仅可以掌握编译理论和方法方面的基本知识,而且能获得设计、实现、分析和移植编译程序方面的初步能力。第一视频教程推荐的这部编译原理教程是一部非常不错的教程。有意学习编译原理相关知识的朋友不妨仔细观看一下!
编译原理一直是计算机学习的必修课。当然,由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是:与程序大小成线性比例的时间内编译器,换言之就是,在0 ( n )时间内,n是程序大小的度量(通常是字符数)。本节将讲述一些主要的数据结构,它们是其操作部分阶段所需要的,并用来在阶段中交流信息。
1. 记号(token)。当扫描程序将字符收集到一个记号中时,它通常是以符号表示这个记号;这也就是说,作为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息(例如:与标识符记号相关的名字或数字记号值)。在大多数语言中,扫描程序一次只需要生成一个记号(这称为单符号先行(single symbol lookahead))。在这种情况下,可以用全程变量放置记号信息;而在别的情况(最为明显的是FORTRAN)下,则可能会需要一个记号数组。
2.语法树(syntax tree)。如果分析程序确实生成了语法树,它的构造通常为基于指针的标准结构,在进行分析时动态分配该结构,则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录,它的域表示由分析程序和之后的语义分析程序收集的信息。例如,一个表达式的数据类型可作为表达式的语法树节点中的域。有时为了节省空间,这些域也是动态分配或存放在诸如符号表的其他数据结构中,这样就可以有选择地进行分配和释放。实际上,根据它所表示的语言结构的类型(例如:表达式节点对于语句节点或声明节点都有不同的要求),每一个语法树节点本身都可能要求存储不同的属性。在这种情况下,可由不同的记录表示语法树中的每个节点,每个节点类型只包含与本身相关的信息。
3.符号表(symbol table)。这个数据结构中的信息与标识符有关:函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互:扫描程序、分析程序或将标识符输入到表格中的语义分析程序;语义分析程序将增加数据类型和其他信息;优化阶段和代码生成阶段也将利用由符号表提供的信息选 出恰当的代码。因为对符号表的访问如此频繁,所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构,但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。
4.常数表(literal table)。常数表的功能是存放在程序中用到的常量和字符串,因此快速插入和查找在常数表中也十分重要。但是,在其中却无需删除,这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。通过允许重复使用常量和字符串,常数表对于缩小程序在存储器中的大小显得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入数据定义的符号地址。
5. 中间代码(intermediate code)。根据中间代码的类型(例如三元式代码和P -代码)和优化的类型,该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器,应特别注意选择允许简单重组的表示。
更新时间:2013-08-22 21:25