Antlr规则优先级

Question

首先我知道这个语法没有意义但是它是为了测试ANTLR规则优先级行为而创建的

grammar test;

options 
{

output=AST;
backtrack=true;
memoize=true;

}

rule_list_in_order :
    (
    first_rule
    | second_rule
    | any_left_over_tokens)+
    ;


first_rule
    :
     FIRST_TOKEN
    ;


second_rule:     
    FIRST_TOKEN NEW_LINE SECOND_TOKEN NEW_LINE;


any_left_over_tokens
    :
    NEW_LINE
    | FIRST_TOKEN
    | SECOND_TOKEN;



FIRST_TOKEN
    : 'First token here'
    ;   

SECOND_TOKEN
    : 'Second token here';

NEW_LINE
    : ('\r'?'\n')   ;

WS  : (' '|'\t'|'\u000C')
    {$channel=HIDDEN;}
    ;

当我给这个语法输入'第一个令牌在这里\n第二个令牌在这里'时,它匹配second_rule.

我原以为它匹配第一个规则然后是any_left_over_tokens,因为first_rule出现在rule_order_list中作为起点的second_rule之前.谁能解释为什么会这样？

干杯

Answer 1

首先,ANTLR的词法分析器将从上到下标记输入.因此,首先定义的令牌优先于其下面的令牌.如果规则具有重叠的标记,则匹配大多数字符的规则将优先(贪婪匹配).

解析器规则中也存在相同的原则.首先定义的规则也将首先匹配.例如,在规则中foo,a将首先尝试子规则b:

foo
  :  a
  |  b
  ;

请注意,在您的情况下,^第二个规则不匹配,但尝试这样做,并失败,因为没有尾随换行符,产生错误:

line 0:-1 mismatched input '<EOF>' expecting NEW_LINE

所以,什么都没有匹配.但是,这是奇数.因为你已经设置了backtrack=true,它至少应该回溯并匹配:

1. first_rule ("这里的第一个标记")
2. any_left_over_tokens ("越线")
3. any_left_over_tokens ("这里的第二个标记")

如果不是first_rule首先匹配,甚至没有尝试匹配second_rule开始.

一个快速演示手工做谓语时(和禁用backtrack的选项{...}部分)将如下所示:

grammar T;

options {
  output=AST;
  //backtrack=true;
  memoize=true;
}

rule_list_in_order
  :  ( (first_rule)=>  first_rule  {System.out.println("first_rule=[" + $first_rule.text + "]");}
     | (second_rule)=> second_rule {System.out.println("second_rule=[" + $second_rule.text + "]");}
     | any_left_over_tokens        {System.out.println("any_left_over_tokens=[" + $any_left_over_tokens.text + "]");}
     )+ 
  ;

first_rule
  :  FIRST_TOKEN
  ;

second_rule
  :  FIRST_TOKEN NEW_LINE SECOND_TOKEN NEW_LINE
  ;

any_left_over_tokens
  :  NEW_LINE
  |  FIRST_TOKEN
  |  SECOND_TOKEN
  ;

FIRST_TOKEN  : 'First token here';   
SECOND_TOKEN : 'Second token here';
NEW_LINE     : ('\r'?'\n');
WS           : (' '|'\t'|'\u000C') {$channel=HIDDEN;};

可以用班级测试:

import org.antlr.runtime.*;

public class Main {
    public static void main(String[] args) throws Exception {
        String source = "First token here\nSecond token here";
        ANTLRStringStream in = new ANTLRStringStream(source);
        TLexer lexer = new TLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        TParser parser = new TParser(tokens);
        parser.rule_list_in_order();
    }
}

产生预期的输出:

first_rule=[First token here]
any_left_over_tokens=[
]
any_left_over_tokens=[Second token here]

请注意,使用以下内容无关紧要:

rule_list_in_order
  :  ( (first_rule)=>  first_rule 
     | (second_rule)=> second_rule
     | any_left_over_tokens
     )+ 
  ;

要么

rule_list_in_order
  :  ( (second_rule)=> second_rule // <--+--- swapped
     | (first_rule)=>  first_rule  // <-/
     | any_left_over_tokens
     )+ 
  ;

,两者都会产生预期的产量.

所以,我的猜测是你可能发现了一个bug.

Yout可以尝试ANTLR邮件列表,如果你想要一个明确的答案(Terence Parr经常在那里经常出现在这里).

祝好运!

PS.我用ANTLR v3.2测试了这个