基于ＶＣ＋＋平臺的ＬＬ（１）語法分析器的設計

崔　蕊　徐安鳳

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

關鍵詞:編譯原理;自上而下語法分析;預測分析

中圖分類號:TP314文獻標識碼:A

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

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

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

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

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

二、構造文法中個非終結符號的FIRST集和FOLLOW集

FIRSTFOLLOW

E->T E (i ) #

E->+TE + ) #

ε ε

T->FT (i +)#

T->*FT * +)#

ε ε

F->(E) ( *+)#

i i

三、構造預測分析表

造表規(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)外出錯。

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

1.語法分析器的邏輯結構

2.工作流程:從左到右,模擬推導過程

(1)#開始符號進棧

(2)設當前狀態(tài)為

(3)Xm與ai對話

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

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

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

其他情況出錯。

3.總控程序算法

開始符號壓棧

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

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

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

讀下一個字符;

}

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

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

棧頂元素出棧;

Xn…X2X1進棧;

}

else error;

}

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

Accept;

Else error;

參考文獻

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

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