《語法分析自上而下分析.ppt》由會員分享，可在線閱讀，更多相關《語法分析自上而下分析.ppt（96頁珍藏版）》請在裝配圖網上搜索。

1、編譯原理,第四章 語法分析--- 自上而下分析,程 序 設 計 語 言,2,本章在編譯程序中的地位,,表 格 管 理,詞法分析器,語法分析器,語義分析與中間代碼產生,優(yōu)化器,目標代碼生成器,源程序,單詞符號,語法單位,中間代碼,中間代碼,目標代碼,,出 錯 處 理,,,,,,,,,,,,,,,,,,,,,,,,,,,3,回顧：語法分析,任務：在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位，如“短語”、“句子”、 “子句”、“程序段”等，為語法正確的輸入構造語法樹(或分析樹)。 語法分析依據(jù)的是語言的語法規(guī)則，即描述程序結構的規(guī)則，通過語法分析確定整個輸入串是否構成一個語

2、法上正確的程序。 語法規(guī)則通常用上下文無關文法描述。 語法分析方法有自上而下和自下而上兩類。 本章和下一章將介紹編譯程序構造中的一些典型的語法分析方法。,2020/7/24,Ch4.語法分析---自上而下分析,4,典型的語法分析方法,自上而下語法分析方法 第四章介紹 遞歸子程序法 預測分析法，即LL(1)法 自下而上語法分析方法 第五章介紹 算符優(yōu)先分析法 規(guī)范歸約法 LR方法：LR(0)、SLR(1)、LR(1)、LALR(1),5,CH.4 語法分析---自上而下分析,掌握：消除文法左遞歸，消除回溯，計算FIRST集、FOLLOW集，LL(1)分析條件， LL(1)文法的概念，預測分析表

3、的構造。 了解理解：自上而下分析方法的基本思想, 自上而下分析的過程。 教學內容： 4.1 語法分析器的功能 4.2 自上而下分析面臨的問題 4.3 LL(1)分析法 4.4 遞歸下降分析程序的構造 4.5 預測分析程序 *4.6 LL(1)分析中的錯誤處理,6,4.1 語法分析器的功能,語法分析是編譯程序的核心部分。 它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定一串單詞符號的語法結構是否符合語法規(guī)則, 是否文法的一個句子。 分析判定的方法： 建立輸入串n的從文法開始符號S出發(fā)的推導 S1n 即建立以S為根的與輸入串n相匹配的語法樹 圖4.1表明語法分析器在編譯程序中的地位,20

4、20/7/24,Ch4.語法分析---自上而下分析,7,4.2 自上而下分析面臨的問題,本節(jié)主要是通過例子 1.說明自上而下分析方法的思想和步驟 2.認識自上而下分析時所遇到的主要困難 自上而下分析的主要困難是: 文法的左遞歸性，使分析陷入無限循環(huán) 回溯的不確定性，要求將已經完成工作推倒重來 為解決這些問題，考慮要消除文法左遞歸和避免回溯。,8,自上而下分析方法的思想,從文法的開始符號出發(fā)，向下推導，試圖推出句子，匹配輸入符號串，尋找輸入串的最左推導，并按與最左推導相對應的順序，自上而下從左到右地建立輸入串的語法分析樹。 推導過程中，試圖根據(jù)當前的輸入符號判斷使用非終結符的哪個候選式去替換。

5、分析過程是一種窮盡一切可能的試探過程；是反復使用不同產生式謀求匹配輸入串的過程。 用例子說明，P67.例4.1,9,自上而下分析(1),例4.1 文法： SxAy A** A* 輸入串 =x*y，分析是否文法的句子？,10,自上而下分析(2),11,自上而下分析(3),12,自上而下分析：說明,注: 自上而下分析過程是帶回溯的試探過程 遇非終結符標記的結, 就試圖用某個候選式展開, 期望此候選能匹配輸入串, 若不能匹配, 則要回溯。 遇終結符號的結，就進行匹配，然后移動輸入串指針ip指向下一個符號。 回溯是一項復雜而費時的工作，須廢棄已做的許多工作，恢復到前面的某一情況，效率很低。

6、 下面討論自上而下分析法存在的困難和缺點 左遞歸、回溯、虛假匹配、當報告分析不成功時難于知道輸入串中出錯的確切位置，等,13,文法的左遞歸問題,文法的左遞歸性 直接左遞歸：文法存在產生式 P P 間接左遞歸：存在推導 P + P 文法具有左遞歸性，采用自上而下方法分析，可能會陷入無限循環(huán)，分析不下去。,例如：文法有左遞歸產生式 AAx 分析中會遇到試圖展開A，卻又立即遇到A，并將永遠循環(huán)下去。在沒有識別任何輸入符號的情況下又得重新要求A去進行新的匹配---消左遞歸！,14,候選式的確定與回溯問題,自上而下分析是一種反復用可能的候選式去進行試探的過程，不能預知本次試探是否會成功，若不成功則需要回

7、溯。 例如文法： SxAy A**|* 判定句子x*y是否該文法定義的語言的句子。 希望：當要進行關于某個非終結符的推導時，能夠根據(jù)當前輸入符號確定候選式，避免回溯。,15,虛假匹配問題,虛假匹配：當一個非終結符用某一候選式匹配成功時，這種成功可能僅是暫時的、虛假的。 例如：文法 S xAy A **|* 識別輸入串 =x**y 是否為該文法的句子 自上而下的語法分析中，若在 SxAy 后選擇用 * 替換 A，則 S xAy x*y 。 的第二個符號可以與葉結點*得以匹配，但第三個符號卻不能與下一葉結點y匹配。 于是分析失敗，意味著不能為串x**y 構造語法樹，即 x**y 不是句子。錯誤的

8、結論。 失敗的原因在于錯誤的選擇了A的產生式 --- 用最長匹配方法解決。,,16,4.3 LL(1) 分析法,下面將集中討論不帶回溯的自上而下分析法 4.3 LL(1)分析法 消除文法左遞歸 提左因子、避免回溯 LL(1)分析條件、LL(1)文法 4.4 遞歸下降分析程序構造 實現(xiàn) LL(1)分析的簡單方法 4.5 預測分析程序 實現(xiàn) LL(1)分析的有效方法,17,4.3.1 左遞歸的消除,無法對左遞歸文法進行有效的自上而下分析，因此必須消除文法的左遞歸。 直接左遞歸 有產生式 AA 間接左遞歸 沒有產生式 AA , 但有推導 A+A 消除直接左遞歸的方法：引入新的非終結符號P，將關于P的

9、如下產生式 PP| (非且不以P打頭) 替換為 PP P P,2020/7/24,Ch4.語法分析---自上而下分析,18,例4.2 表達式文法直接左遞歸的消除,E E + TT T T * FF F ( E )i,E T E E + T E| T F T T* F T F ( E )i,消左,問題：可否不用E、T，而用其他非終結符號？,2020/7/24,Ch4.語法分析---自上而下分析,19,文法直接左遞歸消除：練習,消除下面文法的左遞歸 ： (1) G(H): H H;M|M M d|aHb,解: 消除左遞歸后的文法： (1) G(H): H MH H ;MH|

10、 M d|aHb,(2) G(A): AaAb1|a BBb|d,(2) G(A): A aAb1|a BdB BbB|,20,消除直接左遞歸的一般方法,一般而言，假定關于P的全部產生式是： PP1| P2|| Pm| 1| 2 | | n 其中, 每個都不等于, 而每個都不以P開頭 消除P的直接左遞歸就是把這些規(guī)則改寫成： P 1 P| 2 P|| n P P 1P| 2P| | mP| 直接左遞歸和間接左遞歸的消除方法均在必須掌握之列。P70.有一個消除任何左遞歸的算法，下面先舉例說明消除間接左遞歸的方法。,21,消除間接左遞歸,間接左遞歸的消

11、除: 先將間接左遞歸變?yōu)橹苯幼筮f歸，再按消直接左遞歸的方法消除。 例1：文法 (1) A Bb 有間接左遞歸 (2) B Ac (3) B d 先將(1) 代入(2)得：BBbc，于是 B Bbc|d 再消除直接左遞歸，得到的文法不含左遞歸: A Bb B dB B bc B | ,22,消除間接左遞歸：例1,例1：有間接左遞歸文法： (1) A Bb (2) B Ac (3) B d 也可以先將(2)(3)代入(1)得: A Acb|db 再消直接左遞歸, 得到不含左遞歸的文法: A dbA A

12、cb A| B現(xiàn)在是無用符號, 把B及其產生式刪除。 說明：代入方法不同，得到的不含左遞歸的文法可能是不一樣的，但它們等價。消左以后，可能會出現(xiàn)無用符號，應把它們去掉。,23,間接左遞歸的消除：例2,例2：有間接左遞歸的文法： SAc|c ABb|b BSa|a (1) 將B的定義代入A的產生式得：ASab|ab|b (2) 將A的定義代入S的產生式得: SSabc|abc|bc|c (3) 消除其直接左遞歸：SabcS|bcS|cS SabcS| (4) 刪除“多余的”產生式：ASab|ab|b 和 BSa|a 結果：SabcS|bcS|cS SabcS|,24,消除左遞歸的算法

13、(P70.),消除左遞歸要求文法:1. 無回路(無形如 P + P 的推導)； 2. 無產生式 算法 (1) 以某種順序將文法非終結符排列 P1 , P2 ,, Pn (2) For i:=1 to n do begin for j:=1 to i-1 do 把形如 Pi Pj 的規(guī)則改寫為 Pi 1|2|| k 其中, Pj 1| 2| k 是關于Pj的全部產生式; 消除Pi規(guī)則的直接左遞歸; end; (3) 化簡由(2)得到的文法, 去掉無用的非終結符號。,25,消左遞歸算法：例4.3,解：將非終結符排序為 R、Q、S。 對于R不存在直接左遞歸，把R代入Q的候選式： Q Sab|a

14、b|b 現(xiàn)在Q也不含直接左遞歸，把Q代入S的候選式： S Sabc|abc|bc|c 經消除S的直接左遞歸后，得到整個文法： S abcS|bcS|cS S abcS| Q Sab|ab|b R Sa|a 由于關于 Q, R 的規(guī)則是多余的, 則可化簡得到： S abcS|bcS|cS S abcS|,消除文法 SQc|c Q Rb|b R Sa|a 的左遞歸。,26,消左遞歸算法：注意,注意: 非終結符排序不同, 消左遞歸的結果不同; 不要改變文法的開始符號。 消左還有一個方法 --- 擴充的巴科斯范式(P75.)。 例如，例4.3的文法： SQc|c Q

15、 Rb|b R Sa|a 如果將非終結符排序為 S 、Q、 R 則得到無左遞歸的文法： (參見P70.) S Qc | c Q Rb | b R bcaR|caR| aR R bcaR| ,27,4.3.2 消除回溯、提左因子,強調: 實現(xiàn)有效的自上而下分析，要求文法不得含左遞歸，并且不得回溯?，F(xiàn)在左遞歸已經解決。 接下來討論: 1. 在不得回溯的情況下進行自上而下分析，對于文法有什么要求。 2. 如何改寫文法使?jié)M足消除回溯的要求。 需要引入: 符號串的終結首符集 FIRST() 非終結符A的后隨終結符集 FOLLOW(A),28,為避免回溯對文法的要求,回溯的產生是由于

16、文法中存在非終結符A有n個候選式： A 1| 2| | n 在自上而下分析中展開A時，窮盡A的一切可能的候選式去謀求與輸入串相匹配。 如果能夠: 根據(jù)當前的輸入符號a，能準確地指出其匹配的某個候選式i，而不需要從1開始逐個試探。并且若 i 匹配輸入串成功，那么這種匹配決不會是虛假的；若 i 無法完成匹配任務，那么其他候選式也肯定不能完成。i 是A的全權代表， i 的工作成效完全代表了A。,,29,為避免回溯引入FIRST()集,回溯的產生是由于文法中存在非終結符A有n個候選式： A 1| 2| | n 在面臨當前輸入符號a時要能準確指出唯一可使用的候選式i去代表A謀求與輸入串相匹配，顯然要

17、求各i的終結首符號互不相同。 引入符號串的終結首符集FIRST()，上述要求即： FIRST(i )FIRST(j)= ij，i,j=1,2,,n 顯然，當輸入符號aFIRST(i)時, 可以確定用候選式i去謀求匹配。,30,FIRST()集合及作用,令G是一個不含左遞歸的文法, 符號串VTVN* 定義的終結首符集為： FIRST()= a| * a 且 aVT 特別是，若 * ，則規(guī)定 FIRST()。 FIRST集合的作用: 如果非終結符A 的任何兩個不同的候選i和j有： FIRST(i) FIRST(j) = 那么，當要求A匹配輸入串時，A 就能根據(jù)它所面

18、臨的當前輸入符號a，準確地指派某個候選前去執(zhí)行任務, 這個候選就是那個終結首符集合含a 的i。,2020/7/24,Ch4.語法分析---自上而下分析,31,例1：文法: SaA A Sd AbAS FIRST(S)=a,d FIRST(bAS)=b FIRST(A)=,b FIRST()= 例2：文法: SAa A Sd AbaS FIRST(S)=b, a, d FIRST(Aa)=a,b FIRST(A)=,b,計算FIRST集合: 例,2020/7/24,Ch4.語法分析---自上而下分析,32,練習：文法 EE+T | T TT*F | F

19、 F(E) | i 計算: FIRST((E))=? FIRST(i)=? FIRST(T*F)=? FIRST(F)=? FIRST(E)=?,計算FIRST集合: 練習,解: FIRST((E))= ( FIRST(i)= i FIRST(T*F)= (, i FIRST(F)= (, i FIRST(E)= (, i ,33,如何把一個文法改造成所有候選式的終結首符集兩兩不相交呢？ 其辦法是提取公共左因子。 例如，假定關于A 的規(guī)則是: A 1| 2| |n | 1| 2| |m (其中每個不以開頭) 那末，可以引進新的非終結符, 把這些規(guī)則改寫成： A A|

20、1| 2| |m A 1 | 2 | | n,改寫文法避免回溯: 提左因子,1| 2| |n = (1| 2| | n),34,例1: 有產生式 B bBcA|b 由于FIRST(bBcA) FIRST(b) =b 則需要對B bBcA|b提取公共左因子b 將產生式改寫成：B bB B BcA|,提左因子：例,例2: 有文法 S cAd|b A ab|a 由于FIRST(ab) FIRST(a) =a 則需要對A ab|a提取公共左因子a 將文法改寫成：S cAd|b A aA A b|,2020/7/24,Ch4.語法分析---自上而下分析,35,練習1: 有文法

21、 S iBtS|iBtSeS|a B b 提取公共左因子改寫文法。,提左因子：練習1,解: 提取公共左因子，將文法改寫為 S iBtSS|a S |eS B b,2020/7/24,Ch4.語法分析---自上而下分析,36,練習2: 有文法 A aAB1|a B Bb|d 改寫文法, 使其不含左遞歸, 能避免回溯。,改寫文法：練習2,解: 將文法改寫為: A aA A AB1| B dB B bB|,37,4.3.3 LL(1)分析條件,設文法滿足: 不含左遞歸; 若有 A1|2| |n, 則 FIRST(i)FIRST(j)=

22、 ij 是否就能進行有效的自上而下分析呢? 例4.4 P69.(4.2)的算術表達式文法 E TE E +TE| T FT T *FT| F (E) | i 該文法不含左遞歸, 候選式的FIRST集合兩兩不交 考察識別輸入串 i+i # (#是句末符, #不屬于VT),38,LL(1)分析條件的提出(1),E只有一個候選TE, E替換為 TE T只有一個候選 FT, T替換為 FT,F有兩個候選, iFIRST(i) F替換為 i, i 得到匹配, 移動 ip指+ T有兩個候選, +不屬于任一候選的 FIRST集; 但有 T ,認為 T 自動匹配 注意：+號并不讀進！,E TE E +

23、TE| T FT T *FT| F (E)|i,39,LL(1)分析條件的提出(2),E有兩個候選, +FIRST(+TE), 故E替換為 +TE 。+得到匹配, 移動 ip 指下一個 i 。T只有一個候選, T展開為 FT。F展開為 i。i 得到匹配， 移動 ip 指 #。#不屬于T任一候選的 FIRST集， 但有 T , 認為T 自動匹配。 #不屬于E任一候選的 FIRST集， 但有 E , 認為E 自動匹配。,E TE E +TE| T FT T *FT| F (E)|i,40,LL(1)分析條件的提出(3),問題: 是不是一旦非終結符A面臨輸入符號a, 且a不屬于所有FIRST(i),

24、 但屬于某個FIRST(j), 就一定可以使A自動匹配呢? 答案是不一定。在一定的條件下才可以。否則錯誤。 條件是a 允許跟在A的緊后面 例如上例中，+可跟在T后，#可跟在T、E后面。 下面定義可跟在非終結符后的終結符號的集合FOLLOW。,41,非終結符的后隨終結符集FOLLOW,假定S是文法G的開始符號，對于任何非終結符A，定義： FOLLOW(A) = a | S* Aa且 aVT 特別是, 若S*A, 則規(guī)定 #FOLLOW(A) ( #是句末符號) 也就是說，F(xiàn)OLLOW(A)是所有句型中，出現(xiàn)在緊接A之后的終結符或#。 例： SaA A Sd AbAS FOLL

25、OW(S)=#,a,d FOLLOW(A) = a,d,# SaAabASabbASS,2020/7/24,Ch4.語法分析---自上而下分析,42,計算FOLLOW集合：例,例：P69.(4.2)表達式文法 ETE E+TE| TFT T*FT| F(E)|i FOLLOW(T)= #, +, ), ETE T FT 有 #號 E TE T+TE FT+TE 有+號 E TE T FT (E)T (TE)T (T)T (FT)T 有 ) 號,2020/7/24,Ch4.語法分析---自上而下分析,43,LL(1)分析條件：3個,(1) 文法不含左遞歸。 (2) 對于文法中每個非終

26、結符A的各個候選式的終結首符集兩兩不相交。即，若 A 1 | 2 || n 則： FIRST(i) FIRST(j) = ( i j ) (3) 對文法中每一個非終結符A，若它存在某個候選式的終結首符集包含，則 FIRST(A) FLLOW(A)= 特別注意第3個條件：當空字屬于非終結符的某個候選式的終結首符集時的條件!!!,44,LL(1)文法,一個文法G若滿足上述LL(1)分析的三個條件，則稱該文法G為LL(1)文法。 LL(1)文法: 第一個 L 表示從左到右掃描輸入串 第二個L 表示語法分析欲構造輸入串的最左推導 括號里的 1 表示分析時, 每步只需向前查看一個符號 LL

27、(1)文法是無二義文法, 上述三個條件是LL(1)文法無二義的充分條件。 對LL(1)文法，可以對其輸入串進行有效的無回溯的自上而下分析。,2020/7/24,Ch4.語法分析---自上而下分析,45,LL(1)文法：自上而下分析過程,對LL(1)文法，假設要用非終結符A進行匹配，面臨的輸入符號為a，A的所有產生式為： A 1 | 2 || n (1) 若aFIRST(i ), 則指派 i 執(zhí)行匹配任務。 (2) 若a不屬于任何一個候選式的終結首符集, 則: 若屬于某個FIRST(j )且aFOLLOW(A), 則讓A與自動匹配; 否則, a的出現(xiàn)是一種錯誤。 根據(jù)LL(1)文法的條件,

28、 每一步這樣的工作都是確信無疑的。,46,LL(1)文法：例,例4.2文法(P69.) 不是LL(1)文法, 有左遞歸 例4.2消左以后的文法P69.(4.2)是LL(1)文法 滿足LL(1)分析的三個條件 例1 文法G: S iA A :i=e|=e 是LL(1)文法 滿足LL(1)分析的三個條件: 1. 不含左遞歸 2. FIRST(:i=e)= : , FIRST(=e)==, 不交 3. 候選式的FIRST集都不含,2020/7/24,Ch4.語法分析---自上而下分析,47,LL(1)文法: 例2,例2 文法G: S LU L i:| U

29、 i=e 因為: 1. 不含左遞歸 2. L的各個候選的FIRST集合互不交 3. L有個候選式的FIRST集合含, 再求得 FIRST(L)= i,, FOLLOW(L)= i , 是相交的 所以G不是LL(1)文法。,2020/7/24,Ch4.語法分析---自上而下分析,48,4.4 遞歸下降分析程序構造,當一個文法滿足LL(1)條件時，就可以為該文法構造一個不帶回溯的自上而下分析程序： 這個分析程序由一組遞歸過程組成； 每個遞歸過程對應文法的一個非終結符號，完成該非終結符號所對應的語法成分的分析和識別任務。 這樣一個自上而下語法分析程序稱為遞歸下降分析器。,2020/7/24,Ch4

30、.語法分析---自上而下分析,49,遞歸下降分析程序構造：過程和變量,先設定一些過程和變量，作為遞歸下降分析程序的基本成分。 過程ADVANCE：調整ip指向下一個輸入符號, 讀入ip指向的輸入符號到SYM中。 變量SYM：表示ip當前所指的那個輸入符號。 過程ERROR：出錯診察處理。,50,遞歸下降分析程序構造：非終結符對應的遞歸過程的結構, A1| 2|| n =X1X2Xm Xi(VTVN) XiVT XiVN, IF ELSE IF ELSE 結構 順序結構 IF SYM=Xi THEN ADVANCE ELSE ERROR 調用Xi對應的遞歸過程,2020/7/24,

31、Ch4.語法分析---自上而下分析,51,例: 算術表達式的遞歸下降分析器(1),的子程序 ETE procedure E; begin T; 的過程調用 E E的過程調用 end;,的子程序 E+TE| procedure E; IF SYM=+ THEN begin ADVANCE; T; T的過程調用 E E的過程調用 end;,2020/7/24,Ch4.語法分析---自上而下分析,52,例: 算術表達式的遞歸下降分析器(2),T的子程序 TFT procedure T; begin F; F的過程調用 T T的過程調用 end;,T的子程序 T*FT

32、| procedure E; IF SYM=* THEN begin ADVANCE; F; F的過程調用 T T的過程調用 end;,2020/7/24,Ch4.語法分析---自上而下分析,53,例: 算術表達式的遞歸下降分析器(3),F的子程序 Fi|(E) procedure F; IF SYM=i then ADVANCE ELSE IF SYM=( then,BEGIN ADVANCE; E; E的過程調用 IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,54,擴充巴科斯范式定義系統(tǒng),對前面的產生式(巴科斯

33、范式)進行擴充 ： (1) 用花括號表示閉包運算*。 (2) 用0n表示可以任意重復0次至n次, 00= 0=。 (3) 用方括號表示01，即表示的出現(xiàn)可有可無, 等價于 |。 這樣, 使得產生式右部的形式像正規(guī)式一樣, 這種定義形式稱擴充巴科斯范式定義系統(tǒng)。 例如, P75. “實數(shù)”的擴充巴科斯范式定義 Decimalsigninteger.digitexponent,55,使用擴充BNF定義系統(tǒng)的好處(1),(1)直觀易懂: 如表示不超過10位的無符號整數(shù) 90,(2)便于表示消除左遞歸和提取左因子消除回溯 例, 消除左遞歸，不用引入新的非終結符和產生式,56,使用擴充BNF

34、定義系統(tǒng)的好處(2),(3)便于構造自上而下分析程序, 過程是: 關于非終結符A的產生式 寫為擴充BNF定義形式 畫出其語法圖 轉換為A對應的程序 非終結符號的語法圖 類似于表示正規(guī)式的狀態(tài)轉換圖，所以也稱為文法的狀態(tài)轉換圖。 結點 --- 文法符號 有向邊 --- 文法符號的排列順序,|或 分支 回路 .連接 順序,57,用語法圖描述語言的文法: 例(P75.),58,例: 簡單算術表達式的遞歸下降分析器(P76.)E,ET+T 的子程序, 請與P74.的程序對照 procedure E; begin T; 的過程調用 while SYM=+ do 當前符號

35、等于時 begin ADVANCE; 處理終結符 T 的過程調用 end end; SYM：當前符號,59,例: 簡單算術表達式的遞歸下降分析器(P76.)T,TF*F 的子程序, 請與P74.的程序對照 procedure T; begin F; 的過程調用 while SYM=* then 當前符號等于時 begin ADVANCE; 處理終結符 F 的過程調用 end end;,60,總結遞歸子程序法,1.構造文法。 2.改寫文法：消除二義性、消除左遞歸、提取公共左因子

36、。 3.求每個候選式的FIRST集和非終結符的FOLLOW集。 4.檢查是不是 LL(1)文法,是否滿足LL(1)分析的三個條件。 5.若是LL(1)文法，為該文法的每個非終結符畫出語法圖。 6.按照語法圖，為每個非終結符編寫一個遞歸子程序。,2020/7/24,Ch4.語法分析---自上而下分析,61,4.5 預測分析程序,實現(xiàn)LL(1)分析的另一種有效方法是使用一張分析表和一個分析棧進行聯(lián)合控制。直接根據(jù)當前的非終結符號以及當前輸入符號，確定進行分析所需的候選式。 本節(jié)要介紹的預測分析程序就是屬于這種類型的LL(1)分析器。 本節(jié)要掌握: 1.對給定文法構造符號串的FIRST集合和非終結符

37、的FOLLOW集合的方法。 2. 構造預測分析表的方法。,2020/7/24,Ch4.語法分析---自上而下分析,62,4.5.1 預測分析程序工作過程,系統(tǒng)維持一張分析表和一個分析棧，直接根據(jù)當前的輸入符號，選擇當前非終結符(處于棧頂)的候選式進行推導，希望找到相應輸入符號串的最左推導。 預測分析程序的邏輯結構： 1.一個通用的控制程序 2.一個統(tǒng)一形式的分析表M 不同文法使用內容不同的分析表 3.一個分析棧，#為棧底符號 4.一個輸入緩沖區(qū)，#為輸入串結束符,2020/7/24,Ch4.語法分析---自上而下分析,63,預測分析器模型 P77.圖4.4,..a..#,x . . . #,總

38、控程序 見P77.,預測分析表M 見P76.表4.1,,,,輸出,分析棧,輸入緩沖區(qū),,預測分析表是預測分析器的核心,64,預測分析程序的邏輯結構,1.一個輸入串, “#”號為輸入串結束符,#不屬于VT。 2.一個統(tǒng)一形式的預測分析表M。 行: 所有的非終結符A 列: 所有的終結符號a, 包括“#”號 元素MA,a: 產生式或錯誤,概括了文法的全部信息。例, P76.表4.1文法(4.2)的預測分析表 3. 一個分析棧STACK，隨著分析過程的進行而不斷變化,分析開始時棧底先放一個“#”號,分析結束時,若棧底只剩下“#”號,則分析成功。 4.一個通用的統(tǒng)一的控制程序,分析的每一步都根據(jù)分析表、

39、分析棧及輸入串的當前符號進行控制。,2020/7/24,Ch4.語法分析---自上而下分析,65,表達式文法的預測分析表(P76.),66,預測分析程序的工作過程(1),在系統(tǒng)啟動時，輸入指針指向輸入串的第一個符號，分析棧中存放著棧底符號#和文法的開始符號。 分析的每一步都根據(jù)棧頂符號X和當前輸入符號a查看分析表MX,a,以決定相應的動作。 對任何(X,a),執(zhí)行三種可能的動作之一： (1) 若 X=a=#，則分析成功,停止分析。 (2) 若 X=a#，則將X從STACK棧逐出,讓a指向下一個輸入符號，當前輸入符號得到匹配。,2020/7/24,Ch4.語法分析---自上而下分析,67,預測分

40、析程序的工作過程(2),(3)若XVN ,則查分析表項 MX,a: 若MX,a中存放的是XX1X2Xk,則將X從棧頂逐出,讓 X1,X2,,Xk反序進棧。 若MX,a中存放的是X,則將X逐出,不推什么進棧。 若MX,a中存放的是出錯, 則調用ERROR進行錯誤處理。 預測分析程序的總控程序的形式描述(見P77.),68,預測分析程序的工作過程(P78.),例4.6文法(4.2),輸入串為i*i+i,分析步驟： 分析棧 輸入串 所用產生式 動作,,#E i*i+i# 查表ME,i,出入棧 #ET i*i+i# ETE 查表MT,i,出入棧 #ETF i*i+i# TFT 查表MF

41、,i,出入棧 #ETi i*i+i# Fi 匹配,i出棧,調指針 #ET *i+i# 查表MT,*,出入棧 #E TF* *i+i# T*FT 匹配,*出棧,調指針 #ETF i+i# 查表MF,i,出入棧 #ETi i+i# Fi 匹配,i出棧,調指針,#ET +i# 查表MT,+,出入棧 #E +i# T 查表ME,+,出入棧 #ET+ +i# E+TE 匹配,+出棧,調指針 #ET i# 查表MT,i,出入棧 #ETF i# TFT 查表MF,i,出入棧 #ETi i# Fi 匹配,i出棧,調指針 #ET # 查表MT

42、,#,出入棧 #E # T 查表ME,#,出入棧 # # E,所用的產生式序列形成了最左推導對應的分析樹,分析棧 輸入串 所用產生式 動作,,#ETi i+i# Fi 匹配,i出棧,調指針,70,4.5.2 預測分析表的構造,預測分析法步驟: 1)構造文法，消除二義性； 2)消除左遞歸、提取左因子； 3)求每個候選式的FIRST集和非終結符的FOLLOW集； 4)檢查是不是 LL(1)文法； 若不是 LL(1),說明文法的復雜性超過LL(1)分析法的分析能力； 5)構造預測分析表； 6)實現(xiàn)預測分析器。,2020/7/24,Ch4.語法分析---自上而下分析,71,FIRST集

43、和FOLLOW集,前面定義了: 對于(TN)* , 的終結首符號集 FIRST()=a|*a，aT * 特別的，若*，則FIRST()。 對于AN , A的后隨終結符號集： FOLLOW(A)=a|S*Aa，aT 特別的, 若S* A,則#FOLLOW(A)。 下面介紹構造集合FIRST和FOLLOW的算法,72,求FIRST(X)的算法(P78.),設文法符號XTN (1) 若 XT，則 FIRST(X)=X； (2) 若 XN，取FIRST(X)的初值： a|Xa X FIRST(X)= a|Xa X 第(2)條的要點是查看X的產生式! (3) 下頁,,73,(3) 若XN，

44、重復如下過程，直到其FIRST集不再增大: 若 XY，且YN，則 FIRST(X)= FIRST(X)(FIRST(Y)-) 若 XY1Yk ,且Y1Yi-1* 即FIRST(Yn), 其中 n=1到i-1, 則 FIRST(X)= FIRST(X)(FIRST(Yn)-) 若 Y1Yk*,即任何FIRST(Yi), 其中i=1到k,則 FIRST(X)=FIRST(X) 第(3)條的要點仍然是查看X的產生式，對產生式右部的一個個符號，計算符號的FIRST集合，檢查是否含, 以決定是否繼續(xù)計算!!,求FIRST(X)的算法,74,設符號串=X1X2Xn，構造FIRST(),重復如下過程，直到

45、其FIRST集不再增大: (1) 首先置 FIRST()= FIRST(X1)- (2) 若對任何j=1到i-1, 若X1Xi-1*, 則 FIRST()=FIRST()(FIRST(Xj)-) (3) 若 X1Xn*，則 FIRST()= FIRST() 計算FIRST()的要點是從左到右查看的一個個符號，計算符號的FIRST集合，檢查是否含, 以決定是否繼續(xù)計算！,求FIRST()的算法(P79.),75,例4.7 表達式文法符號的 FIRST集,FIRST(F)=(,i FIRST(T)=FIRST(F)=(,i FIRST(E)=FIRST(T)=(,i FIRST(E)=+， FI

46、RST(T)=*, FIRST(+)=+ FIRST(*)=* FIRST(()=( FIRST())=) FIRST(i)=i FIRST(+TE)=+ FIRST(ETF)=(,i FIRST(ETF)=+,*,(,i FIRST(ET)=+,*,,文法(4.2): ETE E+TE| TFT T*FT| F(E)|i,76,計算FIRST集：例,例1 文法GS: SLU LUi:| Ue=i| FIRST(S)=e,i, FIRST(L)=e,i, FIRST(U)=e, FIRST(LU)=e,i, FIRST(Ui:)=e,i FIRST(e=i)=e,例2

47、文法GE: EE+T|T TT*F|F F(E)|i FIRST(E)=(,i FIRST(T)=(,i FIRST(F)=(,i FIRST(E+T)=(,i FIRST(T*F)=(,i FIRST((E))=(,77,計算FIRST集：練習,解： FIRST(A)= a FIRST(A)= a, FIRST(B)= d FIRST(B)= b, FIRST(AB1)= a FIRST(AB1)=a,b,1 FIRST(AB)=a,b,,文法GA: AaA AAB1| BdB BbB| 計算: FIRST(A),FIRST(A) FIRST(B),FIRST(B) FIRS

48、T(AB1) FIRST(AB1) FIRST(AB),78,求FOLLOW(A)的算法(P79.),設文法GS,對G的所有非終結符, 重復作以下計算: (1)將#加入到 FOLLOW(S),#為句子的結束符 (2)若 AB，BN 則 FOLLOW(B)= FOLLOW(B)FIRST() (3)如果 AB 或 AB,且*，AB，則 FOLLOW(B)= FOLLOW(B)FOLLOW(A) 計算FOLLOW(B)的要點 是查看右部符號串包含B的產生式,計算B右邊符號串的FIRST集合,若該集合含有,則還要計算FOLLOW(A),若B右邊沒有符號,也要計算FOLLOW(A)!!,2020/7/

49、24,Ch4.語法分析---自上而下分析,79,例4.7 表達式文法符號的FOLLOW集,FOLLOW(E)= ),# FOLLOW(E) = FOLLOW(E)= ),# FOLLOW(T)=+,),# FOLLOW(T) = FOLLOW(T)=+,),# FOLLOW(F)=*,+,),#,文法(4.2) ETE E+TE| TFT T*FT| F(E)|i,2020/7/24,Ch4.語法分析---自上而下分析,80,計算FOLLOW集：例,例1 文法GE: EE+T|T TT*F|F F(E)|i FOLLOW(E)=+,),# FOLLOW(T)=*,+,),# FOLLOW

50、(F)=*,+,),#,例2 文法GS: SLU LUi:| Ue=i| FOLLOW(S)=# FOLLOW(L)=e,# FOLLOW(U)=i,#,2020/7/24,Ch4.語法分析---自上而下分析,81,計算FOLLOW集：練習,解： FOLLOW(A)=d,# FOLLOW(A) = FOLLOW(A)=d,# FOLLOW(B)=1 FOLLOW(B) = FOLLOW(B)=1,文法GA: AaA AAB1| BdB BbB| 計算: FOLLOW(A),FOLLOW(A) FOLLOW(B),FOLLOW(B),82,預測分析表(LL(1)分析表)的構造算法(

51、P79.),構造分析表M的算法是確定每個表元素，即確定MA,a： (1) 對文法G的每個產生式A, 先計算FIRST(), 若FIRST()含有, 則還要計算FOLLOW(A), 然后執(zhí)行第步和第步； (2) 對于每個終結符aFIRST()，把A加到MA,a中； (3) 若FIRST() , 則對任何的 bFOLLOW(A), 把A加至MA,b中； (4) 把所有無定義的MA,a標上“出錯標志”。,2020/7/24,Ch4.語法分析---自上而下分析,83,例4.8 表達式文法的預測分析表,84,表達式文法預測分析表的構造,對 F(E)| i FIRST((E))=(；FIRST(i)=i

52、則 確定 MF,(；MF,i,對 ETE FIRST(TE)=(,i 則 M E,( = ME,i= ETE,對 E+TE| FIRST(+TE)=+； FOLLOW(E)=),# 則確定 ME,+; ME,)； ME,#,對TFT FIRST(FT)=(,i；則確定MT,(；MT,i,對T*FT| FIRST(*FT)=*; FORLLOW(T)=+,),# 則確定 MT,*；MT,+；MT,)；MT,#,85,預測分析表與LL(1)文法,上述構造預測分析表的算法可應用于構造任何文法G的預測分析表 M。 但對于某些文法，其 MA，a可能持有若干個產生式，即MA，a是多重定義的。 如

53、果文法G是左遞歸或二義的，那么，其預測分析表 M 至少含有一個多重定義入口。 可以證明，一個文法G的預測分析表M不含多重定義的入口，當且僅當該文法是LL(1)文法。 例如:(4.2)表達式文法是LL(1)文法,分析表不含多重定義; 而下面例子的文法不是LL(1)文法。,86,構造預測分析表：例,文法: SiCtSS|a SeS| Cb FIRST(iCtSS)=i, FIRST(a)=a FIRST(eS)=e, FOLLOW(S)=e,# FIRST(b)=b,該文法不是LL(1)文法!,87,構造預測分析表：練習,P82.第4題文法, 構造 LL(1)分析表(預測分析表)。 ExprExp

54、r Expr(Expr)|Var ExprTail ExprTailExpr| Varid VarTail 做作業(yè)時要寫出各非終 VarTail(Expr)| 結符的FOLLOW()集合,88,由預測分析表構造遞歸下降分析程序(1),ETE 的子程序 procedure E; begin if sym=i or sym=( then begin T; 的過程調用 E E的過程調用 end else error end;,TFT T的子程序 procedure T; begin if sym=i or sym=( then begin F; F的過程調用 T T的過

55、程調用 end else error end;,89,由預測分析表構造遞歸下降分析程序(2),E+TE| 的子程序 procedure E; begin if sym=+ then begin advance; T; T的過程調用 E E的過程調用 end else if sym=i or sym=* or sym=( then error end;,90,由預測分析表構造遞歸下降分析程序(3),T*FT| T的子程序 procedure T; begin if sym=* then begin advance;

56、 F; F的過程調用 T T的過程調用 end else if sym=i or sym=( then error end;,請對照P74.的圖4.2。由預測分析表構造的遞歸下降分析程序更精確。 這里， F(E)| 的子程序沒有給出,它同P74.圖4.2。,91,*4.6 LL(1)分析中的錯誤處理,LL(1)分析中的一種錯誤處理辦法 發(fā)現(xiàn)錯誤 1. 棧頂?shù)慕K結符號與當前輸入符號不匹配； 2.非終結符號A于棧頂，面臨的輸入符號為a，但預測分析表M中的 MA,a項為空(出錯)。 “應急”恢復策略 跳過輸入串中的一些符號直至遇到“同步符號”為止。,92,LL(1)分析中

57、的一種錯誤處理辦法,同步符號的選擇 1. 把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)。 2. 把FIRST(A)中的符號加到A的同步符號集，當FIRST(A)中的符號在輸入串中出現(xiàn)時，可根據(jù)A恢復分析。 請閱讀教材P8081.表4.2是加入同步符號的LL(1)分析表，例4.9是帶錯誤恢復的語法分析過程。,93,CH.4. 自上而下分析小結,自上而下分析的思想 問題：左遞歸，回溯(4.1),FIRST( )集合 FOLLOW( )集合,遞歸下降子程序方法(4.4),預測分析表方法(4.5),94,CH.4. 自上

58、而下分析小結(1),1.采用推導的方法進行分析，從上到下構造語法分析樹，是一種試探的帶回溯的方法。為避免回溯，要求文法沒有公共左因子和左遞歸。要掌握消左遞歸和提左因子的方法。 2.遞歸下降子程序方法：為每一個非終結符構造一個遞歸過程子程序，過程體中是對產生式右部符號串的展開,遇到終結符就匹配,遇到非終結符就調用相應的遞歸過程子程序。 3.預測分析表方法：用一個棧和一個預測分析表模擬遞歸子程序，它的基本工作模式是下推自動機，以格局的變化反映預測分析器的分析過程。,95,CH.4. 自上而下分析小結(2),4.預測分析表的構造：計算FIRST集合和FOLLOW集合，在此基礎上構造預測分析表。 5.

59、 LL(1)文法及其判別： 通過LL(1)分析3個條件可以直接從產生式判定一個文法是否LL(1)文法。 構造預測分析表，其預測分析表中若沒有多重定義條目，則文法、語言和分析器分別被稱為LL(1)的文法、語言和分析器。 6.預測分析表的構造以及LL(1)文法的判別都要用到集合FIRST和FOLLOW的計算，要掌握。,2020/7/24,Ch4.語法分析---自上而下分析,96,習題、作業(yè),P81. 練習： 1. (1)；(2)； 補充(3): 給出符號串(a,)的自上而下分析過程。 2. (1)；(2)；(3)；(4) 要求根據(jù)預測分析表構造遞歸下降分析程序。 3. (1)；(2)；(3)；(4) 4. (1)；(2),