欢迎关注公众号:DeepL Newer

MENU

消除左递归

November 21, 2018 • Read: 1425 • 编译原理阅读设置

在进行语法分析的过程中,我们需要根据文法构建语法分析树。如果分析树构建成功则说明语法正确,反之语法错误。因此,如何构建一棵语法分析树非常重要

构建语法分析树有两种方式,一种是自上而下的分析方法(由根部开始构建语法分析树),另一种是自下而上的分析方法。本文采用的是自上而下的分析方法

自上而下的分析方法存在一个问题:文法中存在左递归怎么办?

什么是左递归?假设存在一个文法E → E+E,可能会存在以下的推导过程

$$ E→E+E→E+E+E→E+E+E+E→... $$

没完没了,陷入左递归状态,因此我们需要消除左递归

左递归的类型有以下两种:

  • 直接左递归

    • 例如 $A→A\alpha|\beta$
  • 间接左递归

    • 例如 $A→^+A\alpha$

消除直接左递归

直接左递归较为直观,以上文提到的$A→A\alpha|\beta$为例,我们对他进行推导

$$ A→A\alpha→A\alpha\alpha→A\alpha\alpha\alpha→...→\beta \alpha...\alpha $$

可以看出,此文法生成的串一定以$\beta$开头,后面跟随若干个$\alpha$,且$\alpha$的个数可以为0

因此我们可以定义一个新的非终结符$A'$,且新的文法满足以下条件

  • 令$\alpha$可以重复,且不产生左递归(即使用右递归)
  • 让A的产生式以$\beta$开头(消除原有的左递归)

因此新的文法如下

$$ \begin{align*} A&→\beta A\\ A'&→\alpha A'|\epsilon \end{align*} $$

事实上,消除左递归的过程就是把左递归转换成了右递归

再举个例子,消除下面文法的左递归

$$ \begin{align*} E&→E+T|T\\ T&→T*F|F\\ F&→(E)|id \end{align*} $$

仔细观察上述文法,发现只有产生式1和产生式2有左递归。对于产生式1,可以将+T看成一个整体$\alpha$,T看成是$\beta$,于是产生式1就可以看成是

$$ E→E\alpha|\beta $$

根据第一个例子中消除左递归的方式,产生式1消除左递归后变为

$$ \begin{align*} E&→\beta E'\\ E'&→\alpha E'|\epsilon \end{align*} $$

再将$\alpha,\beta$换回原来的符号

$$ \begin{align*} E&→TE'\\ E'&→+TE'|\epsilon \end{align*} $$

同理,对于产生式2,将*F看成一个整体$\alpha$,F看成是$\beta$,于是产生式2消除左递归后变为

$$ \begin{align*} T&→FT'\\ T'&→*FT'|\epsilon \end{align*} $$

消除直接左递归的一般形式

如果某条产生式具有直接左递归,例如

$$ A→A\alpha_1|A\alpha_2|...|A\alpha_n|\beta_1|\beta_2|...|\beta_m $$

其中,$\alpha_i\neq \epsilon$且$\beta$不以$A$开头

我们将其转换成不含左递归的产生式

$$ \begin{align*} A&→\beta_1A'|\beta_2A'|...|\beta_mA'\\ A'&→\alpha_1A'|\alpha_2A'|...|\alpha_nA'|\epsilon \end{align*} $$

消除左递归是要付出代价的,引进了一些非终结符和$\epsilon$产生式

消除间接左递归

例如以下文法

$$ \begin{align*} S&→Aa|b\\ A&→Ac|Sd|\epsilon \end{align*} $$

随便推导一下

$$ S→Aa→Sda $$

可以发现推导了两步就出现了左递归。消除间接左递归的方法也很简单,对于上面的例子

  • 首先将S的定义带入A的产生式,得

$$ A→Ac|Aad|bd|\epsilon $$

  • 消除A产生式的直接左递归,得

$$ \begin{align*} A→bdA'|A'\\ A'→cA'|adA'|\epsilon \end{align*} $$

消除间接左递归的方法总结下来,分以下3步

  1. 将递归链上的非终结符逐级带入产生直接左递归
  2. 消除直接左递归
  3. 删除多余文法

消除左递归算法

  • 输入:不含循环推倒(即形如$A→^+A$的推导)和$\epsilon$产生式的文法G
  • 输出:等价的无左递归文法
  • 方法:

Last Modified: August 25, 2020
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. Kaji Kaji

    “A→Aα→AAα→AAAα→...→βα...α”这里应该是“A→Aα→Aαα→Aααα→...→βα...α”吧

    1. mathor mathor

      @Kaji是的,已修正,谢谢@(大拇指)