2

一段时间以来，我一直在尝试学习 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 缺少了 ε 的情况，或者处理方式不对，但我不知道如何处理。有人可以帮忙吗？

4

1 回答 1

2

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

在这种情况下，如果您要前瞻两个令牌而不是一个，则可以解决冲突；M应该预测ε前瞻aEND的生产，以及aM第一个令牌所在的所有其他双令牌前瞻的生产a。

于 2017-02-10T20:38:15.033 回答