递回下降剖析器.PDF

迴下降剖析器 20 10/04/ 18 遞迴下降剖析器(Recursive Descent Parser)的寫法 「遞迴下降剖析器」是屬於一種 「由上往下(Top down) 」的剖析器，也就是說，由文法規則中 的開始符號一路往下使用文法規則產生相符的終端符號，過程中剖析樹是由上往下產生。因 為輸入的單詞值 （終端符號）是由左至右一個個讀進剖析器 ，因此要由一個單詞或數個單詞 的值就知道要選用哪一條文法規則由上往下產生相符的終端符號，這些文法規則中的終端符 號最好是位於規則的最左側 。適用於使用 遞迴下降剖析器」的文法規則最好是沒有左遞迴 的非終端符號。同時如果兩條或兩條以上的文法規則具有較長的靠左手部份，那麼最好將這 些共同的部份取出而另外設計幾條文法規則來產生此一共同部份。 移除左遞迴文法規則的方法是將原本由右往左(左遞迴文法規則) 開始成長的各種符號，改成先 產生最左側的符號，再由左往右側成長(右遞迴文法規則) 。如圖一所示，這兩條文件規則會由 右往左產生一連串的 符號後停止於β 符號，此為典型的左遞迴文法規則。將之改成右遞迴， 為圖二中的文法規則，先產生β 符號後 ，再往右產生一連串的 符號。 1 A - A 1 A -β Atail 2 A - β 2 Atail - Atail 3 Atail - null 圖一 具有左遞迴的文法規則 圖二 移去左遞迴規則後的文法 合併共同左側規則，是將具有共同的左側部份的數條文法規則合併起來 ，成為一條共同的進 入點的文法規則 。如此可以減少由上往下剖析過程中的往前看單詞個數。例如圖三中的兩條 文法規則，要決定是使用1 或2 是要等到剖析器見到過符號B C D 後才能決定 。若是合併成 共同的一條規則，如圖四中的 1 ，那麼在選擇使用哪一條文法規則時就只有一條可以用，就 是 1 。 後續不同的部份其左側是不一樣的，因此只要往前看一個單詞就可以決定使用哪一 條規則。如此，合併共同左側規則可以減少往前看的單詞個數，簡化剖析器。 1 A - B C D E F 1 A - B C D X 2 A - B C D G 2 X - E F 3 X - G 圖三 具有共同左側的兩條文法規則 圖四 共同左側的文法合併後的文法 「遞迴下降剖析器」通常是直接基於文法規則而建立的剖析器 。文法規則必須沒有左遞迴， 而建立的剖析器其剖析過程是由上往下一系列的呼叫函數，函數往往是遞迴呼叫。因此這樣 的剖析器稱為 遞迴下降剖析器」。 在此使用一個簡單的文法 ，如圖五所示，來說明建 「遞 迴下降剖析器」的過程。 1 圖五中列出一範例文法，其終端符號值假設都只有一個字母。在此為 ‘a’, ‘(’, ‘)’, ‘+’, ‘*’,和一個 特殊的輸入結束符號 ‘$’ 。此文法所描述的句子為具有加與乘的單變數數學公式，變數名稱限 定為字母 ‘a’ 。其中可以用左右括號將公式組合起來表示優先次序。範例合法字串例如 “a + a * ( a + a )$” 。 1 S - E$ 1 S - E$ 2 E - E + T 2 E - T Etail 3 E - T 3 Etail - + T Etail 4 T - T * F 4 Etail - null 5 T - F 5 T - F Ttail 6 F - a 6 Ttail - * F Tt