基于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