基于Java的遞歸下降語法分析器的實(shí)現(xiàn)

劉楊

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

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

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

一、LL（1）文法

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

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

2）對文法中任意一個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的候選的FIRST集兩兩不相交;

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

消除左遞歸是直接在文法結(jié)構(gòu)上做修改，防止產(chǎn)生式右部最終推導(dǎo)回到了原來產(chǎn)生式左部的非終結(jié)符。

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

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

二、遞歸下降分析器的設(shè)計(jì)

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

G：

E→TE'

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

T→FT'

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

F→（E） | id |num

可以得到各非終結(jié)符的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）條件。

三、代碼段分析

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

（一）遞歸的開始

（二）執(zhí)行到E中的T和E’

（三）執(zhí)行到F和T’

【參考文獻(xiàn)】

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

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