CML指针类型编译程序的设计与实现

论文摘要

本文主要介绍了如何在CML语言中实现带指针类型的编译器。指针类型在编译器中的实现主要涉及到语法分析、语义分析、中间代码生成以及存储空间的管理。语法分析器有三类。一类是通用的语法分析方法,如Corcke-Younger-Kasami算法和Earley算法,这些分析方法能分析任何文法1。然而这些方法在生成编译器时效率太低。另外两种是编译器常用的是自顶向下的方法和自底向上的方法。不论哪种方法,语法分析程序都是自左向右的扫描输入字符串,每次读一个符号。本文采用的是自顶向下的方法的一种:递归下降法。在编译器的语法分析阶段对指针类型进行分析只能完成指针类型的定义和使用是否在语法上正确,而不能做进一步的分析,进一步的分析需要在语义分析和类型检查阶段才能完成。因此,针对指针类型在语法分析阶段主要工作:指针类型的定义在语法是否正确;指针变量的使用在语法上是否正确。指针类型定义的分析是建立在普通类型定义分析的基础之上,处理的规则很简易,如果在类型定义时是指针类型,向前看TOKEN必须是标识符。指针变量的使用的分析很简单,对于指针变量的使用,前面必定是一个标识符,不管它是变量标识符还是域名标识符,变量标识符和域名标识符只是决定了该指针类型是一个普通的指针类型,还是一个记录类型中的一项。在词法分析和语法分析之后,编译器要进行的工作就是语义上的分析。在语义分析时要结合各种符号表技术以进行查找。要判断指针类型在语义上是否正确,主要要解决以下问题:指针类型的定义在语义上是否正确。指针变量的使用在语义上是否正确。指针变量语义上的检查主要工作在于首先检查该变量是否是指针类型,如果是指针类型,它的用法在语义上正确吗?对于第一个问题,该变量是指针类型吗?这个问题很好解决,只要在符号表中进行查找,如果找到且是指针类型,表明正确,其余均为错误。指针变量的使用在语义上是否正确要进行迭代,即每次循环在变量后面如果有’^’就把该符号消耗掉,同时在符号表中检查它是否是指针类型。另外在这个阶段,还需要涉及超前声明和回填。指针类型主要用在赋值语句和作为过程的参数时使用。它和一般类型检查类似。首先判断是否是指针类型,然后把它们所指向的目标类型的指针进行比较,如果相同,就表明是等价的,否则报错。存储空间的管理主要由栈式分配和堆式分配两种方法。本文主要对堆式分配进行了介绍。堆区空间主要用于存放动态申请空间变量的值。凡是动态申请的空间都分配到堆区中,对于我们的CML语言来讲就是指针类型的分配。动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存?又如何回收那些用户不再使用而“释放”的内存,以备于新的“请求”产生时重新进行分配?对于响应用户提出的分配内存的请求,只需要在堆区中查找满足要求的空间即可,对于释放,在释放空间时要进行相邻空闲空间的合并,以减少碎片。这就要求在进行释放时,要进行相邻空间的检查,看是否是自由空间,如果是,就进行合并,如果不是,则简单的释放。具体有4种情况:1、释放块的左、右邻区均为占用块,此时只要作简单的释放即可。2、释放的左邻区为空闲块,而右邻区为占用块:由于释放块的头部和左邻空闲块的底毗邻,因此只要改变左邻空闲块的结点;增加结点的size域的值且重新设置结点。3、释放的右邻区为空闲块,而左邻区为占用块。由于释放块的底部和右邻空闲块的头部毗邻,因此,当表中结点由原来的右邻空闲块变成合并后的大空闲块时,结点的底部位置不变,但头部要变,由此,链表中的指针也要变。4、释放块的左、右块均为空闲块:为使三个空闲块成为一个大的结点留在可利用空间表中,只要增加左邻空闲块的space容量,同时在链表中删除右邻空闲块的结点即可。在本文中没有涉及垃圾回收的问题。垃圾回收是更现代的语言如JAVA、C#的一个重要特征。垃圾收集中大量的工作都由垃圾算法来完成。任何一种垃圾收集算法都必须做两件基本的工作:首先,它必须检测到垃圾对象的存在;其次,它必须回收垃圾对象所占据的堆空间,并将堆空间归还给系统,让应用程序能够继续使用。一般来说,实现垃圾检测的方式是:定义一组根结点,并从根结点出发检查其他结点的可到达性。如果存在一条引用路径,使得执行中的程序能够从根结点出发访问到被检查的对象,则该对象就是“可到达”的。所有从根结点可到达的对象都被认为是“活”对象,而不可到达的对象则认为是垃圾,因为它们不会再对程序未来的执行造成任何影响。将活对象和垃圾区分开来有两种算法:引用计数和遍历。引用计数型垃圾收集器会在堆上的每个对象中保存一个计数器,用这个计数器来记录指向该对象的引用个数,并以此来区分活对象和垃圾对象。另一方面遍历型垃圾收集器则是从根结点开始切实地遍历整个引用图。在遍历过程中遇到的对象就做上某种标记。遍历结束后,未被标记的对象就是不可到达的,因此被作为垃圾回收。

论文目录

• 中文摘要
• 英文摘要
• 引言
• 第一章 绪论
• 1.1 课题研究的背景
• 1.2 课题研究的主要目的
• 1.3 论文完成的主要工作
• 第二章 词法分析
• 2.1 词法分析概述
• 2.2 CML 语言所定义的词法
• 2.3 词法分析的主要任务
• 2.4 指针类型的词法分析
• 2.5 词法分析程序的实现
• 第三章 语法分析
• 3.1 语法分析概述
• 3.2 LL（1）语法分析方法的实现
• 3.3 CML 语言的语法图
• 3.4 指针类型的语法分析
• 3.4.1 普通类型的语法分析
• 3.4.2 指针类型的语法分析
• 3.4.3 指针变量的使用
• 3.5 语法分析程序的实现
• 第四章 语义分析
• 4.1 语义分析的基础
• 4.1.1 语义分析的内容
• 4.1.2 标识符和类型的内部表示
• 4.1.3 符号表的结构
• 4.1.3.1 符号表的局部化以及建立和查找
• 4.1.3.2 符号表的界面
• 4.2 指针类型的语义分析
• 4.2.1 指针类型的内部表示
• 4.2.2 指针类型定义的语义分析
• 4.2.3 指针变量的使用在语义上的检查
• 4.2.4 超前声明、回填时机及回填算法
• 4.3 类型检查
• 4.3.1 一般类型的等价性检查
• 4.3.2 指针类型的等价检查
• 4.3.3 错误处理
• 第五章 运行时环境
• 5.1 目标机的模型
• 5.2 目标机的指令及格式
• 5.3 解释程序及执行
• 5.4 解释程序执行的实例
• 第六章 运行时的存储空间
• 6.1 运行时的存储空间的结构
• 6.2 运行时的存储空间的分配
• 6.2.1 静态区的存储分配
• 6.2.2 栈区的存储分配
• 6.2.3 堆区的存储分配
• 6.2.4 动态空间（堆区空间）管理
• 6.2.4.1 概述
• 6.2.4.2 分配和释放算法
• 6.2.5 运行时的过程活动记录与栈区的组织结构
• 6.2.5.1 过程的活动记录
• 6.2.5.2 动态链（DL）
• 6.2.5.3 变量的访问
• 第七章 目标代码生成
• 7.1 非指针类型的目标代码生成
• 7.1.1 声明的处理
• 7.1.2 赋值语句
• 7.1.3 过程调用
• 7.1.4 while 语句
• 7.1.5 if 语句
• 7.1.6 for 语句
• 7.2 指针类型的目标代码生成
• 第八章 实例
• 第九章 总结
• 参考文献
• 致谢
• 导师及作者简介