一种多结构信息的汇编程序自动构造方法

一种多结构信息的汇编程序自动构造方法

0绝对地址的生成联合文本通常使用绝对地址访问内存单元或转移地址，这对构建集类化程序带来了很大困难。在源程序编写过程中,通常将转移地址暂缺,待程序基本定型后,用手工计算出目标地址,然后将转移语句补充完整。由于在源程序中存在绝对地址,增加或减少一条汇编语句,可能引起源程序修改的连续反应。文献中虽然提出了将语法制导翻译用于汇编程序自动构造的方法,但在该方法中并没有考虑标号和变量的使用,用户只能使用绝对地址来进行编程。本文提出了一个可使用标号和变量的汇编程序自动构造方法,自动生成的汇编程序允许用户使用标号和变量进行编程,这样避免了源程序中绝对地址的出现。1变址寻址模块以模型机为例讨论构造方法。除第7点外,由于在文献中有较为详细的叙述,故模型机的介绍简略一些。虚拟模型机硬件配置如下:(1)内存共计256*256个单元,地址范围为0-65535。一个单元为1个字,1个字有2个字节组成。(2)内存单元可存放数据,也可存放指令。若存放指令,高4位(12-15)为操作符、低12位(0-11)用于描述地址。第10、11位表征第一地址,第一地址只能是寄存器,3-0分别表示R3-R0。第8、9位用于表征第二地址寻址方式,它们是直接地址、寄存器、直接数和变址寻址。·00:直接地址寻址(M),第二操作数在内存低地址区域,地址范围为0x00-0xFF,用指令的7-0位表示;·01:寄存器寻址,指令的第3-0位的值为0-3,分别表示R0-R3。指令的7-4位的值或为0或为1,0表示寄存器直接寻址(Ri),第二操作数在寄存器Ri中;1表示寄存器间接寻址(@Ri),在寄存器Ri中存放的是第二操作数地址;·10:直接数(D),指令的0-7位表示直接数,数值范围为0x00-0xFF;·11:以C*256为基址、R3为位移的变址寻址(C[R3],0≤C≤0xFF),指令的7-0位表示C。C相当于页号,R3相当于页内位移。当R3用于变址寻址时,R3仅使用低8位,地址计算公式为:C*256+R3&0xFF。(3)系统具有4个通用寄存器(2字节),分别标记为R0-R3,一个标志寄存器SystemFlagReg和一个系统栈顶指示器SystemStackTopReg。SystemFlagReg用于保存Cmp指令的比较结果,R3还可用作变址器。SystemStackTopReg的初值为0,系统堆栈从内存地址66535开始(0-1=65535)。执行CALL指令时,SystemStackTopReg的值减1,系统将断点存入SystemStackTopReg所指的内存单元中(进栈),转移目标由CALL指令的第二地址给出;当执行RET指令时,从SystemStackTopReg所指的单元获得返回地址,系统将SystemStackTopReg的值增1(退栈)。(4)机器指令的操作符(12-15位)描述如下:(5)Read和Write指令无第二地址;Call、Jmp、JmpNeg、JmpPos和JmpZero指令无第一地址;Ret和Halt指令既无第一地址,也无第二地址。(6)机器语言程序从地址256开始存放并执行。转移汇编语句经翻译后,通常由若干条指令来实现,其中转移指令必然使用变址寻址。由于变址寻址需使用寄存器R3,而R3在用户程序中又可用作通用寄存器。为了使得R3中的内容在翻译过程中不致丢失,所以在汇编程序中使用内存单元255来保存R3的值。第0页的其余单元(0-254)可用来存放用户定义的变量值,用户最多可在源程序中定义255个变量。当然,用户也可以不定义变量,使用直接地址寻址方式来访问第0页的内存单元(0-254)。用户编程仍为0地址空间,并非从地址256开始,这一点由汇编程序内部来实现地址的偏移定位。上述模型机器已用软件虚拟实现。2汇编语言的文法描述根据上述模型机器的系统结构设计汇编语言,考虑可使用标号和变量,汇编语言的语法结构可用上下文无关文法定义如下:在上述文法中,0地址指令的操作符用w表示(RET和HALT),A型一地址指令的操作符用x表示(例READ),二地址指令的操作符用y表示(例LOAD),B型一地址指令的操作符用z来表示(例CALL)。寄存器R0-R3用r表示,十六进制数字用d来表示。因变址寻址约定使用R3,故产生式S::=d[r]、S::=d1d0[r]中r的语义值无作用。在产生式尾部添加[r],主要是为了在语法分析时能区别直接数(立即寻址)和变址寻址。标号和变量名可直接使用,无需显式说明。根据上述文法构造SLR(1)分析表,SLR(1)分析表如图1所示。分析表规模为31*17,由于界面有限,分析表没有显示完整。根据上述文法,汇编语句i:i:i:yr,mdd是合法句子,可能没有一个程序员会这样使用标号。3标记的构造和分析汇编语言源程序可以用小写字母书写,也可以用大写字母书写。将空格、TAB和换行视为界符,允许单词之间有多余的界符。操作符和第一地址之间至少要用一个界符分隔,第一地址和第二地址之间用逗号分隔。注释用单撇号(’)引领,至行尾结束。词法分析器首先将源程序从文件读入内存。在读入过程中,将小写字母改为大写字母,去除注释,并在程序尾部添加‘#’。单词二元式编码如下所示:汇编语言语句的词法较简单,共有44个单词。除操作符、寄存器和标识符外,其余均为单字符单词。标识符是以字母开始的数字字母串,约定长度≤8,标识符不能和操作符、寄存器同名。考虑使用十六进制数和直接地址寻址方式,标识符首字符不能是A、B、C、D、E、F和M之一。构造可采用手工方法,也可采用自动构造方法。词法分析结果(单词二元式)保存于文件lex＿r.txt中。变量名的处理可放在词法分析阶段进行,包括地址分配。标号的处理分二阶段进行,在词法分析阶段建立符号表,符号表用来记录标号和变量名。在目标代码生成后,增加一个连接处理(LINK),用于处理标号定义和标号引用语句的一对多翻译。由于标号可能存在先引用后定义的情况,词法分析分二遍扫描,第一遍为标号定义的处理(如表1所示),第二遍才是真正意义上的词法分析(如图2所示)。在第一遍扫描中,找出所有以字母开始的并且以冒号结尾的字符串和由它引领的汇编语句编号,将标号填入符号表。语句编号可利用汇编语句的操作符(例Mul、Read等)找出。例计算5的阶乘的汇编语言源程序如下所示:在第二次扫描中,根据符号串“J1”和“L99”查符号表,获得编号后,生成单词二元式。例若为标号定义,实际上”J1”已完成历史使命,语义分析时并不使用标号i的语义值。为了方便程序处理,考虑二元式的完整性,仍予以填写。若为标号引用,除生成单词二元式,例JmpL99译成(z,12)(i,261),还需填写引用点链,记录引用点的语句编号。若标识符在表中未找到,则认定它为变量名。将其填入符号表中,分配内存单元,并生成单词二元式。若变量名第二次出现,则可直接获得地址,生成单词二元式。例:计算5的阶乘的源程序词法分析结果如图3所示。只要将符号表略加修改,词法分析也可采用一遍扫描方式完成。在处理标识符时,除将单词二元式(i,-1)填入单词二元式表、在符号表记录其所在的语句编号外,还需在符号表中记录标识符二元式在二元式表中的位置,以便回填。在词法分析全部完成后,进行变量内存分配(显然标号已定位),可根据符号表对二元式表中指定单元进行修改。4生成的转移指令s根据汇编程序的文法,语义子程序设计如下:说明:·当i:I(1)归约为I,指令I(1)的语义值已输出,故产生式I→i:I(1)的语义子程序为空。·ival表示单词标识符的值。当i归约为S,若ival>255,说明它是标号的引用。由于转移地址均大于255,此时应使用变址寻址方式,需使用变址器R3,这样使得一条转移指令将对应多条指令。在语义分析时,仍采用一对一的翻译方式,保留操作码和寻址方式,低8位清0,详见图4中指令b300和c300。在连接阶段(LINK),根据符号表进行一对多的翻译,并将转移指令补充完整。若ival<255,则说明是变量,可采用直接地址寻址方式进行译码。·语法/语义分析器的输入为单词二元式(文件Lex＿r.txt),输出为待定位的机器码(文件par＿r.txt)。上述样本程序的语法/语义分析结果如图4所示。5编码编码的复制目标代码的最终定位是依据符号表和待定位的目标代码来实现的。由于在源程序中可能存在标号重复定义,即有一个以上的标号引领同一个汇编语句。所以,首先要消除符号表中的重复定义,包括删除未引用的标号定义,以方便后续处理,经合并处理的符号表如图5所示。转移指令需译成4条指令,例JmpNegJ1译码如下:相当于在标号定义(J1:)前一句(JmpL99)之后增加了2条指令,且标号定义(标号入口)应由原Addr0,1改为LoadR3M255。在顺序执行时,Store和Load指令如同虚设;当执行转移切入时,Load指令将起重要作用。由于增加了指令,使得语句位置发生了变化。可利用上述规律,建立原编号和新编号的对照表,上述样本程序的对照表如表2所示。由于程序第一句可能是转移语句或是标号定义引领的语句,故设置假头,下标为-1或65535(0-1=65535)。新编号的计算公式:根据表2,将表3中原编号处的代码复制到表4对应的新编号处。例,表3中原编号第0句“LoadR1,5”的机器码“2605”复制到表4新编号第0句,表3中原编号第4句“JmpL9”的机器码“b300”复制到表4新编号第7句,表3中原编号第10句“Halt”的机器码“f000”复制到表4新编号第18句。在表4中尚有一些空白,空白部分将根据符号表进行填补。尽管有些单元已有指令,但仍需根据符号表将其补充完整,并作次序调整(例第16句的c300)。根据符号表,可知标号定义位置为261,相对地址为261-256=5,显然它的上一句编号为4。第4句的新编号为7,那么在第8句(7+1)填入“StoreR3,Mff”机器码“3cff”、在第9句(7+2)填入“LoadR3,Mff”机器码“2cff”,并且新的标号定义点为9(页号=0,页内相对位移=9)。根据符号表,可知标号第1个引用点是264,相对地址为264-256=8。第8句的新编号为16,那么在第13句(16-3)填入“StoreR3,Mff”机器码“3cff”、在第14句(16-2)填入“LoadR3,9”机器码“2eff”、在第15句(16-1)填入“JmpNeg0[R3]”机器码“c300”、在第16句(16-0)填入“LoadR3,Mff”机器码“2cff”。另一个标号引用点260处理相同,不再重复。上述算法主要考虑在源程序中可能存在标号引领转移语句的情况,例L1:JmpL2。标号定义的处理,一定要以“标号定义”上一句语句的新编号为基准;转移语句的处理,一定要以“转移语句”的新编号为基准。显然在“JmpNeg”指令之后添加“LoadR3,M255”指令是完全必要的,而在“Jmp”指令之后添加“LoadR3,M255”指令是多余的,该指令永远不可能执行到。只要稍加判断,就可避免不必要的指令添加。考虑使用直接地址译码较为方便,故变量存储区域设定在第0页,这样可将含有变量名的汇编语句译成一条机器指令。实质上变量存储区域可设定在内存高地址任何区域,只要不和目标程序存放区域和系统堆栈区域发生冲突即可,例第254页。由于需采用变址访问,含有变量名的一条汇编语句将对应4条机器指令。可参照转移指令的翻译方法,这里不再详述。连接程序的输入为待定位的机器码(文件par＿r.txt),输出为已定位的机器码(文件link＿r.txt)。虚拟机从文件link＿r.txt读入已定位的机器码解释执行。6测试测试程序和经汇编生成的目标代码如图6、图7所示,中间处理结果如图3、图4所示,虚拟机执行结果略。7基于lr-b语法/语义分析中的编码/转位分析借助于一个虚拟计算机模型,阐述了一个可使用标号和变量的汇编程序自动构造方法,基本解决了宏汇编器自动构造的难点。考虑标号可能存在先引用后定义的情况,词法分析分二遍进行,第一遍主要处理标号定