语法和自上而下的解析

Question

一段时间

以来，我一直在尝试学习LL解析器的工作原理，如果我理解正确，在手动编写自上而下的递归下降解析器时，我应该为每个非终端符号创建一个函数。所以对于这个例子：

S -> AB
A -> aA|ε
B -> bg|dDe
D -> ab|cd

我必须为每个 S、A、B 和 D 创建一个函数，如下所示：

Token B()
{
    if (Lookahead(1) == 'b')
    {
        Eat('b');
        Eat('g');
    }
    else if (Lookahead(1) == 'd')
    {
        Eat('d');
        D();
        Eat('e');
    }
    else
    {
        Error();
    }
    return B_TOKEN;
}

但是，我尝试使用以下语法做同样的事情，我创建的语法来生成与(a|b|c(*正则表达式相同的语言：

S -> Ma
M -> aM|bM|cM|ε

这给了我以下功能：

Token S()
{
    char Ch = Lookahead(1);
    if (Ch == 'a' || Ch == 'b' || Ch == 'c')
    {
        M();
        Eat('a');
    }
    else
    {
        Error();
    }
    return S_TOKEN;
}
Token M()
{
    char Ch = Lookahead(1);
    if (Ch == 'a' || Ch == 'b' || Ch == 'c')
    {
        Eat(ch);
        M();
    }
    return M_TOKEN;
}

这似乎并不好，因为对于输入"bbcaa"，M 将消耗所有内容，之后 S 不会找到最后一个"a"并报告错误，即使语法接受它。感觉 M 错过了ε案例，或者它可能以错误的方式处理，但我不确定如何处理它。有人可以帮忙吗？

Answer 1

自上而下的预测解析器的行为与您在问题中指出的完全一样。换句话说，您的第二种语法不适合自上而下的解析(使用单标记前瞻(。许多语法不是;这包括任何无法根据有限的前瞻性预测使用哪种产品的语法。

在这种情况下，如果您要提前查看两个令牌而不是一个令牌，则可以解决冲突; M应该预测 END 的ε产量，以及第一个代币为 a 的所有其他双代币前瞻的aM产量。