递归下降解析 - 从LL(1)向上

下面简单的"计算器表达式"语法(BNF)可以使用一个简单的递归下降解析器轻松解析,这是一个预测LL(1):

      :=   + 
            |    - 
            |   
      :=   * 
                 / 
                
    :=  
            |   
            |   (  )
    :=  \d+
        :=  [a-zA-Z_]\w+

因为总是足以看到下一个令牌以便知道要选择的规则.但是,假设我添加以下规则:

   :=  
            |    = 

为了在命令行上与计算器交互,使用变量,如下所示:

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

我不能使用简单的LL(1)预测解析器来解析规则吗？我试着为它编写解析器,但似乎我需要知道更多的令牌.是使用回溯的解决方案,还是我可以实现LL(2)并始终向前看两个令牌？

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

这个问题

   :=  
            |    = 

就是当你"看到"时,你无法判断它是否是一个分配的开始(第二条规则),或者它是一个" ".您只会知道何时阅读下一个令牌.

AFAIK ANTLR是LL(*)(并且如果我没有记错的话也可以生成rat-pack解析器),所以考虑到两个令牌,它可能会处理这个语法.

如果您可以使用语法我建议为分配添加关键字(例如let x = 8):

   :=  
            |   "let"  "=" 

或=用来表示评价:

   :=  "=" 
            |    "=" 

我认为使用递归下降解析器有两种方法可以解决这个问题:使用(更多)前瞻或回溯.

展望

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();
    }
}