編譯原理-文法分析

1.文法分析概述

  1.1 定義

          文法分析就是根據進階語言的文法規則對程式的文法結構進行分析。如下圖所示：

1.2 任務

           文法分析的任務就是在詞法分析識别出正确的單詞符号串是否符合語言的文法規則，分析并識别各種文法成分，同時進行文法檢查和錯誤處理，為語義分析和代碼生成做準備。

1.3 地位

           文法分析在編譯過程中處于核心地位。

1.4 文法分析程式

           執行文法分析的程式稱為文法分析程式，也稱為文法分析器。

1.5 文法

           通過對進階語言的文法規則進行形式化的描述，進而能夠更加精确的描述進階語言程式的文法結構，這種描述稱為文法。适合描述進階語言文法規則的文法是上下文無關法。

1.6 判斷依據

         對給定的輸入符号串能否根據文法的規則建立起一顆文法樹。

2.上下文無關文法

2.1 原理

          上下文無關法用遞歸的方式來描述文法規則。文法分析的過程就是按照文法規則對讀入的token串進行分析的過程。token串中的每個單詞符合對應與文法的一個符号。

2.2 文法的定義

2.2.1 概念

        文法是描述語言的文法結構的形式規則（即文法規則），這些規則必須準确且可了解。

1.非終結符	代表一個文法範疇，表示一類具有某種性質的文法機關。在程式設計語言中，非終結符有算術表達式， 指派語句等。用Vn表示非終結符的集合。
2.終結符	出現在最終的句子中的符号稱為終結符，在程式設計語言的文法規則中終結符就是單詞 符号，比如關鍵字、辨別符、界符等等。用Vt表示終結符的集合。
3.産生式	按照一定格式書寫的，用于定義文法範疇的規則。說明了終結符和非終結符組合成字元串的方式， 用P表示産生式的集合。
4.開始符号	是一個特殊的非終結符，至少在一個産生式的左部出現，用S表示，代表該文法定義的語言最終要 得到的文法範疇在程式設計語言中，開始符号就是<程式>。

2.2.2 形式化定義

       文法的形式化定義為：文法G是一個四元組，G=（Vn，Vt，P，S），其中Vn是非終結符集，Vt是終結符集，S是開始符号，P是産生式集合。

2.2.3 定義

       一般的在書寫産生式有下列約定：

1.第一條産生式的左部是開始符号

2.在産生式中，用大寫字母表示非終結符；小寫字母表示終結符；小寫希臘字母（如α、β）代表任意的文法字元串。

3.如果S是文法G的開始符号，也可以将文法G寫成G[S]

4.有時為了書寫簡潔，常把相同左部的多個産生式用|進行縮寫。如A->a1|a2|a3|a4|a5|....

2.3 推導

      從文法的開始符号出發，反複連續使用所有可能的産生式，将一個符号串中的非終結符用某個産生式右部進行替換和展開，直到全部為終結符為止，這個過程就稱為推導。

2.3.1 最左推導

        如果在推導過程中，每一步都是替換符号串中最左邊的非終結符，這樣的推導稱為最左推導。

2.3.2 最右推導

        如果在推導過程中，每一步都是替換符号串中最右邊的非終結符，這樣的推導稱為最右推導。

2.4 文法産生的語言

2.4.1 定義

S（句型）	由開始符号出發推導出的符号串，包含非終結符和終結符。
X（句子）	僅含終結符的句型
L(G)（語言）	文法G産生的所有的句子的集合

2.4.2 等價

      如果文法G1與文法G2産生的語言相同，即L(G1) = L(G2)，則稱文法G1與文法G2是等價的。

2.5 文法樹

2.5.1 定義

          根據文法可以手工或自動生成一個有效的文法分析程式，用來判斷輸入的符号串在文法上是否正确。判斷的一句就是對給定的輸入符号串能否根據文法規則建立起一顆文法樹。

          上述用推導的方式來考察文法定義語言的過程，但是推導不能表示句子的各個組成部分間的結構關系。文法樹能夠表示句子的構成和層次關系。

         文法樹就是用一棵樹來表示一個句型的推導過程，有時也稱為文法分析樹。文法樹是一棵倒立的樹，根在上，枝葉在下。根節點由開始符号标記。随着推導的展開，當某個非終結符被它的候選式所替換時，這個非終結符就産生下一代新結點。

         文法樹的葉子結點由非終結符、終結符和c 标記。

2.5.2 分類

       由于對一個句子或者一個句型的推導過程不止一種，是以文法樹也表示了一個句型的不同的推導過程，包括：最左推導和最右推導。

2.5.3 二義文法

         如果一個文法存在某個句型對應兩棵或兩棵以上不同的文法樹，則稱為這個文法為二義文法。也就是說，二義文法是存在某個句型也不隻有一個最左（最右）推導的文法。對二義文法中某些句子的分析過程中不是唯一的，也就不能确定某個句子應該選擇那棵文法樹進行分析。是以要使用一些附加的規則來消除二義性。

      文法的二義性不能代表語言一定是二義的，隻有當産生的一個語言的所有的文法都是二義的，這個語言才是二義的。因為可以用無二義的文法代替二義的文法。

2.5.4 消除二義性

      利用運算符之間的優先級和結合性來消除算術表達式文法的二義性。在通常的算術運算中，*和/比+和-的優先級高，都遵循左結合的原則，如下所示：

優先級	結合性	運算符
1	左結合	+，-
2	左結合	*，/

        其中左結合性的含義是：當出現相同優先級的運算符時，從左到右進行運算。優先級越高，越優先運算。

2.5.5 文法分析方法

        按照文法樹的建立方法，可以粗略的把文法分析分為兩類：自上而下文法分析法與自下而上文法分析法。

3.3 自上而下的文法分析

3.3.1 定義

       自上而下的文法分析方法就是對任何輸入串（由token串構成的源程式），試圖用一切可能的辦法，從文法開始符号（根結點）出發，自上而下的為輸入串建立一棵文法樹，或者說，為輸入串尋找一個最左推導。

3.3.2 問題引入

       在替換一個非終結符時，如果一個非終結符有多個候選式，選擇哪個候選式是一個問題。自上而下分析的過程本質上是一種試探過程，是反複使用不同産生式謀求比對輸入串的過程。确定的自上而下的分析就是每一次的候選式都是确定的，然而在試探過程中可能會出現以下問題：

     1）試探與回溯

       試探與回溯是一種窮盡一切可能的辦法，效率低，代價高，導緻分析器不穩定。使用自上而下分析時，要設法消除回溯。

       即當文法中存在形如A->αβ1|αβ2......的産生式，即某個非終結符存在多個候選式的字首相同（也稱為公共左因子），則可能造成虛假比對（即目前的比對可能是暫時的），即發現不能比對後重新回溯重新選擇一個候選式進行比對，這樣反複多次，使得在分析過程中可能需要大量的回溯。

     2）左遞歸

      導緻分析過程無限循環。假如文法中存在形如：A->Aa的産生式（稱為左遞歸），分析過程中又使用左推導，則就會使得分析過程陷入無限循環中，是以，使用自上而下分析時，文法應該不包含左遞歸。

3.3.4 回溯的消除

      回溯産生的根本原因在于某個非終結符的多個候選式存在公共左因子，如非終結符A的産生式如下：

A->αβ1|αβ2
           

     如果輸入串中待分析的字字首也為α，此時選擇A的那個候選式就會不确定，可能就導緻回溯。是以，要想進行确定的分析，必須保證文法G的每個非終結符的多個候選式均不包含公共左因子。

   1）改造方法：

改造的方法是提取公共左因子。使得文法的每個非終結符号的各個候選式的首終結符集兩兩不相交。

  2）案例

例1：條件（if）語句的文法有兩個候選式如下：
    <IFS> -> if B then S1 else S2
    <IFS> -> if B then S1

上面存在問題：當輸入的符号是if時，就不能立刻确定選用那個候選式，提取公共因子後：
    <IFS> -> if B then S1 P
        P -> else S2

例2：對A→δα1|δα2|…|δαn，提取公共左因子後為：
    A->δA'
    A'->α1|α2|…|αn
           

       對于例1，當S1比對成功後，根據下一個輸入符号是不是else，再決定是否選擇P的候選式進行比對。

3.3.5 左遞歸的消除

      左遞歸包括直接左遞歸和間接左遞歸。

直接左遞歸	若文法G中有形如A->Aα的産生式，則稱該産生式對A直接左遞歸。
間接左遞歸	若文法G中沒有形如A->Aα的産生式，但是A經過有限步驟推導可以得到A->Aα，則稱該産生式 對A間接左遞歸。

     1）消除文法的直接左遞歸

       消除文法的直接左遞歸是通過對産生式進行改造來實作的。将各個産生式改造後使得各個非終結符不含左遞歸，如下所示：

案例1：
A的候選式為：A->Aα|β
改造後的非直接左遞歸形式：
    A->βA'
    A'->αA'|c（c為空字）
------------------------------------
案例2：如下所示文法G是含有左遞歸的文法
    E->E+T|T
    T->T*F|F
    F->i|(E)
消除左遞歸後如下所示：
    E->TE'
    E'->+TE'|c
    T->FT'
    T'->*FT'|c
    F->(E)|i
           

      實際上是将直接左遞歸改成了直接右遞歸，這樣在最左推導中就不會陷入死循環。

      将上述結果推廣，有以下消除直接左遞歸的形式：

假設文法中A的産生式如下：
    A->Aα1|Aα2|Aα3|......|Aαm|β1|β2|β3......|βn
則消除直接左遞歸如下所示：
    A->β1A'|β2A'|......|βnA'
    A->α1A'|α2A'|......|αmA'|c
           

     2）消除文法中的間接左遞歸

       有些文法中的左遞歸并不是直接的，如下所示：

S->Ac|c
A->Bb|b
B->Sa|a
存在推導：S->Ac->Bbc->Sabc
           

      從上面看出，間接的推導出現了左遞歸。對于間接左遞歸，可以采用先代入，然後再消除直接左遞歸的方法，如下所示：

對于文法如下消除左遞歸：
    S->Ac|c
    A->Bb|b
    B->Sa|a
1）代入：
    将産生式B->Sa|a代入A->Bb|b，有A->(Sa|a)b|b，即A->Sab|ab|b
    将産生式A->Sab|ab|b代入A->Ac|c，有S->(Sab|ab|b)c|c，即S->Sabc|abc|bc|c
2）消除S的直接左遞歸，得到：
    S->abcS'|bcS'|cS'
    S'->abcS'|c
    A->Bb|b
    B->Sa|a
           

3.3.6 LL(1)文法

       沒有左遞歸和沒有公共左因子并不能進行确定的自上而下的分析。如下所示：

有文法如下所示：
    S->Ac|Be
    A->db|b
    B->da|a
當輸入字元串dbc，要求用S的候選式比對d時，雖然S的兩個候選式沒有公共左因子，仍不能準确地選取S的候選式，
不能進行确定的分析。
           

    1）First集

      First(α)是文法G的符号串α的首終結符集，即由該候選式推導出的所有符号串中的第一個終結符或可能的c（空字）的集合，其中α可能是文法符号、c或者候選式，或候選式的一部分。定義為：First(α) = {a|α=>a....，a∈Vt}，其計算的方式如下所示：

1）若産生式形如A->aα，則First(A->aα)={a};
2）若産生式形如A->c，則First(A->c)={c};
3）産生式形如A->Xα，則把First(X)中非c元素加入到First(A->Xα)中去
4）若有産生式形如A->X1X2X3...Xkα,則有
    1.當X1X2X3...Xi=>c（有限步驟，1<=i<=k）時，則把First(Xi+1....Xk)的所有非c元素加入到First(A->X1X2X3...Xkα)中
    2.當X1X2X3...Xk=>c（有限步驟）時，則把First(α)加入到First(A->X1X2X3...Xkα)中
           

     由上面的定義可知：

若文法符号A為終結符（A∈Vt），則First（A）={A}

若文法符号為非終結符A（A∈Vn），求First集的方法就是将非終結符A的每個候選式的First集都加入到First（A）中。

      案例如下所示：

求下述各個候選式和非終結符的First集
    E->TE'
    E'->+TE'|c
    T->FT'
    T'->*FT'|c
    F->(E)|i
-------------------------------
各個候選式的First集:
    First(E->TE') = First(T) = First(F) = {(,i}
    First(E'->+TE') = {+}
    First(E'->c) = {c}
    First(T->FT') = First(F) = {(,i)}
    First(T'->*FT') = {*}
    First(T'->c} = {c}
    First(F->(E)) = {(}
    First(F->i) = {i}
各個非終結符的First集：
    First(E) = First(T) = First(F) = {(,i}
    First(E') = {+,c}
    First(T) = {(,i}
    First(T') = {*,c}
    First(F) = {(,i}
           

    2）Follow集

        表示非終結符A的後随符号集Follow（A），定義如下：

假設S是文法G的開始符号，對G的任何非終結符A：Follow(A)={a|S=>...Aa...，a∈Vt}
若S=>...A，則規定#∈Follow(A)，
           

     通俗來講就是Follow(A)就是所有句型中出現在緊接A之後的終結符号或者#,#表示輸入符号串的結束标記。

     利用Follow集的定義，使用c産生式進行自動比對的過程是：當非終結符A面臨輸入符号a，且a不屬于A的任一候選式的首終結符集，但是A的某個候選式的首終結符集含有c時，隻有當a∈Follow(A)，才能用c産生式進行自動比對。

     計算文法G的每個終結符A的Follow集使用如下算法來計算：

輸入：文法G
輸出：非終結符A的Follow集
步驟：
    1）如果A是開始符号，則#∈Follow(A)。
    2）如果有産生式B->αAaβ,a∈Vt,把a加入到Follow(A)中。
    3）如果有産生式B->αAXβ，X∈Vn，把First(Xβ)中非c元素加入到Follow(A)中。
    4）如果B->αA，或者B->αAβ且β=>c，把Follow(B)加入到Follow(A)中。
    5）對每一個非終結符，浏覽每個産生式，連續使用上述規則，直到A的Follow集不再增大為止。
           

     案例如下所示：

例1：由如下文法：
    S->Ap
    S->Bq
    A->a
    A->cA
    B->b
    B->dB
則Follow集如下所示：
    Follow(S)={#}（規則1，因為是開始符号）
    Follow(A)={p}（規則2）
    Follow(B)={q}（規則2）

例2：有如下文法：
    1) E->TE'
    2) E'->+TE'
    3) E'->c
    4) T->FT'
    5) T'->*FT'
    6) T'->c
    7) F->(E)
    8) F->i
計算的各個非終結符的Follow集如下所示：
    1）Follow(E)={#,)}。E是開始符号，應用規則1；根據産生式7，應用規則2。
    2）Follow(E')=Follow(E)={#,)}
    3）Follow(T)=(First(E')-{c})∪Follow(E')={#,),+}（規則3，4）
    4）Follow(T')=Follow(T)={#,),+}
    5）Follow(F)=(First(T')-{c})∪Follow(T)={*,#,),+}
   
           

     3）文法的判别方法

1.檢查是否含有左遞歸
2.如果沒有左遞歸，則計算其First集，判别其First集是否相交，即是否有回溯
3.若存在某個A=>ε,求A的 Follow集，并判别條件 (3) 是否滿足(是否可以使用ε-産生式進行比對)
           

3.3.7 遞歸下降分析方法

     是進行文法分析的一種方法，要求文法是LL(1)文法。

     1）實作思想如下所示：

1）：分析程式由一組函數組成。每個函數對應于文法的一個非終結符号。
2）：每一個函數的功能是：判斷選擇該非終結符的哪個候選式，并按該候選式的要求處理完輸入符号串。在該候選式的右部中
若遇到非終結符号，調用該非終結符号對應的過程來完成，若為終結符，判斷是否和讀入的符号相同。
           

     遞歸下降分析是直接以程式的方式模拟産生式産生語言的過程，即為每一個非終結符構造一個函數，每個函數的函數體按非終結符的候選式分情況展開，遇到終結符就進行比較，看是否與輸入的符号相同；遇到非終結符就調用該非終結符對應的函數。 

     2）分析過程：

    從調用該文法開始符号對應的函數開始，直到所有非終結符都展開為終結符并得到比對為止。如果分析到這一步則表示分析成功，否則表示輸入符号串有錯。

     3）實作方式

     對于每個非終結符U（假設U的候選式為U->U1|U2|U3|......|U4|）的函數有如下分析方法：

1）根據輸入符号決定使用U的哪一個候選式進行分析
    void U( ){   
       token=目前符号;
	   if(token是First(u1)中的一個符号)  處理u1
	   else if(token是First(u2)中的一個符号)  處理u2		
       ......
	   else	error()    
    }
2）對應于某個候選式Ui（假設Ui是形如X1X2X3......Xn的候選式）的處理Ui(),就是通過順序處理該候選式Ui的每個符号Xi來完成其功能的。
    void Ui(){
        處理X1的程式；
	    處理X2的程式；
	    ......
	    處理Xn的程式；
    }
3）對于每個符号Xi的處理
如果xi為終結符号：
    if (x == 目前輸入符号串中的符号){  
        token = GetNextToken()；return;  }
    else
	    出錯處理
如果xi為非終結符号，直接調用相應的過程：
    xi()
           

    4）案例如下：

     有如下文法:

E -> TE'
E' -> +TE'|c
T -> FT'
T' -> *FT'|c
F -> (E)|i
           

    編寫對應的遞歸下降分析程式:

1）對于非終結符E，候選式為E->TE'
    void E(){
        T();
        E'();
    }
2）對于非終結符E',候選式為E'->+TE'|c
    void E'(){
        if(token=='+'){
            match('+');
            T();
            E'();
        }
    }
3）對于非終結符T，候選式為T->FT'
    void T(){
        F();
        T'();
    }
4）對于非終結符T',候選式為T'->*FT'|c
    void T'(){
        if(token=='*'){
            match('*');
            F();
            T'();
        }
    }
5）對于非終結符F,候選式為F->i|(E)
    void F(){
        if(token=='('){
            match('(');
            E();
            if(token==')'){
                match(')');
            }else{
                error();
            }
        }else if(token=='i'){
            match('i'); 
        }else{
            error();
        }
    }
           

    5）分析程式的接口如下所示：