Приоритеты правил Antlr - PullRequest
Новая
       8

Приоритеты правил Antlr

7 голосов
/ 04 февраля 2011

Во-первых, я знаю, что эта грамматика не имеет смысла, но она была создана для проверки поведения приоритета правила 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 появляется перед second_rule в rule_order_list, который является начальной точкой.Кто-нибудь может объяснить, почему это происходит?

Приветствия

1 Ответ

16 голосов
/ 04 февраля 2011

Прежде всего, лексер ANTLR будет токенизировать ввод сверху вниз.Таким образом, токены, определенные первыми, имеют более высокий приоритет, чем те, которые находятся под ним.А в случае, если у правила есть перекрывающиеся токены, правило, которое соответствует большинству символов, будет иметь приоритет (жадное совпадение).

Тот же принцип действует в правилах синтаксического анализатора.Правила, определенные первыми, также будут сопоставляться первыми.Например, в правиле foo сначала будет проверено подправило a до b: 

foo
  :  a
  |  b
  ;

Обратите внимание, что в вашем случае правило 2 nd нене соответствует, но пытается это сделать и завершается неудачей, потому что нет завершающего разрыва строки, что приводит к ошибке: 

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 в опциях {...} section) будет выглядеть следующим образом: 

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
     )+ 
  ;

, оба будут давать ожидаемый результат.

Итак, я думаю,что вы, возможно, нашли ошибку.

Yout может попробовать список рассылки ANTLR, если вы хотите получить точный ответ (Теренс Парр часто бывает там чаще, чем он здесь).

Удачи!

PS.Я проверил это с ANTLR v3.2

...