antlr3 удалить узел дерева с поддеревом

Я пытаюсь преобразовать дерево в дерево с помощью antlr3.4.

Речь идет (для этого вопроса) о логических выражениях, где «И» и «ИЛИ» разрешено связывать с n выражениями. Этап парсера создает что-то вроде этого

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

К сожалению, есть узлы AST для «И» и «ИЛИ», которые связываются только с одним выражением. (Что бесполезно, но эй - вызываются правила andExpr и orExpr)

Я пытался выгнать их (имеется в виду, заменить их их подузлами), но не смог этого сделать в грамматике дерева. (Кстати: использование обхода/модификации дерева в глубину в чистой 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) 
   ;

Любые идеи, как сделать это правильно?

edit: Прилагается грамматика парсера, которая почти такая же...

 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
Исправление этого в обходчике дерева (ИМХО) неуместно: решите это на уровне парсера. Можете ли вы опубликовать свои правила грамматики парсера? Возможно, я или кто-то другой подскажет, как синтаксический анализатор создать правильный 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; скучал. Это не очень очевидно. Во всяком случае сейчас работает. Большое спасибо за помощь. Теперь я углублюсь в преобразование грамматики дерева. По-видимому, мне приходится повторять большую часть грамматики парсера в грамматике дерева. Кстати: есть ли простой и удобный способ повторного анализа lisp-ish вывода .toStringTree(), потому что мне нужно сохранить ast для последующего использования в базе данных SQL, а .toStringTree() выглядит мило. - person user1753575; 19.10.2012
comment
@user1753575 user1753575, обходчик дерева может выглядеть как грамматика синтаксического анализатора, но в большинстве случаев его можно сжать, см. мой EDIT. Что касается toStringTree(), я бы создал для этого новый вопрос на вашем месте: я посмотрю позже (@work now). - person Bart Kiers; 19.10.2012