优化递归下降算法的尾递归

我们在文章递归下降算法左递归问题这篇文章里面，介绍了如何消除左递归。总结起来，就是把非终结符放到终结符的右边，使得我们在推导的过程中，可以消耗掉下一个token。

但是，这种方法有一个问题。还是以1 + 2 + 3这个表达式为例来讲解一下优化手段。

首先，我们的文法规则如下：

additive -> intLiteral | intLiteral + additive

按照这个文法，我们将会构造出如下抽象语法树：

    +
1       +
    2       3

我们发现，这棵树是向右倾斜的，那么，我们在解析这个抽象语法树的时候，就必然是先计算2 + 3，得到5之后 ，再计算1 + 5。所以，这是右结合的（注意，结合性和优先级的区别，优先级指的是，无论什么时候，都是先计算，而结合性指的是一种普遍的计算顺序，从哪边到哪边。顺带一提的是，优先级我们可以通过层级嵌套来实现，把优先级高的放在子级，那么，它必然就先计算了）。但是，一般来说，我们的加法表达式都是左结合的。（也有右结合的例子，例如$a = 1 + 2，先计算1 + 2，然后再计算$a = 3）。所以 ，我们需要调整一下这个抽象语法树的结构，我们打算让这棵树向左倾斜，这样的话，就会先计算左边的子树，然后再计算左边的子树。所以，我们期望的结构如下 ：

        +
    +       3
1       2

这样，我们在遍历这棵树的时候，就会先计算1 + 2，然后再计算3 + 3。这是符合我们的预期的。

那么，为什么文法：

additive -> intLiteral | intLiteral + additive

生成的AST它是右结合的呢？因为我们的非终结符是在右边，终结符在左边，所以，在一棵子树里面，左节点必然是终结符，右子树必然是一棵递归的树，直到右子树碰到终结符，才停止右子树的生成。

所以，如果我们要让一棵树变成左结合的，我们可以调整一下文法，把非终结符放到左边，终结符放到右边。如下：

additive -> intLiteral | additive + intLiteral

当时，我们之前说过了，左递归会造成无限递归。但是，无限循环的前提是，我们使用的是递归下降算法来生成AST。如果我们不用递归下降算法来构造AST，那么我们是可以避免无限递归的。并且，不是所有的算法都不能处理左递归，例如LR算法是可以处理左递归的。

好了，我们现在使用ebnf来改造下这个文法：

additiveExpression -> intLiteral | additiveExpression + intLiteral
->
additiveExpression: intLiteral | intLiteral (+ intLiteral)*

（需要注意的一点事，这里的+不是正则的元符号+的含义，它仅仅是字符串+）

可能这个过程大家会看不懂，我多讲一点推导过程：

additiveExpression: intLiteral | additiveExpression + intLiteral + intLiteral + intLiteral ....
->
因为，“+ intLiteral + intLiteral + intLiteral ....” 这部分必须终止，所以，additiveExpression最后一次推导必然是得到intLiteral，因此，additiveExpression -> intLiteral additiveExpression'：

additiveExpression: intLiteral | intLiteral additiveExpression'

所以，我们现在需要解决的问题就是如何用additiveExpression'去推导“+ intLiteral + intLiteral + intLiteral ....”。通过归纳法，我们可以很轻易的得到如下结果：

additiveExpression': + intLiteral additiveExpression' | ε

其中，ε表示空集。这在递归的时候，作为结束条件。我们发现，这是一个尾递归了，那么，我们就可以想到尾递归的优化，我们可以写成一个循环：
->
additiveExpression: intLiteral | intLiteral (+ intLiteral)*

因此，最终，我们把一个左递归的文法转化成了一个没有左递归的文法。

然后，我们可以轻易的写出这个文法的代码：

protected function additiveUnRecursiveMode()
{
    /** @var AstNode */
    $child1 = $this->scanner->primary();
    $node = $child1;

    while (true) {
        $token = $this->scanner->peekToken();
        if ($token == null) {
            // 没有token了，所以我们需要终止循环
            break;
        }
        if ($token != Token::ADD) {
            throw new TokenException(sprintf('Token [%s] that are not expected, need a [%s].', $token, Token::ADD), Errno::UN_EXPECTED_TOKEN);
        }
        $this->scanner->readToken();
        $child2 = $this->scanner->primary();
        $node = new AstNode(AstNodeType::ADD_NODE, '+');
        $node->addChildNode($child1);
        $node->addChildNode($child2);
        /**
         * 因为我们希望这棵AST是左结合的，所以，我们把生成的子树作为父节点的左子树
         */
        $child1 = $node;
    }

    // 此处的node是AST的根结点
    return $node;
}