[理学]PL／0编译器的实现文档.doc

第二章 PL/0编译程序的实现 【课前思考】　　复习第1章介绍的一个高级程序设计语言编译程序的功能和实现的步骤。编译程序就是一个语言的翻译程序，通常是把一种高级程序设计语言（称源语言）书写的程序翻译成另一种等价功能语言（称目标语言）的程序。换句话说，编译是指把一种用源语言表示的算法转换到另一种等价的用目标语言表示的算法。编译程序实现的必要步骤有词法、语法、语义分析和代码生成。此外必需有符号表管理程序和出错处理程序。本章介绍的PL/0编译程序的实现是用PASCAL语言书写的【学习目标】 　　本章目的：以PL/0语言编译程序为实例,学习编译程序实现的基本步骤和相关技术，对编译程序的构造和实现得到一些感性认识和建立起整体概念，为后面的原理学习打下基础。 　　 了解并掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对 PL/0语言的形式描述。 　　 了解并掌握PL/0语言编译程序构造和实现的基本技术和步骤。 　　 了解并掌握PL/0语言编译程序的目标程序在运行时数据空间的组织管理。 【学习指南】 　　 要求读者阅读PL/0语言编译程序文本，了解一个编译程序构造的必要步骤和实现技术。一个编译程序的实现比较复杂，读懂一个典型的程序从设计思想到实现技术也有一定难度，特别是入门开始需要耐心。一但读懂，不仅了解编译程序的实现方法和技术，还可学到许多编程技巧和好的编程风格。 　　 阅读PL/0语言编译程序文本时，应从整体结构开始逐步细化，弄清楚每个过程的功能和实现方法及过程之间的相互关系。 　　 建议用一个PL/0源程序的例子为导引作为阅读PL/0语言编译程序文本的入门，然后再逐步全面读懂。 　　 通过对PL/0语言编译程序某些指定功能的扩充，加深对编译程序构造步骤和实现技术的理解，并能在实践中应用。 【难 重 点】 　重点： 　　 弄清源语言(PL/0)目标语言(类pcode)实现语言（这3个语言之间的关系和作用。 　　 掌握用语法图和扩充的巴科斯-瑙尔范式(EBNF)对一个高级程序设计语言的形式描述。 　　 了解PL/0语言编译程序的语法分析技术采用的是自顶向下递归子程序法。 　　 掌握PL/0语言编译程序的整体结构和实现步骤，并弄清词法分析、语法分析、语义分析、代码生成及符号表管理每个过程的功能和相互联系。 　　 掌握PL/0语言编译程序的目标程序在运行时采用栈式动态存储管理的实现技术。 　难点： 　　 符号表管理起着编译期间和目标程序运行时信息联系的纽带，符号表的建立并不困难，但信息之间的关系往往需要反复学习才能理解。 【知识结构】 为了使读者在系统地学习本教材以下各章节之前，对编译程序的构造得到一些感性认识和初步了解，本章推荐了世界著名计算机科学家N.Wirth编写的PL/0语言的编译程序，并对其实现过程作了概括的分析说明，作为读者阅读PL/0语言编译程序文本的提示。对PL/0语言文法的表示只给出语法图和扩充的巴科斯-瑙尔范式(EBNF)的描述形式，不作文法理论上的讨论。由于PL/0语言功能简单、结构清晰、可读性强，而又具备了一般高级语言的必须部分，因而PL/0语言的编译程序能充分体现一个高级语言编译程序实现的基本技术和步骤。因此，PL/0语言编译程序是一个非常合适的小型编译程序的教学模型。所以，阅读PL/0语言编译程序文本后，可帮助读者对编译程序的实现建立起整体概念。 2.1 PL/0语言和类pcode的描述 在上一章中已介绍过，编译程序的功能是把一种高级程序设计语言的程序翻译成某种等价功能的低级语言的程序。PL/0语言的编译程序就是要把PL/0语言程序翻译成为一种称为类pcode的假想的栈式计算机汇编语言程序。这种汇编语言与机器无关，若需要在某一机器上实现PL/0语言程序，只需用机器上配置的任何语言对类pcode语言程序进行解释执行。那么PL/0语言是什么样的语言？类pcode语言又是什么样的结构？它们之间是如何映射的？只有在明确了这些问题之后，才能确定如何构造这个翻译程序。 　　就像一个翻译要把汉语翻译成英语，必须对汉语和英语的单词、语法结构都很精通，才有可能翻译得准确无误。另外，编译程序既然是为了完成这种功能的一个程序，就存在用什么语言来编写这个程序的问题。这些问题在本节将逐步介绍。 现对PL/0语言编译程序的功能用“T”型图（“T”型图将在第13章详细介绍）表示，并用图形概括描述PL/0编译程序的结构框架。本节将用语法图和扩充的巴科斯-瑙尔范式（BACKUS-NAUR FORM）(EBNF)两种形式给出PL/0语言的语法描述。对类pcode代码给出指令的结构形式和含义。 　　巴科斯-瑙尔范式（BACKUS-NAUR FORM）是根据美国的John W.Backus与丹麦的Peter Naur命名的。2.1.1