編譯原理講義
(第四章:語法分析--
自頂向下分析技術(shù))
南京大學(xué)計(jì)算機(jī)系
趙建華
引言
在詞法分析完成之后,進(jìn)入語法分析階段.
語法分析階段的任務(wù)是:檢查程序的語法是否正確,并生成內(nèi)部中間表示形式.
語法分析的
輸入:屬性字序列.
輸出:程序的內(nèi)部中間表示形式.
自頂向下分析技術(shù)與識別算法
從推導(dǎo)的角度看,從識別符號出發(fā),試圖推導(dǎo)出與輸入符號串相同的符號串.一般來講,構(gòu)造出的推導(dǎo)是最左推導(dǎo).
從語法樹的角度看,從根節(jié)點(diǎn),試圖向下一個語法樹,其末端節(jié)點(diǎn)正好與輸入符號串相同.
討論前提
輸入的是符號序列,不對符號構(gòu)造情況感興趣.
語法分析的文法是上下文無關(guān)文法.
自頂向下分析技術(shù)的理論基礎(chǔ)是定理2.7:如果Z::=X1X2…Xn且y為句子.那么如果X1X2…Xn=>y,必然存在y1,y2,…,yn使得Xi=>*yi且y=y1y2… yn.
要解決的基本問題
對于特定的終結(jié)符號,使用哪個重寫規(guī)則來替換 
無回溯的自頂向下分析技術(shù)
先決條件:
無遞歸
既沒有規(guī)則左遞歸,也沒有文法左遞歸.
無回溯性
對于任一非終結(jié)符號U的規(guī)則右部x1|x2|…|xn,其對應(yīng)的字的頭終結(jié)符號兩兩不相交.
遞歸下降分析技術(shù)(實(shí)現(xiàn)思想)
實(shí)現(xiàn)思想:
識別程序由一組過程組成.每個過程對應(yīng)于一個非終結(jié)符號.
每一個過程的功能是:選擇正確的右部,掃描完相應(yīng)的字.在右部中有非終結(jié)符號時,調(diào)用該終結(jié)符號對應(yīng)的過程來完成.
基本架構(gòu)(1)
對于每個非終結(jié)符號U::=u1|u2|…|un處理的方法如下:
U( ){
ch=當(dāng)前符號
if(ch可能是u1字的開頭) 處理u1的程序部分
else if(ch可能是u2字的開頭) 處理u2的程序部分
…
else error() 
}
基本架構(gòu)(1)
對于無回溯的文法保證選擇是唯一的.
但有某個右部的開頭是非終結(jié)符號時,需要用LL(K)方法判斷什么時候使用這個右部.
當(dāng)存在空規(guī)則的時候,可以把error()替代為{return;},這樣的處理使發(fā)現(xiàn)錯誤的情況比較晚.
約定:進(jìn)入這個過程時,對于U的第一個符號已經(jīng)被讀到當(dāng)前符號.離開這個程序的時候,下一個符號已經(jīng)被讀到當(dāng)前符號.
基本架構(gòu)(2)
對于每個右部u1=x1x2…xn的處理架構(gòu)如下:
處理x1的程序;
處理x2的程序;
… … … 
處理xn的程序;
如果右部為空,則不處理.
基本架構(gòu)(3)
對于右部中的每個符號xi
如果xi為終結(jié)符號:
if(x== 當(dāng)前的符號)
{NextCh();return;}
else
出錯處理
如果xi為非終結(jié)符號,直接調(diào)用相應(yīng)的過程:
xi()
遞歸下降技術(shù)(實(shí)例)
文法G4.3
E::=E+T|T T::=T*F|F F::=(E)|i
消左遞歸得到
E::=TE' E'::=+TE'| T::=FT' T'::=*FT'| F::=(E)|i
遞歸下降技術(shù)(實(shí)例續(xù))
對應(yīng)于文法G4.3'中的每個非終結(jié)符號,都有一個過程.
E()
{
if(當(dāng)前符號可能是T的開始符號)
{ T(); E1();}
else
error();
}
和書上不同的是,我們作了出錯處理.一般,當(dāng)只有一個右部的時候,可以不作出錯處理.
遞歸下降技術(shù)(實(shí)例續(xù))
E1()
{
if(ch='+')
{
getnextchar(); T(); E1();
}
else
return;
}
因?yàn)镋1對應(yīng)有空規(guī)則,所以其處理中,不作錯誤處理,而是直接return.實(shí)際表示它沒有讀入任何字符.
遞歸分析程序的運(yùn)行
棧底
E()
T()
輸入:i * i + i
T1()
處理完*,當(dāng)前符號為i
過程調(diào)用棧:
F()
遞歸分析程序的主程序
假設(shè)識別符號對應(yīng)的過程為Z(),那么相應(yīng)的主程序?yàn)?{
GetSymbol(); //首先需要讀入一個符號,以滿 // 足約定.
Z();
檢查是否達(dá)到輸入的結(jié)尾.
}
遞歸分析程序的優(yōu)點(diǎn)
實(shí)現(xiàn)思想簡單明了.程序結(jié)構(gòu)和語法規(guī)則有直接的對應(yīng)關(guān)系.
因?yàn)槊總€過程表示一個非終結(jié)符號的處理,添加語義加工工作比較方便.
需要書寫程序的語言支持遞歸調(diào)用.如果遞歸調(diào)用機(jī)制是高效的,那么分析程序也是高效的.
預(yù)測分析法
使用下推自動機(jī)的方式實(shí)現(xiàn).
使用一個二維分析表和棧聯(lián)合進(jìn)行控制來實(shí)現(xiàn)遞歸下降分析技術(shù).
分析表A實(shí)際上是一個從VN (VT {#})到規(guī)則的映射.當(dāng)自頂向下分析過程中需要將U展開時,如果當(dāng)前符號為T時,應(yīng)該選擇規(guī)則A[U,T].如果A[U,T]為空,表示輸入符號串不正確.
預(yù)測分析過程
PUSH(S,#);PUSH(S,Z);
a=下一個符號;X=TOP(S);
如果X為終結(jié)符號且a==X且a!=#,POP(S); a=下一個符號.
如果X為終結(jié)符號且a==X且a==#,分析結(jié)束,接受句子.
如果X為終結(jié)符號且a!=X,出錯處理.
預(yù)測分析過程
如果X為非終結(jié)符號且A[X,a]為報錯標(biāo)識,出錯處理.
如果X為非終結(jié)符號且A[X,a]='X= X1 X2…Xn1 ,
{ POP(S);
將右部Xn …X2 X1壓入S中.
}
例子
文法G4.3'[E]
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
例子
i
+
*
)
#
(
E
TE'
TE'
E'
+TE'


T
FT'
FT'
T'

FT'


F
i
(E)
i+i*i# 
i+i*i#
+i*i#
i*i#
+i*i#
i+i*i#
+i*i#
i+i*i# 
i*i#
i*i#
*i#
#E
#E'T
#E'T'F
#E'T+
#E'T
#E'T'
#E'T'i
#E'
#E'T'i
#E'T'F
#E'T'
預(yù)測分析表的生成
從前面的論述我們看到,預(yù)測分析過程的驅(qū)動程序時固定的.對于某個文法,分析表是分析過程的核心.
表中A[U,T]='U::=X1X2…Xn'表示對應(yīng)于X1X2…Xn字的首符號可以是T.就是說X1X2…Xn=>*Tw.我們可以通過這個方式來確定分析表中的值.
預(yù)測分析表的生成
一般來講,對于一個符號串X1X2…Xn的字的第一個終結(jié)符號就是X1對應(yīng)的字的第一個終結(jié)符號.但是空規(guī)則的存在使情況有一點(diǎn)復(fù)雜.
對于U1U2…Un,如果U1=>* ,那么符號串對應(yīng)的字的首符號也可以是U2對應(yīng)的字的首符號.計(jì)算一個符號串對應(yīng)的字的首符號的算法也需要考慮到這些.
FIRST(u)和FOLLOW(U)
FIRST(u)={T|u=>*T…,T VT},如果u=>* ,那么,我們規(guī)定 FIRST(u).
FOLLOW(U)={T|Z=>* … UT…, T VT {#}}其中,如果Z=>*…U,那么# FOLLOW(U)
直觀地講:
FIRST(u)包含了u對應(yīng)的字的所有可能的首終結(jié)符號.
FOLLOW(U)表示了句型中可能緊跟再U后面的終結(jié)符號
FIRST(u) 構(gòu)造算法
對于文法X構(gòu)造FIRST(X)
步驟1:如果X VT,那么FIRST(X)={X}
步驟2:如果X VN,且有規(guī)則X::=T…,那么將T添加到FIRST(X)中.如果X::= ,那么 也再FIRST(X)中.
步驟3:對于規(guī)則X::= X1X2…Xn,把FIRST(X1)中的非 符號添加到FIRST(X)中.如果 在FIRST(X1)中,把FIRST(X2)中的非 符號添加到FIRST(X)中…;如果 在FIRST(Xn)中,把 添加到FIRST(X)中.
對于FIRST(u),可是使用類似于步驟3的方法求解得到.
FIRST的例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
FIRST(F)={ (,i }
FIRST(T)=FIRST(F)= { (,i }
FIRST(E')={ +, } FIRST(T')={*, }
… … … … 
FOLLOW(U)的構(gòu)造算法
步驟1 # FOLLOW(Z)
步驟2 如果有規(guī)則U::=xWy,那么FIRST(y)中所有的非 符號都在FOLLOW(W)中.
步驟3 如果有規(guī)則U::=xW或則 U::=xWy且 FIRST(y),那么FOLLOW(U)中的一切符號都在FOLLOW(W)中.
注意:步驟3需要重復(fù)執(zhí)行,直到?jīng)]有哪個非終結(jié)符號的FOLLOW集合增長為止.
FOLLOW例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
FOLLOW(E)={#,)}
FOLLOW(E')=FOLLOW(E)={#,)}
FOLLOW(T)=FIRST(E') FOLLOW(E)-{ }={+,#,)}
FOLLOW(T')=FOLLOW(T)= { }={+,#,)}
FOLLOW(F)=FIRST(T') FOLLOW(T)= {+,#,),*}
預(yù)測分析表的構(gòu)造
基本思想:
當(dāng)我們需要將U選擇某個規(guī)則展開時,如果當(dāng)前的輸入為a,表示我們要將U展開為以a為首符號的字.如果有規(guī)則U::=u,且a FIRST(u),那么表示這個規(guī)則是個好的選擇.
分析表構(gòu)造算法
對于每個規(guī)則U::=u,執(zhí)行一下步驟
對于每個終結(jié)符號a FIRST(u),A[U,a]='U::=u'.
如果 FIRST(u),對于每個FOLLOW(U)中的每個終結(jié)符號b或#,讓A[U,b]='U::= u'.
將其它未定義的分析表元素為ERROR.
分析表的例子
文法G4.3'[E]:
E::=TE' E'::=+TE'| T::=FT'
T'::=*FT'| F::=(E)|i
i
+
*
)
#
(
E
TE'
TE'
E'
TE'


T
FT'
FT'
T'

FT'


F
i
(E)
分析表的沖突
文法G4.6[S] S::=iCtSS'|a S'::=eS| C::=b
FIRST(iCtSS')={i} FIRST(eS)={e} 
FIRST(S)={i,a} FIRST(C)={b}
FIRST(S')={e, }
FOLLOW(S)=FOLLOW(S')={#,e}
a
b
e
i
t
#
S
a
iCtSS'
S'
eS; 
C
b

LL(1)文法
定義:如果其預(yù)測分析表中沒有多重定義的元素,則該文法被稱為LL(1)文法.
LL(1)文法是無二義性的.
定理4.1,文法G是LL(1)的,當(dāng)且僅當(dāng)每個非終結(jié)符號U的任何兩個不同的重寫規(guī)則U::=x | y滿足如下條件:
FIRST(x) FIRST(y)= 
x=>* 和y=>* 不能同時成立
如果y=>* ,那么FIRST(x) FOLLOW(U)= 
對于BNF表示法的處理
如果在規(guī)則的右部是使用BNF表示的,那么使用自頂向下技術(shù)進(jìn)行處理時,需要作出相應(yīng)的變化.
預(yù)測分析法:修改文法,消除BNF表示.
遞歸子程序法:處理規(guī)則右部的過程有所改變.
例子
E ::= T {+T} T::= F {*F}
F ::= i | (E)
LL(1)的處理方法
修改方法:
對于每個{x},引入新的非終結(jié)符號U::=xU | 空.
對于每個[x],引入新的非終結(jié)符號U::= x | 空.
修改文法得到:
E ::= T E' E' ::= +TE' | 空
T ::= F T' T' ::= * F T' |空
F ::= i | (E)
然后可以使用LL(1)技術(shù)來處理.
遞歸子程序法
理論上,可以和LL(k)方法處理BNF表達(dá)式同樣處理.但是,遞歸子程序法可以使用更加直接的方法.
對于規(guī)則右部X1X2…{Xk Xk+1}…Xn的處理方式為
X1的處理; X2的處理;…
while (Xk Xk+1循環(huán)繼續(xù) )
{Xk的處理,Xk+1的處理}
…; Xn的處理
在判斷是否繼續(xù)循環(huán)的時候,判斷的是,下一個符號究竟在first(XkXk+1)中,還是在first(Xk+2Xk+3…)中.