论文部分内容阅读
【摘要】本文研究了如何在Simpletron型虚拟计算机上实现一种称为ZSimple的高级程序设计语言，讨论了该语言的语法特性和编译器的开发要点。
【关键词】虚拟计算机；ZSimple语言
文献[1]提出了一种结构清晰的虚拟计算机Simpletron，非常适合于作为范例出现在教学领域。但Simpletron计算机仅能识别其本身的机器语言SML，作为对Simpletron机功能的扩充，本文提出了在该机上开发一个编译器使用户能够用这个编译器编译一种称为ZSimple的高级程序设计语言的方案。
首先讨论一下这种高级语言ZSimple。ZSimple与流行的BASIC语言的早期版本很相似。每个ZSimple语句包含一个行号和一条ZSimple指令。行号必须以递增的顺序出现。每条指令以下面的某条ZSimple命令开始：rem，input，let，print，goto，if...goto，end。除了end命令之外，所有的命令都可以反复使用。ZSimple只能计算由运算符"+"，"-"，"*"，和"/"组成的整数表达式。这些运算符具有像在C语言中一样的优先级。可以使用圆括号来改变表达式的计算顺序。
ZSimple语言的命令
该编译器只能识别小写字母。ZSimple文件中的所有字符都应该是小写的（大写字母会导致语法错误，除非它們出现在rem语句中，因为在该语句中可以忽略大写字母）。变量的名字是单个字母。ZSimple不允许描述性的变量名，所以变量可以在注释中解释，以说明它们在程序中的作用。ZSimple只使用整型变量。ZSimple没有变量声明--仅仅在程序出现变量名的时候就可以声明变量并将其自动初始化为0。ZSimple不允许字符操作（读字符串、写字符串、比较字符串等）。如果在一个ZSimple程序中遇到了字符串（在一个不是rem的命令之后），编译器就会生成一个语法错误。
在程序执行期间，ZSimple使用条件转移语句if...goto和无条件转移语句goto来控制流程。如果在if...goto语句中条件为真，控制就会转向到程序中指定的一行。在if...goto语句中，下面的关系和相等运算符是有效的：<、>、<=、>=和!=。这些运算符有和C中一样的优先级。
下面来构建ZSimple编译器。首先，考虑如何将ZSimple程序翻译成SML并且由Simpletron模拟器执行。一个包含ZSimple程序的文件由编译器读入并转换成SML代码。SML代码将输出到磁盘的一个文件上，在文件里一条SML指令占据一行。然后将SML文件装载到Simpletron模拟器中，并且将运行结果显示在屏幕上。注意在我们前面开发的Simpletron程序是从键盘获得输入的，现在必须将其改成从文件读入以便它能运行编译器产生的程序。
ZSimple编译器执行两遍扫描，把ZSimple程序转换成SML。第一遍构建符号表（对象），在其中存储了ZSimple程序的每个行号（对象）、变量名（对象）和常量（对象）及它们的类型和在最终的SML代码中的相应位置（符号表将在下面详细讨论）。第一遍也为每个ZSimple语句产生相应的SML指令对象。如我们将会看到，如果ZSimple程序包含将控制转移到程序较后的语句时，生成的SML程序中会包含一些未完成的指令。第二遍编译器定位定位并完成那些未完成的指令，将SML程序输出到一个文件中。
第一遍扫描，编译器开始会把ZSimple程序的一个语句读入内存。必须将语句分解成独立的记号（即语句片段）来处理和编辑（标准库函数strtok可以很容易地完成这个任务）。回想一下，每条语句都是以行号开始，后跟一条语句。编译器把语句分解成记号，如果记号是一个行号、变量或常量，就将其放入符号表中。只有行号是语句中的第一个记号时才将其放入符号表中。symbolTable对象是一个用来表示程序中符号的tableEntry对象的数组。程序中出现的符号的数目没有限制。因此，某些特殊程序的symbolTable可以很大。暂时先把symbolTable设成100个元素的数组。一旦程序开始运行，可以增大或缩小它的大小。每个tableEntry对象包含3个成员。成员symbol是一个整数（记住变量名是单字符）的ASCII值、一个行号或一个常量。成员type是下面说明符号类型的字符之一: 'C'代表常量,'L'代表行号,而'V'代表变量。 成员location包含了符号所在的Simpletron内存位置（00-99）。Simpletron内存是一个100个整数的数组，SML指令和数据存储在其中。对于行号来说，location是Simpletron内存数组中的一个元素，ZSimple语句的SML指令由此开始。对于变量或常量来说，location是Simpletron内存数组中的一个元素，变量或常量存储在那里。变量和常量是在Simpletron内存的后端从后向前分配的。第一个变量或常量存储在位置99，下一个位置98，依此类推。
符号表在把ZSimple程序转换到SML的全程中都有用。我们在作业A中学习了SML指令，它是一个四位的整数，是由两部分组成（操作代码和操作数），其操作码由ZSimple中的命令来确定。例如，ZSimple命令input对应SML操作代码10（读取），而ZSimple命令print对应SML操作码11(写入)。操作数是一个包含数据的内存位置，操作码在操作数上执行它的任务（例如，操作码10从键盘读入一个值，并且把它存储在由操作数指定的内存位置上）。编译器搜索symbolTable来为每个符号确定Simpletron内存位置，所以相应的内存位置可以用来完成SML指令。
每条ZSimple语句的编辑都是基于它的命令。例如，在rem语句中的行号被插入到符号表之后，编译器将忽略语句的剩余部分，因为注释只是起说明性文档的作用。语句input、print、goto和end对应SML的read、write、branch（转移到一个指定的位置）和halt指令。包含这些ZSimple命令的语句被直接转化成SML（注意：如果goto语句要转移到的指定行涉及ZSimple程序后面的语句，那么goto语句可能包含一个未解析的参数;这个参数有时称为向前引用）。
当使用一个未解析引用编译一条goto语句时，必须对其SML指令进行标记，以指出编译器的第二遍扫描一定要完成该指令。将标记存储在有100个元素的int型flags数组中，该数组中的元素都初始化为-1。如果ZSimple程序中的行号涉及的内存位置还是未知的（也就是它不在符号表中），那么行号就存储在flags数组中与未完成指令有相同下标的元素中。未完成指令的操作数临时被设置为00。例如，一个无条件分支指令（涉及到向前引用）将译为+4000，直到编译器的第二遍扫描改变它。下面将简单描述编译器的第二遍扫描。
if...goto和let语句的编译比其他语句更复杂，它们是仅有的产生多于一条SML指令的语句。对于if...goto语句，编译器将产生代码来测试条件，并且在必要时将控制转移到其他代码行。分支转移的结果可能是未解析的引用。每个关系和相等运算符可以使用SML的零分支或负分支来模拟(或者是二者的结合)。
对于let语句，编译器将产生代码来计算由整数变量和（或）常量组成的任意复杂度的算术表达式。表达式应该使用空格把操作数和运算符分隔开。作业B1和B2展示了由中缀到后缀的转换算法和由编译器计算后缀表达式的算法。在实现自己的编译器之前，应该完成这些练习。当编译器遇到一个表达式时，它把表达式由中缀表示法转换成后缀表示法，然后计算后缀表达式。
编译器是如何产生机器语言来计算包含变量的表达式呢？后缀算法包含一个"异常指令"（hook），在那里边，编译器能生成SML指令而并不实际地计算表达式。为了使"异常指令"能在编译器中使用，必须改进后缀计算算法，使得它遇到每个符号时都会搜索符号表（可能是把该符号插入），确定该符号对应的内存位置，并把这个内存位置（而不是符号）压入堆栈。当在后缀表达式中遇到一个运算符时，在堆栈顶部的两个内存位置被弹出，并且使用该内存位置作为操作数来生成实现这个运算的机器语言。每个子表达式的结果将存储在内存中的一个临时位置上，并将其压回堆栈以便于后缀表达式的计算能够继续。当后缀计算完成时，包含计算结果的内存位置是唯一留在堆栈中的位置。该内存位置出栈，生成SML指令并把结果赋给let语句左边的变量。
第二遍扫描
编译器的第二遍扫描执行两个任务：解决任何未解析引用，并将SML代码输出到一个文件中。参数的确定步骤如下：
搜索flags数组寻找未解析引用（即值不是-1的元素）。
定位数组symbolTable中的对象，它包含了存储在flags数组中的符号(确保行号的符号类型是'L')。
把成员location内存位置插入到含有未解析引用的指令中（记住，包含未解析引用的指令操作数是00）。
重复步骤1~3，直到flags数组最后。
在确定过程完成之后，包含SML代码的整个数组将被输出到一个磁盘文件中，该文件中的每行都有一条SML指令。这个文件可以由Simpletron读取并执行（在模拟器改进为从文件中读取输入之后）。
【参考文献】
［1］．曾浩．使用C++开发教学用Simpletron虚拟计算机[J]．福建:福建电脑．2008，(6)
［2］．H．M.Deitel，P．J.Deitel．张引 等译 C++大学教程（第五版）[M]．北京：电子工业出版社，2007．
［3］．张福炎，孙志挥．信息技术教程[M]．南京大学出版社，2004．
［4］．徐君毅．單片微型计算机原理[M]．北京：人民邮电出版社，2004．
作者简介：
曾浩，（1975-－），男，江苏苏州人，南京化工职业技术学院教师，研究方向：计算机及应用
王浩然，（1981-－），男，江苏徐州人，南京化工职业技术学院助教
【关键词】虚拟计算机；ZSimple语言
文献[1]提出了一种结构清晰的虚拟计算机Simpletron，非常适合于作为范例出现在教学领域。但Simpletron计算机仅能识别其本身的机器语言SML，作为对Simpletron机功能的扩充，本文提出了在该机上开发一个编译器使用户能够用这个编译器编译一种称为ZSimple的高级程序设计语言的方案。
首先讨论一下这种高级语言ZSimple。ZSimple与流行的BASIC语言的早期版本很相似。每个ZSimple语句包含一个行号和一条ZSimple指令。行号必须以递增的顺序出现。每条指令以下面的某条ZSimple命令开始：rem，input，let，print，goto，if...goto，end。除了end命令之外，所有的命令都可以反复使用。ZSimple只能计算由运算符"+"，"-"，"*"，和"/"组成的整数表达式。这些运算符具有像在C语言中一样的优先级。可以使用圆括号来改变表达式的计算顺序。
ZSimple语言的命令
该编译器只能识别小写字母。ZSimple文件中的所有字符都应该是小写的（大写字母会导致语法错误，除非它們出现在rem语句中，因为在该语句中可以忽略大写字母）。变量的名字是单个字母。ZSimple不允许描述性的变量名，所以变量可以在注释中解释，以说明它们在程序中的作用。ZSimple只使用整型变量。ZSimple没有变量声明--仅仅在程序出现变量名的时候就可以声明变量并将其自动初始化为0。ZSimple不允许字符操作（读字符串、写字符串、比较字符串等）。如果在一个ZSimple程序中遇到了字符串（在一个不是rem的命令之后），编译器就会生成一个语法错误。
在程序执行期间，ZSimple使用条件转移语句if...goto和无条件转移语句goto来控制流程。如果在if...goto语句中条件为真，控制就会转向到程序中指定的一行。在if...goto语句中，下面的关系和相等运算符是有效的：<、>、<=、>=和!=。这些运算符有和C中一样的优先级。
下面来构建ZSimple编译器。首先，考虑如何将ZSimple程序翻译成SML并且由Simpletron模拟器执行。一个包含ZSimple程序的文件由编译器读入并转换成SML代码。SML代码将输出到磁盘的一个文件上，在文件里一条SML指令占据一行。然后将SML文件装载到Simpletron模拟器中，并且将运行结果显示在屏幕上。注意在我们前面开发的Simpletron程序是从键盘获得输入的，现在必须将其改成从文件读入以便它能运行编译器产生的程序。
ZSimple编译器执行两遍扫描，把ZSimple程序转换成SML。第一遍构建符号表（对象），在其中存储了ZSimple程序的每个行号（对象）、变量名（对象）和常量（对象）及它们的类型和在最终的SML代码中的相应位置（符号表将在下面详细讨论）。第一遍也为每个ZSimple语句产生相应的SML指令对象。如我们将会看到，如果ZSimple程序包含将控制转移到程序较后的语句时，生成的SML程序中会包含一些未完成的指令。第二遍编译器定位定位并完成那些未完成的指令，将SML程序输出到一个文件中。
第一遍扫描，编译器开始会把ZSimple程序的一个语句读入内存。必须将语句分解成独立的记号（即语句片段）来处理和编辑（标准库函数strtok可以很容易地完成这个任务）。回想一下，每条语句都是以行号开始，后跟一条语句。编译器把语句分解成记号，如果记号是一个行号、变量或常量，就将其放入符号表中。只有行号是语句中的第一个记号时才将其放入符号表中。symbolTable对象是一个用来表示程序中符号的tableEntry对象的数组。程序中出现的符号的数目没有限制。因此，某些特殊程序的symbolTable可以很大。暂时先把symbolTable设成100个元素的数组。一旦程序开始运行，可以增大或缩小它的大小。每个tableEntry对象包含3个成员。成员symbol是一个整数（记住变量名是单字符）的ASCII值、一个行号或一个常量。成员type是下面说明符号类型的字符之一: 'C'代表常量,'L'代表行号,而'V'代表变量。 成员location包含了符号所在的Simpletron内存位置（00-99）。Simpletron内存是一个100个整数的数组，SML指令和数据存储在其中。对于行号来说，location是Simpletron内存数组中的一个元素，ZSimple语句的SML指令由此开始。对于变量或常量来说，location是Simpletron内存数组中的一个元素，变量或常量存储在那里。变量和常量是在Simpletron内存的后端从后向前分配的。第一个变量或常量存储在位置99，下一个位置98，依此类推。
符号表在把ZSimple程序转换到SML的全程中都有用。我们在作业A中学习了SML指令，它是一个四位的整数，是由两部分组成（操作代码和操作数），其操作码由ZSimple中的命令来确定。例如，ZSimple命令input对应SML操作代码10（读取），而ZSimple命令print对应SML操作码11(写入)。操作数是一个包含数据的内存位置，操作码在操作数上执行它的任务（例如，操作码10从键盘读入一个值，并且把它存储在由操作数指定的内存位置上）。编译器搜索symbolTable来为每个符号确定Simpletron内存位置，所以相应的内存位置可以用来完成SML指令。
每条ZSimple语句的编辑都是基于它的命令。例如，在rem语句中的行号被插入到符号表之后，编译器将忽略语句的剩余部分，因为注释只是起说明性文档的作用。语句input、print、goto和end对应SML的read、write、branch（转移到一个指定的位置）和halt指令。包含这些ZSimple命令的语句被直接转化成SML（注意：如果goto语句要转移到的指定行涉及ZSimple程序后面的语句，那么goto语句可能包含一个未解析的参数;这个参数有时称为向前引用）。
当使用一个未解析引用编译一条goto语句时，必须对其SML指令进行标记，以指出编译器的第二遍扫描一定要完成该指令。将标记存储在有100个元素的int型flags数组中，该数组中的元素都初始化为-1。如果ZSimple程序中的行号涉及的内存位置还是未知的（也就是它不在符号表中），那么行号就存储在flags数组中与未完成指令有相同下标的元素中。未完成指令的操作数临时被设置为00。例如，一个无条件分支指令（涉及到向前引用）将译为+4000，直到编译器的第二遍扫描改变它。下面将简单描述编译器的第二遍扫描。
if...goto和let语句的编译比其他语句更复杂，它们是仅有的产生多于一条SML指令的语句。对于if...goto语句，编译器将产生代码来测试条件，并且在必要时将控制转移到其他代码行。分支转移的结果可能是未解析的引用。每个关系和相等运算符可以使用SML的零分支或负分支来模拟(或者是二者的结合)。
对于let语句，编译器将产生代码来计算由整数变量和（或）常量组成的任意复杂度的算术表达式。表达式应该使用空格把操作数和运算符分隔开。作业B1和B2展示了由中缀到后缀的转换算法和由编译器计算后缀表达式的算法。在实现自己的编译器之前，应该完成这些练习。当编译器遇到一个表达式时，它把表达式由中缀表示法转换成后缀表示法，然后计算后缀表达式。
编译器是如何产生机器语言来计算包含变量的表达式呢？后缀算法包含一个"异常指令"（hook），在那里边，编译器能生成SML指令而并不实际地计算表达式。为了使"异常指令"能在编译器中使用，必须改进后缀计算算法，使得它遇到每个符号时都会搜索符号表（可能是把该符号插入），确定该符号对应的内存位置，并把这个内存位置（而不是符号）压入堆栈。当在后缀表达式中遇到一个运算符时，在堆栈顶部的两个内存位置被弹出，并且使用该内存位置作为操作数来生成实现这个运算的机器语言。每个子表达式的结果将存储在内存中的一个临时位置上，并将其压回堆栈以便于后缀表达式的计算能够继续。当后缀计算完成时，包含计算结果的内存位置是唯一留在堆栈中的位置。该内存位置出栈，生成SML指令并把结果赋给let语句左边的变量。
第二遍扫描
编译器的第二遍扫描执行两个任务：解决任何未解析引用，并将SML代码输出到一个文件中。参数的确定步骤如下：
搜索flags数组寻找未解析引用（即值不是-1的元素）。
定位数组symbolTable中的对象，它包含了存储在flags数组中的符号(确保行号的符号类型是'L')。
把成员location内存位置插入到含有未解析引用的指令中（记住，包含未解析引用的指令操作数是00）。
重复步骤1~3，直到flags数组最后。
在确定过程完成之后，包含SML代码的整个数组将被输出到一个磁盘文件中，该文件中的每行都有一条SML指令。这个文件可以由Simpletron读取并执行（在模拟器改进为从文件中读取输入之后）。
【参考文献】
［1］．曾浩．使用C++开发教学用Simpletron虚拟计算机[J]．福建:福建电脑．2008，(6)
［2］．H．M.Deitel，P．J.Deitel．张引 等译 C++大学教程（第五版）[M]．北京：电子工业出版社，2007．
［3］．张福炎，孙志挥．信息技术教程[M]．南京大学出版社，2004．
［4］．徐君毅．單片微型计算机原理[M]．北京：人民邮电出版社，2004．
作者简介：
曾浩，（1975-－），男，江苏苏州人，南京化工职业技术学院教师，研究方向：计算机及应用
王浩然，（1981-－），男，江苏徐州人，南京化工职业技术学院助教