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

程序設計語言

2022/11/101Ch4.語法分析---自上而下分析編譯原理第四章程序設計語言2022/11/本章在編譯程序中的地位表格管理詞法分析器語法分析器語義分析與中間代碼產生優化器目標代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標代碼出錯處理2本章在編譯程序中的地位表詞法分析器語法分析器語義分析與中間代回顧：語法分析任務：在詞法分析的基礎上，根據語言的語法規則，把單詞符號串分解成各類語法單位，如“短語”、“句子”、“子句”、“程序段”等，為語法正確的輸入構造語法樹(或分析樹)。語法分析依據的是語言的語法規則，即描述程序結構的規則，通過語法分析確定整個輸入串是否構成一個語法上正確的程序。語法規則通常用上下文無關文法描述。語法分析方法有自上而下和自下而上兩類。本章和下一章將介紹編譯程序構造中的一些典型的語法分析方法。3回顧：語法分析任務：在詞法分析的基礎上，根據語言的語法規則，典型的語法分析方法自上而下語法分析方法第四章介紹

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

自下而上語法分析方法第五章介紹

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

2022/11/104Ch4.語法分析---自上而下分析典型的語法分析方法自上而下語法分析方法第四章介紹202CH.4語法分析---自上而下分析掌握：消除文法左遞歸，消除回溯，計算FIRST集、FOLLOW集，LL(1)分析條件，LL(1)文法的概念，預測分析表的構造。了解理解：自上而下分析方法的基本思想,自上而下分析的過程。教學內容：4.1語法分析器的功能4.2自上而下分析面臨的問題

4.3

LL(1)分析法

4.4遞歸下降分析程序的構造

4.5預測分析程序

*4.6LL(1)分析中的錯誤處理重點難點5CH.4語法分析---自上而下分析掌握：消除文法左遞歸，4.1語法分析器的功能語法分析是編譯程序的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定一串單詞符號的語法結構是否符合語法規則,是否文法的一個句子。分析判定的方法：建立輸入串αn的從文法開始符號S出發的推導

Sα1…αn即建立以S為根的與輸入串αn相匹配的語法樹圖4.1表明語法分析器在編譯程序中的地位64.1語法分析器的功能語法分析是編譯程序的核心部分。64.2自上而下分析面臨的問題本節主要是通過例子1.說明自上而下分析方法的思想和步驟2.認識自上而下分析時所遇到的主要困難自上而下分析的主要困難是:文法的左遞歸性，使分析陷入無限循環回溯的不確定性，要求將已經完成工作推倒重來為解決這些問題，考慮要消除文法左遞歸和避免回溯。2022/11/107Ch4.語法分析---自上而下分析4.2自上而下分析面臨的問題本節主要是通過例子2022/1自上而下分析方法的思想從文法的開始符號出發，向下推導，試圖推出句子，匹配輸入符號串，尋找輸入串的最左推導，并按與最左推導相對應的順序，自上而下從左到右地建立輸入串的語法分析樹。推導過程中，試圖根據當前的輸入符號判斷使用非終結符的哪個候選式去替換。分析過程是一種窮盡一切可能的試探過程；是反復使用不同產生式謀求匹配輸入串的過程。用例子說明，P67.例4.18自上而下分析方法的思想從文法的開始符號出發，向下推導，試圖推自上而下分析(1)例4.1文法：⑴S→xAy⑵A→**⑶A→*

輸入串α=x*y，分析α是否文法的句子？序號ip指向語法樹最左推導說明x*yS根結S,當前符x①x*y③x得匹配,移動ipSxAySxAy用S→xAy展開S欲用xAy匹配輸入串SxAy②x*y9自上而下分析(1)例4.1文法：⑴S→xAy序號ip自上而下分析(2)序號ip指向語法樹最左推導說明Sx*yxAy試用A→**展開ASxAyx**y④**x*y⑤*得匹配,移動ip但y得不到匹配SxAy**用A→**展開失敗回溯:回到第③步⑥SxAySxAyx*y10自上而下分析(2)序號ip指向語法樹最左推導自上而下分析(3)序號ip指向語法樹最左推導說明x*ySxAy試用A→*展開ASxAyx*y⑦*x*y⑧*得匹配,移動ipSxAy*A完成匹配,y得匹配,移動ip,輸入串匹配成功,結束⑨SxAySxAyx*yx*y*11自上而下分析(3)序號ip指向語法樹最左推導自上而下分析：說明注:

自上而下分析過程是帶回溯的試探過程⑴遇非終結符標記的結,就試圖用某個候選式展開,期望此候選能匹配輸入串,若不能匹配,則要回溯。⑵遇終結符號的結，就進行匹配，然后移動輸入串指針ip指向下一個符號。⑶回溯是一項復雜而費時的工作，須廢棄已做的許多工作，恢復到前面的某一情況，效率很低。下面討論自上而下分析法存在的困難和缺點左遞歸、回溯、虛假匹配、當報告分析不成功時難于知道輸入串中出錯的確切位置，等12自上而下分析：說明注:自上而下分析過程是帶回溯的試探過程1文法的左遞歸問題文法的左遞歸性直接左遞歸：文法存在產生式P→Pα間接左遞歸：存在推導P+Pα文法具有左遞歸性，采用自上而下方法分析，可能會陷入無限循環，分析不下去。例如：文法有左遞歸產生式A→Ax

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

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

LL(1)分析法消除文法左遞歸提左因子、避免回溯LL(1)分析條件、LL(1)文法4.4遞歸下降分析程序構造實現LL(1)分析的簡單方法4.5預測分析程序實現LL(1)分析的有效方法164.3LL(1)分析法下面將集中討論不帶回溯的自上而4.3.1左遞歸的消除無法對左遞歸文法進行有效的自上而下分析，因此必須消除文法的左遞歸。直接左遞歸有產生式A→Aα間接左遞歸 沒有產生式A→Aα,但有推導A+Aα消除直接左遞歸的方法：引入新的非終結符號P’，將關于P的如下產生式P→Pα|β(α非ε且β不以P打頭)替換為

P→βP’

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

(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.語法分析---自上而下分析文法直接左遞歸消除：練習消除下面文法的左遞歸：解:消除左消除直接左遞歸的一般方法一般而言，假定關于P的全部產生式是：

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

|n

其中,每個都不等于,而每個都不以P開頭消除P的直接左遞歸就是把這些規則改寫成：

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

A→Bb

B→dB’B’→bcB’|21消除間接左遞歸間接左遞歸的消除:先將間接左遞歸變為直接左遞消除間接左遞歸：例1例1：有間接左遞歸文法：(1)A→Bb(2)B→Ac(3)B→d

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

A→dbA’A’→cbA’|εB現在是無用符號,把B及其產生式刪除。說明：代入方法不同，得到的不含左遞歸的文法可能是不一樣的，但它們等價。消左以后，可能會出現無用符號，應把它們去掉。22消除間接左遞歸：例1例1：有間接左遞歸文法：22間接左遞歸的消除：例2例2：有間接左遞歸的文法：S→Ac|cA→Bb|b B→Sa|a(1)將B的定義代入A的產生式得：A→Sab|ab|b(2)將A的定義代入S的產生式得:

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

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

1.無回路(無形如P+P的推導)；2.無ε產生式算法(1)以某種順序將文法非終結符排列P1,P2,…,Pn(2)Fori:=1tondobeginforj:=1toi-1do把形如Pi→Pjγ的規則改寫為

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

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

1.無消左遞歸算法：例4.3解：將非終結符排序為R、Q、S。對于R不存在直接左遞歸，把R代入Q的候選式：

QSab|ab|b

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

SSabc|abc|bc|c

經消除S的直接左遞歸后，得到整個文法：

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

由于關于Q,R的規則是多余的,則可化簡得到：

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

的左遞歸。25消左遞歸算法：例4.3解：將非終結符排序為R、Q、S。消左遞歸算法：注意注意:①非終結符排序不同,消左遞歸的結果不同;②不要改變文法的開始符號。③消左還有一個方法---擴充的巴科斯范式(P75.)。例如，例4.3的文法：SQc|cQRb|bRSa|a

如果將非終結符排序為S

、Q、R

則得到無左遞歸的文法：(參見P70.)

SQc|c

QRb|bRbcaR’|caR’|aR’

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

A1|2|…|n在自上而下分析中展開A時，窮盡A的一切可能的候選式去謀求與輸入串相匹配。如果能夠:根據當前的輸入符號a，能準確地指出其匹配的某個候選式i，而不需要從1開始逐個試探。并且若i匹配輸入串成功，那么這種匹配決不會是虛假的；若i無法完成匹配任務，那么其他候選式也肯定不能完成。i是A的全權代表，i的工作成效完全代表了A。A輸入串…a…Sαi

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

A1|2|…|n在面臨當前輸入符號a時要能準確指出唯一可使用的候選式i去代表A謀求與輸入串相匹配，顯然要求各i的終結首符號互不相同。

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

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

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

FIRST(i)

FIRST(j)=

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

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

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

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

(其中每個不以開頭)

那末，可以引進新的非終結符,把這些規則改寫成：

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

2|…|

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

由于FIRST(bBcA)FIRST(b)={b}

則需要對BbBcA|b提取公共左因子b將產生式改寫成：B

bB’B’

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

ab|a

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

則需要對A

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

aA’A’

b|34例1:有產生式BbBcA|b提左因子練習1:有文法

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

SiBtSS’|aS’ε|eS

B

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

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

AaA’A’AB1|ε

B

dB’B’bB’|ε

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

TE’E’+TE’|εT

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

TE’E’+TE’|εT

FT’

T’*FT’|εF(E)|i38LL(1)分析條件的提出(1)E只有一個候選TE’,E替換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’自動匹配ε。εε+TE’iFT’ETE’iFT’εi+i#i+i#i+i#E

TE’E’+TE’|εT

FT’

T’*FT’|εF(E)|i39LL(1)分析條件的提出(2)E’有兩個候選,+∈FIRSLL(1)分析條件的提出(3)i+i#最后得到與i+i相匹配的語法樹εε+TE’iFT’ETE’iFT’ε問題:是不是一旦非終結符A面臨輸入符號a,且a不屬于所有FIRST(αi),但ε屬于某個FIRST(αj),就一定可以使A自動匹配ε呢?答案是不一定。在一定的條件下才可以。否則錯誤。條件是a允許跟在A的緊后面例如上例中，+可跟在T’后，#可跟在T’、E’后面。下面定義可跟在非終結符后的終結符號的集合FOLLOW。40LL(1)分析條件的提出(3)i+i#最后得到與i+i相非終結符的后隨終結符集FOLLOW假定S是文法G的開始符號，對于任何非終結符A，定義：

FOLLOW(A)={a|S*…Aa…且aVT}特別是,若S*…A,則規定

#FOLLOW(A)(

#是句末符號)也就是說，FOLLOW(A)是所有句型中，出現在緊接A之后的終結符或‘#’。例：S→aAA→εS→dA→bAS

FOLLOW(S)={#,a,d}FOLLOW(A)={a,d,#}∵SaAabASabbASS41非終結符的后隨終結符集FOLLOW假定S是文法G的開始符號，計算FOLLOW集合：例例：P69.(4.2)表達式文法

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

FT’+TE’∴有+號∵ETE’TFT’

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

A1|

2|…|

n

則：FIRST(i)

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

FIRST(A)FLLOW(A)=

特別注意第3個條件：當空字ε屬于非終結符的某個候選式的終結首符集時的條件!!!2022/11/1043Ch4.語法分析---自上而下分析LL(1)分析條件：3個(1)文法不含左遞歸。2022/1LL(1)文法一個文法G若滿足上述LL(1)分析的三個條件，則稱該文法G為LL(1)文法。LL(1)文法:第一個L

表示從左到右掃描輸入串第二個L

表示語法分析欲構造輸入串的最左推導括號里的1表示分析時,每步只需向前查看一個符號LL(1)文法是無二義文法,上述三個條件是LL(1)文法無二義的充分條件。對LL(1)文法，可以對其輸入串進行有效的無回溯的自上而下分析。44LL(1)文法一個文法G若滿足上述LL(1)分析的三個條件，LL(1)文法：自上而下分析過程對LL(1)文法，假設要用非終結符A進行匹配，面臨的輸入符號為a，A的所有產生式為：A1|

2|…|

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

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

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

過程和變量先設定一些過程和變量，作為遞歸下降分析程序的基本成分。過程ADVANCE：調整ip指向下一個輸入符號,讀入ip指向的輸入符號到SYM中。變量SYM：表示ip當前所指的那個輸入符號。過程ERROR：出錯診察處理。2022/11/1049Ch4.語法分析---自上而下分析遞歸下降分析程序構造：

過程和變量先設定一些過程和變量，作為遞歸下降分析程序構造：

非終結符對應的遞歸過程的結構①A1|

2|…|

n②=X1X2…XmXi∈(VT∪VN)③Xi∈VT④Xi∈VN①IF…ELSEIF…ELSE…結構②順序結構③IFSYM=XiTHENADVANCEELSE

ERROR④調用Xi對應的遞歸過程50遞歸下降分析程序構造：

非終結符對應的遞歸過程的結構①A例:算術表達式的遞歸下降分析器(1)Ｅ的子程序

E→TE’

procedureE;beginT;Ｔ的過程調用E’E’的過程調用end;

Ｅ’的子程序

E’→+TE’|ε

procedureE’;IFSYM=‘+’THENbeginADVANCE;T;T的過程調用E’E’的過程調用

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

T→FT’

procedureT;beginF;F的過程調用T’T’的過程調用end;

T’的子程序

T’→*FT’|ε

procedureE’;IFSYM=‘*’THENbeginADVANCE;F;F的過程調用T’T’的過程調用

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

F→i|(E)

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

BEGINADVANCE;E;E的過程調用

IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR; 2022/11/1053Ch4.語法分析---自上而下分析例:算術表達式的遞歸下降分析器(3)F的子程序F→i|(擴充巴科斯范式定義系統對前面的產生式(巴科斯范式)進行擴充：(1)用花括號{}表示閉包運算*。(2)用{}0n表示可以任意重復0次至n次,{}00=0=。(3)用方括號[]表示{}01，即表示的出現可有可無,等價于|ε。這樣,使得產生式右部的形式像正規式一樣,這種定義形式稱擴充巴科斯范式定義系統。例如,P75.“實數”的擴充巴科斯范式定義Decimal→[sign]integer.{digit}[exponent]54擴充巴科斯范式定義系統對前面的產生式(巴科斯范式)進行擴充使用擴充BNF定義系統的好處(1)(1)直觀易懂:如表示不超過10位的無符號整數<無符號數>→<數字>{<數字>}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)便于表示消除左遞歸和提取左因子消除回溯例,消除左遞歸，不用引入新的非終結符和ε產生式55使用擴充BNF定義系統的好處(1)(1)直觀易懂:如表示不使用擴充BNF定義系統的好處(2)(3)便于構造自上而下分析程序,過程是:

關于非終結符A的產生式寫為擴充BNF定義形式畫出其語法圖轉換為A對應的程序非終結符號的語法圖類似于表示正規式的狀態轉換圖，所以也稱為文法的狀態轉換圖。結點---文法符號有向邊---文法符號的排列順序|或[]分支{}回路.連接順序56使用擴充BNF定義系統的好處(2)(3)便于構造自上而下分析用語法圖描述語言的文法:例(P75.)T→F|T*FT→F{*F}的語法圖＊ＦＴ+TEE→T|E+T

E→T{+T}的語法圖iＥＦ

（）F→i|(E)的語法圖57用語法圖描述語言的文法:例(P75.)T→F|T*F＊ＦＴ例:簡單算術表達式的

遞歸下降分析器(P76.)EE→T{+T}Ｅ的子程序,請與P74.的程序對照procedureE;beginT; Ｔ的過程調用

whileSYM='+'do當前符號等于＋時beginADVANCE;處理終結符＋

TＴ的過程調用

endend; SYM：當前符號

58例:簡單算術表達式的

遞歸下降分析器(P76.)EE→T{例:簡單算術表達式的

遞歸下降分析器(P76.)TT→F{*F}Ｔ的子程序,請與P74.的程序對照procedureT;beginF;Ｆ的過程調用

whileSYM='*'then當前符號等于＊時begin

ADVANCE;處理終結符＊

F Ｆ的過程調用

endend;59例:簡單算術表達式的

遞歸下降分析器(P76.)TT→F{總結遞歸子程序法1.構造文法。2.改寫文法：消除二義性、消除左遞歸、提取公共左因子。3.求每個候選式的FIRST集和非終結符的FOLLOW集。4.檢查是不是LL(1)文法,是否滿足LL(1)分析的三個條件。5.若是LL(1)文法，為該文法的每個非終結符畫出語法圖。6.按照語法圖，為每個非終結符編寫一個遞歸子程序。60總結遞歸子程序法1.構造文法。604.5預測分析程序實現LL(1)分析的另一種有效方法是使用一張分析表和一個分析棧進行聯合控制。直接根據當前的非終結符號以及當前輸入符號，確定進行分析所需的候選式。本節要介紹的預測分析程序就是屬于這種類型的LL(1)分析器。本節要掌握:1.對給定文法構造符號串的FIRST集合和非終結符的FOLLOW集合的方法。2.構造預測分析表的方法。2022/11/1061Ch4.語法分析---自上而下分析4.5預測分析程序實現LL(1)分析的另一種有效方法是使用4.5.1預測分析程序工作過程系統維持一張分析表和一個分析棧，直接根據當前的輸入符號，選擇當前非終結符(處于棧頂)的候選式進行推導，希望找到相應輸入符號串的最左推導。預測分析程序的邏輯結構：1.一個通用的控制程序2.一個統一形式的分析表M不同文法使用內容不同的分析表3.一個分析棧，#為棧底符號4.一個輸入緩沖區，#為輸入串結束符2022/11/1062Ch4.語法分析---自上而下分析4.5.1預測分析程序工作過程系統維持一張分析表和一個分析預測分析器模型P77.圖4.4.…….a………..#x...#總控程序見P77.預測分析表M見P76.表4.1輸出分析棧輸入緩沖區預測分析表是預測分析器的核心2022/11/1063Ch4.語法分析---自上而下分析預測分析器模型P77.圖4.4.…….a………..#x總控預測分析程序的邏輯結構1.一個輸入串,“#”號為輸入串結束符,#不屬于VT。2.一個統一形式的預測分析表M。行:所有的非終結符A列:所有的終結符號a,包括“#”號元素M[A,a]:產生式或錯誤,概括了文法的全部信息。例,P76.表4.1文法(4.2)的預測分析表3.

一個分析棧STACK，隨著分析過程的進行而不斷變化,分析開始時棧底先放一個“#”號,分析結束時,若棧底只剩下“#”號,則分析成功。4.一個通用的統一的控制程序,分析的每一步都根據分析表、分析棧及輸入串的當前符號進行控制。64預測分析程序的邏輯結構1.一個輸入串,“#”號為輸入串結束表達式文法的預測分析表(P76.)輸入符號非終結符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.語法分析---自上而下分析表達式文法的預測分析表(P76.)輸入符號非終結符i+*()預測分析程序的工作過程(1)在系統啟動時，輸入指針指向輸入串的第一個符號，分析棧中存放著棧底符號#和文法的開始符號。分析的每一步都根據棧頂符號X和當前輸入符號a查看分析表M[X,a],以決定相應的動作。對任何(X,a),執行三種可能的動作之一：(1)若X=a=‘#’，則分析成功,停止分析。(2)若X=a≠’#’，則將X從STACK棧逐出,讓a指向下一個輸入符號，當前輸入符號得到匹配。

66預測分析程序的工作過程(1)在系統啟動時，輸入指針指向輸入串預測分析程序的工作過程(2)(3)若X∈VN

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

輸入串

所用產生式動作#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出棧,調指針#E'T'*i+i#查表M[T’,*],出入棧#E‘T’F**i+i#T'→*FT’匹配,*出棧,調指針#E'T’Fi+i#查表M[F,i],出入棧#E'T’ii+i#F→i匹配,i出棧,調指針68預測分析程序的工作過程(P78.)例4.6文法(4.2),輸#E’T’+i#查表M[T’,+],出入棧#E‘+i#T’→ε查表M[E’,+],出入棧#E‘T++i#E’→+TE’匹配,+出棧,調指針#E'Ti#查表M[T,i],出入棧#E'T'Fi#T→FT‘查表M[F,i],出入棧#E'T‘ii#F→i匹配,i出棧,調指針#E'T‘#查表M[T’,#],出入棧#E‘#T'→ε查表M[E’,#],出入棧##E'→ε所用的產生式序列形成了最左推導對應的分析樹分析棧

輸入串

所用產生式動作

#E'T’ii+i#F→i匹配,i出棧,調指針69#E’T’+i#查4.5.2預測分析表的構造預測分析法步驟:1)構造文法，消除二義性；2)消除左遞歸、提取左因子；3)求每個候選式的FIRST集和非終結符的FOLLOW集；4)檢查是不是LL(1)文法；若不是LL(1),說明文法的復雜性超過LL(1)分析法的分析能力；5)構造預測分析表；6)實現預測分析器。 704.5.2預測分析表的構造預測分析法步驟:70FIRST集和FOLLOW集前面定義了:對于α∈(ＶT∪ＶN)*

,

α的終結首符號集

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

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

特別的,若S*…A,則#∈FOLLOW(A)。下面介紹構造集合FIRST和FOLLOW的算法2022/11/1071Ch4.語法分析---自上而下分析FIRST集和FOLLOW集前面定義了:2022/11/97求FIRST(X)的算法(P78.)設文法符號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)條的要點是查看X的產生式!(3)下頁72求FIRST(X)的算法(P78.)設文法符號X∈ＶT∪ＶN(3)若X∈ＶN，重復如下過程，直到其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)條的要點仍然是查看X的產生式，對產生式右部的一個個符號，計算符號的FIRST集合，檢查是否含ε,以決定是否繼續計算!!求FIRST(X)的算法73(3)若X∈ＶN，重復如下過程，直到其FIRST集不再增大設符號串α=X1X2……Xn，構造FIRST(α),重復如下過程，直到其FIRST集不再增大:(1)首先置FIRST(α)=FIRST(X1)-{ε}(2)若對任何j=1到i-1,若X1……Xi-1*ε,則FIRST(α)=FIRST(α)∪(FIRST(Xj)-{ε})(3)若X1……Xn*ε，則FIRST(α)=FIRST(α)∪{ε}計算FIRST(α)的要點是從左到右查看α的一個個符號，計算符號的FIRST集合，檢查是否含ε,以決定是否繼續計算！求FIRST(α)的算法(P79.)74設符號串α=X1X2……Xn，構造FIRST(α),重復如下例4.7表達式文法符號的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表達式文法符號的FIRST集FIRST(F)=計算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計算FIRST集：例例1文法G[S]:例2文法G[E]計算FIRST集：練習解：FIRST(A)={a}FIRST(A’)={a,ε}FIRST(B)=wntz6b6FIRST(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’|ε

計算:FIRST(A),FIRST(A’)FIRST(B),FIRST(B')FIRST(AB1)FIRST(A’B’1)FIRST(A’B’)77計算FIRST集：練習解：文法G[A]:77求FOLLOW(A)的算法(P79.)設文法G[S],對G的所有非終結符,重復作以下計算:(1)將#加入到FOLLOW(S),#為句子的結束符(2)若A→αBβ，B∈ＶN則FOLLOW(B)=FOLLOW(B)∪FIRST(β)–{ε}(3)如果A→αB或A→αBβ,且β*ε，A≠B，則FOLLOW(B)=FOLLOW(B)∪FOLLOW(A)

計算FOLLOW(B)的要點是查看右部符號串包含B的產生式,計算B右邊符號串的FIRST集合,若該集合含有ε,則還要計算FOLLOW(A),若B右邊沒有符號,也要計算FOLLOW(A)!!78求FOLLOW(A)的算法(P79.)設文法G[S],對G的例4.7表達式文法符號的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.語法分析---自上而下分析例4.7表達式文法符號的FOLLOW集FOLLOW(E)=計算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.語法分析---自上而下分析計算FOLLOW集：例例1文法G[E]:例2文法G[S計算FOLLOW集：練習解：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’|ε

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

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

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

bFOLLOW(A),把A加至M[A,b]中；(4)把所有無定義的M[A,a]標上“出錯標志”。82預測分析表(LL(1)分析表)的

構造算法(P79.)構造分例4.8表達式文法的預測分析表輸入符號非終結符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.語法分析---自上而下分析例4.8表達式文法的預測分析表輸入符號非終結符i+*()#表達式文法預測分析表的構造對F→(E)|i

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

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

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

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

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

a

b

e

i

t#SS→aS→iCtSS’

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

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

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

procedureE;beginifsym=‘i’orsym=‘(‘thenbeginT;Ｔ的過程調用E’E’的過程調用

end

elseerrorend; T→FT’T的子程序procedureT;beginifsym=‘i’orsym=‘(‘thenbeginF;F的過程調用T’T’的過程調用end

elseerrorend; 88由預測分析表構造遞歸下降分析程序(1)E→TE’Ｅ的子程序由預測分析表構造遞歸下降分析程序(2)E’→+TE’|εＥ’的子程序procedureE’;beginifsym=‘+’thenbeginadvance;T;T的過程調用E’E’的過程調用

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

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

T’的子程序procedureT’;beginifsym=‘*’thenbeginadvance;F;F的過程調用T’