Génération d'arbres d'analyse avec une tasse Java
https://stackoverflow.com/questions/6033303
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'utilise une tasse avec JFLEX pour valider la syntaxe d'expression. J'ai la fonctionnalité de base qui fonctionne: je peux dire si une expression est valide ou non.
La prochaine étape consiste à implémenter des opérations arithmétiques simples, telles que "Ajouter 1". Par exemple, si mon expression est "1 + a", le résultat doit être "2 + a". J'ai besoin d'accéder à l'analyse de l'analyse pour le faire, car l'identification simplement d'un terme numérique ne le fera pas: le résultat de l'ajout de 1 à "(1 + a) * b" devrait être "(1 + a) * b + 1" , pas "(2 + a) * b".
Quelqu'un a-t-il un exemple de tasse qui génère un arbre d'analyse? Je pense que je pourrai le prendre à partir de là.
En prime, y a-t-il un moyen d'obtenir une liste de tous les jetons en expression à l'aide de JFLEX? Cela semble être un cas d'utilisation typique, mais je ne peux pas comprendre comment le faire.
Éditer: J'ai trouvé un indice prometteur sur le débordement de la pile:Créer un problème d'arbre abstrait de l'analyseur
Discussion de la Coupe et de l'AST:
http://pages.cs.wisc.edu/~fischer/cs536.s08/lectures/lecture16.4up.pdf
Plus précisément, ce paragraphe:
Le symbole renvoyé par l'analyseur est associé au symbole de démarrage de la grammaire et contient l'AST pour l'ensemble du programme source
Cela n'aide pas. Comment traverser l'arbre donné Symbole Par exemple, si la classe de symboles n'a pas de pointeurs de navigation vers ses enfants? En d'autres termes, il ne ressemble ni ne se comporte comme un nœud d'arbre:
package java_cup.runtime;
/**
* Defines the Symbol class, which is used to represent all terminals
* and nonterminals while parsing. The lexer should pass CUP Symbols
* and CUP returns a Symbol.
*
* @version last updated: 7/3/96
* @author Frank Flannery
*/
/* ****************************************************************
Class Symbol
what the parser expects to receive from the lexer.
the token is identified as follows:
sym: the symbol type
parse_state: the parse state.
value: is the lexical value of type Object
left : is the left position in the original input file
right: is the right position in the original input file
******************************************************************/
public class Symbol {
/*******************************
Constructor for l,r values
*******************************/
public Symbol(int id, int l, int r, Object o) {
this(id);
left = l;
right = r;
value = o;
}
/*******************************
Constructor for no l,r values
********************************/
public Symbol(int id, Object o) {
this(id, -1, -1, o);
}
/*****************************
Constructor for no value
***************************/
public Symbol(int id, int l, int r) {
this(id, l, r, null);
}
/***********************************
Constructor for no value or l,r
***********************************/
public Symbol(int sym_num) {
this(sym_num, -1);
left = -1;
right = -1;
value = null;
}
/***********************************
Constructor to give a start state
***********************************/
Symbol(int sym_num, int state)
{
sym = sym_num;
parse_state = state;
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The symbol number of the terminal or non terminal being represented */
public int sym;
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
/** The parse state to be recorded on the parse stack with this symbol.
* This field is for the convenience of the parser and shouldn't be
* modified except by the parser.
*/
public int parse_state;
/** This allows us to catch some errors caused by scanners recycling
* symbols. For the use of the parser only. [CSA, 23-Jul-1999] */
boolean used_by_parser = false;
/*******************************
The data passed to parser
*******************************/
public int left, right;
public Object value;
/*****************************
Printing this token out. (Override for pretty-print).
****************************/
public String toString() { return "#"+sym; }
}
La solution
OK j'ai compris. Mais malheureusement, je ne peux pas publier tout mon code ici. J'essaierai de définir la solution de toute façon, et veuillez poser des questions si quelque chose n'est pas clair.
JFLEX utilise le sien Symbol classer. Regardez ici: jflex.jar / java_cup.runtime / symbol.class
Vous verrez quelques constructeurs ajoutés:
public Symbol(int id, Symbol left, Symbol right, Object o){
this(id,left.left,right.right,o);
}
public Symbol(int id, Symbol left, Symbol right){
this(id,left.left,right.right);
}
La clé ici est Object o, qui est la valeur du symbole.
Définissez votre propre classe pour représenter un nœud arborescence AST, et un autre pour représenter Lexer Token. Certes, vous pouvez utiliser la même classe, mais j'ai trouvé plus clair d'utiliser différentes classes pour distinguer les deux. JFLEX et CUP généreront du code Java, et il est facile de mettre vos jetons et les nœuds mélangés.
Ensuite, dans votre parser.flex, dans les sections de règles lexicales, vous voulez faire quelque chose comme ça pour chaque jeton:
{float_lit} { return symbol(sym.NUMBER, createToken(yytext(), yycolumn)); }
Faites cela pour tous vos jetons. Votre CreateToken pourrait être quelque chose comme ceci:
%{
private LexerToken createToken(String val, int start) {
LexerToken tk = new LexerToken(val, start);
addToken(tk);
return tk;
}
}%
Passons maintenant à Parser.Cup. Déclarez tous vos terminaux de type LexerToken, et tous vos non-terminaux pour être de type Node. Vous voulez lire le manuel de la Coupe, mais pour un rafraîchissement rapide, un terminal serait tout ce qui serait reconnu par le lexer (par exemple, les nombres, les variables, les opérateurs), et non terminal ferait partie de votre grammaire (par exemple, expression, facteur, terme ... ).
Enfin, tout cela se réunit dans la définition de la grammaire. Considérez l'exemple suivant:
factor ::= factor:f TIMES:times term:t
{: RESULT = new Node(times.val, f, t, times.start); :}
|
factor:f DIVIDE:div term:t
{: RESULT = new Node(div.val, f, t, div.start); :}
|
term:t
{: RESULT = t; :}
;
Syntaxe factor:f signifie que vous alias la valeur du facteur à être f, et vous pouvez vous y référer dans la section suivante {: ... :}. N'oubliez pas que nos terminaux ont des valeurs de type LexerToken, et nos non-terminaux ont des valeurs qui sont Nodes.
Votre terme d'expression peut avoir la définition suivante:
term ::= LPAREN expr:e RPAREN
{: RESULT = new Node(e.val, e.start); :}
|
NUMBER:n
{: RESULT = new Node(n.val, n.start); :}
;
Lorsque vous générez avec succès le code de l'analyseur, vous verrez dans votre analyser.java La partie où la relation parent-enfant entre les nœuds est établie:
case 16: // term ::= UFUN LPAREN expr RPAREN
{
Node RESULT =null;
int ufleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).left;
int ufright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).right;
LexerToken uf = (LexerToken)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-3)).value;
int eleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).left;
int eright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).right;
Node e = (Node)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-1)).value;
RESULT = new Node(uf.val, e, null, uf.start);
CUP$parser$result = parser.getSymbolFactory().newSymbol("term",0, ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)), ((java_cup.runtime.Symbol)CUP$parser$stack.peek()), RESULT);
}
return CUP$parser$result;
Je suis désolé de ne pas pouvoir publier un exemple complet de code, mais j'espère que cela permettra à quelqu'un de quelques heures d'essais et d'erreurs. Ne pas avoir de code complet est également bon car il ne rendra pas toutes ces affectations de devoirs CS inutiles.
Comme preuve de vie, voici une assez importante de mon échantillon AST.
Expression d'entrée:
T21 + 1A / log(max(F1004036, min(a1, a2))) * MIN(1B, 434) -LOG(xyz) - -3.5+10 -.1 + .3 * (1)
AST résultant:
|--[+]
|--[-]
| |--[+]
| | |--[-]
| | | |--[-]
| | | | |--[+]
| | | | | |--[T21]
| | | | | |--[*]
| | | | | |--[/]
| | | | | | |--[1A]
| | | | | | |--[LOG]
| | | | | | |--[MAX]
| | | | | | |--[F1004036]
| | | | | | |--[MIN]
| | | | | | |--[A1]
| | | | | | |--[A2]
| | | | | |--[MIN]
| | | | | |--[1B]
| | | | | |--[434]
| | | | |--[LOG]
| | | | |--[XYZ]
| | | |--[-]
| | | |--[3.5]
| | |--[10]
| |--[.1]
|--[*]
|--[.3]
|--[1]
