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

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

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

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

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

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

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

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

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

9、如下產(chǎn)生式 PP| (非且不以P打頭) 替換為 PP P P,2020/7/24,Ch4.語(yǔ)法分析---自上而下分析,18,例4.2 表達(dá)式文法直接左遞歸的消除,E E + TT T T * FF F ( E )i,E T E E + T E| T F T T* F T F ( E )i,消左,問(wèn)題：可否不用E、T，而用其他非終結(jié)符號(hào)？,2020/7/24,Ch4.語(yǔ)法分析---自上而下分析,19,文法直接左遞歸消除：練習(xí),消除下面文法的左遞歸 ： (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,消除直接左遞歸的一般方法,一般而言，假定關(guān)于P的全部產(chǎn)生式是： PP1| P2|| Pm| 1| 2 | | n 其中, 每個(gè)都不等于, 而每個(gè)都不以P開(kāi)頭 消除P的直接左遞歸就是把這些規(guī)則改寫成： P 1 P| 2 P|| n P P 1P| 2P| | mP| 直接左遞歸和間接左遞歸的消除方法均在必須掌握之列。P70.有一個(gè)消除任何左遞歸的算法，下面先舉例說(shuō)明消除間接左遞歸的方法。,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)在是無(wú)用符號(hào), 把B及其產(chǎn)生式刪除。 說(shuō)明：代入方法不同，得到的不含左遞歸的文法可能是不一樣的，但它們等價(jià)。消左以后，可能會(huì)出現(xiàn)無(wú)用符號(hào)，應(yīng)把它們?nèi)サ簟?23,間接左遞歸的消除：例2,例2：有間接左遞歸的文法： SAc|c ABb|b BSa|a (1) 將B的定義代入A的產(chǎn)生式得：ASab|ab|b (2) 將A的定義代入S的產(chǎn)生式得: SSabc|abc|bc|c (3) 消除其直接左遞歸：SabcS|bcS|cS SabcS| (4) 刪除“多余的”產(chǎn)生式：ASab|ab|b 和 BSa|a 結(jié)果：SabcS|bcS|cS SabcS|,24,消除左遞歸的算法

13、(P70.),消除左遞歸要求文法:1. 無(wú)回路(無(wú)形如 P + P 的推導(dǎo))； 2. 無(wú)產(chǎn)生式 算法 (1) 以某種順序?qū)⑽姆ǚ墙K結(jié)符排列 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 是關(guān)于Pj的全部產(chǎn)生式; 消除Pi規(guī)則的直接左遞歸; end; (3) 化簡(jiǎn)由(2)得到的文法, 去掉無(wú)用的非終結(jié)符號(hào)。,25,消左遞歸算法：例4.3,解：將非終結(jié)符排序?yàn)?R、Q、S。 對(duì)于R不存在直接左遞歸，把R代入Q的候選式： Q Sab|a

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

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

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

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

18、臨的當(dāng)前輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù), 這個(gè)候選就是那個(gè)終結(jié)首符集合含a 的i。,2020/7/24,Ch4.語(yǔ)法分析---自上而下分析,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,計(jì)算FIRST集合: 例,2020/7/24,Ch4.語(yǔ)法分析---自上而下分析,32,練習(xí)：文法 EE+T | T TT*F | F

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、等于時(shí) begin ADVANCE; 處理終結(jié)符 T 的過(guò)程調(diào)用 end end; SYM：當(dāng)前符號(hào),59,例: 簡(jiǎn)單算術(shù)表達(dá)式的遞歸下降分析器(P76.)T,TF*F 的子程序, 請(qǐng)與P74.的程序?qū)φ?procedure T; begin F; 的過(guò)程調(diào)用 while SYM=* then 當(dāng)前符號(hào)等于時(shí) begin ADVANCE; 處理終結(jié)符 F 的過(guò)程調(diào)用 end end;,60,總結(jié)遞歸子程序法,1.構(gòu)造文法。 2.改寫文法：消除二義性、消除左遞歸、提取公共左因子

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

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

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

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

40、析程序的工作過(guò)程(2),(3)若XVN ,則查分析表項(xiàng) MX,a: 若MX,a中存放的是XX1X2Xk,則將X從棧頂逐出,讓 X1,X2,,Xk反序進(jìn)棧。 若MX,a中存放的是X,則將X逐出,不推什么進(jìn)棧。 若MX,a中存放的是出錯(cuò), 則調(diào)用ERROR進(jìn)行錯(cuò)誤處理。 預(yù)測(cè)分析程序的總控程序的形式描述(見(jiàn)P77.),68,預(yù)測(cè)分析程序的工作過(guò)程(P78.),例4.6文法(4.2),輸入串為i*i+i,分析步驟： 分析棧 輸入串 所用產(chǎn)生式 動(dòng)作,,#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出棧,調(diào)指針 #ET *i+i# 查表MT,*,出入棧 #E TF* *i+i# T*FT 匹配,*出棧,調(diào)指針 #ETF i+i# 查表MF,i,出入棧 #ETi i+i# Fi 匹配,i出棧,調(diào)指針,#ET +i# 查表MT,+,出入棧 #E +i# T 查表ME,+,出入棧 #ET+ +i# E+TE 匹配,+出棧,調(diào)指針 #ET i# 查表MT,i,出入棧 #ETF i# TFT 查表MF,i,出入棧 #ETi i# Fi 匹配,i出棧,調(diào)指針 #ET # 查表MT

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

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

44、重復(fù)如下過(guò)程，直到其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)條的要點(diǎn)仍然是查看X的產(chǎn)生式，對(duì)產(chǎn)生式右部的一個(gè)個(gè)符號(hào)，計(jì)算符號(hào)的FIRST集合，檢查是否含, 以決定是否繼續(xù)計(jì)算!!,求FIRST(X)的算法,74,設(shè)符號(hào)串=X1X2Xn，構(gòu)造FIRST(),重復(fù)如下過(guò)程，直到

45、其FIRST集不再增大: (1) 首先置 FIRST()= FIRST(X1)- (2) 若對(duì)任何j=1到i-1, 若X1Xi-1*, 則 FIRST()=FIRST()(FIRST(Xj)-) (3) 若 X1Xn*，則 FIRST()= FIRST() 計(jì)算FIRST()的要點(diǎn)是從左到右查看的一個(gè)個(gè)符號(hào)，計(jì)算符號(hào)的FIRST集合，檢查是否含, 以決定是否繼續(xù)計(jì)算！,求FIRST()的算法(P79.),75,例4.7 表達(dá)式文法符號(hào)的 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,計(jì)算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,計(jì)算FIRST集：練習(xí),解： 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| 計(jì)算: FIRST(A),FIRST(A) FIRST(B),FIRST(B) FIRS

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

49、24,Ch4.語(yǔ)法分析---自上而下分析,79,例4.7 表達(dá)式文法符號(hào)的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.語(yǔ)法分析---自上而下分析,80,計(jì)算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.語(yǔ)法分析---自上而下分析,81,計(jì)算FOLLOW集：練習(xí),解： FOLLOW(A)=d,# FOLLOW(A) = FOLLOW(A)=d,# FOLLOW(B)=1 FOLLOW(B) = FOLLOW(B)=1,文法GA: AaA AAB1| BdB BbB| 計(jì)算: FOLLOW(A),FOLLOW(A) FOLLOW(B),FOLLOW(B),82,預(yù)測(cè)分析表(LL(1)分析表)的構(gòu)造算法(

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

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

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

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

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

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

57、的一種錯(cuò)誤處理辦法,同步符號(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ù)分析。 請(qǐng)閱讀教材P8081.表4.2是加入同步符號(hào)的LL(1)分析表，例4.9是帶錯(cuò)誤恢復(fù)的語(yǔ)法分析過(guò)程。,93,CH.4. 自上而下分析小結(jié),自上而下分析的思想 問(wèn)題：左遞歸，回溯(4.1),FIRST( )集合 FOLLOW( )集合,遞歸下降子程序方法(4.4),預(yù)測(cè)分析表方法(4.5),94,CH.4. 自上

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

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