編譯原理實用教程 楊德芳 第4章 自頂向下的語法分析技術

《編譯原理實用教程 楊德芳 第4章 自頂向下的語法分析技術》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第4章自頂向下的語法分析技術本章學習目標語法分析是繼詞法分析之后，編譯過程的第二個階段。它的主要任務是對詞法分析的輸出結果—單詞序列進行分析，識別出合適的語法單位。語法分析分為自頂向下和自底向上的兩類方法。自頂向下的語法分析又分為確定的自頂向下分析（無回溯）和不確定的（帶回溯的）的自頂向下語法分析兩種。本章主要內容有：。自頂向下的語法分析的基本思想。LL(1)語法分析方法。確定的自頂向下分析技術，包括遞歸子程序法和預測分析技術4.1確定的自頂向下分析方法自頂向下分析就是從文法的開始符號出發(fā)并尋找出這樣一個推導序列：推導出的句子恰好是輸入符號串；或者說，能否從根結點出發(fā)向下

2、生長出一棵語法樹，其葉結點組成的句子恰好為輸入符號串。顯然，語法樹的每一步生長（每一步推導）都以能否與輸入符號串匹配為準。如果最終句子得到識別，則證明輸入符號串為該文法的一個句子；否則，輸入符號串不是該文法的句子。自頂向下分析分為確定的自頂向下分析和不確定的自頂向下分析法兩種。具體分析方法歸納如下：（1）自頂向下建樹，試圖生成一個和所給符號串（輸入符號串）相一致的終結符號串。（2）在建樹過程中，按照一定的規(guī)律選擇生成規(guī)則，展開為向下生長的樹。每一步都試圖將生成的尚未消除的最左葉片與輸入符號匹配。（3）匹配失敗后，必須退回到出錯點，選擇其他可能的規(guī)則，直到生長出與讀入符號串

3、完全一致的樹型結構，這種方法稱為回溯。（4）如果按上述方法構造成功，說明讀入的符號串是文法的一個句子；反之，如果窮盡所有的途徑都沒有辦法成功，則說明讀入的符號串不是文法的一個句子。4.1.1確定的自頂向下分析思想確定的自頂向下分析方法，首先要解決從文法的開始符號出發(fā)，如何根據當前的輸入符號（單詞符號）惟一地確定選用哪個產生式替換非終結符往下推導，或者構造一棵相應的語法樹。例題4.1設有文法G[S]：S?pA

4、qBA?cAd

5、aB?dB

6、b若輸入串W=pccadd。自頂向下的推導過程為：S?pA?pcAd?pccAdd?pccadd確定的自頂向下分析的語法樹如圖4-1所示。

7、S（c）（a）（b）（d）SpASpAcAdSpAcAdcAdpAcAdcAda例4.2設有文法G[S]為：S?Ap

8、BqA?a

9、cAB?b

10、dB當輸入串W=ccap時，那么試圖推出輸入串的推導過程為：S?Ap?cAp?ccAp?ccap，構造出確定的自頂向下分析的語法樹如圖4-2所示。該文法的產生式的右部不全是終結符開始，也有非終結符A和B。在推導過程中選用哪個產生式就不直觀。比如在第一步推導中，是選擇以A開始還是以B開始的產生式，我們必須向下再找一步，看看A和B的產生式哪個是有c開始。先看A，A的產生式規(guī)則是有a和c開始，而B的產生式規(guī)則是有b和d開始，很顯然是用以A

11、開始的產生式規(guī)則。所以就產生了推導：S?Ap，此時，A有兩個產生式規(guī)則，很容易判斷出用哪個。通過此例子，能看出在語法推導過程中，有一點很重要，那就是文法中產生式規(guī)則的開始符號。下面就產生式規(guī)則的首符號集進行定義。定義4.1設G=(VN,VT,S,P)是上下文無關文法FIRST(?)={a

12、?a?,a?VT,?,??V*}如果??，則規(guī)定??FIRST(?),，FIRST(?)為?的開始符號集或首符號集。定義4.1設G=(VN,VT,S,P)是上下文無關文法FIRST(?)={a

13、?a?,a?VT,?,??V*}如果??，則規(guī)定??FIRST(?),，FIRST(?

14、)為?的開始符號集或首符號集。例如，FIRST(Ap)={a,c}FIRST(Bq)={b,d}這樣，在推導時，只要這兩個產生式右部的首符號集沒有交集，就可以惟一的選擇產生式的規(guī)則。例4.3若有文法G[S]：S?aA

15、dA?bAS

16、?若輸入串W=abd，則試圖推導出abd串的推導過程為：S?aA?abAS?abS?abd該輸入串確定的語法樹如下圖4-3所示。SaASaAbASSaAbAS?AbA?d定義4.2設G=（VT,VN,S,P）是上下文無關文法，A?VN，S是開始符號FOLLOW（A）={a

17、S?A?，且a?VT，a?FIRST(?)，??VT*，??V+}若S

18、=>?A?，且?=>*?，且#?FOLLOW(A)。也可以定義為FOLLOW（A）={a

19、S…Aa…，a?VT}若有S=>…A，則規(guī)定#?FOLLOW（A）一般來講，我們用“#”作為輸入串的結束符，或稱為句子的括號，如#輸入串#。4.1.2LL(1)文法的定義根據上面的分析我們重新定義一個產生式被選擇時的集合SELECT如下。定義4.3給定上下文無關文法的產生式A??，A?VN，??V*，若?不能推出?，則SELECT(A??)=FIRST(?)如果?能夠推導出?，則SELECT(A??)=(FIRST(?)﹣{?})∪FO