《語(yǔ)法分析-自上而下分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《語(yǔ)法分析-自上而下分析.ppt（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第四章語(yǔ)法分析-自上而下分析,,2,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,,4.1語(yǔ)法分析器的功能4.2自上而下分析面臨的問(wèn)題4.3LL(1)分析法?一、直接左遞歸的消除?二、提取左因子、消除回溯?三、LL(1)分析法4.4遞歸下降分析程序構(gòu)造4.5LL(1)分析中的錯(cuò)誤處理,主要內(nèi)容：,3,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,4.1語(yǔ)法分析器的功能,語(yǔ)法分析是編譯過(guò)程的核心部分。語(yǔ)法分析的任務(wù)：在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)言的語(yǔ)法結(jié)構(gòu)用上下文無(wú)關(guān)文法描述。,,4,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,詞法分析器,符號(hào)表,編譯程序后續(xù)部分,語(yǔ)法分析器,,源程序,單詞符號(hào),,,,取下一單詞符號(hào),語(yǔ)法分析樹(shù),,,,,圖4-1語(yǔ)法分析器在編譯程序中的地位,5,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,語(yǔ)法分析器的功能：按照文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。這里所說(shuō)的輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。關(guān)鍵：對(duì)一個(gè)文法，當(dāng)給你一串（終結(jié)）符號(hào)時(shí)，怎樣知道它是不是該文法的一個(gè)句子呢？這就要判斷，看是否能從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出這個(gè)字符串?；蛘?，從概念上講，就是要建立一棵與輸入串相匹配的語(yǔ)法分析樹(shù)。,6,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,語(yǔ)法分析的方法：自上而下分析法基本思想：從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)，從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”，直到根結(jié)。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。自下而上分析法基本思想：從文法的開(kāi)始符號(hào)出發(fā)，根據(jù)文法的產(chǎn)生式規(guī)則正向推導(dǎo)出給定句子的一種方法；或者說(shuō)，從樹(shù)根開(kāi)始，往下構(gòu)造語(yǔ)法樹(shù)，直到建立每個(gè)葉的分析方法。,7,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,4.2自上而下分析面臨的問(wèn)題,顧名思義，自上而下就是從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。帶回溯的分析方法不帶回溯的遞歸子程序（遞歸下降）分析方法自上而下分析的主旨：對(duì)任意輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。,,8,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,這種分析過(guò)程本質(zhì)上是一種試探過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程。例4-1假定有文法：(1)S→xAy(2)A→**|*分析輸入串x*y(記為?)。,9,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,實(shí)現(xiàn)這種自上而下的帶回溯試探法的一個(gè)簡(jiǎn)單途徑是讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸子程序。每個(gè)這種子程序可作為一個(gè)布爾過(guò)程。一旦發(fā)現(xiàn)它的某個(gè)候選與輸入串相匹配，就用這個(gè)候選去擴(kuò)展語(yǔ)法樹(shù)，并返回“真”值；否則，保持原來(lái)的語(yǔ)法樹(shù)和IP值不變，并返回“假”值。,10,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,面臨的問(wèn)題：,首先，是文法的左遞歸性問(wèn)題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P含有左遞歸的文法將使上述的自上而下的分析過(guò)程陷入無(wú)限循環(huán)。即當(dāng)試圖用P去匹配輸入串時(shí)，我們會(huì)發(fā)現(xiàn)，在沒(méi)有識(shí)別任何輸入符號(hào)的情況下，又得重新要求P去進(jìn)行新的匹配。,,11,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,其次，由于回溯就碰到一大堆麻煩事情。如果我們走了一大段錯(cuò)路，最后必須回頭，那么，就應(yīng)把已經(jīng)做的一大堆語(yǔ)義工作推倒重來(lái)。第三，在上述的自上而下分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種成功可能僅是暫時(shí)的。第四，當(dāng)最終報(bào)告分析不成功時(shí)，我們難于知道輸入串中出錯(cuò)的確切位置。最后，由于帶回溯的自上而下分析實(shí)際上采用了一種窮盡一切可能的試探法，因此效率很低，代價(jià)極高。,12,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,一、左遞歸的消除,使用自頂向下的任何一種算法必須消除左遞歸和提取公共左因子。1、直接左遞歸的消除若文法中有形如P→Pα的產(chǎn)生式，則稱直接左遞歸，如A→Ab|a。設(shè)，有P→Pα|β，若α≠ε，β不以P開(kāi)頭（否則不可能消除左遞歸）。則改寫(xiě)為：可消除左遞歸。,4.3LL(1)分析法,,13,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,一般地，若αi≠ε，βj不以P開(kāi)頭，則可改寫(xiě)為：從而消除直接左遞歸。例：S→Sabc|Sab|ab消除直接左遞歸得：,14,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,2、完全消除左遞歸分析雖不含直接左遞歸，但所以含有左遞歸。如果文法G不含回路（），也不含ε產(chǎn)生式，則下列算法可消除左遞歸（完全）,①把G的非終結(jié)符按任意順序排列成P1,…,Pn②fori:=1tondobeginforj:=1toi-1do把形如的規(guī)則改寫(xiě)成，其中；消除關(guān)于的直接左遞歸end;③化簡(jiǎn)由②得到的文法（取消無(wú)用非終結(jié)符產(chǎn)生式）,15,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例：上述文法①排序：S,Q,R②循環(huán)：i=1時(shí)，處理S→Qc|c，消除直接左遞歸，不變i=2時(shí)，處理Q→Rb|b，j=1，把有關(guān)Q的產(chǎn)生式中以S開(kāi)頭的候選式替換（無(wú)），所以不變i=3時(shí)，處理R→Sa|a，j=1，把以S開(kāi)頭的候選式替換，得R→Qca|ca|a,16,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,j=2，把以Q開(kāi)頭的候選式替換，得：R→Rbca|bca|ab|b消除R的直接左遞歸，得：R→bcaR’|abR’|bR’R’→bcaR’|ε③整理：得：S→Qc|cQ→Rb|bR→bcaR’|abR’|bR’R’→bcaR’|ε,17,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,二、提取左因子、消除回溯1、FIRST（?）設(shè)文法G是不含左遞歸的文法，對(duì)其任何非終結(jié)的候選式?定義：FIRST（?）={a|?a?,a∈VT,?,?∈V*}若?ε，則規(guī)定ε∈FRIST（?）,18,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,2．應(yīng)用如果一個(gè)文法G的非終結(jié)符A的多個(gè)候選式之首符集兩兩不相交，那么在自上而下分析時(shí)便可消除回溯。設(shè)，而FIRST(α1),…,FIRST(αn)兩兩不相交，那么當(dāng)分析時(shí)要A去匹配某輸入串時(shí)，便可根據(jù)此輸入串的輸入符號(hào)a,準(zhǔn)確地選用候選式αi（設(shè)a∈FIRST(αi),若ε∈FIRST(αi)以后討論）。,19,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例：文法S→aSb|c，輸入串為aacbb時(shí)：3．公共左因子的提取：把文法改造為每個(gè)非終結(jié)符的所有候選式兩兩不相交的方法是提取公共左因子?？筛脑鞛椋?20,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,三、LL(1)分析法,預(yù)測(cè)分析（LL(1)）法是實(shí)現(xiàn)自上而下分析的另一種有效方法。它使用一個(gè)分析棧和一張分析表。分析表矩陣元素M[A,a]指出非終結(jié)符A，面臨輸入符號(hào)a時(shí)，應(yīng)選用的候選式（或產(chǎn)生式）。若A不該面臨a，則放一出錯(cuò)標(biāo)志。,21,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,1、LL(1)分析法的工作過(guò)程開(kāi)始往棧stack中放“?！保缓蟀盐募_(kāi)始符號(hào)壓棧。預(yù)測(cè)分析程序總是按stack棧頂符號(hào)X和當(dāng)前輸入符號(hào)a行事。①若X=a=”#”，則分析成功，停止分析②若X=a”#”，則把X從棧頂彈出，a指向下一個(gè)輸入符號(hào)③若X∈Vn，則查分析表。若M[X,a]為某候選式，則彈出X，把該候選式反序壓棧；若M[X,a]=ε,則彈出X，什么也不壓；若M[X,a]=error，則報(bào)錯(cuò)。,22,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,為了便于描述分析過(guò)程，我們定義：，代表?xiàng)面臨輸入符號(hào)a采取第i條動(dòng)作后，棧變?yōu)閅。例1．分析i*i#,23,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,2、FIRST集和FOLLOW集的定義設(shè)G=(VT,VN,P，S)是上下文無(wú)關(guān)文法FIRST（?）={a|?a?,a∈VT,?,?∈V*}若?ε則規(guī)定ε∈FRIST（?）FOLLOW（A）={a?S=>*?A?且a∈FRIST（?），?∈V*，?∈V+}若SuA?,且?ε，則#∈FOLLOW(A),24,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,計(jì)算FIRST集,1.若X?V?,則FIRST(X)={X}2.若X?VN,且有產(chǎn)生式X?a…，則把a(bǔ)加入到FIRST(X)中;若X??也是一條產(chǎn)生式,則把?也加到FIRST(X)中.3.若X?Y…是一個(gè)產(chǎn)生式且Y?VN,則把FIRST(Y)中的所有非?元素都加到FIRST(X)中;若X?Y1Y2…YK是一個(gè)產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對(duì)于任何j,1≤j≤i-1,FIRST(Yj)都含有?(即Y1..Y(i-1)?),則把FIRST(Yj)中的所有非?元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj,j=1,2,…,K)均含有?,則把?加到FRIST(X)中.,,25,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,計(jì)算FOLLOW集,1.對(duì)于文法的開(kāi)始符號(hào)S,置#于FOLLOW(S)中;2.若Ａ?αBβ是一個(gè)產(chǎn)生式,則把??FIRST(β)\{?}加至FOLLOW(B)中;3.若Ａ?αB是一個(gè)產(chǎn)生式,或Ａ?αBβ是??一個(gè)產(chǎn)生式而β?(即??FIRST(β)），??則把FOLLOW（A）加至FOLLOW（B）中．,26,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,,一個(gè)文法G是LL（1）的，當(dāng)且僅當(dāng)對(duì)于G的每一個(gè)非終結(jié)符Ａ的任何兩個(gè)不同產(chǎn)生式Ａ?α?β，下面的條件成立：１．FIRST（α）∩FIRST(β)=?,也就是α?和β推導(dǎo)不出以同一個(gè)終結(jié)符a為首的符號(hào)串；它們不應(yīng)該都能推出空字?．２.假若β?，那么，F(xiàn)IRST（α)∩FOLLOW（A）＝?.也就是，若β?.則α所能推出的串的首符號(hào)不應(yīng)在FOLLOW(A）中．．,27,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例：G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>?(4)T–>FT’(5)T’–>*FT’(6)T’–>?(7)F–>(E)(8)F–>a,各非終結(jié)符的FIRST集合如下：FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝,各非終結(jié)符的FOLLOW集合為：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#},28,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例：G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>?(4)T–>FT’(5)T’–>*FT’(6)T’–>?(7)F–>(E)(8)F–>a試判斷文法G是不是LL(1)文法。,分析：E’–>+TE’|?FIRST(+TE’)=｛+｝FOLLOW(E′)=｛)，＃｝T’–>*FT’|?FIRST(*FT’)=｛*｝FOLLOW(T′)=｛+,)，＃｝F–>(E)|aFIRST((E))=｛(｝FIRST(a)=｛a｝所以G[E]是LL（1）的,29,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,3、LL(1)分析表的構(gòu)造,1.對(duì)文法G的每個(gè)產(chǎn)生式Ａ??執(zhí)行第2步和第3步；2.對(duì)每個(gè)終結(jié)符a?FIRST(?)，把Ａ??加??至?[A,a]中，3.若??FIRST(?)，則對(duì)任何b?FOLLOW(A)??把Ａ??加至?[A,b]中，4.把所有無(wú)定義的?[A,a]標(biāo)上“出錯(cuò)標(biāo)志”。可以證明，一個(gè)文法G的預(yù)測(cè)分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的。,30,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例1：文法，試用LL(1)分析法分析輸入串a(chǎn)bbcde。解：①消除左遞歸得文法：②求必要的FIRST和FOLLOW。FIRST(aAcBe)={a}FIRST(bA’)=FIRST(?)={?}FIRST(d)=ievbyqtbddFOLLOW(A’)=FOLLOW(A)={c},31,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,③構(gòu)造LL(1)分析表④分析,32,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,4、LL(1)文法,分析表有多重入口。若一個(gè)文法G的分析表不含多重入口，則稱它為L(zhǎng)L(1)文法。一個(gè)文法是LL(1)的，當(dāng)且僅當(dāng)G的每個(gè)非終結(jié)符A的任何兩個(gè)侯選式α和β有①FIRST(α)∩FIRST(β)=?②若ε?FIRST(β)，則有FIRST(α)∩FOLLOW(A)=?,,33,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,,LL(1)文法的性質(zhì)：LL(1)文法是無(wú)二義的LL(1)文法不含左遞歸非LL(1)文法的改造消除左遞歸提左公因子將產(chǎn)生式Ａ??β|??變換為：Ａ??BB?β|?,34,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,,例1：文法G（E）：E→E+T｜TT→T*F｜FF→i｜(E)FIRST(E)=｛(,i｝FIRST(T)=｛(,i｝FIRST(F)=｛(,i｝消左遞歸E–>TE’E’–>+TE’E’–>?,例2：S→ifCtS|ifCtSeSC→b提左因子S→ifCtSAA→eS|?First集Follow集Sif#,eAe,?#,eCbtM[A,e]={A→eSA→?},,,35,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,4.4遞歸下降分析程序構(gòu)造,一、遞歸子程序法的原理：對(duì)文法中每個(gè)非終結(jié)符U（它們代表一定的語(yǔ)法成分）都編出一個(gè)子程序，以完成該非終結(jié)符號(hào)所對(duì)應(yīng)的語(yǔ)法成分的分析和識(shí)別任務(wù)。每個(gè)非終結(jié)符號(hào)的子程序功能是：用該非終結(jié)符的產(chǎn)生式規(guī)則右部符號(hào)串去匹配輸入串。注：可匹配任何終結(jié)符，但搜索指針不前進(jìn)。使用自上而下的方法時(shí)前提是：消除左遞歸；提取公共左因子。,,,36,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,當(dāng)一個(gè)文法滿足LL(1)條件時(shí)，我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序，這個(gè)分析程序是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。如果用某種高級(jí)語(yǔ)言寫(xiě)出所有遞歸過(guò)程，那就可以用這個(gè)語(yǔ)言的編譯系統(tǒng)來(lái)產(chǎn)生整個(gè)的分析程序。,37,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例如，考慮文法：E→TE?E?→+TE?|?T→FT?T?→*FT?|?F→(E)|i它的每個(gè)非終結(jié)符都有對(duì)應(yīng)的遞歸過(guò)程，在分析過(guò)程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開(kāi)時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。,38,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,幾個(gè)全局過(guò)程和變量,ADVANCE：是指把輸入串指示器IP調(diào)至指向下一個(gè)輸入符號(hào)SYM：是指IP當(dāng)前所指的那個(gè)輸入符號(hào)ERROR：為出錯(cuò)診察處理程序,39,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,對(duì)應(yīng)的遞歸過(guò)程如下：,PROCEDUREE；BEGINT；E?END；,PROCEDUREE?；IFSYM=‘+’THENBEGINADVANCE；T；E?END,40,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,PROCEDURET；BEGINF；T?END,PROCEDURET?；IFSYM=‘*’THENBEGINADVANCE；F；T?END；,41,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,PROCEDUREF；IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCE;E；IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;,42,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,二、文法的另一種表示法,在元符號(hào)“→”和“|”的基礎(chǔ)上，擴(kuò)充幾個(gè)元語(yǔ)言符號(hào)：1.用花括號(hào){?}表示閉包運(yùn)算?*。2.用{?}n0表示?可任意重復(fù)0次至n次。3.用方括號(hào)[?]表示{?}10，即表示?的出現(xiàn)可有可無(wú)(等價(jià)于?|?)。引入上述元符號(hào)的文法亦稱擴(kuò)充的巴科斯范式。,43,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例如，通常的“實(shí)數(shù)”可定義為：decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-用擴(kuò)充的巴科斯范式來(lái)描述語(yǔ)法的好處是，直觀易懂，便于表示左遞歸消去和因子提取。對(duì)于構(gòu)造自上而下分析器來(lái)說(shuō)，采用這種定義系統(tǒng)描述文法顯然是非?？扇〉?。,44,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,例4.5文法E→T|E+TT→F|T*FF→i|(E)可表示成E→T{+T}T→F{*F}F→i|(E)(4.6),45,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,語(yǔ)法圖,可以用語(yǔ)法圖來(lái)表示語(yǔ)言的文法，它顯得更直觀形象。如文法(4.6)可等價(jià)地用如下所示的語(yǔ)法圖來(lái)表示：,46,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,從文法(4.6)出發(fā)可構(gòu)造一組代替前面的遞歸下降分析程序,PROCEDUREE；BEGINT；WHILESYM=‘+’DOBEGINADVANCE；TENDEND；,PROCEDURET；BEGINF；WHILESYM=‘*’DOBEGINADVANCE；FENDEND；,47,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,PROCEDUREF；IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCE;E；IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;,48,2019/12/19,中南大學(xué)軟件學(xué)院陳志剛,4.5LL(1)分析中的一種錯(cuò)誤處理辦法,發(fā)現(xiàn)錯(cuò)誤1棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配2非終結(jié)符A于棧頂，面臨的輸入符為a，但分析表M的M[A,a]為空“應(yīng)急”恢復(fù)策略跳過(guò)輸入串中的一些符號(hào)直至遇到“同步符號(hào)”為止。同步符號(hào)的選擇1把FOLLOW(A)中的所有符號(hào)作為A的同步符號(hào)。跳過(guò)輸入串中的一些符號(hào)直至遇到這些“同步符號(hào)”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號(hào)加到A的同步符號(hào)集，當(dāng)FIRST(A)中的符號(hào)在輸入中出現(xiàn)時(shí)，可根據(jù)A恢復(fù)分析,,