0

在龙书的附录中，给出了一个 LL(1) 前端作为例子。我认为这很有帮助。但是，我发现对于下面的上下文无关语法，至少需要一个 LL(2) 解析器。

statement : variable ':=' expression
          | functionCall

functionCall : ID'(' (expression ( ',' expression )*)? ')'
             ;
variable : ID
         | ID'.'variable
         | ID '[' expression ']'
         ;

我如何调整 LL(1) 解析器的词法分析器以支持 k 前瞻标记？有一些优雅的方法吗？

我知道我可以为令牌添加一些缓冲区。我想讨论一些编程的细节。

这是解析器：

class Parser
{
    private Lexer lex;
    private Token look;
    public Parser(Lexer l)
    {
        lex = l;
        move();
    }

    private void move()
    {
        look = lex.scan();
    }
}

并Lexer.scan()从流中返回下一个令牌。

4

1 回答 1

1

实际上，您需要缓冲k前瞻标记以进行LL(k)解析。如果k是 2，那么您只需要扩展您当前的方法，该方法在 中缓冲一个令牌look，使用另一个私有成员look2或类似的成员。对于较大的k，您可以使用环形缓冲区。

在实践中，您并不总是需要完整的前瞻。大多数情况下，一个令牌前瞻就足够了。您应该将代码构建为决策树，只有在必要时才咨询未来的令牌以解决歧义。（提供一种特殊的标记类型“未知”通常很有用，它可以分配给缓冲的标记列表以指示先行尚未达到该点。或者，您可以始终保持k先行标记；对于手工构建解析器，这可以更简单。）

或者，您可以使用回退结构，您只需尝试一个替代方案，如果这不起作用，而不是报告语法错误，而是将解析器和词法分析器的状态恢复到下一个替代方案。在这个模型中，词法分析器将当前输入缓冲区位置作为显式参数，并且输入缓冲区需要是可倒带的。但是，您可以使用前瞻缓冲区来有效地记忆词法分析器功能，这可以避免倒带和重新扫描。（扫描通常足够快，偶尔重新扫描并不重要，因此您可能希望推迟添加代码复杂性，直到您的分析表明它有用。）

两个注意事项：

1）我对规则持怀疑态度：

functionCall : ID'(' (expression ( ',' expression )*)* ')'
             ;

例如，这将允许：

function(a[3], b[2] c[x] d[y], e.foo)

这对我来说看起来不对。通常，您会将 的内容标记()为optional而不是repeatable，例如。使用可选标记?而不是第二个 Kleene 星*：

functionCall : ID'(' (expression ( ',' expression )*)? ')'
             ;

2）在我看来，你真的应该考虑对表达式语言使用自下而上的解析，无论是生成的LR(1)解析器还是手工构建的 Pratt 解析器。LL(1)很少是足够的。当然，如果你使用解析器生成器，你可以使用像 ANTLR 这样的工具来有效地实现LL(∞); 这将为您解决前瞻问题。

于 2014-05-14T14:47:28.997 回答