第五章自上而下的語(yǔ)法

1、n本章內(nèi)容本章內(nèi)容：從識(shí)別符號(hào)出發(fā)，不斷建立直接推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串相同的符號(hào)串。從語(yǔ)法樹的角度看，自頂向下分析過(guò)程是以識(shí)別符號(hào)為根結(jié)點(diǎn)根結(jié)點(diǎn)，試圖向下構(gòu)造一棵語(yǔ)法樹，使其末端結(jié)點(diǎn)符號(hào)串正好與輸入符號(hào)串相同。n基本知識(shí)點(diǎn)基本知識(shí)點(diǎn)：自上而下語(yǔ)法分析的基本思想和面臨的問題，消除左遞歸的方法，避免回溯對(duì)文法的要求，遞歸子程序法，LL(1)分析法。n重點(diǎn)重點(diǎn)：消除左遞歸的方法，遞歸子程序的構(gòu)造方法，LL(1)文法，LL(1)分析表的構(gòu)造方法。n難點(diǎn)難點(diǎn)：符號(hào)串的FIRST集合的求法，文法非終結(jié)符號(hào)FOLLOW集合的求法以及LL(1)分析,表的構(gòu)造。第五章第五章 自頂

2、向下語(yǔ)法分析自頂向下語(yǔ)法分析n文法有03型四種，語(yǔ)法分析方法有兩種：自頂向下和自下而上自頂向下和自下而上 自頂向下分析過(guò)程: 為輸入串從開始符開始構(gòu)造語(yǔ)法樹從文法開始符出發(fā)向下推導(dǎo)，推出句子。自頂向下語(yǔ)法分析自頂向下語(yǔ)法分析5.1 確定的自頂向下分析見例5.1S p AS q BA c A dA aW=pccadd輸入串:特點(diǎn):1,產(chǎn)生式右部由終結(jié)符開始;2,相同左部的產(chǎn)生式其右部由不同終結(jié)符開始特點(diǎn):1,產(chǎn)生式右部不全由終結(jié)符開始;2,相同左部的產(chǎn)生式其右部由不同終結(jié)符或非終結(jié)符開始;3,文法無(wú)空產(chǎn)生式產(chǎn)生式右部串的第一個(gè)符號(hào)產(chǎn)生式右部串的第一個(gè)符號(hào)即即frist需要看后跟符號(hào)即follow

3、自頂向下分析總是根據(jù)當(dāng)前句型中的符號(hào)和當(dāng)前輸入的符號(hào)決定下一步應(yīng)執(zhí)行的分析動(dòng)作。如果句型中當(dāng)前為終結(jié)符且與輸入符號(hào)匹配，則讀下一個(gè)輸入符號(hào)；如果當(dāng)前為非終結(jié)符號(hào)，則根據(jù)輸入符號(hào)選擇該非終結(jié)符的一個(gè)產(chǎn)生式進(jìn)行下一步推導(dǎo)，為了分析方便，能夠?qū)斎氪_定句型所選擇的產(chǎn)生式需要定義兩個(gè)集合：即文法符號(hào)串的首符號(hào)集First和非終結(jié)符的后跟符號(hào)集Follow。首符號(hào)集的定義首符號(hào)集的定義:n設(shè)G=（VN、VT、P、S）是上下文無(wú)關(guān)文法，則該文法的符號(hào)串的開始符號(hào)集為：nFIRST（ ）=a| * a，aVT，、V*n若 * ，則 FIRST（ ）設(shè)設(shè)是文法是文法G的任一符號(hào)串，定義的任一符號(hào)串，定義的首

4、符號(hào)集的首符號(hào)集first()是由是由推導(dǎo)出來(lái)的串中作為第一個(gè)符號(hào)的推導(dǎo)出來(lái)的串中作為第一個(gè)符號(hào)的所有終結(jié)符的集合；如果所有終結(jié)符的集合；如果*，則則 first()first()。即:為了求出給定文法關(guān)于符號(hào)X的首符號(hào)集首符號(hào)集first(X)first(X)，應(yīng)用下列規(guī)則，直到再?zèng)]有任何終結(jié)符號(hào)或能加到該首符號(hào)集為止。 求首符號(hào)集求首符號(hào)集:(1)(1)如果如果X X是終結(jié)符，則是終結(jié)符，則first(X)=Xfirst(X)=X。(2)(2)如果如果XX是一個(gè)產(chǎn)生式，則是一個(gè)產(chǎn)生式，則 first(X) first(X)。(3)(3)如果如果X X是非終結(jié)符，并且是非終結(jié)符，并且XYXY

5、1 1Y Y2 2Y YK K是一個(gè)產(chǎn)生是一個(gè)產(chǎn)生式，對(duì)某一個(gè)式，對(duì)某一個(gè)i i若有若有Y Y1 1Y Y2 2Y Yi i- -1 1* * 且且afirst(Yafirst(Yi i) )，則則afirst(X)afirst(X)；如果如果first(Yfirst(Yj j) )，j=1j=1，2 2，kk，則把則把加入加入first(X)first(X)。例如，例如，first(Yfirst(Y1 1) )中的每個(gè)元素都屬于中的每個(gè)元素都屬于first(X)first(X)；如果如果Y Y1 1不能推導(dǎo)出不能推導(dǎo)出，則則first(X)=first(Yfirst(X)=first(Y1

6、1) )； 如果如果Y Y1 1* *，則則把把first(yfirst(y2 2) )加入加入first(X)first(X)。 后跟符號(hào)集的定義后跟符號(hào)集的定義:n設(shè)G=（VN、VT、P、S）是上下文無(wú)關(guān)文法，AVN ，S是開始符號(hào)，則文法符號(hào)A的后跟符號(hào)集為：nFOLLOW（A）=a|S * A 且 aVT，aFIRST（），VT*，V+ n若S * A，且 * ，則# FOLLOW（A） 設(shè)設(shè)A為一個(gè)非終結(jié)符號(hào)，定義為一個(gè)非終結(jié)符號(hào)，定義A的后隨符號(hào)集的后隨符號(hào)集follow(A)為任為任意句型中緊跟在意句型中緊跟在A之后出現(xiàn)的所有終結(jié)符號(hào)的集合。之后出現(xiàn)的所有終結(jié)符號(hào)的集合。即：即：

7、若存在推導(dǎo)S * Aa， 、是任意語(yǔ)法符號(hào)串，follow(A)為所有可能的終結(jié)符號(hào)a的集合。應(yīng)該注意，在推導(dǎo)過(guò)程中，在A和a之間可能出現(xiàn)其它符號(hào)串，但推導(dǎo)的結(jié)果 * ，這樣，仍然有a follow(A)。 對(duì)給定的文法對(duì)給定的文法，求其非終結(jié)符A的集合follow(A)，應(yīng)用下列規(guī)則，直到follow(A)不能再加入任何終結(jié)符號(hào)為止。(1)若A是開始符號(hào)，則輸入符號(hào)的結(jié)束標(biāo)志#follow(A)。(2)如果存在產(chǎn)生式BA，則把first()除之外的所有符號(hào)加入follow(A)。(3)如果存在產(chǎn)生式BA或 BA，且first()包含,即 ，則把 follow(B) 加入 follow(A)。

8、 選擇集合SELECT:n給定上下文無(wú)關(guān)文法的產(chǎn)生式A （ AVN， V* ），n若 * ，則SELECT( A )= FIRST（ ）n若 * ，則SELECT（ A ）= (FIRST（ ）) FOLLOW（A）即即設(shè) A 是文法G的任意產(chǎn)生式，該產(chǎn)生式的選用集定義如下：1)若 ,且不存在推導(dǎo) +,則產(chǎn)生式A 的選用集select(A )= first()2) 若 ,但存在推導(dǎo) +, 則產(chǎn)生式A 的選用集select(A )= first() follow(A)3) 若 = ,即產(chǎn)生式為A , 則其選用集select(A )= follow(A) LL（1）文法的定義n一個(gè)上下文無(wú)關(guān)文法是

9、LL（1）文法的充要條件是：n對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式， A A ，滿足SELECT（A） SELECT（A ）= ，其中、不能同時(shí) * 即關(guān)于任一非終結(jié)符的不同產(chǎn)生式其選用集互不相交，則稱G為L(zhǎng)L(1)文法。 判斷某一文法是否是LL(1)文法的步驟1、求出文法中所有能推出的非終結(jié)符號(hào)；2、計(jì)算文法中每一個(gè)產(chǎn)生式右部符號(hào)串的FIRST集；3、計(jì)算文法中每一個(gè)非終結(jié)符號(hào)的FOLLOW集；4、根據(jù)定義計(jì)算文法中每一個(gè)產(chǎn)生式的SELECT集；5、計(jì)算文法中具有相同左部產(chǎn)生式的SELECT集的交集，根據(jù)LL（1）文法定義確定該文法是否為L(zhǎng)L（1）文法。補(bǔ)充例：5.2 LL(1) 文法的判別n提

10、取左公共因子文法中，如果同一非終極符的不同可選右部包含相同的前綴，則在最左推導(dǎo)過(guò)程中，對(duì)同一輸入符號(hào)不能唯一地確定應(yīng)該使用的產(chǎn)生式，于是只能嘗試，造成回溯5.3 非LL(1)文法的等價(jià)變換 結(jié)論n產(chǎn)生式中含有左遞歸的文法不是LL（1）文法n相同左部的產(chǎn)生式中含有左公共因子的文法不是LL（1）文法左公共因子一般地如有產(chǎn)生式：A 12 n 當(dāng)輸入符號(hào)為從推導(dǎo)出來(lái)的非空串時(shí)，則不能立即決定使用產(chǎn)生式 A 1 ，還是2 ，在此情況下，為了避免回溯，把產(chǎn)生式改寫為： A A A 1 2 n 其中稱為左公因子。于是，對(duì)當(dāng)前非終極符A若輸入為中推導(dǎo)出來(lái)的串，則唯一地使用產(chǎn)生式A A。 對(duì)文法中一切左遞歸的消

11、除要求文法中不含回路即無(wú)A+ A的推導(dǎo)。滿足這個(gè)要求的充分條件是:文法中不包含形如文法中不包含形如A A 的有害規(guī)則的有害規(guī)則和和 A 的空產(chǎn)生式的空產(chǎn)生式. 左遞歸直接左遞歸的形式為：A A1 A2 Am12 n 消除左遞歸后可改寫為：A1 A 2 A n AA1 A 2A m A回溯：回溯是指否定前面的工作而退回到某環(huán)節(jié)重新做起。左遞歸n消除直接左遞歸消除間接左遞歸消除文法中所有左遞歸 消除左遞歸 如何消除一個(gè)文法的一切左遞歸呢？如果一個(gè)文法不含回路(形如A=+A的推導(dǎo))，且產(chǎn)生式的右部也不含的候選式，那么，下述算法將消除文法的左遞歸： (1) 將文法GS的所有非終結(jié)符按一給定的順序排列：

12、A1、A2、An ； (2) 執(zhí)行下述循環(huán)語(yǔ)句將間接左遞歸改為直接左遞歸： for (i=1;i=n;i+) for (j=1;j1)在實(shí)際中極少使用。對(duì)給定的輸入串按照LL(1)文法進(jìn)行分析，其分析器模型模型如下: 輸入緩沖區(qū) 輸入緩沖區(qū)：存放要分析的詞匯串分析棧：存放當(dāng)前句型中尚待分析的文法符號(hào)分析表M：是個(gè)矩陣。每行對(duì)應(yīng)文法的一個(gè)非終極符A A，每列對(duì)應(yīng)終極符號(hào)a a，矩陣MAMA，aa表示當(dāng)前棧頂為A A、輸入符號(hào)為a a時(shí)應(yīng)選用的產(chǎn)生式LL（1）分析算法分析算法 LL（1）分析表分析表MMXYZ a + b # 分析棧分析棧 輸出輸出#n預(yù)測(cè)分析程序n先進(jìn)后出棧n預(yù)測(cè)分析表預(yù)測(cè)分析器

13、組成預(yù)測(cè)分析器組成（1）如果 X = a = #，算法結(jié)束并報(bào)告分析成功。接受輸入串（2）如果 X = a #，則從棧中彈出X，并使緩沖區(qū)指針前進(jìn)到下一個(gè)輸入符號(hào)。（3）如果X是一個(gè)非終極符，則查分析表，若MA，a為X的產(chǎn)生式，用該產(chǎn)生式右部的逆替換棧頂符號(hào)，否則出錯(cuò)。 LL（1）分析算法執(zhí)行如下：分析算法執(zhí)行如下： LL(1)分析算法輸入：串w, 文法G的分析表M輸出：如果w L（G）則產(chǎn)生w的最左推導(dǎo)，否則輸出錯(cuò)誤信息。方法：初態(tài)時(shí)，分析棧為 #S ，棧頂S是文法的開始符號(hào)；緩沖區(qū)為 w #。分析器按下列操作進(jìn)行語(yǔ)法分析：1） Push #,S；指針 ip 指向串 w # 的第一個(gè)符號(hào)；2

14、） repeat3） 令X為棧頂符號(hào)，a為ip所指的符號(hào)；4） if X 為終結(jié)符或# then5） if X = a = # then 接收 w6） else if X = a # then 彈出 X，并使ip前進(jìn)7） else error8） else /* X為非終結(jié)符 */9） if MX,a = X Y1Y2 Yk then begin10） 彈出X；11） push Yk，Y2，Y1 /* Y1在棧頂 */12） end 13） else error14） until X = # ；/ * 棧為空 */ 預(yù)測(cè)分析程序框圖預(yù)測(cè)分析程序框圖表表5.3 表達(dá)式文法的預(yù)測(cè)分析表表達(dá)式文法的

15、預(yù)測(cè)分析表E E+T |TTT*F|F Fi |(E)例如有文法為例如有文法為: 1.判斷文法是否為判斷文法是否為L(zhǎng)L(1)的的?2.構(gòu)造預(yù)測(cè)分析表構(gòu)造預(yù)測(cè)分析表 i+*()#ETE TE E +TE TFT FT T *FT Fi (E) 表表5.4 表達(dá)式文法的預(yù)測(cè)分析表表達(dá)式文法的預(yù)測(cè)分析表步驟步驟分析棧分析棧剩余輸入串剩余輸入串所用產(chǎn)生式所用產(chǎn)生式1234567891011121314151617# E# ET# ETF# ETi# ET# E# ET+# ET# ETF# ETi# ET# ETF # ETF# ETi# E T# E#i + i * i#i + i * i#i + i * i #i + i * i#+ i * i #+ i * i #+ i *