算符優(yōu)先分析算法的探討與改進(jìn)

摘要：算符優(yōu)先分析算法是編譯原理教材中介紹的一種重要的語法分析算法，但教材中講述的該算法并不完整，有一定的缺陷，本文結(jié)合實(shí)例提出了改進(jìn)的算法。

關(guān)鍵詞：算符優(yōu)先分析算法；錯(cuò)誤診斷恢復(fù)機(jī)制；句柄

中圖分類號：G434 文獻(xiàn)標(biāo)識碼：A

“編譯原理”是計(jì)算機(jī)專業(yè)的一門綜合性較強(qiáng)的專業(yè)課程。算符優(yōu)先分析算法是“編譯原理”課程中所涉及的一種重要的語法分析算法。目前教材中講述的算符優(yōu)先分析算法沒有考慮到在語法分析中出現(xiàn)錯(cuò)誤時(shí)如何及時(shí)報(bào)告錯(cuò)誤并盡快從錯(cuò)誤中恢復(fù)過來，因此現(xiàn)有教材中的算符優(yōu)先分析算法并不完整。本文通過實(shí)例分析了算符優(yōu)先分析算法在進(jìn)行語法分析時(shí)的各種出錯(cuò)情況，并給出了各種出錯(cuò)情況下錯(cuò)誤診斷恢復(fù)機(jī)制的構(gòu)造方法。加入錯(cuò)誤診斷恢復(fù)機(jī)制后，可使算符優(yōu)先分析算法在語法分析中出現(xiàn)錯(cuò)誤時(shí)，能及時(shí)報(bào)告錯(cuò)誤并盡快從錯(cuò)誤中恢復(fù)過來，使分析繼續(xù)下去，改進(jìn)后的算法更加完整準(zhǔn)確。

1算符優(yōu)先法的構(gòu)造[1]

算符優(yōu)先法包含三個(gè)要素：算符優(yōu)先表、棧和分析程序。下面以簡化的表達(dá)式文法為例介紹算符優(yōu)先法的構(gòu)造過程。簡化的表達(dá)式文法G[E]如下：

E→E+T|T

T→T*F|F

F→i|(E)

可證明文法G[E]為算符優(yōu)先文法。構(gòu)造文法G[E]的算符優(yōu)先表如表1。

算符優(yōu)先法的分析程序是通用的，其算法如圖1[2]。

k:=1;s[k]:=’#’; /*數(shù)組s[]為棧，k為棧指針*/

REPEAT

把下一輸入符號讀入a;

IF s[k]∈VT THEN j:=k ELSE j:=k-1;/*取棧頂運(yùn)算符*/

WHILE s[j]>a DO/*若棧頂運(yùn)算符s[j]的優(yōu)先級高于讀入運(yùn)算符的優(yōu)先級，則……