ANTLR грамматика с неоднозначными альтернативами - PullRequest
Новая
       4

ANTLR грамматика с неоднозначными альтернативами

1 голос
/ 28 октября 2011

Моя грамматика дает неожиданный результат. Я не уверен, является ли это просто моей ошибкой или некоторыми проблемами с логикой обработки неоднозначных альтернатив ANTLR.

Вот моя грамматика: 

    grammar PPMacro;
options {
  language=Java;
  backtrack=true;

}

file: (inputLines)+ EOF;

inputLines 
:  ( preprocessorLineSet  |  oneNormalInputLine )  ; 

oneNormalInputLine  @after{System.out.print("["+$text+"]");}  
: (any_token_except_crlf)* CRLF ;

preprocessorLineSet 
: ifPart endifLine;

ifPart: ifLine  inputLines*   ;
ifLine  @after{System.out.print("{"+$text+"}" );} 
:  '#' IF (any_token_except_crlf)* CRLF ;

endifLine @after{System.out.print("{"+$text+"}" );} 
:  '#' ENDIF (any_token_except_crlf)* CRLF ;

any_token_except_crlf: (ANY_ID | WS | '#'|IF|ENDIF);
// just matches everything

CRLF: '\r'?  '\n'  ;
WS: (' '|'\t'|'\f' )+;
Hash: '#'  ;
IF     : 'if'    ;
ENDIF  : 'endif' ;
ANY_ID: ( 'a'..'z'|'A'..'Z'|'0'..'9'| '_')+ ;

Объяснение

Он предназначен для разбора блока C ++ #if ... #endif

Я пытаюсь распознать вложенный блок #if #endif. Это делается моим препроцессором LineSet . Он содержит рекурсивное определение для поддержки вложенного блока. oneNormalInputLine предназначен для обработки чего-либо, кроме формы #if. Это правило соответствует правилу соответствия чему-либо и фактически соответствует строке #if. Но я намеренно поместил его после препроцессораLineSet в inputLines . Я ожидаю, что этот порядок может помешать совпадению строк #if или #endif. Причина использования правила перехвата заключается в том, что я хочу, чтобы правило принимало любой другой синтаксис c ++ и просто возвращало их в вывод.

Я мой тест, я просто распечатываю все. Строки, совпадающие с preprocessorLineSet , должны быть окружены {}, а строки, соответствующие oneNormalInputLine , должны быть окружены [].

Пример ввода : 

#if s
s
#if a
s 
s
#endif
#endif

и это 

#if
abc
#endif

Соответствующие выходы: 

[#if s
][s
][#if a
][s
][s
][#endif
][#endif
]

и это 

[#if
][abc
][#endif
]

Проблема

Все выходные строки, включая #if #endif, окружены [], что означает, что они совпадают ТОЛЬКО с oneNormalInputLine ! Но я не ожидаю этого. preprocessorLineSet должен соответствовать строкам #if. Почему я получил этот результат?

Эта строка содержит неоднозначные альтернативы: 

inputLines  :  ( preprocessorLineSet  |  oneNormalInputLine );

, поскольку оба могут соответствовать #if и #endif. Но я ожидаю, что следует использовать первую альтернативу, а не более позднюю. Также обратите внимание, что функция возврата включена.

EDIT Причина, по которой мое правило oneNormalInputLine принимает все, заключается в том, что трудно выразить что-то, не имеющее определенного шаблона, поскольку шаблон #if может быть довольно сложным: 

/***

comments

*/   # /***
comments
*/ if

является допустимым шаблоном. Написание правила, не имеющего этого шаблона, кажется трудным.

Ответы [ 2 ]

1 голос
/ 28 октября 2011

Ваш any_token_except_crlf вызывает двусмысленность. Вам нужно исправить это (и удалить backtrack=true;), разрешив этому правилу соответствовать следующему:

  • космические символы;
  • a '#', за которым следует что-либо кроме 'if', 'endif' и разрывы строк;
  • любой символ, кроме '#' и разрывов строк, за которыми следует 'if' или 'endif'
  • идентификатор.

Небольшой рабочий пример (я назвал правила немного по-другому ...): 

grammar PPMacro;

options {
  output=AST;
}

tokens {
  FILE;
}

file
  :  line+ EOF -> ^(FILE line+)
  ;

line
  :  if_stat
  |  normal_line
  ;

if_stat
  :  HASH IF normal_line line* HASH ENDIF -> ^(IF normal_line line*)
  ;

normal_line
  :  non_special* CRLF -> non_special*
  ;

non_special
  :  WS
  |  HASH ~(IF | ENDIF | CRLF)
  |  ~(HASH | CRLF) (IF | ENDIF)
  |  ID
  ;

CRLF  : '\r'?  '\n'  ;
WS    : (' ' | '\t' | '\f')+;
HASH  : '#'  ;
IF    : 'if'    ;
ENDIF : 'endif' ;
ID    : ( 'a'..'z'|'A'..'Z'|'0'..'9'| '_')+ ;

Это можно проверить с помощью класса: 

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    PPMacroLexer lexer = new PPMacroLexer(new ANTLRFileStream("test.cpp"));
    PPMacroParser parser = new PPMacroParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.file().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

и файл test.cpp, который может выглядеть следующим образом: 

a b
#if s
t
#if a
u 
v
#endif
#endif
c
d

, который будет производить следующее AST:

enter image description here

EDIT

Я только что увидел, что вы хотите учесть многострочные комментарии и пробелы между # и if (и endif). Вы могли бы справиться с такой вещью лучше всего в лексере, как это: 

grammar PPMacro;

options {
  output=AST;
}

tokens {
  FILE;
  ENDIF;
}

file
  :  line+ EOF -> ^(FILE line+)
  ;

line
  :  if_stat
  |  normal_line
  ;

if_stat
  :  IF normal_line line* ENDIF -> ^(IF normal_line line*)
  ;

normal_line
  :  non_special* CRLF -> non_special*
  ;

non_special
  :  WS
  |  ID
  ;

IF      : '#' NOISE* ('if' | 'endif' {$type=ENDIF;});
CRLF    : '\r'?  '\n';
WS      : (' ' | '\t' | '\f')+;
ID      : ('a'..'z' | 'A'..'Z' | '0'..'9' | '_')+;
COMMENT : '/*' .* '*/' {skip();};

fragment NOISE
  :  '/*' .* '*/'
  |  WS
  ;

fragment ENDIF : ;

, который будет анализировать следующий ввод: 

a b
# /* 
comment 
*/ if s
t
#    if a
u 
v
#      /*
another 
comment */  endif
#endif
c
d

почти в том же AST, как я писал выше.

1 голос
/ 28 октября 2011

Ваш подход не очень надежен - я бы посоветовал вам сделать его простым и использовать действующее правило языка, которое гласит, что каждая строка, начинающаяся с #, является директивой препроцессора, а та, которая не начинаетсяс # нет.Не было бы никакой двусмысленности в грамматике, использующей это правило, и было бы намного проще понять.

Теперь, почему ваша грамматика не работает?Проблема в том, что ваше preprocesstoLineSet правило не может сопоставить что-либо. 

preprocessorLineSet 
: ifPart endifLine;

ifPart: ifLine  inputLines*   ;

Оно начинается с #if ..., затем должно соответствовать другим строкам и, как первое совпадение #endif приходит, должно соответствовать и заканчиваться.Однако на самом деле это не так.inputLines может соответствовать практически любой строке (в значительной степени - она ​​не будет соответствовать, например, операторам C ++ и другим неидентификаторам), включая все директивы препроцессора.Это означает, что правило ifPart будет соответствовать концу ввода, и endifLine не останется.Обратите внимание, что обратное отслеживание не влияет на это, потому что, как только ANTLR соответствует правилу (в данном случае ifPart, которое будет успешным для всей остальной части ввода, поскольку * является жадным), оно никогда не будет возвращаться к нему.Правила ANTLR для отслеживания возврата волосатые ...

Обратите внимание, что если вы сделаете oneNormalLine не , совпадающими с директивами препроцессора (например, это будет что-то вроде (nonHash any*| ) CRLF, оно начнет работать.

...