英昌盛

(吉林師范大學(xué) 計(jì)算機(jī)學(xué)院，吉林 四平 136000)

0 引言

表達(dá)式的分析、求值等運(yùn)算是編譯程序中的一個(gè)關(guān)鍵部分。研究翻譯程序的工作原理和工作流程，對(duì)于教師的教學(xué)和研究，對(duì)于學(xué)生理論聯(lián)系實(shí)際都具有較為實(shí)用的意義和價(jià)值。

1 系統(tǒng)設(shè)計(jì)及概要設(shè)計(jì)

1.1 運(yùn)算符和數(shù)據(jù)類(lèi)型的支持

系統(tǒng)支持算術(shù)運(yùn)算、關(guān)系運(yùn)算和邏輯運(yùn)算。算術(shù)運(yùn)算符有包括:()、+、-、*、/、^(乘方)，其中^為新增運(yùn)算符。邏輯運(yùn)算符包括:!、＆(邏輯與為化簡(jiǎn)運(yùn)算符)、|(邏輯或?yàn)榛?jiǎn)運(yùn)算符)。關(guān)系運(yùn)算符包括:＞、＞=、==、_(負(fù)號(hào))。

系統(tǒng)支持整數(shù)及浮點(diǎn)數(shù)。在進(jìn)行算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算時(shí)運(yùn)算規(guī)則和結(jié)合性基本同C語(yǔ)言中相應(yīng)的規(guī)則一致。

1.2 數(shù)據(jù)結(jié)構(gòu)

用戶輸入的數(shù)據(jù)是隨機(jī)的，同時(shí)程序處理數(shù)據(jù)時(shí)用棧這種結(jié)構(gòu)實(shí)現(xiàn)較好，所以系統(tǒng)采用兩個(gè)鏈棧［1］來(lái)保存運(yùn)算量和運(yùn)算符。因輸入的變量個(gè)數(shù)無(wú)法確定，系統(tǒng)采用動(dòng)態(tài)生成鏈表［2］來(lái)存儲(chǔ)。

2 系統(tǒng)實(shí)現(xiàn)

2.1 算符優(yōu)先級(jí)及數(shù)據(jù)結(jié)構(gòu)

系統(tǒng)使用結(jié)構(gòu)體數(shù)組charindex［］和OPTable［］保存運(yùn)算符及其對(duì)應(yīng)的優(yōu)先級(jí)。charindex［］用來(lái)存放運(yùn)算符和該運(yùn)算符的棧外、內(nèi)優(yōu)先級(jí)在OPTable［］中的下標(biāo)。charindex［］結(jié)構(gòu)體數(shù)組的op域用來(lái)保存第i個(gè)運(yùn)算符，index域用來(lái)存放第i個(gè)運(yùn)算符在OPTable［］結(jié)構(gòu)體數(shù)組相應(yīng)元素中的下標(biāo)，如表1［3］所示。

表1 運(yùn)算符及其棧內(nèi)、外優(yōu)先級(jí)

OPTable［］的opri域和ipri域分別表示charindex［］數(shù)組中第i個(gè)運(yùn)算符對(duì)應(yīng)的棧外、棧內(nèi)優(yōu)先級(jí)。為方便運(yùn)算和節(jié)省棧的域，OPTable［］的元素個(gè)數(shù)較charindex［］的元素個(gè)數(shù)多三項(xiàng)。系統(tǒng)只用一個(gè)整數(shù)表示一個(gè)運(yùn)算符，而＞=，==，＜=等運(yùn)算符都是兩個(gè)字符組成的字符串，不便于統(tǒng)一處理，經(jīng)研究發(fā)現(xiàn)完全可以用＜、=、＞三個(gè)運(yùn)算符的在OPTable［］中的下標(biāo)值分別加1來(lái)表示＜=、==、＞=在OPTable［］中的下標(biāo)值，因而＜、=、＞三者之間的索引值按2遞增。具體定義如下:

2.2 處理規(guī)則

(1)初始化時(shí)在運(yùn)算棧內(nèi)壓入一個(gè)#;同時(shí)#作為表達(dá)式結(jié)束標(biāo)記。

(2)若棧外運(yùn)算符的棧外優(yōu)先級(jí)比棧頂運(yùn)算符的棧內(nèi)優(yōu)先級(jí)高，則棧外運(yùn)算符入棧;否則棧頂運(yùn)算符退棧，并取出相應(yīng)個(gè)數(shù)的運(yùn)算量進(jìn)行運(yùn)算，把運(yùn)算結(jié)果壓回運(yùn)算量棧，直到棧外運(yùn)算符的棧外優(yōu)先級(jí)比棧頂運(yùn)算符的棧內(nèi)優(yōu)先級(jí)高為止，將棧外運(yùn)算符入棧;若棧外運(yùn)算符的棧外優(yōu)先級(jí)和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級(jí)相等，則棧頂運(yùn)算符一定為’(’，此時(shí)為()的情況，作出錯(cuò)處理。

(3)運(yùn)算符退棧時(shí)，若遇到棧外運(yùn)算符的棧外優(yōu)先級(jí)和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級(jí)相等情況(此時(shí)一定是括號(hào))，則彈出棧頂運(yùn)算符，拋棄棧外運(yùn)算符。

(4)若運(yùn)算完畢運(yùn)算量棧只剩一個(gè)運(yùn)算量、符號(hào)?？?，則運(yùn)算結(jié)果正確，其他情況則為錯(cuò)誤。

(5)若 a＞0，則 -a=a*(-1)。

(6)程序中不支持在表達(dá)式中有賦值運(yùn)算。即若遇到‘=’而其后的第一個(gè)字符不是‘=’則認(rèn)為出錯(cuò)。

2.3 核心實(shí)現(xiàn)

函數(shù)evaluate用于求解經(jīng)過(guò)規(guī)范化的用戶輸入表達(dá)式，有四個(gè)參數(shù):s為經(jīng)過(guò)規(guī)范化后的用戶輸入表達(dá)式;s1為運(yùn)算量棧指針;s2為運(yùn)算符棧指針;s3為變量鏈表指針。程序中首先定義了一些臨時(shí)變量，然后在運(yùn)算符棧內(nèi)壓入#的索引及其棧外、棧內(nèi)優(yōu)先級(jí)作為標(biāo)記如下:

s2=pushstack(s2，0，1，1);/*#的索引、棧內(nèi)外級(jí)入棧*/

在表達(dá)式未結(jié)束且已掃描過(guò)的部分表達(dá)式合法的情況下循環(huán)處理。若是數(shù)字或小數(shù)點(diǎn)則進(jìn)入數(shù)值處理分支并繼續(xù)讀取，并將運(yùn)算量壓入運(yùn)算量棧中。若讀到的是字母，則進(jìn)入變量分支，并在變量表中進(jìn)行查找變量值并壓入運(yùn)算量棧之中。

對(duì)于運(yùn)算符首先查找運(yùn)算符表，然后在OPTable［］表中找到其對(duì)應(yīng)的棧內(nèi)、外優(yōu)先級(jí)，并對(duì)棧外運(yùn)算符的棧外優(yōu)先級(jí)和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級(jí)作相應(yīng)的比較，根據(jù)比較結(jié)果進(jìn)行相應(yīng)的運(yùn)算。

［1］嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社出版，2009.

［2］譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)教程［M］.4版.北京:清華大學(xué)出版社出版，2010.

［3］唐策善.數(shù)據(jù)結(jié)構(gòu)—用C語(yǔ)言描述.［M］.北京:高等教育出版社，2003.