基于Java的遞歸下降語法分析器的實現

劉楊

【摘 要】遞歸下降分析是設計LL（1）文法的自上而下語法分析的一種思路。相對于其他的語法分析構造方法，這一邏輯簡單明了，易于用代碼實現。只不過，作為自上而下的分析方法，在編寫代碼前，要確保所分析的文法是不含左遞歸并且是消除回溯的。

本文將先后介紹LL（1）文法的成立條件和遞歸下降分析器的設計邏輯，最后給出程序的關鍵代碼段示例。

【關鍵詞】編譯原理;語法分析;自上而下分析;遞歸下降;LL（1）分析

一、LL（1）文法

這里，首先給出LL（1）文法的三個成立條件：

1）文法中不含有左遞歸;

2）對文法中任意一個非終結符的各個產生式的候選的FIRST集兩兩不相交;

3）對文法中每個非終結符A，若其某個產生式的FIRST集合含有ε，則需要FIRST（A）與FOLLOW（A）不相交。

消除左遞歸是直接在文法結構上做修改，防止產生式右部最終推導回到了原來產生式左部的非終結符。

上述第2個條件是為了消除大部分回溯。在面臨單個字符時，同一個終結符的不同產生式可能都可以初步接受（FIRST集合有重合部分），但是正確結果往往只有一個;而想發現錯誤也往往要把該條產生式的路徑走到底，這就造成程序可能要不斷地“碰壁”而從頭開始重新掃描輸入，造成大量不必要的開銷。但是，只要同一個非終結符的每個產生式FIRST集不相交，導致各個產生式識別初步接受的字符集合是獨立的，相對唯一的，那么識別字串的路徑就能保證是唯一的。

上述第3個條件，是為了解決和ε產生式有關的回溯問題。掃描輸入串的過程中，當某一個字符不能被當前產生式直接識別，如果該產生式對應的非終結符有ε產生式，那么可以考慮使用ε暫時作為識別結果，使得程序能夠向后判斷產生式是否匹配。使用ε產生式的條件是，當前字符必須在當前非終結符的后繼/后隨終結符集中出現過，也就是其FOLLOW集。

二、遞歸下降分析器的設計

遞歸下降，就是自上而下語法分分析的主要思想。遞歸下降分析器專指的是實現LL（1）分析的程序。這樣的程序，由一組遞歸的過程組成，其中每一個遞歸過程代表著文法的一個非終結符。也就是程序結構與文法的產生式結構緊密相連，這也是該程序易于構造的重要原因。執行的過程類似于數據結構中對二叉樹的從左到右的深度優先遍歷。下面我們以文法G為設計對象：

G：

E→TE'

E'→+TE'| -TE' |ε

T→FT'

T'→*FT'| /FT' |ε

F→（E） | id |num

可以得到各非終結符的FIRST集和FOLLOW集：

FIRST（E） = {（， id， num};FIRST（E'） = {+， -， ε};FIRST（T） = {（， id， num}

FIRST（T'） = {*， /， ε};FIRST（F） = {（， id， num}

FOLLOW（E） = {）， #};FOLLOW（E'） = {id， num};FOLLOW（T） = {id， num}

FOLLOW（T'） = {id， num};FOLLOW（F） = {id， num}

上述文法明顯滿足了LL（1）條件。

三、代碼段分析

以下以產生式E→TE’為例展示遞歸過程;E’、T’等使用E2、T2表示。

（一）遞歸的開始

（二）執行到E中的T和E’

（三）執行到F和T’

【參考文獻】

[1] 陳火旺，等.程序設計語言編譯原理（第3版）[M].北京：國防工業出版社，2006： 68-76

[2] [美] Andrew W.Appel.現代編譯原理[M].趙克佳，等，譯.北京：人民郵電出版社， 2006： 36-37