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

摘要：算符優(yōu)先分析法是編譯原理課程中的重點(diǎn)和難點(diǎn)之一。本文針對(duì)相等、小于和大于優(yōu)先關(guān)系，分析了優(yōu)先歸約關(guān)系的本質(zhì)，提出了優(yōu)先關(guān)系和最左素短語(yǔ)的分析模型。

關(guān)鍵詞：編譯原理；歸約；優(yōu)先關(guān)系；最左素短語(yǔ)

中圖分類(lèi)號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

1引言

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科強(qiáng)調(diào)4個(gè)方面的專(zhuān)業(yè)能力：計(jì)算思維能力，算法設(shè)計(jì)與分析能力，程序設(shè)計(jì)與實(shí)現(xiàn)能力，計(jì)算機(jī)系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)和運(yùn)用能力。這也是計(jì)算機(jī)科學(xué)與其他學(xué)科的重要區(qū)別。相關(guān)的理論是計(jì)算機(jī)學(xué)科的基礎(chǔ)。理論方面的知識(shí)是計(jì)算機(jī)的真正靈魂。理論是從計(jì)算機(jī)應(yīng)用當(dāng)中抽象出來(lái)的，目的在于使用抽象出來(lái)的理論去更好地指導(dǎo)實(shí)踐[1]。

程序設(shè)計(jì)與實(shí)現(xiàn)能力在編譯原理課程得到了具體的體現(xiàn)。編譯原理是計(jì)算機(jī)學(xué)科中少有的從實(shí)踐到理論，再?gòu)睦碚摰綄?shí)踐的一門(mén)專(zhuān)業(yè)課程。編譯技術(shù)不斷進(jìn)步，已經(jīng)成為計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)重要分支。編譯技術(shù)集中體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展的重要成果與精華[2]。

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

自下而上語(yǔ)法分析中的算符優(yōu)先分析方法是是編譯原理課程中的重點(diǎn)和難點(diǎn)之一。算符優(yōu)先分析法使用終結(jié)符號(hào)之間的歸約順序進(jìn)行語(yǔ)法結(jié)構(gòu)的分析。在算術(shù)表達(dá)式中，有運(yùn)算符號(hào)的優(yōu)先級(jí)和結(jié)合性的規(guī)定，而算符優(yōu)先分析法的實(shí)質(zhì)就是仿效表達(dá)式的計(jì)算過(guò)程而設(shè)計(jì)的。其本質(zhì)是對(duì)終結(jié)符之間的優(yōu)先關(guān)系和最左素短語(yǔ)進(jìn)行分析。

2終結(jié)符之間的優(yōu)先關(guān)系

2.1算符優(yōu)先文法

上下文無(wú)關(guān)文法G，如果沒(méi)有形如

P→ε

或

P→...QR...

的產(chǎn)生式，則稱(chēng)G為算符文法。

算符優(yōu)先分析方法考慮的是可能相鄰的兩個(gè)終結(jié)符之間的歸約順序問(wèn)題(模仿算術(shù)表達(dá)式中相鄰的兩個(gè)運(yùn)算符之間的計(jì)算的順序問(wèn)題)。

對(duì)算符文法G，a，bIcirc;VT 優(yōu)先關(guān)系定義為

(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的任何終結(jié)符a、b之間的優(yōu)先關(guān)系至多只有=、>、<中的一個(gè)；或者終結(jié)符a、b之間沒(méi)有優(yōu)先關(guān)系 則G稱(chēng)為算符優(yōu)先文法。

2.2優(yōu)先關(guān)系模型

對(duì)于3種優(yōu)先關(guān)系，分別建立對(duì)應(yīng)的優(yōu)先關(guān)系分析模型，自然引入構(gòu)造優(yōu)先關(guān)系表所需要的FIRSYVT和LASTVT集合。

(1) 相等優(yōu)先關(guān)系

若文法G 有

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

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

圖1相等相等優(yōu)先關(guān)系模型圖

(2) 小于優(yōu)先關(guān)系

若文法G有

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

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

圖2小于優(yōu)先關(guān)系模型圖

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

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

(3) 大于相等優(yōu)先關(guān)系

若G中有

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

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

圖3大于優(yōu)先關(guān)系6模型圖

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

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

2.3特殊符號(hào)#的優(yōu)先關(guān)系

對(duì)于算符優(yōu)先分析方法，需要使用#作為待分析串的開(kāi)始和結(jié)束標(biāo)記，也需要定義#與其他終結(jié)符號(hào)的優(yōu)先歸約關(guān)系。

對(duì)文法進(jìn)行改造，增加開(kāi)始符號(hào)S′，增加產(chǎn)生式S′→#S#。

使得開(kāi)始標(biāo)記#的優(yōu)先歸約關(guān)系小于FIRSTVT(S)的所有元素，即開(kāi)始標(biāo)記#的優(yōu)先歸約關(guān)系小于待分析串所有可能開(kāi)始的字符；而LASTVT(S)的所有元素優(yōu)先歸約關(guān)系大于結(jié)束標(biāo)記#，即待分析串所有可能結(jié)束的字符優(yōu)先歸約關(guān)系大于結(jié)束標(biāo)記#。

開(kāi)始和結(jié)束標(biāo)記#的優(yōu)先歸約關(guān)系是最低的。

2.4其他相關(guān)問(wèn)題

(1) 相同終結(jié)符的優(yōu)先關(guān)系未必是=

(2) 有aa

(3)a、b之間未必一定有優(yōu)先關(guān)系

(4) 兩個(gè)終結(jié)符之間若沒(méi)有優(yōu)先關(guān)系，則表示兩個(gè)終結(jié)符不可能相鄰，這也是算符優(yōu)先分析方法判斷語(yǔ)法錯(cuò)誤的依據(jù)。

3最左素短語(yǔ)的判斷

句型的一般形式為：

#N1a1N2a2…NnanNn+1#

最左素短語(yǔ)是滿(mǎn)足條件的最左子串NjajNj+1…NiaiNi+1

其中，條件為

aj-1

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

ai>ai+1

最左素短語(yǔ)的出現(xiàn)依據(jù)的是終結(jié)符號(hào)歸約順序的轉(zhuǎn)折。最左素短語(yǔ)模型如圖4所示。

圖4最左素短語(yǔ)模型圖

4總結(jié)

實(shí)際教學(xué)證明，此模型可有效地幫助學(xué)生理解優(yōu)先關(guān)系的定義和算符優(yōu)先分析方法的原理和技術(shù)。

參考文獻(xiàn)

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

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

[3]Andrew W.Apple.現(xiàn)代編譯器的Java實(shí)現(xiàn)[M].北京:電子工業(yè)出版社，2004.

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

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

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”