语法和自上而下的解析

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)*a 正则表达式相同的语言：

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

top-down 预测解析器的行为与您在问题中指出的完全相同。换句话说，您的第二个语法不适合 top-down 解析（使用 one-token 前瞻）。许多语法不是；其中包括无法根据有限前瞻预测使用哪个产生式的任何语法。

在这种情况下，如果您要向前看两个标记而不是一个标记，则可以解决冲突； M 应该预测前瞻 aEND 的 ε 生产，以及所有其他产品的 aM 生产two-token 前瞻，其中第一个标记是 a.

语法和自上而下的解析

Grammar and top down parsing

grammar

parsing

topdown