BEGIN k:=k+1;s[k]:=a END.
UNTIL a=’#’
圖1算符優先分析程序
表1的算符優先表，圖1的算符優先分析程序和棧共同構成了文法G[E]的算符優先分析器。
2算符優先析法的錯誤診斷恢復機制的構造
使用算符優先法進行語法分析時，出現下面兩種情況，則發生錯誤：
(1) 若棧頂算符與當前輸入符號間不存在優先關系；
(2) 若找到某一句柄，但不存在任一產生式，其右部與此句柄形式吻合。
2.1第一種出錯情況下錯誤診斷恢復機制的構造[3]
在第一種出錯情況下，即棧頂算符與當前輸入符號間不存在優先關系時，可采用改變、插入或刪除符號的方法來糾正錯誤。例如a和b是棧頂的兩個相繼出現的算符(b為棧頂)，c和d為當前輸入串中前面兩個符號，且b和c之間不存在優先關系，此時出現錯誤，分析無法繼續。一種解決方法是若a的優先級低于或等于c，則可將b從棧頂刪除，此時a變為棧頂算符，a與c之間有優先關系，可繼續分析；另一種解決方法是找出某個算符e，使得b≤e≤c，把e插入輸入串中c的前面，繼續分析。若找不到單個符號e，則可插入一串符號，使得b≤e1≤e2≤…≤en≤c。按照這一原則可構造出現第一種情況的錯誤時的出錯處理子程序。
文法G[E]的算符優先表表1中的空白表項即為算符之間無優先關系的情況，分析這些情況并按照上述原則可構造文法G[E]的算符優先分析器糾正第一種情況錯誤時的出錯處理子程序如下：
e1:/*表1中的終結符號對((，#)無優先關系，當棧頂算符為(，當前輸入符號為#，說明表達式中有(，但無)便結束了，此時調用此子程序*/
將(從棧頂刪除，繼續分析。給出診斷信息；“缺少)。”
e2:/*表1中的終結符號對()，()，()，i)，(i，()，(i，i)無優先關系，當棧頂算符為)或i，當前輸入符號為i或(時出錯，)或i不能直接跟i或(，它們之間應有運算符，此時調用此程序*/
在輸入串當前符號前插入+，繼續分析。給出診斷信息：“缺少運算符。”
e3:/*表1中的終結符號對(#，))無優先關系，當棧頂算符為#，當前輸入符號為)時，說明表達式中有)，但)前無與其配對的(，此時出錯，調用此程序*/
從輸入串中刪除當前符號)，繼續分析。給出診斷信息：“缺少(。”
e4:/*表1中的終結符號對(#，#)優先級相等，若棧頂為#，當前輸入符號為#，這時可能會出現兩種情況：(1)若棧頂有非終結符E，則說明表達式分析正常結束，不出錯。(2)若棧頂為空，此時出錯，則調用此程序。*/
在輸入串當前符號前插入i，繼續分析。給出診斷信息；“缺少表達式。”
將e1、e2、e3、e4加入表1的出錯位置，表示出錯時調用相應的出錯處理子程序。改寫后的表1變為表2。用算符優先法進行語法分析時，算符優先分析程序須不斷查算符優先表，來比較棧頂算符與讀入算符之間的優先級，當發現棧頂算符與讀入算符之間無優先關系時就出錯，調用相應的錯誤處理子程序使分析繼續下去。
2.2第二種情況下錯誤診斷恢復機制的構造
算符優先法的第二種出錯情況指算符優先法在分析過程中，找到某一句柄時要進行歸約，但不存在任一產生式，其右部與該句柄形式吻合。所謂形式吻合是指句柄與某一產生式右部非終結符位置一致，終結符位置一致，名稱一致，此時可將該句柄歸約為一非終結符N。用算符優先法進行分析時，棧中已處理部分與輸入串中剩余的未處理部分構成一個句型，假設棧中為#a1N1a2N2…anNn，輸入串為an+1…ak#，則當前句型為#a1N1a2N2…anNnan+1…ak#，句柄指當前句型的最左素短語，它的特點是句柄中算符的優先級相等，句柄中算符的優先級高于句柄外相鄰算符的優先級。若a1an+1，則當前句型的句柄為N1a2N2…anNn，該句柄應與某產生式右部形式吻合才可歸約。若句柄與任一產生式右部都不形式吻合則出錯，這種情況下的出錯處理子程序應能完成兩項功能：診斷錯誤和從錯誤中恢復過來。下面以文法G[E]的算符優先分析器為例介紹針對第二種出錯情況的出錯處理子程序的設計。
e5:/*句柄中含+時，若該句柄正確，則它應與產生式E→E+T右部形式吻合，即+兩邊各出現一個非終結符，否則出錯，調用此程序*/
將句柄歸約為非終結符N，繼續分析。給出診斷信息：“缺表達式。”
e6:/*句柄中含*時，若該句柄正確，則它應與產生式T→T*F右部形式吻合，即*兩邊各出現一個非終結符，否則出錯，調用此程序*/
將句柄歸約為非終結符N，繼續分析。給出診斷信息：“缺表達式。”
e7:/*句柄中含i時，若該句柄正確，則它應與產生式F→i右部形式吻合，即i左邊或右邊不能出現非終結符，否則出錯，調用此程序*/
將句柄歸約為非終結符N，繼續分析。給出診斷信息：“表達式間無運算符連接。”
e8:/*句柄中含()時，若該句柄正確，則它應與產生式F→(E)右部形式吻合，即括號中應有一非終結符，否則出錯，調用此程序*/
將句柄歸約為非終結符N，繼續分析。給出診斷信息：“括號間無表達式。”
2.3含錯誤診斷恢復機制的算符優先法進行語法分析的過程
圖1的算符優先分析程序，表2的含出錯處理子程序的算符優先表，出錯處理子程序e5、e6、e7、e8和棧共同構成了文法G[E]的含錯誤診斷恢復機制的算符優先法。假設輸入串為i+)i，含錯誤診斷恢復機制的算符優先法對該串進行語法分析的過程如表3。
3結論
本文討論了如何通過加入錯誤診斷恢復機制對算符優先分析算法進行改進和完善。加入錯誤診斷恢復機制后，算符優先分析算法在語法分析中出現錯誤時，能對錯誤正確地診斷并及時從錯誤中恢復過來，使分析繼續下去。加入錯誤診斷恢復機制后的算符優先分析算法在教學和多次實例中證明是正確有效的。
參考文獻：
[1] 呂映芝，張素琴，蔣維杜. 編譯原理[M]. 北京:清華大學出版社，1998.
[2] 陳火旺，劉春林，譚慶平等. 程序設計語言編譯原理(第3版)[M]. 北京:國防工業出版社，2000.
[3] Alfred V.aho， Ravi Sethi， Jeffrey D. uLLman著. 李建中，姜守旭譯. 編譯原理[M]. 北京:機械工業出版社，2003.
