下列简单的"计算器表达式"语法(BNF)可以使用简单的递归下降解析器轻松地解析，该解析器是预测LL(1)：

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

因为查看下一个标记就足够了，以便知道要选择的规则。但是，假设我添加了以下规则：

<command>   :=  <expr>
            |   <id> = <expr>

为了与命令行上的计算器进行交互，并使用变量，如下所示：

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

我不能使用简单的LL(1)预测解析器来解析<command>规则吗？我试图为此编写解析器，但似乎我需要进一步了解更多令牌。是使用回溯的解决方案，还是我可以只实现LL(2)并始终向前看两个标记？

RD解析器生成器如何处理此问题(例如，ANTLR)？

解决方案

问题在于语法：

<command>   :=  <expr>
            |   <id> = <expr>

不是一个相互递归的过程。对于递归体面的解析器，我们将需要确定一个非递归等效项。

rdentato post的文章展示了如何解决此问题，假设我们可以使用语法。此PowerPoint更详细地阐明了问题，并显示了解决方法：
http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2Fxml.cs.nccu.edu.tw%2Fcourses%2Fcompiler%2Fcp2006%2Fslides%2Flec3-解析％ 26TopDownParsing.ppt＆ei = -YLaSPrWGaPwhAK5ydCqBQ＆usg = AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q＆sig2 = nlYKQVfakmqy_57137XzrQ

问题

<command>   :=  <expr>
            |   <id> = <expr>

就是当我们"看到"<id>时，我们无法分辨它是分配的开始(第二条规则)还是"`<factor>"。我们只会知道何时读取下一个令牌。

AFAIK ANTLR是LL(*)(并且如果我没有记错的话，还能够生成rat-pack解析器)，因此考虑到两个令牌，它很可能会处理这种麻烦。

如果我们可以使用该语法，建议我们为该作业添加一个关键字(例如let x = 8)：

<command>   :=  <expr>
            |   "let" <id> "=" <expr>

或者使用=表示评估：

<command>   :=  "=" <expr>
            |   <id> "=" <expr>

ANTLR 3使用的是" LL(*)"解析器，而不是LL(k)解析器，因此，如果需要使用经过特别优化的确定性有限自动机( DFA)。

我认为有两种方法可以使用递归下降解析器解决此问题：通过使用(更多)超前或者回溯。

展望

command() {
    if (currentToken() == id && lookaheadToken() == '=') {
        return assignment();
    } else {
        return expr();
    }
}

回溯

command() {
    savedLocation = scanLocation();
    if (accept( id )) {
         identifier = acceptedTokenValue();
         if (!accept( '=' )) {
             setScanLocation( savedLocation );
             return expr();
         }
         return new assignment( identifier, expr() );
    } else {
         return expr();
    }
}