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

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

3、自頂向下分析總是根據當前句型中的符號和當前輸入的符號決定下一步應執行的分析動作。如果句型中當前為終結符且與輸入符號匹配，則讀下一個輸入符號；如果當前為非終結符號，則根據輸入符號選擇該非終結符的一個產生式進行下一步推導，為了分析方便，能夠對輸入串確定句型所選擇的產生式需要定義兩個集合：即文法符號串的首符號集First和非終結符的后跟符號集Follow。首符號集的定義首符號集的定義:n設G=（VN、VT、P、S）是上下文無關文法，則該文法的符號串的開始符號集為：nFIRST（ ）=a| * a，aVT，、V*n若 * ，則 FIRST（ ）設設是文法是文法G的任一符號串，定義的任一符號串，定義的首

4、符號集的首符號集first()是由是由推導出來的串中作為第一個符號的推導出來的串中作為第一個符號的所有終結符的集合；如果所有終結符的集合；如果*，則則 first()first()。即:為了求出給定文法關于符號X的首符號集首符號集first(X)first(X)，應用下列規則，直到再沒有任何終結符號或能加到該首符號集為止。 求首符號集求首符號集:(1)(1)如果如果X X是終結符，則是終結符，則first(X)=Xfirst(X)=X。(2)(2)如果如果XX是一個產生式，則是一個產生式，則 first(X) first(X)。(3)(3)如果如果X X是非終結符，并且是非終結符，并且XYXY

5、1 1Y Y2 2Y YK K是一個產生是一個產生式，對某一個式，對某一個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) )中的每個元素都屬于中的每個元素都屬于first(X)first(X)；如果如果Y Y1 1不能推導出不能推導出，則則first(X)=first(Yfirst(X)=first(Y1

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

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

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

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

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

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

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

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

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

15、預測分析表E E+T |TTT*F|F Fi |(E)例如有文法為例如有文法為: 1.判斷文法是否為判斷文法是否為LL(1)的的?2.構造預測分析表構造預測分析表 i+*()#ETE TE E +TE TFT FT T *FT Fi (E) 表表5.4 表達式文法的預測分析表表達式文法的預測分析表步驟步驟分析棧分析棧剩余輸入串剩余輸入串所用產生式所用產生式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 *