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

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

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

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

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

算符優(yōu)先法包含三個要素：算符優(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;/*取棧頂運算符*/

WHILE s[j]>a DO/*若棧頂運算符s[j]的優(yōu)先級高于讀入運算符的優(yōu)先級，則說明棧中有句柄，找到句柄進(jìn)行歸約*/

BEGIN

REPEAT

Q:=s[j];

IF s[j-1]∈VTTHEN j:=j-1 ELSE j:=j-2

UNTIL s[j]

把s[j-1]…s[k]歸約為N;/*s[j-1]…s[k]為句柄*/

k:=j+1;

s[k]:=N

END;

IF s[j]

BEGIN k:=k+1;s[k]:=a END.

UNTIL a=’#’

圖1算符優(yōu)先分析程序

表1的算符優(yōu)先表，圖1的算符優(yōu)先分析程序和棧共同構(gòu)成了文法G[E]的算符優(yōu)先分析器。

2算符優(yōu)先析法的錯誤診斷恢復(fù)機(jī)制的構(gòu)造

使用算符優(yōu)先法進(jìn)行語法分析時，出現(xiàn)下面兩種情況，則發(fā)生錯誤：

(1) 若棧頂算符與當(dāng)前輸入符號間不存在優(yōu)先關(guān)系；

(2) 若找到某一句柄，但不存在任一產(chǎn)生式，其右部與此句柄形式吻合。

2.1第一種出錯情況下錯誤診斷恢復(fù)機(jī)制的構(gòu)造[3]

在第一種出錯情況下，即棧頂算符與當(dāng)前輸入符號間不存在優(yōu)先關(guān)系時，可采用改變、插入或刪除符號的方法來糾正錯誤。例如a和b是棧頂?shù)膬蓚€相繼出現(xiàn)的算符(b為棧頂)，c和d為當(dāng)前輸入串中前面兩個符號，且b和c之間不存在優(yōu)先關(guān)系，此時出現(xiàn)錯誤，分析無法繼續(xù)。一種解決方法是若a的優(yōu)先級低于或等于c，則可將b從棧頂刪除，此時a變?yōu)闂ｍ斔惴?，a與c之間有優(yōu)先關(guān)系，可繼續(xù)分析；另一種解決方法是找出某個算符e，使得b≤e≤c，把e插入輸入串中c的前面，繼續(xù)分析。若找不到單個符號e，則可插入一串符號，使得b≤e1≤e2≤…≤en≤c。按照這一原則可構(gòu)造出現(xiàn)第一種情況的錯誤時的出錯處理子程序。

文法G[E]的算符優(yōu)先表表1中的空白表項即為算符之間無優(yōu)先關(guān)系的情況，分析這些情況并按照上述原則可構(gòu)造文法G[E]的算符優(yōu)先分析器糾正第一種情況錯誤時的出錯處理子程序如下：

e1:/*表1中的終結(jié)符號對((，#)無優(yōu)先關(guān)系，當(dāng)棧頂算符為(，當(dāng)前輸入符號為#，說明表達(dá)式中有(，但無)便結(jié)束了，此時調(diào)用此子程序*/

將(從棧頂刪除，繼續(xù)分析。給出診斷信息；“缺少)?！?/p>

e2:/*表1中的終結(jié)符號對()，()，()，i)，(i，()，(i，i)無優(yōu)先關(guān)系，當(dāng)棧頂算符為)或i，當(dāng)前輸入符號為i或(時出錯，)或i不能直接跟i或(，它們之間應(yīng)有運算符，此時調(diào)用此程序*/

在輸入串當(dāng)前符號前插入+，繼續(xù)分析。給出診斷信息：“缺少運算符?！?/p>

e3:/*表1中的終結(jié)符號對(#，))無優(yōu)先關(guān)系，當(dāng)棧頂算符為#，當(dāng)前輸入符號為)時，說明表達(dá)式中有)，但)前無與其配對的(，此時出錯，調(diào)用此程序*/

從輸入串中刪除當(dāng)前符號)，繼續(xù)分析。給出診斷信息：“缺少(?！?/p>

e4:/*表1中的終結(jié)符號對(#，#)優(yōu)先級相等，若棧頂為#，當(dāng)前輸入符號為#，這時可能會出現(xiàn)兩種情況：(1)若棧頂有非終結(jié)符E，則說明表達(dá)式分析正常結(jié)束，不出錯。(2)若棧頂為空，此時出錯，則調(diào)用此程序。*/

在輸入串當(dāng)前符號前插入i，繼續(xù)分析。給出診斷信息；“缺少表達(dá)式?！?/p>

將e1、e2、e3、e4加入表1的出錯位置，表示出錯時調(diào)用相應(yīng)的出錯處理子程序。改寫后的表1變?yōu)楸?。用算符優(yōu)先法進(jìn)行語法分析時，算符優(yōu)先分析程序須不斷查算符優(yōu)先表，來比較棧頂算符與讀入算符之間的優(yōu)先級，當(dāng)發(fā)現(xiàn)棧頂算符與讀入算符之間無優(yōu)先關(guān)系時就出錯，調(diào)用相應(yīng)的錯誤處理子程序使分析繼續(xù)下去。

2.2第二種情況下錯誤診斷恢復(fù)機(jī)制的構(gòu)造

算符優(yōu)先法的第二種出錯情況指算符優(yōu)先法在分析過程中，找到某一句柄時要進(jìn)行歸約，但不存在任一產(chǎn)生式，其右部與該句柄形式吻合。所謂形式吻合是指句柄與某一產(chǎn)生式右部非終結(jié)符位置一致，終結(jié)符位置一致，名稱一致，此時可將該句柄歸約為一非終結(jié)符N。用算符優(yōu)先法進(jìn)行分析時，棧中已處理部分與輸入串中剩余的未處理部分構(gòu)成一個句型，假設(shè)棧中為#a1N1a2N2…anNn，輸入串為an+1…ak#，則當(dāng)前句型為#a1N1a2N2…anNnan+1…ak#，句柄指當(dāng)前句型的最左素短語，它的特點是句柄中算符的優(yōu)先級相等，句柄中算符的優(yōu)先級高于句柄外相鄰算符的優(yōu)先級。若a1an+1，則當(dāng)前句型的句柄為N1a2N2…anNn，該句柄應(yīng)與某產(chǎn)生式右部形式吻合才可歸約。若句柄與任一產(chǎn)生式右部都不形式吻合則出錯，這種情況下的出錯處理子程序應(yīng)能完成兩項功能：診斷錯誤和從錯誤中恢復(fù)過來。下面以文法G[E]的算符優(yōu)先分析器為例介紹針對第二種出錯情況的出錯處理子程序的設(shè)計。

e5:/*句柄中含+時，若該句柄正確，則它應(yīng)與產(chǎn)生式E→E+T右部形式吻合，即+兩邊各出現(xiàn)一個非終結(jié)符，否則出錯，調(diào)用此程序*/

將句柄歸約為非終結(jié)符N，繼續(xù)分析。給出診斷信息：“缺表達(dá)式?！?/p>

e6:/*句柄中含*時，若該句柄正確，則它應(yīng)與產(chǎn)生式T→T*F右部形式吻合，即*兩邊各出現(xiàn)一個非終結(jié)符，否則出錯，調(diào)用此程序*/

將句柄歸約為非終結(jié)符N，繼續(xù)分析。給出診斷信息：“缺表達(dá)式?！?/p>

e7:/*句柄中含i時，若該句柄正確，則它應(yīng)與產(chǎn)生式F→i右部形式吻合，即i左邊或右邊不能出現(xiàn)非終結(jié)符，否則出錯，調(diào)用此程序*/

將句柄歸約為非終結(jié)符N，繼續(xù)分析。給出診斷信息：“表達(dá)式間無運算符連接?！?/p>

e8:/*句柄中含()時，若該句柄正確，則它應(yīng)與產(chǎn)生式F→(E)右部形式吻合，即括號中應(yīng)有一非終結(jié)符，否則出錯，調(diào)用此程序*/

將句柄歸約為非終結(jié)符N，繼續(xù)分析。給出診斷信息：“括號間無表達(dá)式?！?/p>

2.3含錯誤診斷恢復(fù)機(jī)制的算符優(yōu)先法進(jìn)行語法分析的過程

圖1的算符優(yōu)先分析程序，表2的含出錯處理子程序的算符優(yōu)先表，出錯處理子程序e5、e6、e7、e8和棧共同構(gòu)成了文法G[E]的含錯誤診斷恢復(fù)機(jī)制的算符優(yōu)先法。假設(shè)輸入串為i+)i，含錯誤診斷恢復(fù)機(jī)制的算符優(yōu)先法對該串進(jìn)行語法分析的過程如表3。

3結(jié)論

本文討論了如何通過加入錯誤診斷恢復(fù)機(jī)制對算符優(yōu)先分析算法進(jìn)行改進(jìn)和完善。加入錯誤診斷恢復(fù)機(jī)制后，算符優(yōu)先分析算法在語法分析中出現(xiàn)錯誤時，能對錯誤正確地診斷并及時從錯誤中恢復(fù)過來，使分析繼續(xù)下去。加入錯誤診斷恢復(fù)機(jī)制后的算符優(yōu)先分析算法在教學(xué)和多次實例中證明是正確有效的。

參考文獻(xiàn)：

[1] 呂映芝，張素琴，蔣維杜. 編譯原理[M]. 北京:清華大學(xué)出版社，1998.

[2] 陳火旺，劉春林，譚慶平等. 程序設(shè)計語言編譯原理(第3版)[M]. 北京:國防工業(yè)出版社，2000.

[3] Alfred V.aho， Ravi Sethi， Jeffrey D. uLLman著. 李建中，姜守旭譯. 編譯原理[M]. 北京:機(jī)械工業(yè)出版社，2003.