antlr3 премахва дървовиден възел с поддърво

Опитвам се да направя трансформация от дърво към дърво с antlr3.4

Става въпрос (за този въпрос) за булеви изрази, когато "И" и "ИЛИ" са разрешени да се свързват с n израза. Етапът на анализатора създава нещо подобно

 (OR 
   (AND (expr1) (expr2) (expr3) 
     (OR (AND (expr4))
         (AND (expr5))
         (AND (expr6))
     )
   )
 )

За съжаление има AST възли за "И" и "ИЛИ", които се свързват само с един израз. (Което е безполезно, но хей - правилата andExpr и orExpr се извикват)

Опитах се да ги изгоня (което означава, да ги заменя с техните подвъзли), но не успях да го направя в дървовидна граматика. (BTW: Използването на обхождане/модификация на първо дърво в дълбочина в чиста Java работи, но това не е моето намерение)

Опитах се да използвам предикати, но изглежда не мога да го разбера правилно.

Това е граматиката за анализиране на потока непроменен

 start  :  
   orExpr^   EOF!  
   ;

 orExpr       :  
   ^(OR  r+=andExpr+ )   -> ^(OR $r)
   ;

 andExpr  : 
   ^(AND unaryExpr+ )
   ; 

 notExpr:
   ^( NOT unaryExpr)    
   ;

 unaryExpr : 
   .+  // it gets more complicated below this
   ;

Опитах предикат, за да хвана случая с един подвъзел, но не успях да предам непроменен случай n>1

 orExpr @init { int N = 0; }
   :  
   ( ^(OR  (r+=andExpr {N++;})+ )  {N==1}? -> $r) 
   ;

Някакви идеи как да го направя правилно?

редактиране: Приложена е граматиката на анализатора, която е почти същата...

 start 
   :  '('! orExpr^  ')'! EOF!        ;
 orExpr
   : a+=andExpr (  OR_T a+=andExpr )*  -> ^(OR  $a+ )  // 'AND' and 'OR' are multivalent
   ;

 andExpr
   : u+=unaryExpr ( AND_T u+=unaryExpr )* -> ^(AND $u+ )
   ; 

 notExpr
   : NOT_T unaryExpr -> ^( NOT unaryExpr)   
   ;

 unaryExpr
   : '('!  orExpr ')'! // -> ^( BRACE orExpr), brace not needed in the ast (but needed for propper parsing)
   |   notExpr
   |   internal^  // internal is very complex in itself
   ;

antlr transform tree antlr3 subtree
person user1753575    schedule 17.10.2012    source източник
comment
Коригирането на това в дървоходеца (IMHO) не е правилното място: решете го на ниво анализатор. Можете ли да публикувате граматическите си правила на анализатора? Може би аз или някой друг може да предложи начин за анализатора да създаде правилния AST от самото начало.   -  person Bart Kiers    schedule 17.10.2012
comment
граматиката на анализатора е горе-долу същата:   -  person user1753575    schedule 18.10.2012

Отговори (1)


arrow_upward
1
arrow_downward

Можете да направите това директно в анализатора. Трябва да създадете още няколко правила за анализатор, за да не объркате ANTLR в правилата за пренаписване (вижте вградените коментари):

grammar T;

options {
  output=AST;
  ASTLabelType=CommonTree;
}

start 
 : orExpr EOF! {System.out.println($orExpr.tree.toStringTree());}
 ;

orExpr
 : (andExpr2 -> andExpr2) ((OR andExpr)+ -> ^(OR andExpr2 andExpr+))?
 ;

// You can't use `andExpr` directly in the `orExpr` rule otherwise the rewrite
// rule `-> ^(OR ... )` gets confused.
andExpr2 : andExpr;

andExpr
 : (notExpr2 -> notExpr2) ((AND notExpr)+ -> ^(AND notExpr2 notExpr+))?
 ; 

notExpr2 : notExpr;

notExpr
 : NOT^ notExpr
 | atom  
 ;

atom
 : '(' orExpr ')' -> orExpr
 | ID
 ;

OR    : '||';
AND   : '&&';
NOT   : '!';
ID    : 'a'..'z'+;
SPACE : ' ' {skip();};

Анализът на вход като "a && b && c || d || f || g" ще произведе следния AST:

въведете описание на изображението тук

РЕДАКТИРАНЕ

Тогава граматиката на дървото ще изглежда така:

tree grammar TWalker;

options {
  tokenVocab=T;
  ASTLabelType=CommonTree;
}

start 
 : expr
 ;

expr
 : ^(OR expr+)
 | ^(AND expr+)
 | ^(NOT expr)
 | ID
 ;
person Bart Kiers    schedule 18.10.2012
comment
Здравей Барт, аз също опитах нещо подобно, но подсказката с andExpr2 : andExpr; липсваше. Не е много очевидно. Както и да е, сега работи. Благодаря много за помощта. Сега ще се задълбоча в трансформациите на граматиката на дървото. Изглежда, че трябва да повторя по-голямата част от граматиката на анализатора в дървовидната граматика. Между другото: има ли прост и удобен начин за повторна обработка на изхода на .toStringTree(), защото трябва да съхраня ast за по-късна употреба в aSQL DB и .toStringTree() изглежда сладко. - person user1753575; 19.10.2012
comment
@user1753575, дървоходецът може да изглежда като граматиката на анализатора, но в повечето случаи може да бъде компактен доста, вижте моето РЕДАКТИРАНЕ. Относно toStringTree(), на твое място бих създал нов въпрос за това: ще погледна по-късно (@work now). - person Bart Kiers; 19.10.2012