递归对自顶向下语法分析的影响

摘要：在编译程序的语法分析中，含有左递归的文法，无法采用自顶向下的方法来进行语法分析，该文从递归的角度出发，讨论递归对自顶向下语法分析的影响。

关键词：编译器 ；语法分析；递归；左递归；右递归

中图分类号：TP314.51 文献标识码：A 文章编号：1009-3044（2018）04-0231-02

语法分析是编译程序的核心部分，语法分析方法有多种，每一种语法分析方法只能处理某一种形式的文法，为了适应所选择的语法分析方法，常常需要对原始文法进行改造。比如含有左递归文法或二义性文法将无法采用自顶向下的方法来进行语法分析，本文从递归的角度出发，讨论递归对自顶向下语法分析的影响。

1 递归的定义

递归作为一种算法在程序设计语言中广泛应用，程序调用自身的编程技巧称为递归，递归可把一个大型复杂的问题层层转化为一个与原始问题相似的规模较小的问题来求解，只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要优势在于用有限的语句来定义对象的无限集合。其缺点是递归算法相对于非递归算法效率低，在递归调用的过程中系统需要为每一层的返回点、局部变量等开辟栈来存储，如果递归次数过多容易造成栈溢出。

2 文法中的递归

若文法中存在一个（或多个）非终结符号，它可以推导出含有其自身的符号串，则称该非终结符号是递归的。一个文法中如果含有递归的非终结符号，则此该文法称为递归文法。

文法中递归的分类：

假设A是文法G的某个语法变量，如果存在推导AαAβ，则称文法是递归的；

1） 当α=ε时，称之为左递归；当β=ε时，称之为右递归；

2） 如果AαAβ需要两步以上推导，则称文法G是间接递归；并且当α=ε时，称之为间接左递归；当β=ε时，称之为间接右递归；

3） 如果文法G中存在形如A→αAβ的产生式，则称文法G是直接递归；当α=ε时，称之为直接左递归，当β=ε时，称之为直接右递归。

3 递归对自顶向下语法分析的影响

3.1 消除左递归引起的无穷推导问题

使用自顶向下语法分析法进行语法分析时，假设文法中存在非终结符A，并且有AAa左递归，此文法是不能使用自顶向下的方法进行语法分析的。因为当试图用A去匹配输入串时，有可能使分析过程陷入无限循环，因为可能在没有“匹配”任何输入符号的情况下，又要求用下一层A去进行新的匹配，即使当某个非终结符用某个选择匹配成功时，这种成功可能是暂时的，由于存在这種虚假现象，需要使用复杂的回溯技术，而试探与回溯效率低、代价高，只有理论意义，在实践中价值不大。因此，要想使用自顶向下的语法分析，必须消除文法中的左递归。

1） 消除直接左递归

采用直接改写法：即把文法中直接左递归改写为一个等价的非直接左递归形式。

假定关于A的全部产生式为：

A→Aα1|Aα2|…|Aαm|β1|β2|…|βn （αi非空，βj不以A开头，1≤i≤m，1≤j≤n）

消除直接左递归后改写为：

A→β1A | β2A| …|βnA

A→α1A|ɑ2A|…|ɑmA|ε

此方法改写后可删除文法中直接左递归，但不能消除两步或多步推导形成的间接左递归。

2） 消除文法中所有多重间接左递归的方法：

当文法中含有多重间接左递归时，需先将产生式非终结符进行置换，将间接左递归转变为直接左递归，再按直接改写法来消除直接左递归。

输入：不含循环推导和A→ε产生式的文法G

输出：与G等价的不含左递归的文法

步骤：1.将文法的非终结符按某一顺序排序，例如：P1，P2，…，Pn

2. for i：=1 to n

3. { for j：=1 to i-1

4. { 若Pj的所有产生式为Pj→δ1|δ2|…|δk

5. 将其替换形如Pi→Pjr的产生式得到Pi→δ1r|δ2r|…|δkr；}

6. 消除Pi中的一切直接左递归

7. 化简上述所得文法，去除无用产生式

3.2 递归下降语法分析法中的递归

递归下降分析法，是一种确定的自顶向下语法分析方法，它根据各个产生式的结构，为文法的每个语法变量编写一个处理子程序，用来识别该语法变量所代表的语法成分。由于产生式中的语法变量可能是递归调用的，所以这种实现方法要求子程序可以递归调用，另外，这种分析方法也是寻求输入串的一个最左推导过程，所以称为递归下降分析法。它要求文法必须满足LL（1）文法。

采用递归下降分析法的文法中不能含有直接左递归的产生式，因为左递归会使递归下降语法分析器进入一个无限循环。

递归下降分析法递归调用多，所以速度慢，占用空间较多。

4 文法中同时含有左递归和右递归的危害

如果一文法中既含有左递归又含有右递归，即有AAvA或AA 或 A Aα及A βA （v∈V*）三者之一情况，则称此文法是二义性的。

对于编译程序而言，二义性文法是有害的。由于语法结构分析上的不确定性，必然会导致语义处理上的不确定性，最终生成的目标代码具有不确定性。并且对于二义性文法来说，不存在一种确切的方法进行语法分析，此时可通过引入新的语法变量，来消除文法的二义性。

例：文法G[E]： E→id E→E+E E→E*E E→（E） 同时含有左递归和右递归，是二义性文法。

但在规定了优先顺序和结合律后可将文法改写为：

G[E]：E → T| E+T

T → H| T*H

H →（E）| id

此时文法中只含有左递归而无右递归，改写后的文法是个无二义性文法。

5 结束语

含有左递归文法或二义性文法将无法采用自顶向下的方法来进行语法分析，此时我们可以将含有左递归的文法转换为改写为一个等价的非直接左递归形式，将二义性文法通过规定优先顺序和结合律将文法改写为无二义性文法。如果改写后的文法是满足LL（1）文法，就可以采用确定的自顶向下分析法进行语法分析。

参考文献：

[1] 朱朝霞，周云才. 二义性文法的语法分析方法探讨[J] 长江大学学报，2008，5（6）.

[2] 蒋宗礼，姜守旭. 编译原理[M]. 北京：高等教育出版社，2010.

[3] 张素琴， 吕映芝，等. 编译原理[M].北京：清华大学出版社，2005.

[4] 张昱，陈意云. 编译原理与技术[M] 北京：高等教育出版社 2010.

[5] 陈火旺， 蒋伟进，等. 编译原理[M] 长沙：中南大学出版社，2005.

[6] 黄贤英，王柯柯. 编译原理及实践教程[M]. 北京：清华大学出版社，2008.