ANTLR: Comment puis-je produire un arbre avec plus de 2 enfants?

Compte tenu de la grammaire,ANTLR: Comment puis-je produire un arbre avec plus de 2 enfants?

parse : expr EOF -> ^(ROOT expr); 
expr : atom ('|'^ atom)*; 
atom : LITERAL | ('('! expr ')'!); 

LITERAL : 'a'..'z'; 
WS  : (' '|'\t'|'\r'|'\n'){Skip();};

et entrée,

a|b|c

Je reçois un arbre qui ressemble,

http://graph.gafol.net/pic/dsqoQhzgs.png

Alors que je voudrais un arbre qui ressemble ,

http://graph.gafol.net/pic/dsrGWVUfz.png

Comment pourrais-je exprimer cela dans la grammaire?

Source

2010-12-09 mpen

C'est un peu difficile. Vous pourrait le faire en utilisant un syntactic predicate(LOOK-AHEAD-TOKENS-HERE)=> avant correspondant à un « OU chaîne »:

expr 
    : (atom '|')=> atom ('|' atom)+ -> ^('|' atom+) 
    | atom 
    ;

qui gère correctement a|b|c, a|b et a. Mais vous voudrez peut-être expliquer la langue que vous essayez d'analyser: il pourrait y avoir de meilleurs moyens (plus élégants?) De l'exprimer. Pourquoi ne voudriez-vous pas avoir un AST comme dans votre premier diagramme? L'évaluation des expressions est facile quand la racine (opérande) n'a que deux enfants, n'est-ce pas?

Source

2010-12-09 22:15:50

Ne pouvez-vous pas le faire sans un look-ahead si vous changez le '*' en '+'? Je suis en train d'analyser les expressions régulières. Je pense qu'il sera plus facile d'avoir toutes les alternatives en tant que frères et sœurs parce que je veux en choisir un au hasard. S'ils sont imbriqués dans un arbre binaire comme dans le premier AST, 'c' aurait 50% de chance d'être choisi, et les 2 autres auraient 25%, alors que je veux qu'il soit de 33% chacun ... à moins l'utilisateur utilise des crochets. – mpen

Désolé, le '*' devait être un '+' (a édité ma réponse). Mais non, il y a toujours une décision non-LL (*) dans cette règle. Essayez-le, si vous ne l'avez pas déjà fait. –

Je suis entièrement d'accord avec le dernier paragraphe de Bart. Le premier AST a tout son sens et ce que vous voulez en faire ne l'est pas. Cela le rend également plus difficile à comprendre. – phillip

parse : expr EOF -> ^(ROOT expr); 
expr : atom ('|'^ atom)* -> atom+; 
atom : LITERAL | ('('! expr ')'!); 

LITERAL : 'a'..'z'; 
WS  : (' '|'\t'|'\r'|'\n'){Skip();};

Je pense que cela va le faire en ajoutant une règle de réécriture, mais je n'ai pas antlrworks en ce moment, donc je ne peux pas être sûr. Mais c'est proche alors donnez-lui un coup de feu et modifiez la syntaxe de réécriture si nécessaire.

Source

2010-12-09 21:51:10 phillip

Cela ne fonctionnera pas: vous ne pouvez pas mélanger '^' et '->' dans une règle. Et si vous supprimez le '^' de 'expr', il ne parvient pas à analyser correctement les' LITERAL' simples. Essayez-le. –

Bummer ... Je viens de trouver quelque chose de similaire, 'atom ('|' atom) * ->^('|' atom +);' fonctionne bien quand il y a un | | 'mais sinon il échoue comme Bart l'a dit. – mpen

ANTLR: Comment puis-je produire un arbre avec plus de 2 enfants?

Répondre

Questions connexes