毕业设计（论文）-Linux平台下的MIX汇编器设计与实现.doc

河南大学2007届本科毕业论文Linux平台下的MIX汇编器设计与实现The Design and Realization of MIX Compiler under Linux Platform论文作者姓名： 所在学院：计算机与信息工程学院 所学专业：计算机科学与技术 导师姓名职称：论文完成时间：2007年5月20日 2007年5月20日河南大学2007届毕业论文（设计、创作）开题报告（由学生本人认真填写）学号02023191姓名朱选伟导师姓名职称陈志国（教授）杜莹（助教）开题时间2006年12月1日课题题目Linux下的MIX汇编器的设计与实现课题来源导师指定 自定 其他来源课题的目的、意义以及和本课题有关的国内外现状分析：1、目的：在Linux平台下实现计算机程序设计艺术一书中描述的MIX汇编器的功能。2、意义：能够更好地学习计算机程序设计艺术一书，并对虚拟机技术有较好的理解。3、现状：在Windows平台下有相关的软件MIXBuider，但在Linux平台下并没有相关的软件存在。研究目标、研究内容和准备解决的问题：1、目标：在Linux操作系统平台下完成MIX虚拟机的汇编器。2、内容：Linux操作系统平台的编程环境熟悉，掌握虚拟机技术以及汇编技术。3、准备解决的问题：汇编语法问题，虚拟机的实现问题以及Linux编程的基础知识熟悉。拟采取的方法、技术或设计（开发）工具：Linux操作系统，C+编程语言，GNU汇编器，虚拟机技术，汇编原理预期成果：1、毕业设计成果Linux平台下的MIX汇编器软件2、毕业论文Linux平台下的MIX汇编器设计与实现进度计划：2006.12.1 - 2007.4.1：查找资料、搜集相关素材2007.4.2 - 2007.4.11：完成Linux平台的熟悉工作2007.4.12 - 2007.4.21：完成汇编程序部分的设计2007.4.22 - 2007.4.30：完成机器指令的解释执行部分的设计2007.5.1 - 2007.5.15：整理资料、撰写毕业论文2007.5.16 - 2007.5.25：根据导师要求，完善毕业设计和论文指导教师对选题报告的意见：同意开题 指导教师签名： 2006年12月1日开题报告II河南大学2007届毕业论文（设计、创作）任务书（由学生本人认真填写）学号02023191姓名朱选伟导师姓名陈志国，杜莹任务书起止日期2006年12月8日 至 2007年5月20日论文提要： 论文将要介绍四个方面的内容：1、Linux下编译的一般过程、Makefile文件。2、开发环境以及基础知识，包括MIX系统及汇编语言以及虚拟机技术。3、本系统的总体规划及设计。4、系统具体设计与实现。课题任务要求：1、熟悉Linux操作系统的编程环境，熟悉基本的编程操作。2、学习MIX汇编语言。3、掌握虚拟机技术以及汇编原理的相关知识。4、利用前面的知识开发出具体系统。主要参考文献：1 钱能等编著，C+程序设计教程，清华大学出版社，1999年4月 2 D.E.Knuth著，The Art of Computer Programming,Volume 1 Fundamental Algorithms，第3版，清华大学出版社，2002年9月3 陈火旺等著，程序设计语言编译原理，第三版，国防工业出版社，2001年1月4 Richard m.Stallman著，Using and Porting the GNU Compiler Collection, Free Software Foundation，1998年5 Andrew S.Tanenbaum著，王鹏、尤晋元等译，操作系统设计与实现，电子工业出版社，1998年河南大学2007届毕业设计（论文、创作）中期检查表学院名称：计算机与信息工程学院题目名称Linux平台下的MIX汇编器的设计与实现学号02023191所学专业计算机科学与技术指导教师姓 名陈志国杜莹姓名朱选伟一、毕业设计进展情况1、基本完成主体框架的设计，完成了小部分的编码工作。2、对Linux编程环境有了一定了解，对虚拟机技术及汇编技术有了一定的了解。3、具体实现大部分没有完成。二、存在问题1、总体实现并不理想，对虚拟机的了解不深而直接导致整体结构分工不理想。2、对Linux的编程环境掌握并不熟练，导致编程过程频频受阻。三、下一阶段的研究方法或设计思路加快学习虚拟机技术并且重新审视主体模块构成。并集中精力放在主要掌握Linux的基本编程知识。四、指导教师对学生设计（论文、创作）进展等方面的评语 该生较好地完成了基本模块的划分和编码工作，但是进度稍慢，各部分的实现和功能调试仍需认真完成。 指导教师签字： 2007年4月10日此表除第四项外由学生填写指导教师签名河南大学2007届毕业论文（设计、创作）综合成绩表（一）学院名称：计算机与信息工程学院学 号02023191姓名朱选伟专业计算机科学与技术指导教师陈志国（教授）、杜莹（助教）综合得分89论文题目Linux平台下的MIX汇编器的设计与实现指导教师评语及得分指导教师评语该生较好地完成了该汇编器的设计与实现，论文撰写认真，选题新颖。评分项目分值指导教师对毕业论文（设计、创作）评分撰写开题报告、文献综述15调查研究查阅整理资料10学习态度与规范要求10数据处理、文字表达10论文（设计、创作）质量和创新意识55合计100得分138785389指导教师签名 2007年5月20日评阅教师评语及评分评阅教师评语该生选题新颖，论文内容翔实，但软件技术上也并不很成熟，希望以后多加努力。评分项目分值评阅毕业论文（设计、创作）评分撰写开题报告、文献综述15调查研究查阅整理资料10学习态度与规范要求10数据处理、文字表达10论文（设计、创作）质量和创新意识55合计100得分128785388评阅教师签名 2007年5月21日此表由教师填写河南大学2007届毕业论文（设计、创作）综合成绩表（二）学号02023191姓名朱选伟所在学院计算机与信息工程学院答辩委员会评语及评分答辩委员会评语 答辩委员签字： 2007年5月26日评分 项目 分值论文答辩小组评分答辩情况论文质量合计（100）内容表达情况（15）答辩问题情况（25）规范要求与文字表达（20）论文（设计、创作）质量和创新意识（40）得分1223183689答辩委员会主任签字： 2007年5月26日毕业论文（设计、创作）成绩综合评定： 89 分综合评定等级：良备注：一、论文的质量评定，应包括对论文的语言表达、结构层次、逻辑性理论分析、设计计算、分析和概括能力及在论文中是否有新的见解或创新性成果等做出评价。从论文来看学生掌握本专业基础理论和基本技能的程度。二、成绩评定采用结构评分法，即由指导教师、评阅教师和答辩委员会分别给分（以百分计），评阅教师得分乘以20%加上指导教师得分乘以20%加上答辩委员会得分乘以60%即综合成绩。评估等级按优、良、中、差划分，优90-100分；良76-89分；中60-75分；差60分以下。三、评分由专业教研室或院组织专门评分小组（不少于5人），根据指导教师和答辩委员会意见决定每个学生的分数，在有争议时，应由答辩委员会进行表决。四、毕业论文答辩工作结束后，各院应于6月20日前向教务处推荐优秀论文以汇编成册，推荐的篇数为按当年学院毕业生人数的1.5%篇。五、各院亦可根据本专业的不同情况，制定相应的具有自己特色的内容。须报教务处备案。六、书写格式要求：1、目录；2、内容提要须书写200左右汉字，开题报告（文科除外）的内容要根据不同专业的课题任务要求，阐述查阅文献、文案论证、解题思路、工作步骤等；3、正文（含引言、结论等）；4、参考文献（或资料）河南大学本科生毕业论文（设计、创作）承诺书论文题目Linux平台下的MIX汇编器的设计与实现姓 名朱选伟所学专业计算机科学与技术学 号02023191完成时间2007年5月20日指导教师姓名职称陈志国（教授）、杜莹（助教）承诺内容：1、本毕业论文（设计、创作）是学生 朱选伟 在导师 陈志国、杜莹 的指导下独立完成的，没有抄袭、剽窃他人成果，没有请人代做，若在毕业论文（设计、创作）的各种检查、评比中被发现有以上行为，愿按学校有关规定接受处理，并承担相应的法律责任。2、学校有权保留并向上级有关部门送交本毕业论文（设计、创作）的复印件和磁盘。备注：学生签名： 指导教师签名： 2007 年 5 月 20 日 2007 年 5 月 20 日说明：学生毕业论文（设计、创作）如有保密等要求，请在备注中明确，承诺内容第2条即以备注为准。目 录第1章 绪论11.1 Linux下编译的一般过程11.2 Makefile文件简介21.3 C+编程语言31.4 GCC编译器简介3第2章 系统开发基础知识简介42.1 MIX系统及汇编语言简介42.1.1 MIX系统简介42.1.2 MIX指令集62.1.3 MIXAL汇编语言72.2 虚拟机技术简介8第3章 系统总体规划及设计93.1 概要介绍93.1.1 MIX汇编语言的汇编93.1.2 MIX机器指令的载入93.1.3 MIX机器指令的运行93.2 汇编器概要设计103.2.1 词法分析器103.2.2 语法分析器103.2.3 代码生成器113.2.4 符号表113.2.5 错误处理模块113.3 汇编器主要数据结构及算法113.3.1 地址计数器LC113.3.2 符号表113.3.3 未知标号表12第4章 系统具体设计与实现134.1 MIX系统基本结构模块概述134.2 MIX虚拟机系统的具体实现134.2.1 Makefile文件154.2.2 MIX虚拟机主程序174.2.3 MIXAL汇编调试器主程序184.2.4 Assemble汇编程序18结 论22参考文献23河南大学本科毕业生学士学位论文摘 要MIX计算机是一个假想的计算机，它来源于著名的计算机编程艺术（the art of computer programing）。现实中并没有真正的实体机器，为了学习这本书，作者就在自己的PC上实现该计算机的虚拟机以使书上的代码可以顺利运行。C/C+是Linux操作系统平台下的主流语言，相对简便好用，就选用C+作为实现的主要语言，这涉及到Linux平台下的基本的C+编译的知识。这部分编译知识与平常使用较多的Windows平台下的编译知识有着显著不同，所以会进行较多的介绍。在一台电脑上模拟另一种体系结构不同的计算机涉及到了虚拟机的基本知识，虚拟机技术的核心是汇编技术。本文首先简单介绍了Linux下编译的一般过程、Makefile文件以及开发环境，包括MIX系统、汇编语言以及虚拟机技术。然后介绍了本系统的总体规划及设计。最后讲述了系统具体设计与实现。关键词 MIX汇编器，VM技术，C/C+，LinuxABSTRACTMIX is a fictitious 16 bits computer created by D E.Knuth in his famous bookThe Art of Computer Programming，and all algorithms in his book are coded by MIX assemble language. Nowadays computers can not execute those codes, so I want to achieve the main system structure of this machine on my PC for learning this book. There is not a such software in the Linux platform, so that is a good idea to actualize it under the Linux platform. C/C+ are the system languages of the Linux operating system, and I choose the C+ as a main language. The C+ compiler knowledge of the Linux operating system is very different from Windows, so I shall give a particular introduction about it. The Virtual Machine technology is the central idea to “virtual” a machine, and of course it is the most important technology to the realization of MIX computer system. The main idea of VM is involved the assemble technology.This paper firstly introduces the process of compiler under Linux Platform, the file of Makefile and the background of the system.Then explains the design of this system as a whole. Finally, introduces the realize of this system.Keywords MIX compiler, Vm technolegy, C+, Linux第 23 页第1章 绪论MIX计算机是D.E.Knuth在其名著计算机编程艺术（The art of computer programming）中描述的一种计算机，他书中的所有算法都由该计算机的汇编语言实现。但现实生活中并没有运行MIX体系结构的计算机，所以在现有的计算机上并不能直接运行书中的MIX汇编代码。唯一的办法只有在现有的计算机上将MIX的主要体系结构加以模仿，使它可以运行书中的MIX汇编代码。由于在Linux平台下并没有相关的软件存在，所以在Linux下构造这样一个具有MIX计算机系统结构的虚拟机具有开创性的意义。实现的MIX汇编器的主要的作用是运行MIX汇编语言，它的主体部分是一个汇编器。虚拟机的实现依赖于对计算机系统模仿，除去平台和语言的关系，最主要的技术是虚拟机技术，该技术通过软件的方法使在一台计算机上运行另一台体系结构完全不同的计算机的机器指令的想法成为了可能。这其中最主要的代表便是Java虚拟机，它使Java语言实现了“平台无关性”。因此借鉴这个很著名的虚拟机技术来实现对该系统的模拟会有性能上的保证。下面，首先对编程的基本环境作一个简单的介绍，然后就开始介绍该虚拟机的设计与实现。Linux平台下的编程习惯与Windows平台下有很大的不同，它很“原始”，基本上所有的东西都要自己设置，下面假定读者极少接触Linux，会对Linux平台下的编程技术作一个相对简要但清楚的介绍。1.1 Linux下编译的一般过程Linux下没有.NET之类的集成开发环境。它基本的开发工具是Vi，与Windows下的记事本很相像，在它上面输入源程序，然后用命令执行该程序。Linux支持多种语言，例如C语言、C+语言以及perl语言等。最常见和最重要的是C语言的编译器GCC与C+语言的编译器G+。这个执行者有着多达一百条的编译命令在需要时让你输，并且需要编程者与操作系统直接打交道，对于需要操作系统功能调用的地方，程序员必须自己设置适合的系统调用以及库函数。Linux下编写程序的基本步骤是：（1）用vi或Emacs写下源代码，保存。（2）用GCC编译它（在命令行下输入命令：gcc 编译选项 保存名字.c）。（3）一般情况下，若编译无错误的话，会生成一个.out文件，键入如下命令运行它：名字.out。当然在很多情况下不能一次就正确编译通过，会有很多错误需要改正和调试，这时候就可以用GCC自带的调试工具进行调试，直至可以运行。以上仅是最一般的汇编过程，若是有多个源文件的大型程序，就不得不自己定义他们之间的相互依赖关系和编译调用关系，这就涉及到了Make工具和Makefile文件，这可能是与Windows平台下的编程习惯最不同的一点，所以对此作稍微详细的介绍。1.2 Makefile文件简介Make工具能自动地确定一个大程序系统中哪些程序文件需要被重新编译，并发出命令对这些程序文件进行编译。Make命令执行时，需要一个Makefile文件，以告诉Make命令需要怎么样去编译和链接程序。Makefile关系到了整个工程的编译规则。一个工程中的源文件不计其数，其按类型、功能、模块分别放在若干个目录中，Makefile定义了一系列的规则来指定，哪些文件需要先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至进行更复杂的功能操作，因为Makefile就像一个Shell脚本一样，其中也可以执行操作系统的命令。Makefile规则如下：target . : prerequisites . command . . （1）Target：是一个目标文件，也可以是执行文件，还可以是一个标签（Label）。（2）Prerequisites：就是要生成target所需要的文件或是目标。（3）Command：是make需要执行的命令（任意的Shell命令）。这是一个文件的依赖关系，也就是说，Target这一个或多个的目标文件依赖于Prerequisites中的文件，其生成规则定义在Command中。这就是Makefile的规则。1.3 C+编程语言由于Linux操作系统平台的系统语言是C语言，因此它对C+语言也有着较好的支持。Linux下的C+与C用同一个编译器GCC（G+事实上属于GCC），这个编译器也是与Windows操作系统下的一般编译器有着很大的不同，下面对这个编译器进行简要的介绍。1.4 GCC编译器简介GCC（GNU Compiler Collection）是自由软件组织GNU开发的一款C/C+编译器，是Linux平台下的标准C/C+编译器，功能非常的强大，但使用也非常的繁琐。由于Linux操作系统平台下没有集成开发环境，因此开发者不得不自己对程序进行编译和调试，而这个就要用到基本的编译选项，这时要注意多使用man选项查看基本的帮助。第2章 系统开发基础知识简介本章介绍基本的MIX汇编知识和虚拟机的技术背景。首先介绍MIX系统的结构和汇编语言，在此基础上简单介绍主要技术-虚拟机技术的基本原理。2.1 MIX系统及汇编语言简介为了实现MIX汇编语言的正常运行，这样就必须涉及到汇编器的实现和MIX虚拟机的实现，而在真实的机器上汇编器和机器指令的执行二者的联系是相当紧密的。作为实现的基础，在这里就将MIX系统结构和MIX汇编语言放在一起介绍。2.1.1 MIX系统简介计算机系统包括CPU、存储器、外设、以及输入输出系统，MIX也不例外。图2-1是文献2书中自带的一个图，用来说明MIX系统用到的基本结构。MIX系统由CPU、一个具有四千个存储单元的存储器、外设为磁带和磁盘的几部分组成，下面就突出重点的介绍一下它的基本指令，机器指令的组成以及汇编语言的语法。1 CPU中使用的寄存器寄存器A和寄存器X是CPU中最常使用的寄存器，用作对数据进行算术运算和操作，Aaccumulater可以独立使用，也可与Xextension连接使用，而就像看到的，A寄存器是基本寄存器也称低位寄存器，而X寄存器则是高位寄存器也称扩展位寄存器。I是Index registers，用于计数或访问可变的存储器地址。J是Jump address，用于存放与jump指令相关的地址。注意在MIX系统中，一个计算机字是5个字节，一个字节含6位，这与目前的计算机系统是不同的。I寄存器的内容假想为+/-000mn处理。J寄存器的内容假想为+mn000处理。即J寄存器不能有负值存在。图2-1 MIX计算机系统结构2 汇编指令结构与相应的机器指令翻译基本结构为： C M ,I(F)上面这个式子是指令的表达形式。其中，C代表command的，M代表memory，I代表index，F代表field。当I=0时，可写为C M(F)，下面是具体的机器码存放规则以及相应的解释。一条指令是以一个符号位加上一个计算机字存放的：+/- I F C 。其中各域的作用说明如下：（1）+/-：代表一个符号位。（2） ：占两个字节，即C M ,I(F) 中的M，就是内存单元的编号(即地址)，一个内存单元就是一个计算机字的大小，即word=rA。（3） I ：占一个字节，表示第几个变址寄存器。（4）F：占一个字节，F=8L+R，CM,I(F)通常写成CM,I(L：R),表示该指令操作是相对于某内存单元的第L字节至第R字节表示的内容来做的。当F为(0:5)时，可写为C M,I，此时若I=0，就写成C M。在MIX里一个计算机字是5个字节，一个字节含6位。（5）C：占一个字节，C以不同的值存在代表不同的操作指令。3 MIX具体汇编指令使用举例下面举例说明指令的表达形式。以下的指令是LDA，即把指定内存处的指令装入寄存器A中。假设存储单元2000的内容为：-86354指令与指令完成后寄存器A中的内容对照如下所示：LDA 2000 -86354LDA 2000(1:5) +86354LDA 2000(3:5) +00354LDA 2000(0:3) -00863LDA 2000(4:4) +00005LDA 2000(0:0) -00000LDA 2000(1:1) +000082.1.2 MIX指令集具体指令见图2-2。MIX指令系统由基本的装入、存储、跳转、运算以及比较等种类的操作组成。具体的使用可参见上节的“MIX具体指令说明”，下面仍以LDA 2000为例。大致的情况是，如果指令中没有逗号，即没有I寄存器的加入，那么指令背后的数字即表示直接的内存地址。若是有I寄存器，则该地址必须与I寄存器中的地址进行运算之后方可作为指令运行时使用的内存地址。由于MIX汇编语言中没有像现在一般的汇编语言的可直接分别访问字、字节、双字的指令访问模式，它是通过后面的括号中的内容表示操作的是该地址所表示的内存字的哪几个字节，比如(1:5)就表示载入的是从第一字节到第五字节的内容，进而达到访问字节的目的。图2-2 MIX系统汇编指令集2.1.3 MIXAL汇编语言在总结了MIX指令集后，看看mixal汇编语言的定义。用mixal写的程序结构如下：程序一行一行来读，但整体结构上看开头的符号只是一些自定义的记号，或者是代表某个数值，或者代表所在行指令在内存中的单元地址。它后面的符号一般是一个MIXAL汇编指令或MIX指令集中的某个指令。然后才是表达式，其含义和写法都和第二列的指令是相关联的，是操作数和操作指令的关系。以*开头的语句，以及第四列都是注释。2.2 虚拟机技术简介Java虚拟机是现在最著名的虚拟机,所以主要借鉴了Java虚拟机的原理，在它的基础上简化而得MIX系统的实现。Java虚拟机由五个部分组成：一组指令集、一组寄存器、一个栈、一个无用单元收集堆(Garbage-collected-heap)以及一个方法区域。这五部分是虚拟机的逻辑成份，不依赖任何实现技术或组织方式，但它们的功能必须在真实机器上以某种方式实现。也就是说，为了实现所要的机器的性能，必须自己构造一个不依赖硬件的、逻辑实现的中间层结构，自己完成指令的装入而不是由机器硬件来完成。第3章 系统总体规划及设计本章主要介绍系统的相关具体规划。基本的功能划分是首先对MIX汇编语言进行汇编解释，然后将解释得到的机器指令从“内存”载入到“寄存器”中，最后运行机器指令。整个虚拟机在结构上采用一种自顶向下的方式将各功能模块分类并且定义各自的接口，保证没有结构上的过多藕和，使各模块相互独立。3.1 概要介绍该部分介绍了各个功能模块所要完成的基本工作，以及相关的基本构造。具体介绍了各部分实现时要完成的主要工作和面临的主要问题。3.1.1 MIX汇编语言的汇编汇编是将MIX汇编语言转换为相应的MIX机器指令并将其放入相应的内存中供下一步使用。由于MIX系统的机器指令和汇编语言之间有非常明确的对应关系，因此只需按照MIX汇编语言的基本语法，一步步汇编即可。这个过程中最主要的工作涉及到一个机器指令与汇编指令的对照表，汇编的主体工作便是利用这个表，用C+语言描述它们的对应关系，说明几个域应该怎么填。3.1.2 MIX机器指令的载入载入的工作主要是先将编译得到的机器指令送给“CPU”，并提供程序地址供运行时用。3.1.3 MIX机器指令的运行作用是根据LC载入相应的机器指令，执行并重新设置LC指向下一条要执行的指令。下面重点介绍汇编部分，因为这是整个虚拟机实现的基础，事实上也是集中体现了整个结构的特点。3.2 汇编器概要设计根据Alfred.V.Aho所描述的编译器模块结构，可以将MIX汇编器设计为的几个功能模块：词法分析器、语法分析器、代码生成器、符号表和错误处理模块。各个功能模块之间的相互关系如图3-1所示。对于本部分的实现借鉴了C+程序设计语言中的一个桌面计算器的设计理念。图3-1 MIX汇编器结构3.2.1 词法分析器词法分析器将MIX源程序解释成一个个独立的记号，然后将记号的类型以及记号所对应的值返回给语法分析器。3.2.2 语法分析器语法分析器依据MIX语言的相关规则，对由词法分析器返回的记号序列进行分析。在语法分析的过程中，一般会生成相应的符号表，同时调用代码生成器生成目标代码。如果在语法分析过程中遇到任何错误语句，则调用错误处理模块。语法分析的主要实现思想是采用自顶向下递归下降的实现。虽然在一般情况下不鼓励采用递归的方式去构造语法分析部分，但由于MIX汇编语言相对简单，且C+函数调用的代价相对较低，而递归实现相对结构清晰，容易实现，所以在这里采用了递归的方式。3.2.3 代码生成器代码生成器负责生成每个机器指令的存储工作。当MIX源程序太长或者指令参数使用错误时，代码生成器提示错误信息。3.2.4 符号表符号表是一个辅助功能模块，主要用于处理标号信息。该模块提供必要的符号操作，像定义符号、查询符号等。3.2.5 错误处理模块错误处理模块输出相关的错误信息和发生错误的位置，然后退出程序。错误处理模块不会分析产生错误原因，也不会修复任何错误。3.3 汇编器主要数据结构及算法传统的汇编器采用两次汇编来处理标号向前引用问题。在第一遍扫描先确定所有的标号的地址，并保存在符号表中。第二遍扫描依据第一遍扫描所生成的符号表来汇编每一条汇编语句。本系统也采用了这种方法，因为它的技术很成熟，但是由于MIX汇编语言的简易性，所以就采用了变异的一遍扫描的方法，具体的做法是将第一遍扫描的结果和汇编过程结合在一起，实际上也属于二遍扫描。MIX汇编器主要的数据结构包括：地址计数器LC、符号表和未知标号表。3.3.1 地址计数器LC地址计数器LC用于计算每个标号对应的地址和生成目标代码的存储位置。3.3.2 符号表MIX汇编器采用散列表来组织符号信息，同时使用链表来处理散列冲突的情况。3.3.3 未知标号表未知标号表记录在第一次扫描中遇到的向前引用标号的信息，然后在第二次扫描中用于修正目标代码。第4章 系统具体设计与实现有了前面的基础，本章将给出基本的模块以及与之相关的基本原理和它们之间的联系与实现。这里涉及少量的代码，需要用到的C+语言的知识。4.1 MIX系统基本结构模块概述MIX系统的基本结构在第2章已详细的介绍过，本章的主要任务是在此基础上首先合理地描述该系统的硬件结构，适当地定义它的硬件行为，然后再描述机器指令的实现过程。具体的实现参照了Java虚拟机的原理和最新的关于mixal虚拟机的实现（是Knuth先生关于MIX系统的一个扩展）。而后是汇编程序的实现，需要在前一章所述的基础上描述其汇编解释过程并得到相关的机器指令。4.2 MIX虚拟机系统的具体实现经过以上分析，基本的实现就待编码了。但是，在编码中首先遇到的是调试问题。于是就在原来结构的基础上换一个输出，形成一个汇编语言和机器码的对照跟踪，从而具有一个简单的调试功能。由此整个程序的实现分成了两个基本的功能块：汇编器部分和机器部分，汇编器部分用于输出对照机器码用于调试，而机器部分就是运行得到结果。它们的基本结构是一样的，不同的仅仅是在输出上，一个用于得到结果，一个得到对应机器指令，下面就先给出基本的结构块，然后再就具体的不同介绍二者的实现。根据前面的介绍，就将与机器紧密相关的几个部分分块，放在几个不同的源文件中，这样既容易修改实现起来也显得结构清晰，封装容易。以下是对这几个部分的介绍：MIX机器的模拟相关(mix-machine.cpp)：具体与机器码的编译、运行、连接相关，是本程序实现的一个主要部分，定义了机器相关类。MIX模拟器（mix-sim.cpp）：MIX虚拟机的模拟程序。这是一个主程序，是MIX汇编指令的实现部分。MIX的汇编（mix-assemble.cpp）：实现了MIX汇编语言的语法分析和二进制代码生成的工作对MIX程序进行解释执行。它是本次设计的另一个重点，包含用于将MIXAL汇编语言解释为MIX机器码的类。MIX汇编器（mixal.cpp）：可以输出包含MIX汇编语言对应机器码的列表文件。I/O控制（mix-io.cpp）：外设部分的设置。虽然没有实现磁带机等外设，但是定义了基本的I/O，这里的数据使用自定义的字符数据类型。出错处理（mix-error.cpp）：对所有错误进行处理。这里没有句柄之类的处理函数，仅有一句出错提示。对底层设施的模拟（mix-arith）：MIX汇编和模拟的底层设施，定义了基本的数据类型，CPU类型、内存、汇编格式等。杂类（misc.h）：一些不好划分的类都放到了这里。包含了一些对字符和操作数的定义，是一些能用到的字符。其中，除了mixal.cpp,mix-sim.cpp两个主程序之外，每个源程序文件都有一个同名的.h头文件，定义了一些关系较为密切的数据和宏，而misc仅有一个.h头文件。图4-1展示了MIX系统基本的系统结构。下面一节列出MIX系统设计的各个功能具体代码实现。源代码目录下的文件可分为四类：Makefile文件、cpp源程序、*.H头文件以及一个用MIX汇编语言写的源程序文件。程序主体可分为两部分MIX计算机环境模拟部分和MIX汇编器部分，主体分别属于是mix.cpp和mixal.cpp文件。MIX程序先经汇编程序编译后在所谓的“机器”上运行。这两个部分事实上并没有实质联系，MIX部分是实际的程序执行显示结果部分，而MIXAL则是显示相应的机器指令主要供调试用。他们的主体结构类似，只是在输入和结果上有一些不同。调用的主体函数也基本相同。下面先由Makefile文件入手将总体结构阐述一下再深入理解具体组成。图4-1 MIX系统基本组成图4.2.1 Makefile文件Makefile文件联系着所有的文件，描述了所有源文件之间的关系。下面是该文件的代码（#后为注释）：makefile:all: mix mixal #all表示创建Makefile所知的最顶层目标，这里是mix mixal.PHONY: clean #清除执行文件和所有的中间目标文件clean:-rm *.omix: mix-sim.o mix-machine.o mix-assemble.o mix-arith.o mix-error.o mix-io.o g+ -O2 -o mix mix-sim.o mix-machine.o mix-assemble.o mix-arith.o mix-error.o mix-io.o #运用G+将以上名称中含有mix的.O（object）目标文件组装成mixmixal: mixal.o mix-assemble.o mix-arith.o mix-error.o g+ -O2 -o mixal mixal.o mix-assemble.o mix-arith.o mix-error.o#同上，用G+将mixal.o mix-assemble.o mix-arith.o mix-error.o组装成可执行文件文件mixalmix-assemble.o: mix-assemble.cpp mix-assemble.h mix-arith.h mix-error.h misc.hg+ -O2 -c mix-assemble.cpp #将mix-assemble.cpp编译为.O目标文件。其他文件为用到的包含文件，此处的mix-sim.o: mix-sim.cpp mix-assemble.h mix-machine.h mix-arith.h mix-error.h misc.hg+ -O2 -c mix-sim.cpp #将mix-sim.cpp 编译为.O目标文件mix-machine.o: mix-machine.cpp mix-machine.h mix-arith.h mix-error.h misc.hg+ -O2 -c mix-machine.cpp #编译mix-machine.cppmix-arith.o: mix-arith.cpp mix-arith.h mix-error.h misc.hg+ -O2 -c mix-arith.cpp #编译mix-arith.cppmix-error.o: mix-error.cpp mix-error.hg+ -O2 -c mix-error.cpp #编译mix-error.cppmix-io.o: mix-io.cpp mix-io.h misc.hg+ -O2 -c mix-io.cpp 编译mix-io.cpp整个程序执行的过程是：（1）在源代码目录make all。（2）primes.mix是用MIX汇编语言写的计算前500个素数的程序。命令行下输入./mix primes.mix即可看到结果（需调试时输入/mixal primes.mix）。以下是基本函数及相关的重要数据类型。表4-1 主要函数名称函数词法分析器Get-token()语法分析，中间代码生成Assemble(filename)载入Load(programname)执行指令Execute-instruction()运行MIX.Run()MIX虚拟机Mix-sim()汇编器Mixal()打开MIX源代码文件Src_file.open(filename)出错处理MIXError() 表4-2是主要的数据结构定义。表4-2 基本数据结构名称含义Sym_node链表结构，大多数的地址域采取此结构Op_spec操作码的结构Trie_node三叉搜索树，符号表的基本结构Op_init_table初始时的符号表 Enum opcode对操作数代码的定义，详见前面的内容MIXWord字节定义，基本的数据类型MIXProgramMIX汇编程序类型MIXCPUCpu类MIXMemeryCell内存类MIXMachine机器类，所要实现的虚拟机的类MIXDeviceI/O设备的定义4.2.2 MIX虚拟机主程序这个模块的基本作用是模拟MIX计算机系统，也就是汇编执行MIX机器指令。主体的程序是mix-sim.cpp，主要作用是显示必要信息并执行相应命令打开汇编并执行MIX机器指令，作用类似于Linux下的shell命令行解释程序。主体结构如下：（1）prog_name = argv0;if( argc = 1 ) usage(1);elsefor( int ix = 1; ix argc; +ix )/这部分是读入在界面下的命令，并执行。省略了具体执行代码，可参见源程序内的mix-sim.cpp文件。这里有几个选项，用于显示帮助，版本等信息。（2） src_file.open( src_filename, std:ios_base:in); /打开文件if( !src_file )cerr Cannot open source file src_filename endl;return -1;clock_t tBegin, tEnd;tryMIXProgram &prog = assemble( src_file );/编译文件tBegin = clock();mix.load(prog); /载入if( !interacting ) /没有互动就执行mix.run();else /否则按命令行事while(1) /这部分显示执行情况。需要编译互动选项时用。其/余部分仍参见mix-sim.cpp源文件。4.2.3 MIXAL汇编调试器主程序 Mixal实现与MIX的实现大同小异，步骤基本一样。作用是输出包含MIX汇编语言对应机器指令的列表文件供调试使用。只看最后的输出实现。最后介绍主要的汇编部分的结构与实现。4.2.4 Assemble汇编程序汇编部分核心是语法分析器。它采用了一种递归下降的语法分析方式。对于语法中每个产生式对应着一个处理函数，还需要调用其他的函数。终结符由词法分析程序get_token()识别，而非终结符由语法分析函数expr()和prim()识别。一旦一个表达式的两个运算对象都已经知道了，就立即对这个表达式进行求值。分析器利用函数get_token()取得输入，最后一次调用get_token()得到的值可以在全局变量curr_tok中找到，C