編譯原理語法3(自頂向下語法分析：遞歸下降)

《編譯原理語法3(自頂向下語法分析：遞歸下降)》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第6講編譯原理西北農林科技大學本科教程主講教師：趙建邦第三章語法分析3.1文法和語言3.2推導與語法樹3.3自頂向下的語法分析3.4自底向上的語法分析3.5規(guī)范規(guī)約的自底向上語法分析方法第三章《語法分析》3.3自頂向下的語法分析遞歸下降分析法LL(1)分析法（下一講內容）重點掌握消除左遞歸消除回溯構建遞歸下降子程序本講目標3.3自頂向下的語法分析算法思想：從文法的開始符號出發(fā)，向下推導，如果推導出的句子恰好為輸入符號串，則輸入符號串為符合該文法的句子；或者：開始符號作為根節(jié)點，向下生長出一棵語法樹，其葉子節(jié)點組成的句子恰好為輸入符號串。這里的每一步“生長”對應一次直接推導。自頂向下分析方

2、法:1、不確定的自頂向下分析2、確定的自頂向下分析遞歸下降分析法LL(1)分析法1、不確定的自頂向下分析方法假定文法G[S]為S→xAyA→ab

3、a若輸入串為xay，則其分析過程如下：(1)建立根節(jié)點S；(2)關于S的產生式只有一個，則生長語法樹,匹配語法樹的第一個終結符x；(3)A?→?ab

4、a有兩個候選式，選擇第一個,并且匹配語法樹的第二個葉子節(jié)點a；(4)輸入串xay期待匹配y,而語法樹中的b與之匹配失??；SAyabx3.3自頂向下的語法分析1、不確定的自頂向下分析方法假定文法G[S]為S?→?xAyA?→?ab

5、a若輸入串為xay，則其分析過程如下：(5)撤銷匹配a，注銷A所生成

6、的子樹，回溯；(6)選擇產生式A→a，重新匹配a；(7)匹配輸入串的字符y；而語法樹的最后一個葉子節(jié)點也是y,因此語法樹和輸入串xay匹配成功。SAyabxa3.3自頂向下的語法分析小結：關于不確定的自頂向下分析方法這種自頂向下的分析是一個不斷試探的過程；即，在分析過程中，如果出現(xiàn)多個產生式(即候選式)可供選擇，則逐一試探每一候選式進行匹配，每當一次試探失敗，就選取下一候選式再進行試探；此時，必須回溯到這一次試探的初始現(xiàn)場，包括注銷已生長的子樹及將匹配指針調回到失敗前的狀態(tài)。這種帶回溯的自頂向下分析方法實際上是一種窮舉的試探方法，其分析效率極低，在實用的編譯程序中很少使用。3.3自頂向下

7、的語法分析2、確定的自頂向下分析方法確定的自頂向下分析要求文法滿足兩個條件：(1)文法不含左遞歸：即不存在這樣的非終結符號A：有A→A…存在或者有；原因：左遞歸的文法使自頂向下分析工作陷入無限循環(huán)E→E+T3.3自頂向下的語法分析(2)無回溯，對文法的任一非終結符號，當其產生式右部有多個候選式可供選擇時，各候選式所推出的終結符號串的首字符集合要兩兩不相交原因：會導致先前做的一大堆語法工作和語義工作(指中間代碼產生工作和各種表格的簿記工作)推倒重來3、消除左遞歸方法：引入一個新的非終結符，把含有左遞歸的產生式改寫為右遞歸。設關于非終結符A的直接左遞歸的產生式形如A?→?Aα

8、β其中，α、β

9、是任意的符號串且β不以A開頭。該產生式所能推導的句子如下：…3.3自頂向下的語法分析再看下面不含A的直接左遞歸的產生式：A?→?βA'A'→?αA'

10、ε這兩個產生式所能推導的句子如下：可見，兩種產生式所推導的結果相同：都能描述正規(guī)表達式βα*3.3自頂向下的語法分析3、消除左遞歸規(guī)則：將產生式A?→?Aα

11、β改寫為：A?→?βA‘A’→?αA‘

12、ε其中，A’是新引入的非終結符。ε不可缺少，否則推導過程無法結束。3.3自頂向下的語法分析例如，含有直接左遞歸的表達式文法G[E]為G[E]:E?→?E+T

13、TT?→?T*F

14、FF?→?(E)

15、iE?→?TE'E'?→?+TE'

16、ε(3.2)

17、經過消去直接左遞歸后得到文法G'[E]為T?→?FT'T'?→?*FT'

18、εG'[E]:F?→?(E)

19、i3.3自頂向下的語法分析3、消除左遞歸一般情況下，設文法中關于A的產生式為A?→?Aα1

20、Aα2

21、…

22、Aαm

23、β1

24、β2

25、…

26、βn其中，每個α都不等于ε且每個β都不以A開頭，則消除A的直接左遞歸性就是將其改為：例如，對產生式E→E+T

27、E-T

28、T，消除直接左遞歸后為3.3自頂向下的語法分析R=(β1

29、β2

30、…

31、βn)(α1

32、α2

33、…

34、αm)*E→TE'E'→+TE'

35、-TE'

36、ε3、消除間接左遞歸注意：也有些文法是含有間接左遞歸的，如下述文法G[S]:G[S]:S?→?Qc

37、cQ→?

38、Rb

39、bR→?Sa

40、a(3.3)中的S、Q、R都具有間接左遞歸3.3自頂向下的語法分析3、消除間接左遞歸如何消除一個文法的一切左遞歸呢？如果一個文法不含回路(形如A=>A的推導)，且產生式的右部也不含ε的候選式，那么，下述算法將消除文法的左遞歸：(1)將文法G[S]的所有非終結符按一給定的順序排列：A1、A2、…、An；+3.3自頂向下的語法分析(2)執(zhí)行下述循環(huán)語句將消除所有左遞歸for(i=1;i<=n;i++){for(j=