Ch4語(yǔ)法分析 自上而下分析課件

編譯原理第四章語(yǔ)法分析---自上而下分析

程序設(shè)計(jì)語(yǔ)言

2022/11/101Ch4.語(yǔ)法分析---自上而下分析編譯原理第四章程序設(shè)計(jì)語(yǔ)言2022/11/本章在編譯程序中的地位表格管理詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號(hào)語(yǔ)法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理2本章在編譯程序中的地位表詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代回顧：語(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ǔ)法上正確的程序。語(yǔ)法規(guī)則通常用上下文無(wú)關(guān)文法描述。語(yǔ)法分析方法有自上而下和自下而上兩類。本章和下一章將介紹編譯程序構(gòu)造中的一些典型的語(yǔ)法分析方法。3回顧：語(yǔ)法分析任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，典型的語(yǔ)法分析方法自上而下語(yǔ)法分析方法第四章介紹

遞歸子程序法預(yù)測(cè)分析法，即LL(1)法

自下而上語(yǔ)法分析方法第五章介紹

算符優(yōu)先分析法規(guī)范歸約法LR方法：LR(0)、SLR(1)、LR(1)、LALR(1)

2022/11/104Ch4.語(yǔ)法分析---自上而下分析典型的語(yǔ)法分析方法自上而下語(yǔ)法分析方法第四章介紹202CH.4語(yǔ)法分析---自上而下分析掌握：消除文法左遞歸，消除回溯，計(jì)算FIRST集、FOLLOW集，LL(1)分析條件，LL(1)文法的概念，預(yù)測(cè)分析表的構(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.6LL(1)分析中的錯(cuò)誤處理重點(diǎn)難點(diǎn)5CH.4語(yǔ)法分析---自上而下分析掌握：消除文法左遞歸，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)

Sα1…αn即建立以S為根的與輸入串αn相匹配的語(yǔ)法樹(shù)圖4.1表明語(yǔ)法分析器在編譯程序中的地位64.1語(yǔ)法分析器的功能語(yǔ)法分析是編譯程序的核心部分。64.2自上而下分析面臨的問(wèn)題本節(jié)主要是通過(guò)例子1.說(shuō)明自上而下分析方法的思想和步驟2.認(rèn)識(shí)自上而下分析時(shí)所遇到的主要困難自上而下分析的主要困難是:文法的左遞歸性，使分析陷入無(wú)限循環(huán)回溯的不確定性，要求將已經(jīng)完成工作推倒重來(lái)為解決這些問(wèn)題，考慮要消除文法左遞歸和避免回溯。2022/11/107Ch4.語(yǔ)法分析---自上而下分析4.2自上而下分析面臨的問(wèn)題本節(jié)主要是通過(guò)例子2022/1自上而下分析方法的思想從文法的開(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è)候選式去替換。分析過(guò)程是一種窮盡一切可能的試探過(guò)程；是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過(guò)程。用例子說(shuō)明，P67.例4.18自上而下分析方法的思想從文法的開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，試圖推自上而下分析(1)例4.1文法：⑴S→xAy⑵A→**⑶A→*

輸入串α=x*y，分析α是否文法的句子？序號(hào)ip指向語(yǔ)法樹(shù)最左推導(dǎo)說(shuō)明x*yS根結(jié)S,當(dāng)前符x①x*y③x得匹配,移動(dòng)ipSxAySxAy用S→xAy展開(kāi)S欲用xAy匹配輸入串SxAy②x*y9自上而下分析(1)例4.1文法：⑴S→xAy序號(hào)ip自上而下分析(2)序號(hào)ip指向語(yǔ)法樹(shù)最左推導(dǎo)說(shuō)明Sx*yxAy試用A→**展開(kāi)ASxAyx**y④**x*y⑤*得匹配,移動(dòng)ip但y得不到匹配SxAy**用A→**展開(kāi)失敗回溯:回到第③步⑥SxAySxAyx*y10自上而下分析(2)序號(hào)ip指向語(yǔ)法樹(shù)最左推導(dǎo)自上而下分析(3)序號(hào)ip指向語(yǔ)法樹(shù)最左推導(dǎo)說(shuō)明x*ySxAy試用A→*展開(kāi)ASxAyx*y⑦*x*y⑧*得匹配,移動(dòng)ipSxAy*A完成匹配,y得匹配,移動(dòng)ip,輸入串匹配成功,結(jié)束⑨SxAySxAyx*yx*y*11自上而下分析(3)序號(hào)ip指向語(yǔ)法樹(shù)最左推導(dǎo)自上而下分析：說(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ù)到前面的某一情況，效率很低。下面討論自上而下分析法存在的困難和缺點(diǎn)左遞歸、回溯、虛假匹配、當(dāng)報(bào)告分析不成功時(shí)難于知道輸入串中出錯(cuò)的確切位置，等12自上而下分析：說(shuō)明注:自上而下分析過(guò)程是帶回溯的試探過(guò)程1文法的左遞歸問(wèn)題文法的左遞歸性直接左遞歸：文法存在產(chǎn)生式P→Pα間接左遞歸：存在推導(dǎo)P+Pα文法具有左遞歸性，采用自上而下方法分析，可能會(huì)陷入無(wú)限循環(huán)，分析不下去。例如：文法有左遞歸產(chǎn)生式A→Ax

分析中會(huì)遇到試圖展開(kāi)A，卻又立即遇到A，并將永遠(yuǎn)循環(huán)下去。在沒(méi)有識(shí)別任何輸入符號(hào)的情況下又得重新要求A去進(jìn)行新的匹配---消左遞歸！SAxAxAx……13文法的左遞歸問(wèn)題文法的左遞歸性例如：文法有左遞歸產(chǎn)生式A→候選式的確定與回溯問(wèn)題自上而下分析是一種反復(fù)用可能的候選式去進(jìn)行試探的過(guò)程，不能預(yù)知本次試探是否會(huì)成功，若不成功則需要回溯。例如文法：S→xAyA→**|*判定句子x*y是否該文法定義的語(yǔ)言的句子。希望：當(dāng)要進(jìn)行關(guān)于某個(gè)非終結(jié)符的推導(dǎo)時(shí)，能夠根據(jù)當(dāng)前輸入符號(hào)確定候選式，避免回溯。SxAy**不成功，回溯SxAy*成功

x*y是句子14候選式的確定與回溯問(wèn)題自上而下分析是一種反復(fù)用可能的候選式去虛假匹配問(wèn)題虛假匹配：當(dāng)一個(gè)非終結(jié)符用某一候選式匹配成功時(shí)，這種成功可能僅是暫時(shí)的、虛假的。例如：文法S→xAyA→**|*識(shí)別輸入串α=x**y是否為該文法的句子自上而下的語(yǔ)法分析中，若在SxAy后選擇用*替換A，則SxAyx*y。α的第二個(gè)符號(hào)可以與葉結(jié)點(diǎn)*得以匹配，但第三個(gè)符號(hào)卻不能與下一葉結(jié)點(diǎn)y匹配。于是分析失敗，意味著不能為串x**y構(gòu)造語(yǔ)法樹(shù)，即x**y不是句子。錯(cuò)誤的結(jié)論。失敗的原因在于錯(cuò)誤的選擇了A的產(chǎn)生式---用最長(zhǎng)匹配方法解決。x**ySxAy*x**ySxAy*15虛假匹配問(wèn)題虛假匹配：當(dāng)一個(gè)非終結(jié)符用某一候選式匹配成功時(shí)，4.3LL(1)分析法下面將集中討論不帶回溯的自上而下分析法4.3

LL(1)分析法消除文法左遞歸提左因子、避免回溯LL(1)分析條件、LL(1)文法4.4遞歸下降分析程序構(gòu)造實(shí)現(xiàn)LL(1)分析的簡(jiǎn)單方法4.5預(yù)測(cè)分析程序?qū)崿F(xiàn)LL(1)分析的有效方法164.3LL(1)分析法下面將集中討論不帶回溯的自上而4.3.1左遞歸的消除無(wú)法對(duì)左遞歸文法進(jìn)行有效的自上而下分析，因此必須消除文法的左遞歸。直接左遞歸有產(chǎn)生式A→Aα間接左遞歸 沒(méi)有產(chǎn)生式A→Aα,但有推導(dǎo)A+Aα消除直接左遞歸的方法：引入新的非終結(jié)符號(hào)P’，將關(guān)于P的如下產(chǎn)生式P→Pα|β(α非ε且β不以P打頭)替換為

P→βP’

P’→αP’｜ε174.3.1左遞歸的消除無(wú)法對(duì)左遞歸文法進(jìn)行有效的自上而下分例4.2表達(dá)式文法直接左遞歸的消除E→E+T｜TT→T*F｜FF→(E)｜iE→TE’E’→+TE’|εT→FT’T’→*FT’｜εF→(E)｜i消左問(wèn)題：可否不用E’、T’，而用其他非終結(jié)符號(hào)？2022/11/1018Ch4.語(yǔ)法分析---自上而下分析例4.2表達(dá)式文法直接左遞歸的消除E→E+T｜TE文法直接左遞歸消除：練習(xí)消除下面文法的左遞歸：

(1)G(H):H→H;M|MM→d|aHb解:消除左遞歸后的文法：(1)G(H):H→MH’

H’→;MH’|εM→d|aHb

(2)G(A):

A→aAb1|aB→Bb|d

(2)G(A):A→aAb1|aB→dB’B’→bB’|ε2022/11/1019Ch4.語(yǔ)法分析---自上而下分析文法直接左遞歸消除：練習(xí)消除下面文法的左遞歸：解:消除左消除直接左遞歸的一般方法一般而言，假定關(guān)于P的全部產(chǎn)生式是：

PP1|P2|…|Pm|1|2|…

|n

其中,每個(gè)都不等于,而每個(gè)都不以P開(kāi)頭消除P的直接左遞歸就是把這些規(guī)則改寫(xiě)成：

P1P’|2P’|…|nP’P’1P’|2P’|…|mP’|直接左遞歸和間接左遞歸的消除方法均在必須掌握之列。P70.有一個(gè)消除任何左遞歸的算法，下面先舉例說(shuō)明消除間接左遞歸的方法。20消除直接左遞歸的一般方法一般而言，假定關(guān)于P的全部消除間接左遞歸間接左遞歸的消除:先將間接左遞歸變?yōu)橹苯幼筮f歸，再按消直接左遞歸的方法消除。例1：文法(1)A→Bb有間接左遞歸(2)B→Ac(3)B→d先將(1)代入(2)得：B→Bbc，于是B→Bbc|d再消除直接左遞歸，得到的文法不含左遞歸:

A→Bb

B→dB’B’→bcB’|21消除間接左遞歸間接左遞歸的消除:先將間接左遞歸變?yōu)橹苯幼筮f消除間接左遞歸：例1例1：有間接左遞歸文法：(1)A→Bb(2)B→Ac(3)B→d

也可以先將(2)(3)代入(1)得:A→Acb|db再消直接左遞歸,得到不含左遞歸的文法:

A→dbA’A’→cbA’|εB現(xiàn)在是無(wú)用符號(hào),把B及其產(chǎn)生式刪除。說(shuō)明：代入方法不同，得到的不含左遞歸的文法可能是不一樣的，但它們等價(jià)。消左以后，可能會(huì)出現(xiàn)無(wú)用符號(hào)，應(yīng)把它們?nèi)サ簟?2消除間接左遞歸：例1例1：有間接左遞歸文法：22間接左遞歸的消除：例2例2：有間接左遞歸的文法：S→Ac|cA→Bb|b B→Sa|a(1)將B的定義代入A的產(chǎn)生式得：A→Sab|ab|b(2)將A的定義代入S的產(chǎn)生式得:

S→Sabc|abc|bc|c(3)消除其直接左遞歸：S→abcS’|bcS’|cS’ S’→abcS’|ε(4)刪除“多余的”產(chǎn)生式：A→Sab|ab|b和B→Sa|a結(jié)果：

S→abcS’|bcS’|cS’ S’→abcS’|ε 23間接左遞歸的消除：例2例2：有間接左遞歸的文法：23消除左遞歸的算法(P70.)消除左遞歸要求文法:

1.無(wú)回路(無(wú)形如P+P的推導(dǎo))；2.無(wú)ε產(chǎn)生式算法(1)以某種順序?qū)⑽姆ǚ墙K結(jié)符排列P1,P2,…,Pn(2)Fori:=1tondobeginforj:=1toi-1do把形如Pi→Pjγ的規(guī)則改寫(xiě)為

Pi→δ1γ|δ2γ|…|δkγ其中,Pj→δ1|δ2…|δk是關(guān)于Pj的全部產(chǎn)生式;消除Pi規(guī)則的直接左遞歸;

end; (3)化簡(jiǎn)由(2)得到的文法,去掉無(wú)用的非終結(jié)符號(hào)。24消除左遞歸的算法(P70.)消除左遞歸要求文法:

1.無(wú)消左遞歸算法：例4.3解：將非終結(jié)符排序?yàn)镽、Q、S。對(duì)于R不存在直接左遞歸，把R代入Q的候選式：

QSab|ab|b

現(xiàn)在Q也不含直接左遞歸，把Q代入S的候選式：

SSabc|abc|bc|c

經(jīng)消除S的直接左遞歸后，得到整個(gè)文法：

SabcS’|bcS’|cS’S’abcS’|QSab|ab|bRSa|a

由于關(guān)于Q,R的規(guī)則是多余的,則可化簡(jiǎn)得到：

SabcS’|bcS’|cS’S’abcS’|消除文法SQc|cQRb|bRSa|a

的左遞歸。25消左遞歸算法：例4.3解：將非終結(jié)符排序?yàn)镽、Q、S。消左遞歸算法：注意注意:①非終結(jié)符排序不同,消左遞歸的結(jié)果不同;②不要改變文法的開(kāi)始符號(hào)。③消左還有一個(gè)方法---擴(kuò)充的巴科斯范式(P75.)。例如，例4.3的文法：SQc|cQRb|bRSa|a

如果將非終結(jié)符排序?yàn)镾

、Q、R

則得到無(wú)左遞歸的文法：(參見(jiàn)P70.)

SQc|c

QRb|bRbcaR’|caR’|aR’

R’bcaR’|26消左遞歸算法：注意注意:①非終結(jié)符排序不同,消左遞4.3.2消除回溯、提左因子強(qiáng)調(diào):實(shí)現(xiàn)有效的自上而下分析，要求文法不得含左遞歸，并且不得回溯?，F(xiàn)在左遞歸已經(jīng)解決。接下來(lái)討論:1.在不得回溯的情況下進(jìn)行自上而下分析，對(duì)于文法有什么要求。2.如何改寫(xiě)文法使?jié)M足消除回溯的要求。需要引入:符號(hào)串α的終結(jié)首符集FIRST(α)非終結(jié)符A的后隨終結(jié)符集FOLLOW(A)274.3.2消除回溯、提左因子強(qiáng)調(diào):實(shí)現(xiàn)有效的自上而下分析為避免回溯對(duì)文法的要求回溯的產(chǎn)生是由于文法中存在非終結(jié)符A有n個(gè)候選式：

A1|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。A輸入串…a…Sαi

……28為避免回溯對(duì)文法的要求回溯的產(chǎn)生是由于文法中存在非終結(jié)符A有為避免回溯引入FIRST()集回溯的產(chǎn)生是由于文法中存在非終結(jié)符A有n個(gè)候選式：

A1|2|…|n在面臨當(dāng)前輸入符號(hào)a時(shí)要能準(zhǔn)確指出唯一可使用的候選式i去代表A謀求與輸入串相匹配，顯然要求各i的終結(jié)首符號(hào)互不相同。

引入符號(hào)串α的終結(jié)首符集FIRST(α)，上述要求即：FIRST(i)∩FIRST(j)=φ

i≠j，i,j=1,2,…,n顯然，當(dāng)輸入符號(hào)a∈FIRST(i)時(shí),可以確定用候選式i去謀求匹配。29為避免回溯引入FIRST()集回溯的產(chǎn)生是由于文法中存在非FIRST()集合及作用令G是一個(gè)不含左遞歸的文法,符號(hào)串∈{VT∪VN}*定義的終結(jié)首符集為：

FIRST()={a|*a…且aVT}特別是，若*，則規(guī)定FIRST()。FIRST集合的作用:如果非終結(jié)符A的任何兩個(gè)不同的候選i和j有：

FIRST(i)

FIRST(j)=

那么，當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的當(dāng)前輸入符號(hào)a，準(zhǔn)確地指派某個(gè)候選前去執(zhí)行任務(wù),這個(gè)候選就是那個(gè)終結(jié)首符集合含a的i。30FIRST()集合及作用令G是一個(gè)不含左遞歸的文法,符號(hào)例1：文法:S→aAA→εS→dA→bAS

FIRST(S)={a,d}FIRST(bAS)=FIRST(A)={ε,b}FIRST(ε)={ε}例2：文法:S→AaA→εS→dA→baS

FIRST(S)={b,a,d}FIRST(Aa)={a,b}FIRST(A)={ε,b}計(jì)算FIRST集合:例2022/11/1031Ch4.語(yǔ)法分析---自上而下分析例1：文法:S→aAA→ε計(jì)算FIRST集練習(xí)：文法E→E+T|TT→T*F|FF→(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}2022/11/1032Ch4.語(yǔ)法分析---自上而下分析練習(xí)：文法E→E+T|TT→T*F如何把一個(gè)文法改造成所有候選式的終結(jié)首符集兩兩不相交呢？其辦法是提取公共左因子。例如，假定關(guān)于A的規(guī)則是:

A1|2|…|n|1|2|…|m

(其中每個(gè)不以開(kāi)頭)

那末，可以引進(jìn)新的非終結(jié)符,把這些規(guī)則改寫(xiě)成：

AA’|1|2|…|mA’1|

2|…|

n改寫(xiě)文法避免回溯:提左因子1|2|…|n=(1|2|…|n)33如何把一個(gè)文法改造成所有候選式的終結(jié)首符集兩兩不相交呢？改寫(xiě)例1:有產(chǎn)生式BbBcA|b

由于FIRST(bBcA)FIRST(b)=

則需要對(duì)BbBcA|b提取公共左因子b將產(chǎn)生式改寫(xiě)成：B

bB’B’

BcA|提左因子：例例2:有文法ScAd|bA

ab|a

由于FIRST(ab)FIRST(a)={a}

則需要對(duì)A

ab|a提取公共左因子a將文法改寫(xiě)成：ScAd|bA

aA’A’

b|34例1:有產(chǎn)生式BbBcA|b提左因子練習(xí)1:有文法

SiBtS|iBtSeS|aBb提取公共左因子改寫(xiě)文法。提左因子：練習(xí)1解:提取公共左因子，將文法改寫(xiě)為

SiBtSS’|aS’ε|eS

B

b2022/11/1035Ch4.語(yǔ)法分析---自上而下分析練習(xí)1:有文法提左因子：練習(xí)1解:提取公共左因子，將文練習(xí)2:有文法

AaAB1|aBBb|d改寫(xiě)文法,使其不含左遞歸,能避免回溯。改寫(xiě)文法：練習(xí)2解:將文法改寫(xiě)為:

AaA’A’AB1|ε

B

dB’B’bB’|ε

2022/11/1036Ch4.語(yǔ)法分析---自上而下分析練習(xí)2:有文法改寫(xiě)文法：練習(xí)2解:將文法改寫(xiě)為:204.3.3LL(1)分析條件設(shè)文法滿足:①不含左遞歸;②若有A→α1|α2|…|αn,則FIRST(αi)∩FIRST(αj)=φi≠j是否就能進(jìn)行有效的自上而下分析呢?例4.4P69.(4.2)的算術(shù)表達(dá)式文法E

TE’E’+TE’|εT

FT’T’*FT’|εF(E)|i該文法不含左遞歸,候選式的FIRST集合兩兩不交考察識(shí)別輸入串i+i#(#是句末符,#不屬于VT)374.3.3LL(1)分析條件設(shè)文法滿足:①不含LL(1)分析條件的提出(1)E只有一個(gè)候選TE’,E替換為T(mén)E’T只有一個(gè)候選FT’,T替換為FT’F有兩個(gè)候選,i∈FIRST(i)F替換為i,i得到匹配,移動(dòng)ip指+T’有兩個(gè)候選,+不屬于任一候選的FIRST集;但有T’→ε,認(rèn)為T(mén)’自動(dòng)匹配ε注意：+號(hào)并不讀進(jìn)！ETE’i+i#FT’εETE’ii+i#FT’E

TE’E’+TE’|εT

FT’

T’*FT’|εF(E)|i38LL(1)分析條件的提出(1)E只有一個(gè)候選TE’,E替換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(mén)’自動(dòng)匹配ε。#不屬于E’任一候選的FIRST集，但有E’→ε,認(rèn)為E’自動(dòng)匹配ε。εε+TE’iFT’ETE’iFT’εi+i#i+i#i+i#E

TE’E’+TE’|εT

FT’

T’*FT’|εF(E)|i39LL(1)分析條件的提出(2)E’有兩個(gè)候選,+∈FIRSLL(1)分析條件的提出(3)i+i#最后得到與i+i相匹配的語(yǔ)法樹(shù)εε+TE’iFT’ETE’iFT’ε問(wèn)題:是不是一旦非終結(jié)符A面臨輸入符號(hào)a,且a不屬于所有FIRST(αi),但ε屬于某個(gè)FIRST(αj),就一定可以使A自動(dòng)匹配ε呢?答案是不一定。在一定的條件下才可以。否則錯(cuò)誤。條件是a允許跟在A的緊后面例如上例中，+可跟在T’后，#可跟在T’、E’后面。下面定義可跟在非終結(jié)符后的終結(jié)符號(hào)的集合FOLLOW。40LL(1)分析條件的提出(3)i+i#最后得到與i+i相非終結(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é)符或‘#’。例：S→aAA→εS→dA→bAS

FOLLOW(S)={#,a,d}FOLLOW(A)={a,d,#}∵SaAabASabbASS41非終結(jié)符的后隨終結(jié)符集FOLLOW假定S是文法G的開(kāi)始符號(hào)，計(jì)算FOLLOW集合：例例：P69.(4.2)表達(dá)式文法

E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFOLLOW(T’)={#,+,)}∵ETE’TFT’∴有#號(hào)∵ETE’T+TE’

FT’+TE’∴有+號(hào)∵ETE’TFT’

(E)T’(TE’)T’(T)T’(FT’)T’∴有)號(hào)2022/11/1042Ch4.語(yǔ)法分析---自上而下分析計(jì)算FOLLOW集合：例例：P69.(4.2)表達(dá)式文法∵LL(1)分析條件：3個(gè)(1)文法不含左遞歸。(2)對(duì)于文法中每個(gè)非終結(jié)符A的各個(gè)候選式的終結(jié)首符集兩兩不相交。即，若

A1|

2|…|

n

則：FIRST(i)

FIRST(j)=(ij)(3)對(duì)文法中每一個(gè)非終結(jié)符A，若它存在某個(gè)候選式的終結(jié)首符集包含，則

FIRST(A)FLLOW(A)=

特別注意第3個(gè)條件：當(dāng)空字ε屬于非終結(jié)符的某個(gè)候選式的終結(jié)首符集時(shí)的條件!!!2022/11/1043Ch4.語(yǔ)法分析---自上而下分析LL(1)分析條件：3個(gè)(1)文法不含左遞歸。2022/1LL(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(1)文法是無(wú)二義文法,上述三個(gè)條件是LL(1)文法無(wú)二義的充分條件。對(duì)LL(1)文法，可以對(duì)其輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。44LL(1)文法一個(gè)文法G若滿足上述LL(1)分析的三個(gè)條件，LL(1)文法：自上而下分析過(guò)程對(duì)LL(1)文法，假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為：A1|

2|…|

n(1)若a∈FIRST(i),則指派i執(zhí)行匹配任務(wù)。(2)

若a不屬于任何一個(gè)候選式的終結(jié)首符集,則:①若ε屬于某個(gè)FIRST(j)且a∈FOLLOW(A),則讓A與ε自動(dòng)匹配;②否則,a的出現(xiàn)是一種錯(cuò)誤。根據(jù)LL(1)文法的條件,每一步這樣的工作都是確信無(wú)疑的。2022/11/1045Ch4.語(yǔ)法分析---自上而下分析LL(1)文法：自上而下分析過(guò)程對(duì)LL(1)文法，假設(shè)要用非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集都不含ε46LL(1)文法：例例4.2文法(P69.)不是LL(1)LL(1)文法:例2例2文法G:S→LU

L→i:|εU→i=e因?yàn)?1.不含左遞歸2.L的各個(gè)候選的FIRST集合互不交3.L有個(gè)候選式的FIRST集合含ε,再求得FIRST(L)={i,ε},FOLLOW(L)={i},是相交的所以G不是LL(1)文法。2022/11/1047Ch4.語(yǔ)法分析---自上而下分析LL(1)文法:例2例2文法G:S→LU4.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ǔ)法分析程序稱為遞歸下降分析器。2022/11/1048Ch4.語(yǔ)法分析---自上而下分析4.4遞歸下降分析程序構(gòu)造當(dāng)一個(gè)文法滿足LL(1)條件時(shí)遞歸下降分析程序構(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ò)診察處理。2022/11/1049Ch4.語(yǔ)法分析---自上而下分析遞歸下降分析程序構(gòu)造：

過(guò)程和變量先設(shè)定一些過(guò)程和變量，作為遞歸下降分析程序構(gòu)造：

非終結(jié)符對(duì)應(yīng)的遞歸過(guò)程的結(jié)構(gòu)①A1|

2|…|

n②=X1X2…XmXi∈(VT∪VN)③Xi∈VT④Xi∈VN①I(mǎi)F…ELSEIF…ELSE…結(jié)構(gòu)②順序結(jié)構(gòu)③IFSYM=XiTHENADVANCEELSE

ERROR④調(diào)用Xi對(duì)應(yīng)的遞歸過(guò)程50遞歸下降分析程序構(gòu)造：

非終結(jié)符對(duì)應(yīng)的遞歸過(guò)程的結(jié)構(gòu)①A例:算術(shù)表達(dá)式的遞歸下降分析器(1)Ｅ的子程序

E→TE’

procedureE;beginT;Ｔ的過(guò)程調(diào)用E’E’的過(guò)程調(diào)用end;

Ｅ’的子程序

E’→+TE’|ε

procedureE’;IFSYM=‘+’THENbeginADVANCE;T;T的過(guò)程調(diào)用E’E’的過(guò)程調(diào)用

end; 2022/11/1051Ch4.語(yǔ)法分析---自上而下分析例:算術(shù)表達(dá)式的遞歸下降分析器(1)Ｅ的子程序E→TE’例:算術(shù)表達(dá)式的遞歸下降分析器(2)T的子程序

T→FT’

procedureT;beginF;F的過(guò)程調(diào)用T’T’的過(guò)程調(diào)用end;

T’的子程序

T’→*FT’|ε

procedureE’;IFSYM=‘*’THENbeginADVANCE;F;F的過(guò)程調(diào)用T’T’的過(guò)程調(diào)用

end; 2022/11/1052Ch4.語(yǔ)法分析---自上而下分析例:算術(shù)表達(dá)式的遞歸下降分析器(2)T的子程序T→FT’例:算術(shù)表達(dá)式的遞歸下降分析器(3)F的子程序

F→i|(E)

procedureF;IFSYM=‘i’then ADVANCEELSE IFSYM=‘(‘then

BEGINADVANCE;E;E的過(guò)程調(diào)用

IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR; 2022/11/1053Ch4.語(yǔ)法分析---自上而下分析例:算術(shù)表達(dá)式的遞歸下降分析器(3)F的子程序F→i|(擴(kuò)充巴科斯范式定義系統(tǒng)對(duì)前面的產(chǎn)生式(巴科斯范式)進(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ò)充巴科斯范式定義Decimal→[sign]integer.{digit}[exponent]54擴(kuò)充巴科斯范式定義系統(tǒng)對(duì)前面的產(chǎn)生式(巴科斯范式)進(jìn)行擴(kuò)充使用擴(kuò)充BNF定義系統(tǒng)的好處(1)(1)直觀易懂:如表示不超過(guò)10位的無(wú)符號(hào)整數(shù)<無(wú)符號(hào)數(shù)>→<數(shù)字>{<數(shù)字>}90ET|E+TTF|T*FF(E)|iET{+T}TF{*F}F(E)|i例,提左因子ABC|BCD|AXZ|AXYABC(ε|D)|AX(Z|Y)提左ABC(ε|D){X(Z|Y)}消左(2)便于表示消除左遞歸和提取左因子消除回溯例,消除左遞歸，不用引入新的非終結(jié)符和ε產(chǎn)生式55使用擴(kuò)充BNF定義系統(tǒng)的好處(1)(1)直觀易懂:如表示不使用擴(kuò)充BNF定義系統(tǒng)的好處(2)(3)便于構(gòu)造自上而下分析程序,過(guò)程是:

關(guān)于非終結(jié)符A的產(chǎn)生式寫(xiě)為擴(kuò)充BNF定義形式畫(huà)出其語(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)的排列順序|或[]分支{}回路.連接順序56使用擴(kuò)充BNF定義系統(tǒng)的好處(2)(3)便于構(gòu)造自上而下分析用語(yǔ)法圖描述語(yǔ)言的文法:例(P75.)T→F|T*FT→F{*F}的語(yǔ)法圖＊ＦＴ+TEE→T|E+T

E→T{+T}的語(yǔ)法圖iＥＦ

（）F→i|(E)的語(yǔ)法圖57用語(yǔ)法圖描述語(yǔ)言的文法:例(P75.)T→F|T*F＊ＦＴ例:簡(jiǎn)單算術(shù)表達(dá)式的

遞歸下降分析器(P76.)EE→T{+T}Ｅ的子程序,請(qǐng)與P74.的程序?qū)φ誴rocedureE;beginT; Ｔ的過(guò)程調(diào)用

whileSYM='+'do當(dāng)前符號(hào)等于＋時(shí)beginADVANCE;處理終結(jié)符＋

TＴ的過(guò)程調(diào)用

endend; SYM：當(dāng)前符號(hào)

58例:簡(jiǎn)單算術(shù)表達(dá)式的

遞歸下降分析器(P76.)EE→T{例:簡(jiǎn)單算術(shù)表達(dá)式的

遞歸下降分析器(P76.)TT→F{*F}Ｔ的子程序,請(qǐng)與P74.的程序?qū)φ誴rocedureT;beginF;Ｆ的過(guò)程調(diào)用

whileSYM='*'then當(dāng)前符號(hào)等于＊時(shí)begin

ADVANCE;處理終結(jié)符＊

F Ｆ的過(guò)程調(diào)用

endend;59例:簡(jiǎn)單算術(shù)表達(dá)式的

遞歸下降分析器(P76.)TT→F{總結(jié)遞歸子程序法1.構(gòu)造文法。2.改寫(xiě)文法：消除二義性、消除左遞歸、提取公共左因子。3.求每個(gè)候選式的FIRST集和非終結(jié)符的FOLLOW集。4.檢查是不是LL(1)文法,是否滿足LL(1)分析的三個(gè)條件。5.若是LL(1)文法，為該文法的每個(gè)非終結(jié)符畫(huà)出語(yǔ)法圖。6.按照語(yǔ)法圖，為每個(gè)非終結(jié)符編寫(xiě)一個(gè)遞歸子程序。60總結(jié)遞歸子程序法1.構(gòu)造文法。604.5預(yù)測(cè)分析程序?qū)崿F(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é)符的FOLLOW集合的方法。2.構(gòu)造預(yù)測(cè)分析表的方法。2022/11/1061Ch4.語(yǔ)法分析---自上而下分析4.5預(yù)測(cè)分析程序?qū)崿F(xiàn)LL(1)分析的另一種有效方法是使用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é)束符2022/11/1062Ch4.語(yǔ)法分析---自上而下分析4.5.1預(yù)測(cè)分析程序工作過(guò)程系統(tǒng)維持一張分析表和一個(gè)分析預(yù)測(cè)分析器模型P77.圖4.4.…….a………..#x...#總控程序見(jiàn)P77.預(yù)測(cè)分析表M見(jiàn)P76.表4.1輸出分析棧輸入緩沖區(qū)預(yù)測(cè)分析表是預(yù)測(cè)分析器的核心2022/11/1063Ch4.語(yǔ)法分析---自上而下分析預(yù)測(cè)分析器模型P77.圖4.4.…….a………..#x總控預(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)元素M[A,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ù)分析表、分析棧及輸入串的當(dāng)前符號(hào)進(jìn)行控制。64預(yù)測(cè)分析程序的邏輯結(jié)構(gòu)1.一個(gè)輸入串,“#”號(hào)為輸入串結(jié)束表達(dá)式文法的預(yù)測(cè)分析表(P76.)輸入符號(hào)非終結(jié)符i+*()#EE→TE’E→TE’E＇E’→+TE’E’→εE’→εTT→FT’T→FT’Ｔ＇T’→εT’→*FT’T’→εT’→εＦF→iF→(E)2022/11/1065Ch4.語(yǔ)法分析---自上而下分析表達(dá)式文法的預(yù)測(cè)分析表(P76.)輸入符號(hào)非終結(jié)符i+*()預(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查看分析表M[X,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)得到匹配。

66預(yù)測(cè)分析程序的工作過(guò)程(1)在系統(tǒng)啟動(dòng)時(shí)，輸入指針指向輸入串預(yù)測(cè)分析程序的工作過(guò)程(2)(3)若X∈VN

,則查分析表項(xiàng)M[X,a]:①若M[X,a]中存放的是X→X1X2…Xk,則將X從棧頂逐出,讓X1,X2,…,Xk反序進(jìn)棧。②若M[X,a]中存放的是X→ε,則將X逐出,不推什么進(jìn)棧。③若M[X,a]中存放的是出錯(cuò),則調(diào)用ERROR進(jìn)行錯(cuò)誤處理。預(yù)測(cè)分析程序的總控程序的形式描述(見(jiàn)P77.)2022/11/1067Ch4.語(yǔ)法分析---自上而下分析預(yù)測(cè)分析程序的工作過(guò)程(2)(3)若X∈VN,則查分析表項(xiàng)預(yù)測(cè)分析程序的工作過(guò)程(P78.)例4.6文法(4.2),輸入串為i*i+i,分析步驟：分析棧

輸入串

所用產(chǎn)生式動(dòng)作#Ei*i+i#查表M[E,i],出入棧#E'Ti*i+i#E→TE‘查表M[T,i],出入棧#E'T'Fi*i+i#T→FT‘查表M[F,i],出入棧#E‘T’ii*i+i#F→i匹配,i出棧,調(diào)指針#E'T'*i+i#查表M[T’,*],出入棧#E‘T’F**i+i#T'→*FT’匹配,*出棧,調(diào)指針#E'T’Fi+i#查表M[F,i],出入棧#E'T’ii+i#F→i匹配,i出棧,調(diào)指針68預(yù)測(cè)分析程序的工作過(guò)程(P78.)例4.6文法(4.2),輸#E’T’+i#查表M[T’,+],出入棧#E‘+i#T’→ε查表M[E’,+],出入棧#E‘T++i#E’→+TE’匹配,+出棧,調(diào)指針#E'Ti#查表M[T,i],出入棧#E'T'Fi#T→FT‘查表M[F,i],出入棧#E'T‘ii#F→i匹配,i出棧,調(diào)指針#E'T‘#查表M[T’,#],出入棧#E‘#T'→ε查表M[E’,#],出入棧##E'→ε所用的產(chǎn)生式序列形成了最左推導(dǎo)對(duì)應(yīng)的分析樹(shù)分析棧

輸入串

所用產(chǎn)生式動(dòng)作

#E'T’ii+i#F→i匹配,i出棧,調(diào)指針69#E’T’+i#查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è)分析器。 704.5.2預(yù)測(cè)分析表的構(gòu)造預(yù)測(cè)分析法步驟:70FIRST集和FOLLOW集前面定義了:對(duì)于α∈(ＶT∪ＶN)*

,

α的終結(jié)首符號(hào)集

FIRST(α)={a|α*a…，a∈ＶT*}特別的，若α*ε，則ε∈FIRST(α)。對(duì)于A∈ＶN,A的后隨終結(jié)符號(hào)集：

FOLLOW(A)={a|S*…Aa…，a∈ＶT}

特別的,若S*…A,則#∈FOLLOW(A)。下面介紹構(gòu)造集合FIRST和FOLLOW的算法2022/11/1071Ch4.語(yǔ)法分析---自上而下分析FIRST集和FOLLOW集前面定義了:2022/11/97求FIRST(X)的算法(P78.)設(shè)文法符號(hào)X∈ＶT∪ＶN(1)若X∈ＶT，則FIRST(X)={X}；(2)若X∈ＶN，取FIRST(X)的初值： {a|X→a…∈￡}X→ε￡FIRST(X)= {a|X→a…∈￡}∪{ε}X→ε∈￡第(2)條的要點(diǎn)是查看X的產(chǎn)生式!(3)下頁(yè)72求FIRST(X)的算法(P78.)設(shè)文法符號(hào)X∈ＶT∪ＶN(3)若X∈ＶN，重復(fù)如下過(guò)程，直到其FIRST集不再增大:①若X→Y…∈￡，且Y∈ＶN，則FIRST(X)=FIRST(X)∪(FIRST(Y)-{ε})②若X→Y1…Yk∈￡,且Y1……Yi-1*ε

即ε∈FIRST(Yn),其中n=1到i-1,則FIRST(X)=FIRST(X)∪(FIRST(Yn)-{ε})③若Y1……Yk*ε,即ε∈任何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)的算法73(3)若X∈ＶN，重復(fù)如下過(guò)程，直到其FIRST集不再增大設(shè)符號(hào)串α=X1X2……Xn，構(gòu)造FIRST(α),重復(fù)如下過(guò)程，直到其FIRST集不再增大:(1)首先置FIRST(α)=FIRST(X1)-{ε}(2)若對(duì)任何j=1到i-1,若X1……Xi-1*ε,則FIRST(α)=FIRST(α)∪(FIRST(Xj)-{ε})(3)若X1……Xn*ε，則FIRST(α)=FIRST(α)∪{ε}計(jì)算FIRST(α)的要點(diǎn)是從左到右查看α的一個(gè)個(gè)符號(hào)，計(jì)算符號(hào)的FIRST集合，檢查是否含ε,以決定是否繼續(xù)計(jì)算！求FIRST(α)的算法(P79.)74設(shè)符號(hào)串α=X1X2……Xn，構(gòu)造FIRST(α),重復(fù)如下例4.7表達(dá)式文法符號(hào)的FIRST集FIRST(F)={(,i}FIRST(T)=FIRST(F)={(,i}FIRST(E)=FIRST(T)={(,i}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+}FIRST(*)={*}FIRST(()={(}FIRST())={)}FIRST(i)={i}FIRST(+TE’)={+}FIRST(ETF)={(,i}FIRST(E’T’F)={+,*,(,i}FIRST(E’T’)={+,*,ε}文法(4.2):E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|i75例4.7表達(dá)式文法符號(hào)的FIRST集FIRST(F)=計(jì)算FIRST集：例例1文法G[S]:

S→LUL→Ui:|εU→e=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文法G[E]:

E→E+T|TT→T*F|FF→(E)|iFIRST(E)={(,i}FIRST(T)={(,i}FIRST(F)={(,i}FIRST(E+T)={(,i}FIRST(T*F)={(,i}FIRST((E))={(}76計(jì)算FIRST集：例例1文法G[S]:例2文法G[E]計(jì)算FIRST集：練習(xí)解：FIRST(A)={a}FIRST(A’)={a,ε}FIRST(B)=eonoomoFIRST(B')={b,ε}FIRST(AB1)={a}FIRST(A’B’1)={a,b,1}FIRST(A’B’)={a,b,ε}文法G[A]:A→aA’A'→AB1|εB→dB'B’→bB’|ε

計(jì)算:FIRST(A),FIRST(A’)FIRST(B),FIRST(B')FIRST(AB1)FIRST(A’B’1)FIRST(A’B’)77計(jì)算FIRST集：練習(xí)解：文法G[A]:77求FOLLOW(A)的算法(P79.)設(shè)文法G[S],對(duì)G的所有非終結(jié)符,重復(fù)作以下計(jì)算:(1)將#加入到FOLLOW(S),#為句子的結(jié)束符(2)若A→αBβ，B∈ＶN則FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}(3)如果A→αB或A→αBβ,且β*ε，A≠B，則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)!!78求FOLLOW(A)的算法(P79.)設(shè)文法G[S],對(duì)G的例4.7表達(dá)式文法符號(hào)的FOLLOW集FOLLOW(E)={),#}FOLLOW(E')=FOLLOW(E)={),#}FOLLOW(T)={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)={*,+,),#}文法(4.2)E→TE'E'→+TE’|εT→FT'T'→*FT’|εF→(E)|i2022/11/1079Ch4.語(yǔ)法分析---自上而下分析例4.7表達(dá)式文法符號(hào)的FOLLOW集FOLLOW(E)=計(jì)算FOLLOW集：例例1文法G[E]:

E→E+T|TT→T*F|FF→(E)|iFOLLOW(E)={+,),#}FOLLOW(T)={*,+,),#}FOLLOW(F)={*,+,),#}例2文法G[S]:

S→LUL→Ui:|εU→e=i|εFOLLOW(S)={#}FOLLOW(L)={e,#}FOLLOW(U)={i,#}2022/11/1080Ch4.語(yǔ)法分析---自上而下分析計(jì)算FOLLOW集：例例1文法G[E]:例2文法G[S計(jì)算FOLLOW集：練習(xí)解：FOLLOW(A)={d,#}FOLLOW(A')=FOLLOW(A)={d,#}FOLLOW(B)={1}FOLLOW(B')=FOLLOW(B)={1}文法G[A]:A→aA’A'→AB1|εB→dB'B‘→bB’|ε

計(jì)算:FOLLOW(A),FOLLOW(A')FOLLOW(B),FOLLOW(B')

2022/11/1081Ch4.語(yǔ)法分析---自上而下分析計(jì)算FOLLOW集：練習(xí)解：文法G[A]:2022/11/9預(yù)測(cè)分析表(LL(1)分析表)的

構(gòu)造算法(P79.)構(gòu)造分析表M的算法是確定每個(gè)表元素，即確定M[A,a]：(1)對(duì)文法G的每個(gè)產(chǎn)生式A,先計(jì)算FIRST(α),若FIRST(α)含有ε,則還要計(jì)算FOLLOW(A),然后執(zhí)行第⑵步和第⑶步；(2)對(duì)于每個(gè)終結(jié)符aFIRST()，把A加到M[A,a]中；(3)若FIRST(),則對(duì)任何的

bFOLLOW(A),把A加至M[A,b]中；(4)把所有無(wú)定義的M[A,a]標(biāo)上“出錯(cuò)標(biāo)志”。82預(yù)測(cè)分析表(LL(1)分析表)的

構(gòu)造算法(P79.)構(gòu)造分例4.8表達(dá)式文法的預(yù)測(cè)分析表輸入符號(hào)非終結(jié)符i+*()#EE→TE’E→TE’E＇E’→+TE’E’→εE’→εTT→FT’T→FT’Ｔ＇T’→εT’→*FT’T’→εT’→εＦF→iF→(E)2022/11/1083Ch4.語(yǔ)法分析---自上而下分析例4.8表達(dá)式文法的預(yù)測(cè)分析表輸入符號(hào)非終結(jié)符i+*()#表達(dá)式文法預(yù)測(cè)分析表的構(gòu)造對(duì)F→(E)|i

FIRST((E))={(}；FIRST(i)={i}

則確定M[F,(]；M[F,i]對(duì)E→TE'FIRST(TE')={(,i}

則M[E,(]=M[E,i]=E→TE'對(duì)E'→+TE'|ε

FIRST(+TE')={+}；FOLLOW(E')={),#}則確定M[E',+];M[E',)]；M[E',#]對(duì)T→FT'FIRST(FT')={(,i}；則確定M[T,(]；M[T,i]對(duì)T'→*FT'|εFIRST(*FT')={*};FORLLOW(T')={+,),#}

則確定M[T',*]；M[T',+]；M[T',)]；M[T',#]84表達(dá)式文法預(yù)測(cè)分析表的構(gòu)造對(duì)F→(E)|iFIR預(yù)測(cè)分析表與LL(1)文法上述構(gòu)造預(yù)測(cè)分析表的算法可應(yīng)用于構(gòu)造任何文法G的預(yù)測(cè)分析表M。但對(duì)于某些文法，其M[A，a]可能持有若干個(gè)產(chǎn)生式，即M[A，a]是多重定義的。如果文法G是左遞歸或二義的，那么，其預(yù)測(cè)分析表M至少含有一個(gè)多重定義入口?？梢宰C明，一個(gè)文法G的預(yù)測(cè)分析表M不含多重定義的入口，當(dāng)且僅當(dāng)該文法是LL(1)文法。例如:(4.2)表達(dá)式文法是LL(1)文法,分析表不含多重定義;而下面例子的文法不是LL(1)文法。85預(yù)測(cè)分析表與LL(1)文法上述構(gòu)造預(yù)測(cè)分析表的算法可應(yīng)用于構(gòu)構(gòu)造預(yù)測(cè)分析表：例文法:S→iCtSS’|aS'→eS|εC→bFIRST(iCtSS’)={i},FIRST(a)={a}FIRST(eS)={e},FOLLOW(S’)={e,#}FIRST(b)=

a

b

e

i

t#SS→aS→iCtSS’

S’S’→eSS’→εS’→ε

CC→b該文法不是LL(1)文法!86構(gòu)造預(yù)測(cè)分析表：例文法:S→iCtSS’|aS'→構(gòu)造預(yù)測(cè)分析表：練習(xí)P82.第4題文法,構(gòu)造LL(1)分析表(預(yù)測(cè)分析表)。Expr→－ExprExpr→(Expr)|VarExprTailExprTail→－Expr|εVar→idVarTail做作業(yè)時(shí)要寫(xiě)出各非終VarTail→(Expr)|ε結(jié)符的FOLLOW()集合－()

id#Expr－Expr(Expr)VarExprTailExprTail－ExprεεVaridVarTailVarTailε(Expr)εε87構(gòu)造預(yù)測(cè)分析表：練習(xí)P82.第4題文法,構(gòu)造LL(1)分由預(yù)測(cè)分析表構(gòu)造遞歸下降分析程序(1)E→TE’Ｅ的子程序

procedureE;beginifsym=‘i’orsym=‘(‘thenbeginT;Ｔ的過(guò)程調(diào)用E’E’的過(guò)程調(diào)用

end

elseerrorend; T→FT’T的子程序procedureT;beginifsym=‘i’orsym=‘(‘thenbeginF;F的過(guò)程調(diào)用T’T’的過(guò)程調(diào)用end

elseerrorend; 88由預(yù)測(cè)分析表構(gòu)造遞歸下降分析程序(1)E→TE’Ｅ的子程序由預(yù)測(cè)分析表構(gòu)造遞歸下降分析程序(2)E’→+TE’|εＥ’的子程序procedureE’;beginifsym=‘+’thenbeginadvance;T;T的過(guò)程調(diào)用E’E’的過(guò)程調(diào)用

endelseifsym=‘i’orsym=‘*’orsym=‘(‘thenerror

end; 89由預(yù)測(cè)分析表構(gòu)造遞歸下降分析程序(2)E’→+TE’|ε由預(yù)測(cè)分析表構(gòu)造遞歸下降分析程序(3)T’→*FT’|ε

T’的子程序procedureT’;beginifsym=‘*’thenbeginadvance;F;F的過(guò)程調(diào)用T’