英昌盛

(吉林師范大學 計算機學院，吉林 四平 136000)

0 引言

表達式的分析、求值等運算是編譯程序中的一個關鍵部分。研究翻譯程序的工作原理和工作流程，對于教師的教學和研究，對于學生理論聯(lián)系實際都具有較為實用的意義和價值。

1 系統(tǒng)設計及概要設計

1.1 運算符和數(shù)據(jù)類型的支持

系統(tǒng)支持算術運算、關系運算和邏輯運算。算術運算符有包括:()、+、-、*、/、^(乘方)，其中^為新增運算符。邏輯運算符包括:!、＆(邏輯與為化簡運算符)、|(邏輯或為化簡運算符)。關系運算符包括:＞、＞=、==、_(負號)。

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

1.2 數(shù)據(jù)結構

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

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

2.1 算符優(yōu)先級及數(shù)據(jù)結構

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

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

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

2.2 處理規(guī)則

(1)初始化時在運算棧內(nèi)壓入一個#;同時#作為表達式結束標記。

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

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

(4)若運算完畢運算量棧只剩一個運算量、符號棧空，則運算結果正確，其他情況則為錯誤。

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

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

2.3 核心實現(xiàn)

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

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

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

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

［1］嚴蔚敏.數(shù)據(jù)結構［M］.北京:清華大學出版社出版，2009.

［2］譚浩強.C語言程序設計教程［M］.4版.北京:清華大學出版社出版，2010.

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