編譯原理中算符優先分析的教學探討

文章編號：1672-5913(2008)12-0080-03

摘要：算符優先分析法是編譯原理課程中的重點和難點之一。本文針對相等、小于和大于優先關系，分析了優先歸約關系的本質，提出了優先關系和最左素短語的分析模型。

關鍵詞：編譯原理；歸約；優先關系；最左素短語

中圖分類號：G642

文獻標識碼：B

1引言

計算機科學與技術學科強調4個方面的專業能力：計算思維能力，算法設計與分析能力，程序設計與實現能力，計算機系統的認知、分析、設計和運用能力。這也是計算機科學與其他學科的重要區別。相關的理論是計算機學科的基礎。理論方面的知識是計算機的真正靈魂。理論是從計算機應用當中抽象出來的，目的在于使用抽象出來的理論去更好地指導實踐[1]。

程序設計與實現能力在編譯原理課程得到了具體的體現。編譯原理是計算機學科中少有的從實踐到理論，再從理論到實踐的一門專業課程。編譯技術不斷進步，已經成為計算機科學中發展最迅速、最成熟的一個重要分支。編譯技術集中體現了計算機科學發展的重要成果與精華[2]。

程序語言及其編譯的研究在計算機科學中的始終處于非常重要的地位。編譯程序構造的基本原理和技術蘊涵計算機科學解決問題的思路和抽象、解決問題的方法，也廣泛應用于一般軟件的設計和實現，其中的設計思想、算法、思維方式和技術都可能會對學生今后的發展產生比較大的影響。編譯原理對計算機專業的學生的重要性與高等數學對理科學生的重要性幾乎可以相提并論。同時，由于這門課程涉及其他多門課程的知識，使得它成為大學階段中最難學的課程之一。

自下而上語法分析中的算符優先分析方法是是編譯原理課程中的重點和難點之一。算符優先分析法使用終結符號之間的歸約順序進行語法結構的分析。在算術表達式中，有運算符號的優先級和結合性的規定，而算符優先分析法的實質就是仿效表達式的計算過程而設計的。其本質是對終結符之間的優先關系和最左素短語進行分析。

2終結符之間的優先關系

2.1算符優先文法

上下文無關文法G，如果沒有形如

P→ε

或

P→...QR...

的產生式，則稱G為算符文法。

算符優先分析方法考慮的是可能相鄰的兩個終結符之間的歸約順序問題(模仿算術表達式中相鄰的兩個運算符之間的計算的順序問題)。

對算符文法G，a，bIcirc;VT 優先關系定義為

(1) 若G有P→...ab...或P→...aQb...， 則a=b

(2) 若G有P→...aQ...且QTHORN;+b… 或 QTHORN;+Rb...，則a

(3) 若G有P→...Qb... 且QTHORN;+...a 或 QTHORN;+…aR，則a>b

若算符文法G的任何終結符a、b之間的優先關系至多只有=、>、<中的一個；或者終結符a、b之間沒有優先關系 則G稱為算符優先文法。

2.2優先關系模型

對于3種優先關系，分別建立對應的優先關系分析模型，自然引入構造優先關系表所需要的FIRSYVT和LASTVT集合。

(1) 相等優先關系

若文法G 有

P→...ab...或P→...aQb...

則a與b是一起歸約為P的(當然，還要連同其他的一些符號)。因此，a與b的歸約順序是一致的(相等的)，即 a=b。相等優先關系模型如圖1所示。

圖1相等相等優先關系模型圖

(2) 小于優先關系

若文法G有

P→...aQ... 且Q THORN;+b…或QTHORN;+Rb...

那么，需要先規約包含b的最左素短語為Q，然后才可能規約…aQ…為P。即a

圖2小于優先關系模型圖

而對于Q THORN;+b…或QTHORN;+Rb... ，定義FIRSTVT集合為

FIRSTVT(Q)={a|QTHORN;+a… 或QTHORN;+Ra…，aIcirc;VT，R Icirc;VN}

(3) 大于相等優先關系

若G中有

P→...Qb...且QTHORN;+...a或QTHORN;+…aR

那么，需要先規約包含a的最左素短語為Q，然后才可能規約…Qb…為P。即a>b。大于優先關系模型如圖3所示。

圖3大于優先關系6模型圖

對于QTHORN;+...a或QTHORN;+…aR，定義LASTVT集合為

LASTVT(Q)={a|QTHORN;+...a 或 QTHORN;+…aR，aIcirc;VT，R Icirc;VN}

2.3特殊符號#的優先關系

對于算符優先分析方法，需要使用#作為待分析串的開始和結束標記，也需要定義#與其他終結符號的優先歸約關系。

對文法進行改造，增加開始符號S′，增加產生式S′→#S#。

使得開始標記#的優先歸約關系小于FIRSTVT(S)的所有元素，即開始標記#的優先歸約關系小于待分析串所有可能開始的字符；而LASTVT(S)的所有元素優先歸約關系大于結束標記#，即待分析串所有可能結束的字符優先歸約關系大于結束標記#。

開始和結束標記#的優先歸約關系是最低的。

2.4其他相關問題

(1) 相同終結符的優先關系未必是=

(2) 有aa

(3)a、b之間未必一定有優先關系

(4) 兩個終結符之間若沒有優先關系，則表示兩個終結符不可能相鄰，這也是算符優先分析方法判斷語法錯誤的依據。

3最左素短語的判斷

句型的一般形式為：

#N1a1N2a2…NnanNn+1#

最左素短語是滿足條件的最左子串NjajNj+1…NiaiNi+1

其中，條件為

aj-1

aj=aj+1=…=ai-1=ai

ai>ai+1

最左素短語的出現依據的是終結符號歸約順序的轉折。最左素短語模型如圖4所示。

圖4最左素短語模型圖

4總結

實際教學證明，此模型可有效地幫助學生理解優先關系的定義和算符優先分析方法的原理和技術。

參考文獻

[1] 蔣宗禮，姜守旭.形式語言與自動機理論(第2版)[M].北京:清華大學出版社.2007.

[2] 龔天富.語言及編譯(第2版)[M]. 北京:電子工業出版社，2003.

[3]Andrew W.Apple.現代編譯器的Java實現[M].北京:電子工業出版社，2004.

[4]Dick Grune etc.Modern Compiler Design[M].JOHN WILEYSONS，LTD，2002.

[5] 余勝泉，張建偉.信息時代的教學與實踐[M].北京:高等教育出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”