一種多結(jié)構(gòu)信息的匯編程序自動構(gòu)造方法

一種多結(jié)構(gòu)信息的匯編程序自動構(gòu)造方法

0絕對地址的生成聯(lián)合文本通常使用絕對地址訪問內(nèi)存單元或轉(zhuǎn)移地址，這對構(gòu)建集類化程序帶來了很大困難。在源程序編寫過程中,通常將轉(zhuǎn)移地址暫缺,待程序基本定型后,用手工計(jì)算出目標(biāo)地址,然后將轉(zhuǎn)移語句補(bǔ)充完整。由于在源程序中存在絕對地址,增加或減少一條匯編語句,可能引起源程序修改的連續(xù)反應(yīng)。文獻(xiàn)中雖然提出了將語法制導(dǎo)翻譯用于匯編程序自動構(gòu)造的方法,但在該方法中并沒有考慮標(biāo)號和變量的使用,用戶只能使用絕對地址來進(jìn)行編程。本文提出了一個(gè)可使用標(biāo)號和變量的匯編程序自動構(gòu)造方法,自動生成的匯編程序允許用戶使用標(biāo)號和變量進(jìn)行編程,這樣避免了源程序中絕對地址的出現(xiàn)。1變址尋址模塊以模型機(jī)為例討論構(gòu)造方法。除第7點(diǎn)外,由于在文獻(xiàn)中有較為詳細(xì)的敘述,故模型機(jī)的介紹簡略一些。虛擬模型機(jī)硬件配置如下:(1)內(nèi)存共計(jì)256*256個(gè)單元,地址范圍為0-65535。一個(gè)單元為1個(gè)字,1個(gè)字有2個(gè)字節(jié)組成。(2)內(nèi)存單元可存放數(shù)據(jù),也可存放指令。若存放指令,高4位(12-15)為操作符、低12位(0-11)用于描述地址。第10、11位表征第一地址,第一地址只能是寄存器,3-0分別表示R3-R0。第8、9位用于表征第二地址尋址方式,它們是直接地址、寄存器、直接數(shù)和變址尋址?！?0:直接地址尋址(M),第二操作數(shù)在內(nèi)存低地址區(qū)域,地址范圍為0x00-0xFF,用指令的7-0位表示;·01:寄存器尋址,指令的第3-0位的值為0-3,分別表示R0-R3。指令的7-4位的值或?yàn)?或?yàn)?,0表示寄存器直接尋址(Ri),第二操作數(shù)在寄存器Ri中;1表示寄存器間接尋址(@Ri),在寄存器Ri中存放的是第二操作數(shù)地址;·10:直接數(shù)(D),指令的0-7位表示直接數(shù),數(shù)值范圍為0x00-0xFF;·11:以C*256為基址、R3為位移的變址尋址(C[R3],0≤C≤0xFF),指令的7-0位表示C。C相當(dāng)于頁號,R3相當(dāng)于頁內(nèi)位移。當(dāng)R3用于變址尋址時(shí),R3僅使用低8位,地址計(jì)算公式為:C*256+R3&0xFF。(3)系統(tǒng)具有4個(gè)通用寄存器(2字節(jié)),分別標(biāo)記為R0-R3,一個(gè)標(biāo)志寄存器SystemFlagReg和一個(gè)系統(tǒng)棧頂指示器SystemStackTopReg。SystemFlagReg用于保存Cmp指令的比較結(jié)果,R3還可用作變址器。SystemStackTopReg的初值為0,系統(tǒng)堆棧從內(nèi)存地址66535開始(0-1=65535)。執(zhí)行CALL指令時(shí),SystemStackTopReg的值減1,系統(tǒng)將斷點(diǎn)存入SystemStackTopReg所指的內(nèi)存單元中(進(jìn)棧),轉(zhuǎn)移目標(biāo)由CALL指令的第二地址給出;當(dāng)執(zhí)行RET指令時(shí),從SystemStackTopReg所指的單元獲得返回地址,系統(tǒng)將SystemStackTopReg的值增1(退棧)。(4)機(jī)器指令的操作符(12-15位)描述如下:(5)Read和Write指令無第二地址;Call、Jmp、JmpNeg、JmpPos和JmpZero指令無第一地址;Ret和Halt指令既無第一地址,也無第二地址。(6)機(jī)器語言程序從地址256開始存放并執(zhí)行。轉(zhuǎn)移匯編語句經(jīng)翻譯后,通常由若干條指令來實(shí)現(xiàn),其中轉(zhuǎn)移指令必然使用變址尋址。由于變址尋址需使用寄存器R3,而R3在用戶程序中又可用作通用寄存器。為了使得R3中的內(nèi)容在翻譯過程中不致丟失,所以在匯編程序中使用內(nèi)存單元255來保存R3的值。第0頁的其余單元(0-254)可用來存放用戶定義的變量值,用戶最多可在源程序中定義255個(gè)變量。當(dāng)然,用戶也可以不定義變量,使用直接地址尋址方式來訪問第0頁的內(nèi)存單元(0-254)。用戶編程仍為0地址空間,并非從地址256開始,這一點(diǎn)由匯編程序內(nèi)部來實(shí)現(xiàn)地址的偏移定位。上述模型機(jī)器已用軟件虛擬實(shí)現(xiàn)。2匯編語言的文法描述根據(jù)上述模型機(jī)器的系統(tǒng)結(jié)構(gòu)設(shè)計(jì)匯編語言,考慮可使用標(biāo)號和變量,匯編語言的語法結(jié)構(gòu)可用上下文無關(guān)文法定義如下:在上述文法中,0地址指令的操作符用w表示(RET和HALT),A型一地址指令的操作符用x表示(例READ),二地址指令的操作符用y表示(例LOAD),B型一地址指令的操作符用z來表示(例CALL)。寄存器R0-R3用r表示,十六進(jìn)制數(shù)字用d來表示。因變址尋址約定使用R3,故產(chǎn)生式S::=d[r]、S::=d1d0[r]中r的語義值無作用。在產(chǎn)生式尾部添加[r],主要是為了在語法分析時(shí)能區(qū)別直接數(shù)(立即尋址)和變址尋址。標(biāo)號和變量名可直接使用,無需顯式說明。根據(jù)上述文法構(gòu)造SLR(1)分析表,SLR(1)分析表如圖1所示。分析表規(guī)模為31*17,由于界面有限,分析表沒有顯示完整。根據(jù)上述文法,匯編語句i:i:i:yr,mdd是合法句子,可能沒有一個(gè)程序員會這樣使用標(biāo)號。3標(biāo)記的構(gòu)造和分析匯編語言源程序可以用小寫字母書寫,也可以用大寫字母書寫。將空格、TAB和換行視為界符,允許單詞之間有多余的界符。操作符和第一地址之間至少要用一個(gè)界符分隔,第一地址和第二地址之間用逗號分隔。注釋用單撇號(’)引領(lǐng),至行尾結(jié)束。詞法分析器首先將源程序從文件讀入內(nèi)存。在讀入過程中,將小寫字母改為大寫字母,去除注釋,并在程序尾部添加‘#’。單詞二元式編碼如下所示:匯編語言語句的詞法較簡單,共有44個(gè)單詞。除操作符、寄存器和標(biāo)識符外,其余均為單字符單詞。標(biāo)識符是以字母開始的數(shù)字字母串,約定長度≤8,標(biāo)識符不能和操作符、寄存器同名?？紤]使用十六進(jìn)制數(shù)和直接地址尋址方式,標(biāo)識符首字符不能是A、B、C、D、E、F和M之一。構(gòu)造可采用手工方法,也可采用自動構(gòu)造方法。詞法分析結(jié)果(單詞二元式)保存于文件lex＿r.txt中。變量名的處理可放在詞法分析階段進(jìn)行,包括地址分配。標(biāo)號的處理分二階段進(jìn)行,在詞法分析階段建立符號表,符號表用來記錄標(biāo)號和變量名。在目標(biāo)代碼生成后,增加一個(gè)連接處理(LINK),用于處理標(biāo)號定義和標(biāo)號引用語句的一對多翻譯。由于標(biāo)號可能存在先引用后定義的情況,詞法分析分二遍掃描,第一遍為標(biāo)號定義的處理(如表1所示),第二遍才是真正意義上的詞法分析(如圖2所示)。在第一遍掃描中,找出所有以字母開始的并且以冒號結(jié)尾的字符串和由它引領(lǐng)的匯編語句編號,將標(biāo)號填入符號表。語句編號可利用匯編語句的操作符(例Mul、Read等)找出。例計(jì)算5的階乘的匯編語言源程序如下所示:在第二次掃描中,根據(jù)符號串“J1”和“L99”查符號表,獲得編號后,生成單詞二元式。例若為標(biāo)號定義,實(shí)際上”J1”已完成歷史使命,語義分析時(shí)并不使用標(biāo)號i的語義值。為了方便程序處理,考慮二元式的完整性,仍予以填寫。若為標(biāo)號引用,除生成單詞二元式,例JmpL99譯成(z,12)(i,261),還需填寫引用點(diǎn)鏈,記錄引用點(diǎn)的語句編號。若標(biāo)識符在表中未找到,則認(rèn)定它為變量名。將其填入符號表中,分配內(nèi)存單元,并生成單詞二元式。若變量名第二次出現(xiàn),則可直接獲得地址,生成單詞二元式。例:計(jì)算5的階乘的源程序詞法分析結(jié)果如圖3所示。只要將符號表略加修改,詞法分析也可采用一遍掃描方式完成。在處理標(biāo)識符時(shí),除將單詞二元式(i,-1)填入單詞二元式表、在符號表記錄其所在的語句編號外,還需在符號表中記錄標(biāo)識符二元式在二元式表中的位置,以便回填。在詞法分析全部完成后,進(jìn)行變量內(nèi)存分配(顯然標(biāo)號已定位),可根據(jù)符號表對二元式表中指定單元進(jìn)行修改。4生成的轉(zhuǎn)移指令s根據(jù)匯編程序的文法,語義子程序設(shè)計(jì)如下:說明:·當(dāng)i:I(1)歸約為I,指令I(lǐng)(1)的語義值已輸出,故產(chǎn)生式I→i:I(1)的語義子程序?yàn)榭??！val表示單詞標(biāo)識符的值。當(dāng)i歸約為S,若ival>255,說明它是標(biāo)號的引用。由于轉(zhuǎn)移地址均大于255,此時(shí)應(yīng)使用變址尋址方式,需使用變址器R3,這樣使得一條轉(zhuǎn)移指令將對應(yīng)多條指令。在語義分析時(shí),仍采用一對一的翻譯方式,保留操作碼和尋址方式,低8位清0,詳見圖4中指令b300和c300。在連接階段(LINK),根據(jù)符號表進(jìn)行一對多的翻譯,并將轉(zhuǎn)移指令補(bǔ)充完整。若ival<255,則說明是變量,可采用直接地址尋址方式進(jìn)行譯碼?！ふZ法/語義分析器的輸入為單詞二元式(文件Lex＿r.txt),輸出為待定位的機(jī)器碼(文件par＿r.txt)。上述樣本程序的語法/語義分析結(jié)果如圖4所示。5編碼編碼的復(fù)制目標(biāo)代碼的最終定位是依據(jù)符號表和待定位的目標(biāo)代碼來實(shí)現(xiàn)的。由于在源程序中可能存在標(biāo)號重復(fù)定義,即有一個(gè)以上的標(biāo)號引領(lǐng)同一個(gè)匯編語句。所以,首先要消除符號表中的重復(fù)定義,包括刪除未引用的標(biāo)號定義,以方便后續(xù)處理,經(jīng)合并處理的符號表如圖5所示。轉(zhuǎn)移指令需譯成4條指令,例JmpNegJ1譯碼如下:相當(dāng)于在標(biāo)號定義(J1:)前一句(JmpL99)之后增加了2條指令,且標(biāo)號定義(標(biāo)號入口)應(yīng)由原Addr0,1改為LoadR3M255。在順序執(zhí)行時(shí),Store和Load指令如同虛設(shè);當(dāng)執(zhí)行轉(zhuǎn)移切入時(shí),Load指令將起重要作用。由于增加了指令,使得語句位置發(fā)生了變化?？衫蒙鲜鲆?guī)律,建立原編號和新編號的對照表,上述樣本程序的對照表如表2所示。由于程序第一句可能是轉(zhuǎn)移語句或是標(biāo)號定義引領(lǐng)的語句,故設(shè)置假頭,下標(biāo)為-1或65535(0-1=65535)。新編號的計(jì)算公式:根據(jù)表2,將表3中原編號處的代碼復(fù)制到表4對應(yīng)的新編號處。例,表3中原編號第0句“LoadR1,5”的機(jī)器碼“2605”復(fù)制到表4新編號第0句,表3中原編號第4句“JmpL9”的機(jī)器碼“b300”復(fù)制到表4新編號第7句,表3中原編號第10句“Halt”的機(jī)器碼“f000”復(fù)制到表4新編號第18句。在表4中尚有一些空白,空白部分將根據(jù)符號表進(jìn)行填補(bǔ)。盡管有些單元已有指令,但仍需根據(jù)符號表將其補(bǔ)充完整,并作次序調(diào)整(例第16句的c300)。根據(jù)符號表,可知標(biāo)號定義位置為261,相對地址為261-256=5,顯然它的上一句編號為4。第4句的新編號為7,那么在第8句(7+1)填入“StoreR3,Mff”機(jī)器碼“3cff”、在第9句(7+2)填入“LoadR3,Mff”機(jī)器碼“2cff”,并且新的標(biāo)號定義點(diǎn)為9(頁號=0,頁內(nèi)相對位移=9)。根據(jù)符號表,可知標(biāo)號第1個(gè)引用點(diǎn)是264,相對地址為264-256=8。第8句的新編號為16,那么在第13句(16-3)填入“StoreR3,Mff”機(jī)器碼“3cff”、在第14句(16-2)填入“LoadR3,9”機(jī)器碼“2eff”、在第15句(16-1)填入“JmpNeg0[R3]”機(jī)器碼“c300”、在第16句(16-0)填入“LoadR3,Mff”機(jī)器碼“2cff”。另一個(gè)標(biāo)號引用點(diǎn)260處理相同,不再重復(fù)。上述算法主要考慮在源程序中可能存在標(biāo)號引領(lǐng)轉(zhuǎn)移語句的情況,例L1:JmpL2。標(biāo)號定義的處理,一定要以“標(biāo)號定義”上一句語句的新編號為基準(zhǔn);轉(zhuǎn)移語句的處理,一定要以“轉(zhuǎn)移語句”的新編號為基準(zhǔn)。顯然在“JmpNeg”指令之后添加“LoadR3,M255”指令是完全必要的,而在“Jmp”指令之后添加“LoadR3,M255”指令是多余的,該指令永遠(yuǎn)不可能執(zhí)行到。只要稍加判斷,就可避免不必要的指令添加。考慮使用直接地址譯碼較為方便,故變量存儲區(qū)域設(shè)定在第0頁,這樣可將含有變量名的匯編語句譯成一條機(jī)器指令。實(shí)質(zhì)上變量存儲區(qū)域可設(shè)定在內(nèi)存高地址任何區(qū)域,只要不和目標(biāo)程序存放區(qū)域和系統(tǒng)堆棧區(qū)域發(fā)生沖突即可,例第254頁。由于需采用變址訪問,含有變量名的一條匯編語句將對應(yīng)4條機(jī)器指令。可參照轉(zhuǎn)移指令的翻譯方法,這里不再詳述。連接程序的輸入為待定位的機(jī)器碼(文件par＿r.txt),輸出為已定位的機(jī)器碼(文件link＿r.txt)。虛擬機(jī)從文件link＿r.txt讀入已定位的機(jī)器碼解釋執(zhí)行。6測試測試程序和經(jīng)匯編生成的目標(biāo)代碼如圖6、圖7所示,中間處理結(jié)果如圖3、圖4所示,虛擬機(jī)執(zhí)行結(jié)果略。7基于lr-b語法/語義分析中的編碼/轉(zhuǎn)位分析借助于一個(gè)虛擬計(jì)算機(jī)模型,闡述了一個(gè)可使用標(biāo)號和變量的匯編程序自動構(gòu)造方法,基本解決了宏匯編器自動構(gòu)造的難點(diǎn)?？紤]標(biāo)號可能存在先引用后定義的情況,詞法分析分二遍進(jìn)行,第一遍主要處理標(biāo)號定