1、第第 5 5 講講西北農林科技大學本科教程西北農林科技大學本科教程 主講教師：趙建邦主講教師：趙建邦 第三章第三章 語法分析語法分析l3.1 3.1 文法和語言文法和語言l3.2 3.2 推導與語法樹推導與語法樹l3.3 3.3 自頂向下的語法分析自頂向下的語法分析l3.4 3.4 自底向上的語法分析自底向上的語法分析l3.5 3.5 規范規約的自底向上語法分析方法規范規約的自底向上語法分析方法u第三章第三章語法分析語法分析l3.2 3.2 推導與語法樹推導與語法樹l推導與短語推導與短語l語法樹與二義性語法樹與二義性u重點掌握重點掌握l短語、句柄的概念短語、句柄的概念l二義性的消除二義性的消除

2、本講目標本講目標 u3.2.1 推導與短語推導與短語1、規范推導、規范推導在在3.1.1節中，所給句子節中，所給句子i+i*i推導序列中的每一步推導都是對推導序列中的每一步推導都是對句型中的句型中的最右非終結符最右非終結符用相應產生式的右部進行替換，這樣用相應產生式的右部進行替換，這樣的推導稱為的推導稱為最右最右推導推導（規范推導），（規范推導），規范推導的逆過程稱為規范推導的逆過程稱為規范規約規范規約如果如果每一步推導都是對句型中的最左非終結符用相應產生式每一步推導都是對句型中的最左非終結符用相應產生式的右部進行替換，則稱為的右部進行替換，則稱為最左最左推導推導3.2 3.2 推導與語法樹推

3、導與語法樹舉例：舉例：文法GE：EE+E | E*E | (E) | i (3.1) 句子i+i*i的最左推導和最右推導？u3.2.1 推導與短語推導與短語2、短語、短語設設是文法是文法GS的一個句型，如果有：的一個句型，如果有：則稱則稱是句型是句型關于非終結符關于非終結符A的一個的一個短語短語，或稱，或稱是是的的一個一個短語短語。特別是有。特別是有A產生式時，產生式時，為句型為句型的一個的一個直接直接短語短語或或簡單簡單短語短語 短語短語的兩個條件缺一不可。僅有的兩個條件缺一不可。僅有A 未必意味著未必意味著就是句型就是句型的一個短語，還需要的一個短語，還需要有有 加以限制；即短語屬加以限制

4、；即短語屬于句型的組成部分。于句型的組成部分。3.2 3.2 推導與語法樹推導與語法樹A且AS* AS*u3.2.1 推導與短語推導與短語3、句柄、句柄一個句型的最左直接短語稱為該句型的一個句型的最左直接短語稱為該句型的句柄句柄。注意，一個句。注意，一個句型的直接短語可能不只一個，但型的直接短語可能不只一個，但最左直接短語則是惟一的最左直接短語則是惟一的。3.2 3.2 推導與語法樹推導與語法樹舉例：舉例：文法GE：SAB A bB B Sb | a 句型“baSb”的短語和句柄？解答解答：（1）baSbbaBbBBABS SS*A且AS* baSbS句型本身是該句型關于開始符號的短語句型本身

5、是該句型關于開始符號的短語最左推導u3.2.1 推導與短語推導與短語3.2 3.2 推導與語法樹推導與語法樹解答解答：（2）baSbbaBbBBABS baBS*A且AS* SbB句型baSb的子串Sb,是該句型相對于非終結符B的一個短語，而且是該句型的直接短語 （3）baSbbBSbASbABS bBSbS*aB最右推導句型baSb的子串a, 是該句型相對于非終結符B的一個短語，而且是該句型的直接短語、句柄最左推導u3.2.1 推導與短語推導與短語3.2 3.2 推導與語法樹推導與語法樹解答解答：（4）A且AS* baSbbBSbASbABS ASbS*baA最右推導句型baSb的子串ba,

6、 是該句型相對于非終結符A的一個短語注意：注意：短語、直接短語、句柄短語、直接短語、句柄都是針對某一都是針對某一句型句型來說的，來說的，都是指句型中的哪些符號串能夠構成短語、直接短語、句都是指句型中的哪些符號串能夠構成短語、直接短語、句柄。柄。脫離句型，談論三者是無意義的。脫離句型，談論三者是無意義的。例例5.2 文法文法G G E T | E +T T F | T * F F i |（E）i i1 1* *i i2 2+i+i3 3 是文法是文法G G的一個句型嗎？的一個句型嗎？如果是，求出其句柄。如果是，求出其句柄。u3.2.1 推導與短語推導與短語4、素短語、素短語含有終結符的短語，如果

7、它不存在也具有同樣性質的真子串含有終結符的短語，如果它不存在也具有同樣性質的真子串（不能包含有另一個素短語），則該短語為（不能包含有另一個素短語），則該短語為素素短語短語 (1)是短語是短語 (2)至少包含一個終結符至少包含一個終結符 (3)不再包含其它素短語不再包含其它素短語例如，在例如，在 中中，i i、E E* *i i和和E+EE+E* *i i是句型是句型E E+ +E E* *i i的的三個短語；其中三個短語；其中i i為素短語；為素短語；E E* *i i雖為短語且含有終結符，但雖為短語且含有終結符，但它的真子串它的真子串i i是素短語，故是素短語，故E E* *i i不是素短語

8、；同樣不是素短語；同樣E+EE+E* *i i也不是也不是素短語。素短語。 3.2 3.2 推導與語法樹推導與語法樹u3.2.1 推導與短語推導與短語4、素短語、素短語(練習練習) 3.2 3.2 推導與語法樹推導與語法樹E+TE+TETF*FTi先找短語：先找短語：T、T*F 、 T+T*F 、 i 、 T+T*F+i 再找素短語：再找素短語：T*F 、 iE+EE*EEi先找短語：先找短語：i 、E*i 、 E+E*i 再找素短語：再找素短語：iu3.2.2 語法樹與二義性語法樹與二義性對程序語言來說，有兩個問題需要解決：對程序語言來說，有兩個問題需要解決： (1)(1)判別程序在語法上是

9、否正確；判別程序在語法上是否正確； (2)(2)句子的識別或分析。句子的識別或分析。在編譯方法中，為了便于識別或分析句子而引入了在編譯方法中，為了便于識別或分析句子而引入了語法樹語法樹這一重這一重要的輔助工具要的輔助工具語法樹語法樹以圖示化的形式把句子分解成各個組成部分來描述或以圖示化的形式把句子分解成各個組成部分來描述或分析分析句子的語法結構句子的語法結構，這種圖示化的表示與所定義的文法規則完全一，這種圖示化的表示與所定義的文法規則完全一致，但更為直觀和完整致，但更為直觀和完整3.2 3.2 推導與語法樹推導與語法樹u3.2.2 語法樹與二義性語法樹與二義性1、語法樹、語法樹(定義定義)對文

10、法對文法GS=(VT, VN, S, )，滿足下列條件的樹稱為，滿足下列條件的樹稱為GS的的語語法樹法樹：(1) 每個結點用每個結點用GS的一個終結符或非終結符標記；的一個終結符或非終結符標記；(2) 根結點用文法開始符根結點用文法開始符S標記標記； (3) 內部結點內部結點(指非樹葉結點指非樹葉結點)一定是非終結符一定是非終結符，如果某內部結，如果某內部結點點A有有n個分支，它的所有子結點從左至右依次標記為個分支，它的所有子結點從左至右依次標記為x1、x2、xn，則，則Ax1x2xn一定是文法一定是文法GS的一條產生式的一條產生式； (4) 如果某結點標記為如果某結點標記為，則它必為葉結點且

11、是其父結點的惟，則它必為葉結點且是其父結點的惟一子結點。一子結點。3.2 3.2 推導與語法樹推導與語法樹圖圖3-4 句子句子i+i*i的語法樹的語法樹1、開始符S作為根結點3.2 3.2 推導與語法樹推導與語法樹2、父親節點是產生式左部，孩子節點對應產生式右部“EE+E”3、在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的樹葉結點自左至右排列起來就是一個句型。4、一棵已經完成的語法樹無法判斷是來自于最左推導還是最右推導，而使用文法規則的推導過程是有先后之分的。如果堅持使用最左(或最右)推導，那么一棵語法樹就完全等價于一個最左(或最右)推導u3.2.2 3.2.2 語法樹與二義性語法樹與二

12、義性2 2、子樹與短語、子樹與短語語法樹某個結點連同它的所有后代組成了一棵語法樹某個結點連同它的所有后代組成了一棵子樹子樹。只含有。只含有單層分枝的子樹稱為單層分枝的子樹稱為簡單子樹簡單子樹。子子樹與短語的關系十分密切，根據子樹的概念，句型的短語、樹與短語的關系十分密切，根據子樹的概念，句型的短語、直接短語、句柄和素短語的直觀解釋如下直接短語、句柄和素短語的直觀解釋如下： ( (1)1) 短語：短語：子樹的末端結點子樹的末端結點( (即樹葉即樹葉) ) 組成組成的符號串是相對于子樹根的短語的符號串是相對于子樹根的短語； ( (2 2) ) 直接直接短語短語：簡單子樹的：簡單子樹的末端結點末端結

13、點 組成組成的符號串是相對于簡單子樹根的符號串是相對于簡單子樹根的的 直接直接短語短語3.2 3.2 推導與語法樹推導與語法樹SABbBaSbu3.2.2 3.2.2 語法樹與二義性語法樹與二義性2 2、子樹與短語、子樹與短語 (3) (3) 句柄：句柄：最左簡單子樹的最左簡單子樹的末端末端 結點結點組成的符號串為句柄組成的符號串為句柄； (4) (4) 素素短語短語：子樹的末端結點子樹的末端結點組組 成成的符號串含終結符，且的符號串含終結符，且在在 該該子樹中不再有包含終結符的更小子子樹中不再有包含終結符的更小子樹樹顯然顯然，從語法樹出發尋找短語、直接短語、句柄和素短語要直，從語法樹出發尋找

14、短語、直接短語、句柄和素短語要直觀得多觀得多。注意。注意: :子樹末端結點組成的符號串子樹末端結點組成的符號串是指由該子樹根開始是指由該子樹根開始向下生長的向下生長的所有所有末端結點末端結點( (即樹葉即樹葉) )，該子樹的部分末端結點并，該子樹的部分末端結點并不是該子樹的短語。不是該子樹的短語。3.2 3.2 推導與語法樹推導與語法樹SABbBaSb圖3-5 E+E*i的語法樹3.2 3.2 推導與語法樹推導與語法樹圖3-6 E+E+E*i的語法樹直接短語、句柄、素短語不是短語直接短語u3.2.2 3.2.2 語法樹與二義性語法樹與二義性3 3、語法的二義性、語法的二義性對于文法任一句型的推

15、導序列，總能為其構造一棵語法樹，對于文法任一句型的推導序列，總能為其構造一棵語法樹，那么文法的某個句型是否只對應一棵唯一的語法樹呢？那么文法的某個句型是否只對應一棵唯一的語法樹呢？也就也就是它是否只有唯一的一個最左（最右）推導呢？是它是否只有唯一的一個最左（最右）推導呢？對于文法對于文法(3.1)，句子，句子i+i*i存在兩種最左（最右）推導，形成兩存在兩種最左（最右）推導，形成兩棵不同的語法樹棵不同的語法樹:3.2 3.2 推導與語法樹推導與語法樹最左推導最左推導1 1 i*iiE*iiE*EiEiEEE 最左推導最左推導2 2 i*iiE*iiE*EiE*EEE*EE 圖3-7 句子i+i

16、*i的兩棵不同的語法樹3.2 3.2 推導與語法樹推導與語法樹u3.2.2 3.2.2 語法樹與二義性語法樹與二義性3 3、語法的二義性、語法的二義性u3.2.2 3.2.2 語法樹與二義性語法樹與二義性3 3、語法的二義性、語法的二義性再如，條件語句的文法再如，條件語句的文法GSGS為為 GSGS: S: Sif b Sif b S S Sif b S else Sif b S else S S Sa a定義：文法定義：文法GSGS的一個句子如果能找到的一個句子如果能找到兩種不同的最左推導兩種不同的最左推導( (或最右推導或最右推導) )，或者或者存在兩棵不同的語法樹存在兩棵不同的語法樹，則

17、稱這個句子，則稱這個句子是是二義性二義性的。一個文法如果包含二義性的句子，則這個文法的。一個文法如果包含二義性的句子，則這個文法是是二義文法二義文法，否則是無二義文法。，否則是無二義文法。3.2 3.2 推導與語法樹推導與語法樹句子句子 if b if b a else a if b if b a else a 的兩棵不同語法樹的兩棵不同語法樹, ,請畫出對應的兩棵語法樹請畫出對應的兩棵語法樹u3.2.2 3.2.2 語法樹與二義性語法樹與二義性4 4、文法二義性的消除、文法二義性的消除對于一個二義性文法對于一個二義性文法GS，如果能找到一個非二義性文法，如果能找到一個非二義性文法GS，使得，

18、使得L(G)=L(G)，則該二義性文法的二義性是，則該二義性文法的二義性是可以消可以消除的除的。如果找不到這樣的。如果找不到這樣的GS，則二義性文法描述的語言為，則二義性文法描述的語言為先天二義性先天二義性的的。文法二義性消除方法：文法二義性消除方法： (1)不改變文法中原有的語法規則，僅增加一些語法的非形式不改變文法中原有的語法規則，僅增加一些語法的非形式規定；規定； (2)構造一個等價的無二義性文法，把排除二義性的規則合并構造一個等價的無二義性文法，把排除二義性的規則合并到原有文法中，改寫原有的文法。到原有文法中，改寫原有的文法。(增加新的非終結符增加新的非終結符)3.2 3.2 推導與語

19、法樹推導與語法樹u3.2.2 3.2.2 語法樹與二義性語法樹與二義性4、文法二義性的消除、文法二義性的消除例：將例：將文法文法(3.1)改寫為無二義性的文法改寫為無二義性的文法GE如下如下： GE: EE+T | T TT*F | F F (E) | i此時此時，句子，句子 i+i*i 就就只有只有如圖如圖3-9所示的惟一一棵語法所示的惟一一棵語法樹：樹：3.2 3.2 推導與語法樹推導與語法樹例例3.6 試將如下的二義性文法試將如下的二義性文法GS的二義性消除：的二義性消除：GS: Sif b S | if b S else S | a解答解答 消除GS的二義性可采用如下兩種方法：(1) 不改變已有規則，僅加進一項非形式的語法規定：