slide04自頂向下(Top-Down)語法

1、編譯原理 自頂向下（自頂向下（Top-Down）語法分析）語法分析第四講第四講編譯原理 基本思想基本思想 自頂向下預(yù)測分析自頂向下預(yù)測分析 LL(1) 分析分析自頂向下語法分自頂向下語法分析析 帶回溯的自頂向下分析帶回溯的自頂向下分析 文法變換：消除左遞歸、提取左公因子文法變換：消除左遞歸、提取左公因子 LL(1) 分析中的出錯處理分析中的出錯處理 LL(K) 文法的有關(guān)結(jié)論（選講）文法的有關(guān)結(jié)論（選講）編譯原理基本思想基本思想- 核心問題核心問題：識別：識別（recognition）與與解析解析（parsing） 對任意對任意上下文無關(guān)文法上下文無關(guān)文法G = (V ，T ，P，S ) 和任

2、意和任意w T *，是否有，是否有w L(G)？ 若成立，若成立， 則給出分析樹或（最左）推導(dǎo)步驟；否則，則給出分析樹或（最左）推導(dǎo)步驟；否則， 進行報錯處理。進行報錯處理。- 兩種實現(xiàn)途徑兩種實現(xiàn)途徑 自頂向下（自頂向下（top-down）分析）分析 自底向上自底向上（bottom-up）分析分析 語法分析語法分析編譯原理- 從文法從文法開始符號開始符號出發(fā)進行推導(dǎo)；每一步推導(dǎo)出發(fā)進行推導(dǎo)；每一步推導(dǎo) 都獲得文法的一個都獲得文法的一個句型句型；直到產(chǎn)生出一個；直到產(chǎn)生出一個句句 子子，恰好是所期望的終結(jié)符串，恰好是所期望的終結(jié)符串- 每一步推導(dǎo)是對當(dāng)前句型中剩余的某個非終每一步推導(dǎo)是對當(dāng)前句

3、型中剩余的某個非終 結(jié)符進行擴展，即用該非終結(jié)符的一個產(chǎn)生結(jié)符進行擴展，即用該非終結(jié)符的一個產(chǎn)生 式的右部替換該非終結(jié)符式的右部替換該非終結(jié)符- 如果不存在任何一個可以產(chǎn)生出所期望的終如果不存在任何一個可以產(chǎn)生出所期望的終 結(jié)符串的推導(dǎo)，則表明存在語法錯誤結(jié)符串的推導(dǎo)，則表明存在語法錯誤 自頂向下分析思想自頂向下分析思想基本思想基本思想編譯原理 自頂向下分析舉例自頂向下分析舉例 S （ S AB） AB （A aA） aAB （ B b） aAb （A aA） aaAb （ A aA） aaaAb （ A ） aaab文法文法 G（S）: S AB A aA | B b | bB- 單詞序列單

4、詞序列 aaab 的一個自頂向下分析過程的一個自頂向下分析過程基本思想基本思想編譯原理- 兩類非確定性兩類非確定性 在每一步推導(dǎo)中，選擇對哪一個非終結(jié)符、在每一步推導(dǎo)中，選擇對哪一個非終結(jié)符、 哪一個產(chǎn)生式都可能是非確定的哪一個產(chǎn)生式都可能是非確定的 分析成功的分析成功的結(jié)果結(jié)果：得到一個：得到一個推導(dǎo)推導(dǎo) 一般方法一般方法帶回溯的自頂向下分析帶回溯的自頂向下分析編譯原理 舉例舉例 S （1） AB （2） aAB （5） aAbB （2） aaAbB （2） aaaAbB （3） aaabB （回溯回溯） 復(fù)雜度很高復(fù)雜度很高 失敗條件較復(fù)雜失敗條件較復(fù)雜文法文法 G（S）:（1）S AB（

5、2）A aA（3）A （4）B b（5）B bB- 單詞序列單詞序列 aaab 的一個自頂向下分析過程的一個自頂向下分析過程帶回溯的自頂向下分析帶回溯的自頂向下分析編譯原理- 僅有產(chǎn)生式選擇是非確定的僅有產(chǎn)生式選擇是非確定的 在每一步推導(dǎo)中，總是對最左邊的非終結(jié)符在每一步推導(dǎo)中，總是對最左邊的非終結(jié)符 進行替換，但選擇哪一個產(chǎn)生式是非確定的進行替換，但選擇哪一個產(chǎn)生式是非確定的 分析成功的分析成功的結(jié)果結(jié)果：得到一個：得到一個最左推導(dǎo)最左推導(dǎo) 原理原理：每個合法的句子都存在至少一個起始：每個合法的句子都存在至少一個起始 于開始符號的最左推導(dǎo)；一個終結(jié)符串，只于開始符號的最左推導(dǎo)；一個終結(jié)符串，

6、只 要存在一個起始于開始符號的最左推導(dǎo)，它要存在一個起始于開始符號的最左推導(dǎo)，它 就是一個合法的句子就是一個合法的句子 從左向右掃描從左向右掃描輸入單詞，輸入單詞，失敗條件較簡單失敗條件較簡單 改進的方法改進的方法帶回溯的自頂向下分析帶回溯的自頂向下分析編譯原理 改進的方法舉例改進的方法舉例 S （1） AB （2） aAB （3） aB （回溯回溯） aAB （2） aaAB （2） aaaAB （3） aaaB （5） aaabB （回溯回溯） aaaB （4） aaab （成功成功）文法文法 G（S）:（1）S AB（2）A aA（3）A （4）B b（5）B bB- 單詞序列單詞序列

7、aaab 的一個自頂向下分析過程的一個自頂向下分析過程帶回溯的自頂向下分析帶回溯的自頂向下分析復(fù)雜度降低復(fù)雜度降低失敗條件簡化失敗條件簡化編譯原理- 非終結(jié)符選擇和產(chǎn)生式選擇都是確定的非終結(jié)符選擇和產(chǎn)生式選擇都是確定的 在每一步推導(dǎo)中，總是對在每一步推導(dǎo)中，總是對最左最左邊的邊的非終結(jié)符非終結(jié)符 進行展開，且選擇哪一個進行展開，且選擇哪一個產(chǎn)生式產(chǎn)生式是是確定確定的，的， 因此是一種因此是一種無回溯無回溯的方法的方法 從左向右掃描，可能從左向右掃描，可能向前查看向前查看（lookahead） 確定數(shù)目的單詞確定數(shù)目的單詞 分析成功的分析成功的結(jié)果結(jié)果：得到：得到唯一的最左推導(dǎo)唯一的最左推導(dǎo) 分

8、析分析條件條件：對：對文法文法需要有一定的需要有一定的限制限制 確定的自頂向下分析確定的自頂向下分析自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理 舉例舉例（向前查看（向前查看 2 個個單詞）單詞） S （1） AB （2）aAB （2） anAB （3） anB （5） anbB （5） anbm-1B （4） anbm （成功成功）文法文法 G（S）:（1）S AB（2）A aA（3）A （4）B b（5）B bB- 單詞序列單詞序列 anbm（n 0,0,m 0 0）的預(yù)測分析過程）的預(yù)測分析過程只要向前查看只要向前查看 2 個個單詞，就可預(yù)測分單詞，就可預(yù)測分析析L(G)中所有句子中所有句子

9、自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理 左遞歸帶來的問題左遞歸帶來的問題文法文法 G（S）:（1）S Sa（2）S b- 考慮下列文法識別考慮下列文法識別 ban 的分析過程的分析過程 S （1） Sa （1） Saa （1） Saaa （1） San （2） ban但是：但是：無論向前查看的單詞數(shù)確定為多少，無論向前查看的單詞數(shù)確定為多少，都無法滿足預(yù)測分析都無法滿足預(yù)測分析L(G)中所有句子的需求中所有句子的需求需要向前查看需要向前查看n+2個單詞，個單詞，才能確定這樣的推導(dǎo)序列才能確定這樣的推導(dǎo)序列自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理 要求要求文法不含左遞歸文法不含左遞歸- 例：例

10、：直接左遞歸直接左遞歸- 可以通過文法變換可以通過文法變換消除左遞歸消除左遞歸 專門討論專門討論- 例：例：間接左遞歸間接左遞歸P PaP bP AaA Pb自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理 左公因子帶來的問題左公因子帶來的問題文法文法 G（S）: S abA abB A a B b- 如下文法需要向前查看如下文法需要向前查看3 3個單詞來預(yù)測分析個單詞來預(yù)測分析 L(G)中的句子中的句子文法文法 G（S）: S aAb aAc A a aA- 對于如下文法無法確定需要向前查看多少對于如下文法無法確定需要向前查看多少 個單詞來預(yù)測分析個單詞來預(yù)測分析 L(G) 中的句子中的句子自頂向下

11、預(yù)測分析自頂向下預(yù)測分析編譯原理 通常要求通常要求文法不含左公因子文法不含左公因子- 可以通過文法變換可以通過文法變換消除左公因子消除左公因子 專門討論專門討論自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理 應(yīng)用較普遍的自頂向下預(yù)測分析是應(yīng)用較普遍的自頂向下預(yù)測分析是 LL（1 1）分析）分析- 要求文法一定是要求文法一定是LL（1）文法文法 專門討論專門討論自頂向下預(yù)測分析自頂向下預(yù)測分析編譯原理- 第一個第一個“L”, 代表從代表從左左（Left）向右掃描單詞）向右掃描單詞- 第二個第二個“L”, ,代表產(chǎn)生的是代表產(chǎn)生的是最左最左（Leftmost） 推導(dǎo)推導(dǎo)- “1”代表向前查看（代表向前查

12、看（lookahead）一個一個單詞單詞 LL（1）的）的含義含義LL（1） 分析分析編譯原理- 要求文法是要求文法是LL（1）的）的- 什么是什么是LL（1）文法）文法？ 先引入兩個重要概念先引入兩個重要概念 對文法的限制對文法的限制LL（1） 分析分析編譯原理- First 集合集合- Follow 集合集合 兩個重要概念兩個重要概念LL（1） 分析分析編譯原理- 定義定義 設(shè)設(shè) G =（VT，VN，P，S）是上下文無關(guān)文法是上下文無關(guān)文法 對對 ( (VT VN) )* *， First（ ）= a * a , a VT, ( (VT VN) )*, 或者或者 *時時 a = 或者或者

13、First（ ）= a lm* a , a VT, (VT VN)*, 或者或者 lm*時時 a = First 集合集合LL（1） 分析分析編譯原理 計算計算 First 集合集合LL（1） 分析分析對所有對所有 x VN VT vAu P, 且且v是是u的后綴的后綴, 則則-對對 x V ，置，置 First(x)=x；對其它；對其它x，置，置 First(x)= -重復(fù)如下過程，直到所有重復(fù)如下過程，直到所有 First 集合沒有變化為止：集合沒有變化為止： (1) 對于對于 A P，置置 First(A) = First(A) . (2) 對于對于 Y1Y2YK vAu P, 且且v是

14、是u的后綴的后綴, 其中其中 k 1，Yj VN V （1 j k）, 若若 j:1 j i-1( First(Yj) First(Yi), 其中其中1 i k ，則令，則令 First(Y1Y2YK) = First(Yj) - - 否則，若否則，若 j:1 j k( First(Yj), 則令則令 First(Y1Y2YK) = First(Yj). (3) 若有若有 AY1Y2YK P，則置則置 First(A) = First(A) First(Y1Y2YK) .j=1ij=1k編譯原理 例例：計算：計算 First 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B c

15、C（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = First(B) = First(C) = First(D) = First(AB) = First(Da) = First(cC) = First(aADC) = 編譯原理 例例：計算：計算 First 集合集合( ( 續(xù)續(xù)) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst()

16、= LL（1） 分析分析First(S) = First(A) = First(B) = First(C) = First(D) = , bFirst(AB) = First(Da) = First(cC) = First(aADC) = 編譯原理 例例：計算：計算 First 集合集合( ( 續(xù)續(xù)) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = First(B) = First(C) = F

17、irst(D) = , bFirst(AB) = First(Da) = a, bFirst(cC) = c First(aADC) = a 編譯原理 例例：計算：計算 First 集合集合( ( 續(xù)續(xù)) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = , a, bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = First(Da) = a,

18、 bFirst(cC) = c First(aADC) = a 編譯原理 例例：計算：計算 First 集合集合( ( 續(xù)續(xù)) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = First(A) = , a, bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = a, b, cFirst(Da) = a, bFirst(cC) = cFirst(aADC) = a編譯

19、原理 例例：計算：計算 First 集合集合( ( 續(xù)續(xù)) )文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC（5）D bFirst(a) = aFirst(b) = bFirst(c) = cFirst() = LL（1） 分析分析First(S) = a, b, c First(A) = , a , bFirst(B) = cFirst(C) = a, First(D) = , bFirst(AB) = a, b, cFirst(Da) = a, bFirst(cC) = cFirst(aADC) = a編譯原理- 定義定義 設(shè)設(shè) G =（VT，VN，P，S

20、）是上下文無關(guān)文法，是上下文無關(guān)文法，對對 每個每個 A VN， Follow(A) = a S# * A # 且且 a First( #)， , (VT VN)* （# 代表輸入單詞序列右邊的結(jié)束符）代表輸入單詞序列右邊的結(jié)束符） Follow 集合集合LL（1） 分析分析編譯原理 計算計算 Follow 集合集合-置置 Follow(S) = #，置所有其它的，置所有其它的 Follow 集合為集合為 ；-重復(fù)如下步驟，直至所有重復(fù)如下步驟，直至所有Follow集不再變化為止：集不再變化為止： 對于對于 AB P，把，把 First() - - 加至加至 Follow(B); 若有若有 F

21、irst()，則把，則把 Follow(A) 加至加至 Follow(B) 中中LL（1） 分析分析編譯原理 例例：計算：計算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, Follow(S) = #LL（1） 分析分析Follow(A) = Follow(B) = Follow(C) = Follow(D) = 編譯原理 例例：計算：計算 First 和和 Follow 集合

22、集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(A) = cFollow(B) = # Follow(S) = #Follow(A) = Follow(B) = Follow(C) = Follow(D) = 編譯原理 例例：計算：計算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(

23、B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(D) = a Follow(S) = #Follow(A) = cFollow(B) = #Follow(C) = Follow(D) = 編譯原理 例例：計算：計算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1）

24、分析分析Follow(C) = # Follow(S) = #Follow(A) = cFollow(B) = #Follow(C) = Follow(D) = a編譯原理 例例：計算：計算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析Follow(A) = c,b,a, # Follow(S) = #Follow(A) = cFollow(B) = #F

25、ollow(C) = #Follow(D) = aFollow(D) = a, #編譯原理 例例：計算：計算 First 和和 Follow 集合集合文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bFirst(B) = cFirst() = First(a) = aFirst(DC) = b, a, First(C) = a, LL（1） 分析分析 Follow(S) = #Follow(A) = c,b,a, #Follow(B) = #Follow(C) = #Follow(D) = a, # 編譯原理 定義：定義： 預(yù)測集合預(yù)測集合（Pred

26、ictive Set） 設(shè)設(shè) G =（VT，VN，P，S）是上下文無關(guān)文法。是上下文無關(guān)文法。對任何產(chǎn)生式對任何產(chǎn)生式 A P，其預(yù)測集合，其預(yù)測集合 PS (A) 定義定義為：為：- 如果如果 first()，那么，那么 PS (A) = first ()；- 如果如果 first ()，那么，那么 PS (A) = ( first () ) follow(A) LL（1） 分析分析編譯原理 定義：定義： LL（1）文法）文法文法文法 G 是是 LL（1）文法）文法，當(dāng)且僅當(dāng)對于，當(dāng)且僅當(dāng)對于 G 的每個非的每個非終結(jié)符終結(jié)符 A 的任何兩個不同產(chǎn)生式的任何兩個不同產(chǎn)生式 A，下面，下面的條

27、件成立：的條件成立： PS (A) PS (A) = LL（1） 分析分析編譯原理 舉例舉例：驗證如下文法驗證如下文法 G（S）不是不是 LL（1）文法文法文法文法 G（S）:（1）S AB（2）A Da（3）B cC（4）C aADC （5）D bPS(ADa) = b,aPS(A) = c,b,a, #PS(CaADC) = aPS(C ) = #PS(Db) = bPS(D ) = a, #LL（1） 分析分析First(Da) = b, aFirst() = First(aADC) = aFirst(b) = bFollow(A) = c,b,a, #Follow(C) = #Foll

28、ow(D) = a, #PS(ADa) PS(A ) PS(C aADC ) PS(C ) = PS(Db) PS(D ) = 編譯原理- 遞歸下降遞歸下降 LL（1）分析程序分析程序 每個非終結(jié)符對應(yīng)一個分析子程序每個非終結(jié)符對應(yīng)一個分析子程序 LL（1）分析的實現(xiàn)分析的實現(xiàn)- 表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序 借助于借助于預(yù)測分析表預(yù)測分析表和一個和一個下推棧下推棧LL（1） 分析分析編譯原理- 工作工作原理原理 每個非終結(jié)符都對應(yīng)一個每個非終結(jié)符都對應(yīng)一個子程序子程序。該子程序。該子程序 的行為根據(jù)語法描述來明確：根據(jù)下一個輸?shù)男袨楦鶕?jù)語法描述來明確：根據(jù)下一個輸 入符號來確定按

29、照哪一個產(chǎn)生式進行處理，入符號來確定按照哪一個產(chǎn)生式進行處理， 再根據(jù)該產(chǎn)生式的右端，再根據(jù)該產(chǎn)生式的右端， 每遇到一個終結(jié)符，則判斷當(dāng)前讀入的單詞是否每遇到一個終結(jié)符，則判斷當(dāng)前讀入的單詞是否 與該終結(jié)符相匹配，若匹配，再讀取下一個單詞與該終結(jié)符相匹配，若匹配，再讀取下一個單詞 繼續(xù)分析；不匹配，則進行出錯處理繼續(xù)分析；不匹配，則進行出錯處理 每遇到一個非終結(jié)符，則調(diào)用相應(yīng)的子程序每遇到一個非終結(jié)符，則調(diào)用相應(yīng)的子程序 遞歸下降遞歸下降LL(1)分析程序分析程序遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 例例 對于下列關(guān)于對于下列關(guān)于 function 的唯一產(chǎn)生式的唯一產(chǎn)生式

30、FUNC ID ( ) （，和和 是非終結(jié)符）是非終結(jié)符） 非終結(jié)符對應(yīng)的遞歸下降非終結(jié)符對應(yīng)的遞歸下降子子程序程序void ParseFunction() MatchToken(T_FUNC); /匹配匹配FUNC MatchToken(T_ID); /匹配匹配ID MatchToken(T_LPAREN); / 匹配匹配 （ ParseParameterList(); MatchToken(T_RPAREN); / 匹配匹配 ） ParseStatement();遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 例例 續(xù)上頁續(xù)上頁 非終結(jié)符對應(yīng)的遞歸下降非終結(jié)符對應(yīng)的遞歸下降子子程序

31、程序void MatchToken(int expected) if (lookahead != expected) /判別當(dāng)前單詞是否與判別當(dāng)前單詞是否與 /期望的終結(jié)符匹配期望的終結(jié)符匹配 printf(syntax error n); exit(0); else / 若匹配若匹配,消費掉當(dāng)前單詞并讀入下一個消費掉當(dāng)前單詞并讀入下一個 lookahead = getToken(); /調(diào)用詞法分析程序調(diào)用詞法分析程序遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 例例 對于下列文法對于下列文法 G(S): S AaS BbS d A a B c 遞歸下降遞歸下降LL(1)分析程序分

32、析程序舉例舉例PS(SAaS) = aPS(SBbS) = c,b PS(Sd) = dPS(Aa) = aPS(B) = bPS(Bc) = cFirst（AaS）= aFirst（BbS）= c,b First（d）= dFirst（a）= aFirst（ ）= First（c）= cFollow（S）= # Follow（A）= aFollow（B）= b遞歸下降遞歸下降 LL（1）分析程序分析程序PS(SAaS)，PS(SBbS) 以及以及 PS(Sd) 互不相交，互不相交， PS(B) 和和 PS(Sd)互不相交，互不相交，所以所以，G(S) 是是 LL(1) 文法文法編譯原理- 一

33、般結(jié)構(gòu)一般結(jié)構(gòu) 設(shè)設(shè) A 的產(chǎn)生式的產(chǎn)生式: A u1 u2 . un, 相對于非終結(jié)符相對于非終結(jié)符 A 的遞歸下降子程序的遞歸下降子程序 ParseA 的一般結(jié)的一般結(jié) 構(gòu)如右圖所示構(gòu)如右圖所示 非終結(jié)符對應(yīng)的非終結(jié)符對應(yīng)的 遞歸下降遞歸下降子子程序程序void ParseA() switch (lookahead) case PS(Au1): /* code to recognize u1 */ break; case PS(Au2): /* code to recognize u2 */ break; . case PS(Aun): /* code to recognize un */

34、 break; default: printf(syntax error n); exit(0); 遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 接上接上例例 針對文法針對文法G(S)構(gòu)造的遞歸下降分析程序構(gòu)造的遞歸下降分析程序void ParseS( ) switch (lookahead) case a: ParseA( ); MatchToken(a); ParseS( ); break;G(S): S AaS BbS d A a B cPS(SAaS) = aPS(SBbS) = c,b PS(Sd) = d case b,c: ParseB( ); MatchToken(b

35、); ParseS( ); break; case d: MatchToken(d); break; default: printf(syntax error n) exit(0); 遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 接上接上例例 針對文法針對文法G(S) 構(gòu)造的遞歸下降分析程序構(gòu)造的遞歸下降分析程序void ParseA( ) if (lookahead=a) MatchToken(a); else printf(syntax error n”); exit(0); PS(Aa) = aPS(B) = bPS(Bc) = cvoid ParseB( ) if (look

36、ahead=c) MatchToken(c); else if (lookahead=b) else printf(syntax error n”); exit(0); G(S): S AaS BbS d A a B c遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理 實際應(yīng)用中的推廣實際應(yīng)用中的推廣 上面只討論了根據(jù)普通文法構(gòu)造遞歸下降分析程序。實上面只討論了根據(jù)普通文法構(gòu)造遞歸下降分析程序。實 際上，也可以將產(chǎn)生式右端擴展為更復(fù)雜的描述表達(dá)際上，也可以將產(chǎn)生式右端擴展為更復(fù)雜的描述表達(dá) 式，即除了文法符號之間的連接運算之外，還可以有選式，即除了文法符號之間的連接運算之外，還可以有選 擇

37、、重復(fù)、任選以及優(yōu)先括號等運算（如擇、重復(fù)、任選以及優(yōu)先括號等運算（如 EBNF 范式中范式中 的運算），以使語法描述更加簡潔，分析程序更加高效的運算），以使語法描述更加簡潔，分析程序更加高效 （比較：若將其展開為普通文法，則需要引入多個非終（比較：若將其展開為普通文法，則需要引入多個非終 結(jié)符，增加多個對應(yīng)的子程序）。結(jié)符，增加多個對應(yīng)的子程序）。- X1 | X1 | | Xm 多個成分之間的選擇多個成分之間的選擇- X 成分成分 X 的重復(fù)（的重復(fù)（0 到多次）到多次）- X 成分成分 X 的任選（的任選（0 或或 1 次）次）- ( X ) 成分成分 X 優(yōu)先優(yōu)先遞歸下降遞歸下降 LL

38、（1）分析程序分析程序編譯原理 實際應(yīng)用中的推廣實際應(yīng)用中的推廣 將產(chǎn)生式右端擴展后，同樣要求它的將產(chǎn)生式右端擴展后，同樣要求它的 First 集合，以適集合，以適 應(yīng)遞歸下降分析程序的構(gòu)造方法。應(yīng)遞歸下降分析程序的構(gòu)造方法。- First（X1 | X2 | | Xm）= First（X1） First（Xm）- First（ X ）= First（X） - First（ X ）= First（X） - First（( X )）= First（X）遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理 實際應(yīng)用中的推廣實際應(yīng)用中的推廣 將產(chǎn)生式右端擴展后，子程序的處理過程中需要針對不將產(chǎn)生式右

39、端擴展后，子程序的處理過程中需要針對不 同運算選擇不同的語句形式（普通文法只有連接運算，同運算選擇不同的語句形式（普通文法只有連接運算， 所以只對應(yīng)順序語句）。所以只對應(yīng)順序語句）。- X1 | X2 | | Xm 對應(yīng)選擇語句對應(yīng)選擇語句- X 對應(yīng)循環(huán)語句對應(yīng)循環(huán)語句- X 對應(yīng)對應(yīng) If-Then 語句語句- ( X ) 對應(yīng)復(fù)合語句對應(yīng)復(fù)合語句- 可參考可參考 PL/0 編譯器的語法分析程序編譯器的語法分析程序遞歸下降遞歸下降 LL（1）分析程序分析程序編譯原理- 工作工作原理原理 利用利用預(yù)測分析表預(yù)測分析表和一個和一個下推棧下推棧實現(xiàn)實現(xiàn) 初始時，下推棧只包含初始時，下推棧只包含#

40、；首先將文法開始符；首先將文法開始符 號入棧；之后依如下步驟：號入棧；之后依如下步驟：（1） 若棧頂為若棧頂為 終終 結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符 相匹配，若匹配，再讀取下一相匹配，若匹配，再讀取下一 單詞繼續(xù)分析；單詞繼續(xù)分析； 不匹配，則進行出錯處理；（不匹配，則進行出錯處理；（2）若棧頂為非終）若棧頂為非終 結(jié)符，則根據(jù)該非終結(jié)符和當(dāng)前輸入單詞查預(yù)測結(jié)符，則根據(jù)該非終結(jié)符和當(dāng)前輸入單詞查預(yù)測 分析表，若相應(yīng)表項中是產(chǎn)生式（唯一的），分析表，若相應(yīng)表項中是產(chǎn)生式（唯一的）， 則將此非終結(jié)符出棧，并把產(chǎn)生式右部符號從則將此非終結(jié)符出棧，并把

41、產(chǎn)生式右部符號從 右至左入棧；若表項為空，則進行出錯處理；右至左入棧；若表項為空，則進行出錯處理； （3）重復(fù)（）重復(fù)（1）和（）和（2），直到棧頂為），直到棧頂為 # 同時輸同時輸 入也遇到結(jié)束符入也遇到結(jié)束符 # 時，分析結(jié)束時，分析結(jié)束 表驅(qū)動表驅(qū)動LL(1)分析程序分析程序表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理- 表驅(qū)動分析程序需要的表驅(qū)動分析程序需要的二維表二維表M- 表的每一表的每一行行 A 對應(yīng)一個對應(yīng)一個非終結(jié)符非終結(jié)符- 表的每一表的每一列列 a 對應(yīng)某個對應(yīng)某個終結(jié)符終結(jié)符或輸入結(jié)束符或輸入結(jié)束符 # #- 表中的項表中的項 M(A,a) 表示棧頂為表示棧頂為A，

42、下一個輸入符下一個輸入符 號為號為a時，可選的時，可選的產(chǎn)生式集合產(chǎn)生式集合- 對于對于LL（1）文法，可以構(gòu)造出一個）文法，可以構(gòu)造出一個 M(A,a) 最最 多只包含一個產(chǎn)生式的預(yù)測分析表，可稱之為多只包含一個產(chǎn)生式的預(yù)測分析表，可稱之為 LL（1）分析表）分析表- M(A,a) 不含產(chǎn)生式時，對應(yīng)一個出錯位置不含產(chǎn)生式時，對應(yīng)一個出錯位置 預(yù)測分析表預(yù)測分析表表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 預(yù)測分析表的構(gòu)造算法預(yù)測分析表的構(gòu)造算法-對文法對文法 G 的每個產(chǎn)生式的每個產(chǎn)生式 A 執(zhí)行如下步驟：執(zhí)行如下步驟： 對每個對每個 a PS(A)，將，將 A 加入加入 MA,a-

43、把所有無定義的把所有無定義的 MA,a 標(biāo)上標(biāo)上“出錯標(biāo)志出錯標(biāo)志”可以證明可以證明: 一個文法一個文法 G 的預(yù)測分析表不含多重入的預(yù)測分析表不含多重入口，當(dāng)且僅當(dāng)該文法是口，當(dāng)且僅當(dāng)該文法是 LL(1) 的的表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 預(yù)測分析表的構(gòu)造預(yù)測分析表的構(gòu)造舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c可構(gòu)造如下預(yù)測分析表：可構(gòu)造如下預(yù)測分析表：SAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序PS(SAaS) = aPS(SBbS) = c,b PS(Sd) = dPS(Aa) = aPS

44、(B) = bPS(Bc) = c編譯原理 表驅(qū)動預(yù)測分析程序分析算法表驅(qū)動預(yù)測分析程序分析算法 初始時初始時#入棧，然后文法開始符號入棧；首個輸入符號讀進入棧，然后文法開始符號入棧；首個輸入符號讀進 a ； flag =TRUE； while (flag) do 棧頂符號棧頂符號出棧出棧并放在并放在X中；中； if (XVT) if (X=a) 把下一把下一個輸入符號讀進個輸入符號讀進a; else ERROR; else if (X=#） if (a=#) flag = FALSE; else ERROR; else if (MX,a = XX1X2Xk) Xk,XK-1,X1依次依次進棧

45、進棧; else ERROR; /*分析成功，過程完畢分析成功，過程完畢*表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#S剩余的輸入串剩余的輸入串 aabd#SAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#S

46、剩余的輸入串剩余的輸入串 aabd#aASAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#S剩余的輸入串剩余的輸入串 aabd#aaSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過

47、程：#S剩余的輸入串剩余的輸入串 abd#aSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#S剩余的輸入串剩余的輸入串 bd#SAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：

48、#剩余的輸入串剩余的輸入串 bd#SbBSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#剩余的輸入串剩余的輸入串 bd#SbSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#

49、剩余的輸入串剩余的輸入串 d#SSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#剩余的輸入串剩余的輸入串 d#dSAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理 表驅(qū)動預(yù)測分析過程表驅(qū)動預(yù)測分析過程舉例舉例- 對于下列文法對于下列文法G(S)： S AaS BbS d A a B c 分析輸入串分析輸入串 aabd 的過程：的過程：#剩余的輸入串

50、剩余的輸入串 #SAaSSBbSSdAaBBcSBbS表驅(qū)動表驅(qū)動 LL（1）分析程序分析程序編譯原理- LL(1) 文法通常不含左遞歸和左公因子文法通常不含左遞歸和左公因子- 許多文法在消除左遞歸和提取左公因子后可許多文法在消除左遞歸和提取左公因子后可 以變換為以變換為LL(1)文法文法- 但不含左遞歸和左公因子的文法不一定都是但不含左遞歸和左公因子的文法不一定都是 LL(1)文法文法 文法變換：消除左遞歸、提取左公因子文法變換：消除左遞歸、提取左公因子文法變換文法變換編譯原理文法變換：消除左遞歸文法變換：消除左遞歸 左遞歸消除規(guī)則左遞歸消除規(guī)則-消除直接左遞歸消除直接左遞歸 對形如對形如

51、P P 的產(chǎn)生式，其中的產(chǎn)生式，其中非非 ， 不以不以 P 打頭，打頭， 可改寫為：可改寫為： P Q Q Q 其中其中Q為新增加的非終結(jié)符為新增加的非終結(jié)符編譯原理文法變換：消除左遞歸文法變換：消除左遞歸 左遞歸消除規(guī)則左遞歸消除規(guī)則-消除直接左遞歸消除直接左遞歸 對更一般的形如對更一般的形如 PP1 P2 Pm 1 2 n 的一組產(chǎn)生式，其中的一組產(chǎn)生式，其中i（1 i m）不為）不為 ，j（1 j n） 不以不以 P 打頭，打頭， 可改寫為：可改寫為： P1Q 2Q nQ Q 1Q 2Q mQ 其中其中Q為新增加的非終結(jié)符為新增加的非終結(jié)符編譯原理文法變換：消除左遞歸文法變換：消除左遞歸

52、 左遞歸消除左遞歸消除舉例舉例原文法原文法 G E: E E T T T T F F F (E) a消除左遞歸后的文法消除左遞歸后的文法 G E: (1) E TE (2) E TE (3) E (4) T FT (5) T FT (6) T (7) F (E) (8) F a編譯原理文法變換：消除左遞歸文法變換：消除左遞歸 左遞歸消除規(guī)則左遞歸消除規(guī)則-消除一般左遞歸消除一般左遞歸 對無回路對無回路(A A) 、無、無 -產(chǎn)生式的文法，通過下列步驟可消除產(chǎn)生式的文法，通過下列步驟可消除 一般左遞歸（包括直接和間接左遞歸）：一般左遞歸（包括直接和間接左遞歸）： （1）以某種順序?qū)⑽姆ǚ墙K結(jié)符排

53、列）以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1 ,A2 An （2）for i = 1 , n do for j=1,i-1 do 用用Ai 1 r 2r kr反復(fù)替代形如反復(fù)替代形如Ai Ajr的規(guī)則的規(guī)則, 其中其中Aj 1 2 k是關(guān)于是關(guān)于Aj的全部產(chǎn)生式的全部產(chǎn)生式; 消除消除Ai規(guī)則的直接左遞歸規(guī)則的直接左遞歸; （3）化簡由（）化簡由（2）得到的文法）得到的文法編譯原理文法變換：消除左遞歸文法變換：消除左遞歸 左遞歸消除左遞歸消除舉例舉例原文法原文法 GS: S PQ a P QS b Q SP c非終結(jié)符排序為非終結(jié)符排序為 S、P、Q，按造消除一般左遞歸的方，按造消除一般左遞歸的方法，

54、進行如下變換法，進行如下變換:Q SP c結(jié)結(jié)果果：S PQ a P QS bQ bQPR aPR cRR SQPRQ PQP aP cQ QSQP bQP aP cQ bQPR aPR cRR SQPR編譯原理文法變換：消除左遞歸文法變換：消除左遞歸 左遞歸消除左遞歸消除舉例舉例 原文法原文法 GS: S PQ a P QS b Q SP c 按造非終結(jié)符的另一種排序按造非終結(jié)符的另一種排序Q、P、S，依消除一般左，依消除一般左遞歸的方法，進行如下變換遞歸的方法，進行如下變換:P QS b結(jié)結(jié)果果 S cSQR bQR aR P SPS cS b Q SP c R PSQR P SPS cS

55、 bS PQ aS SPSQ cSQ bQ aS cSQR bQR aRR PSQR 編譯原理文法變換：提取左公因子文法變換：提取左公因子 提取左公因子規(guī)則提取左公因子規(guī)則- 對形如對形如 P 的一對產(chǎn)生式，可用如下三個產(chǎn)生式替換：的一對產(chǎn)生式，可用如下三個產(chǎn)生式替換： P Q Q 其中其中Q為新增加的未出現(xiàn)過的非終結(jié)符為新增加的未出現(xiàn)過的非終結(jié)符編譯原理文法變換：提取左公因子文法變換：提取左公因子 提取左公因子規(guī)則提取左公因子規(guī)則- 一般含有左公因子的產(chǎn)生式形如一般含有左公因子的產(chǎn)生式形如 P 1 2 m 1 2 n 其中，每個其中，每個不以不以開頭開頭. .提取左公共因子，提取左公共因子，

56、 產(chǎn)生式改寫成：產(chǎn)生式改寫成： P Q 1 2 n Q 1 2 m編譯原理文法變換：提取左公因子文法變換：提取左公因子- 對文法對文法 G(S): S if C t S if C t S e S C b 提取左公因子后，可改寫為文法提取左公因子后，可改寫為文法G(S)： S if C t S A A e S C b 提取左公因子提取左公因子舉例舉例編譯原理文法變換文法變換 舉例：舉例：許多文法在消除左遞歸和提取左公因許多文法在消除左遞歸和提取左公因 子后可以變換為子后可以變換為LL(1)文法文法可驗證如下文法可驗證如下文法 GE是是LL(1)文法文法: (1) E TE (2) E TE (3

57、) E (4) T FT (5) T FT (6) T (7) F (E) (8) F a編譯原理文法變換文法變換 舉例：舉例：不含左遞歸和左公因子的文法不含左遞歸和左公因子的文法 不一定是不一定是LL(1)文法文法 First集集 Follow集集if C t S A : if S: #,eeS: e A: #,eb b C: t MA,e = Ae S，A S if C t S if C t S e S C b提取左公因子后：提取左公因子后： S if C t S A A e S C b編譯原理文法變換文法變換 問題探討問題探討 某些非某些非LL(1)的文法也可采用的文法也可采用LL(1)

58、分析方法分析方法MA,e = A e S， A S if C t S if C t S e S C b提取左公因子后：提取左公因子后： S if C t S A A e S 優(yōu)先使用優(yōu)先使用編譯原理預(yù)測分析中的出錯處理預(yù)測分析中的出錯處理 錯誤處理的原則錯誤處理的原則- 盡可能準(zhǔn)確指出錯誤位置和錯誤屬性盡可能準(zhǔn)確指出錯誤位置和錯誤屬性- 盡可能進行校正盡可能進行校正編譯原理預(yù)測分析中的出錯處理預(yù)測分析中的出錯處理- 遞歸下降遞歸下降LL(1)分析中的出錯處理分析中的出錯處理介紹一種短語層錯誤恢復(fù)技術(shù)介紹一種短語層錯誤恢復(fù)技術(shù)- 表驅(qū)動表驅(qū)動LL(1)分析中的出錯處理分析中的出錯處理 介紹一種簡

59、單的應(yīng)急錯誤恢復(fù)技術(shù)介紹一種簡單的應(yīng)急錯誤恢復(fù)技術(shù) 預(yù)測分析中的出錯處理預(yù)測分析中的出錯處理編譯原理- 出錯報告出錯報告（error reporting） 棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配棧頂?shù)慕K結(jié)符與當(dāng)前輸入符不匹配 非終結(jié)符非終結(jié)符A于棧頂，面臨的輸入符為于棧頂，面臨的輸入符為a， 但分析表但分析表M的的MA,a為空為空 表驅(qū)動表驅(qū)動LL(1)分析中的錯誤處理分析中的錯誤處理預(yù)測分析中的出錯處理預(yù)測分析中的出錯處理編譯原理- 簡單的簡單的應(yīng)急恢復(fù)應(yīng)急恢復(fù)（panic-mode error recovery） 跳過輸入串中的一些符號直至遇到跳過輸入串中的一些符號直至遇到同步符號同步符號 （sy

60、nchronizing token）為止為止同步符號的選擇：同步符號的選擇： 把把 Follow(A) 中的所有符號作為中的所有符號作為A的同步符號的同步符號, 跳過跳過 輸入串中的一些符號直至遇到這些輸入串中的一些符號直至遇到這些“同步符號同步符號”， 把把A從棧中彈出，可使分析繼續(xù)從棧中彈出，可使分析繼續(xù) 把把First(A)中的符號加到中的符號加到A的同步符號集，當(dāng)?shù)耐椒柤?，?dāng)First(A) 中的符號在輸入中出現(xiàn)時，可根據(jù)中的符號在輸入中出現(xiàn)時，可根據(jù)A恢復(fù)分析恢復(fù)分析預(yù)測分析中的出錯處理預(yù)測分析中的出錯處理 表驅(qū)動表驅(qū)動LL(1)分析中的錯誤處理分析中的錯誤處理編譯原理 在進入某