递归下降算法左递归问题

我们在学习编译原理的过程中，一定会学习到递归下降的算法来进行语法分析。

首先，我们需要去理解“下降”的含义。我们可以这么去理解：

上级文法嵌套下级文法，上级的算法调用下级的算法。表现在生成 AST 中，上级算法生成上级节点，下级算法生成下级节点

好的，现在，我们来通过一个计算器的程序来学习一下递归下降算法。

首先，我们有一个问题。我们能否用正则表达式来表达算数表达式？答案是不能。

假设我们想要用正则表达式去表达所有的算数表达式，那么这一定是一个体力活，并且计算能力是有限的。例如，我们可以有如下的算数表达式：

1 + 2
1 + 2 + 3
1 * 2 + 3
1 + 2 * 3
......  等等

那么，我们是没有办法找到一个或者有限个正则表达式来表达所有的算数表达式。

好的，现在，我们尝试着用递归下降算法来解决算数表达式的问题。为了简单讨论，这里，我们只有加法，并且只包含整数。所以，我们有如下的语法：

additive
: int
| additive int
;

意思是，我们的加法表达式可以只是一个整数，也可以是加法表达式加上一个整数。而加法表达式加上一个整数，这个就是我们递归下降算法中“递归”的含义了。但是，上面的程序，是会造成左递归的。

比如说我们要计算这个算数表达式：1 + 2

我们可以来模拟计算过程：

首先匹配是不是整型字面量，发现是，但是后面还有token，所以匹配失败；
然后匹配是不是加法表达式，这里是递归调用；
会重复上面两步，无穷无尽。

所以，左递归是递归下降算法无法处理的（因为左递归的情况下，我们是无法消耗token的，因此造成了无限递归）。但是，我们有如下的解决办法，我们把递归的加法表达式移到右边，那么就有了如下的语法：

additive
: int
| int additive
;

我们可以来模拟计算过程：

首先匹配是不是整型字面量，发现是，但是后面还有token，所以匹配失败；
然后匹配是不是整型字面量，发现是，然后消耗一个加号，然后递归的再次匹配加法表达式；
然后匹配是不是整形字面量，发现是。
匹配完成！

我们发现，这个语法可以解决左递归问题。因为这个方法可以消耗掉一个int token和一个加号 token之后，再递归的执行加法表达式。

我们可以编写如下代码来描述这个过程：

<?php

/**
 * additive
 * : int
 * | additive int
 * ;
 */
define('UNKNOW', 0);
define('INT_NODE', 1);
define('ADD_NODE', 2);

class Node
{
    /**
     * @var array[Node]
     */
    public $children;

    /**
     * @var int
     */
    public $nodeType;

    /**
     * @var int
     */
    public $value;

    public function __construct(int $nodeType = UNKNOW, ?int $value = null)
    {
        $this->nodeType = $nodeType;
        $this->value = $value;
    }

    public function addChildNode(Node $node)
    {
        $this->children[] = $node;
    }
}

function primary(SplQueue $queue): Node {
    /** @var int */
    $token = $queue->dequeue();

    return new Node(INT_NODE, $token);
}

function peekToken(SplQueue $queue) {
    if ($queue->isEmpty()) {
        return null;
    }
    return $queue->bottom();
}

function readToken(SplQueue $queue) {
    return $queue->dequeue();
}

function additive(SplQueue $queue): Node {
    /** @var Node */
    $child1 = primary($queue);
    $node = $child1;
    $token = peekToken($queue);

    if ($child1->nodeType === INT_NODE && $token != null) {
        if ($token == '+') {
            readToken($queue);
            $child2 = additive($queue);
            $node = new Node(ADD_NODE);
            $node->addChildNode($child1);
            $node->addChildNode($child2);
        }
    }
    return $node;
}

$queue = new SplQueue;

$queue->enqueue(1);
$queue->enqueue('+');
$queue->enqueue(2);

$node = additive($queue);

最后，我们将会得到一个ADD_NODE类型的根结点。其中第一个子节点是值为1的Node，第二个节点是值为2的Node。然后，我们对这个AST进行遍历，就可以得到算数表达式的结果了。