崔　蕊　徐安鳳

摘要:文章討論了LL(1)語法分析器的工作原理和過程,以具體實(shí)例說明語法定義、造表和總控程序的實(shí)現(xiàn)過程。

關(guān)鍵詞:編譯原理;自上而下語法分析;預(yù)測分析

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

文章編號:1674-1145(2009)23-0133-01

編譯程序能夠?qū)④浖Z言書寫的各種程序處理成可在計(jì)算機(jī)上執(zhí)行的程序,是重要的系統(tǒng)軟件。在編譯系統(tǒng)中,語法分析階段是整個(gè)編譯過程中繼詞法分析后的第二個(gè)階段。按照建立語法分析樹的方法,語法分析分為兩類:自上而下分析和自下而上分析。本文討論的預(yù)測分析法屬于自上而下的方法。

一、語法規(guī)則的表示

語法規(guī)則是由上下文無關(guān)文法進(jìn)行定義的。例如一個(gè)語言可用一系列的產(chǎn)生式定義:<程序>-> begin <語句串> end <語句串> -> <語句><;<語句串>> 等等,為了方便問題描述,把實(shí)際含義用符號進(jìn)行抽象,本文討論的例子就是抽象后的符號表示的。本文所討論的預(yù)測分析自上而下語法分析式由初始符號出發(fā),利用產(chǎn)生式不斷推導(dǎo),實(shí)際就是從左到右掃描符號串,模擬句子推導(dǎo)的過程。因此文法必必須為滿足推導(dǎo)條件的LL(1)文法。LL(1)文法的條件是:(1)文法不含左遞歸;(2)每個(gè)非終結(jié)符號的各個(gè)產(chǎn)生式的候選首字符集兩兩不相交;(3)每個(gè)非終結(jié)符號的候選首字符集包含空,則首字符集和跟隨字符集的交集為空。具體可查看LL(1)文法的相關(guān)知識。本文的文法如下(是LL(1)文法):E->T EE->+TE|ε T->FTT->*FT|εF->(E)|I

其中大寫字母為非終極符號,E為初始符,其他為終結(jié)符號。

二、構(gòu)造文法中個(gè)非終結(jié)符號的FIRST集和FOLLOW集

FIRSTFOLLOW

E->T E (i ) #

E->+TE + ) #

ε ε

T->FT (i +)#

T->*FT * +)#

ε ε

F->(E) ( *+)#

i i

三、構(gòu)造預(yù)測分析表

造表規(guī)則為:(1)若A->ri|…|rma∈FIRST(ri) M[A,a]=A->ri;(2)rj->εa∈FLLOW(A) 則M[A,a]=A->rj;(3)除(1)(2)外出錯(cuò)。

四、LL(1)語法分析器實(shí)現(xiàn)

1.語法分析器的邏輯結(jié)構(gòu)

2.工作流程:從左到右,模擬推導(dǎo)過程

(1)#開始符號進(jìn)棧

(2)設(shè)當(dāng)前狀態(tài)為

(3)Xm與ai對話

情況1:Xm=ai!= #Xm出棧,輸入串的指針右移一位。

情況2:Xm∈VN,查表M[Xm,ai]= Xm->UVW,Xm退棧,按WVU順序進(jìn)棧(最左側(cè)在棧頂)輸入串指針不變。

情況3:Xm=ai= # 成功。

其他情況出錯(cuò)。

3.總控程序算法

開始符號壓棧

While(棧頂符!=# &&下一個(gè)輸入符!=#)

{If(棧頂符號==下一個(gè)輸入符)

{ 棧內(nèi)彈出棧頂符;

讀下一個(gè)字符;

}

else if(棧頂符號是非終結(jié)符A&&下一個(gè)a)

{ 查表M[A,a]->X1X2…Xn;

棧頂元素出棧;

Xn…X2X1進(jìn)棧;

}

else error;

}

If(棧頂符==# &&下一個(gè)輸入符==#)

Accept;

Else error;

參考文獻(xiàn)

[1]陳火旺,劉春林,譚慶平,等.程序設(shè)計(jì)語言編譯原理[M].國防工業(yè)出版社,2002.

[2]陳意云,張昱.編譯原理[M].北京:高等教育出版社,2003.