tree - sintacticos - ANTLR duplicar un árbol

arbol sintactico compiladores

Question

Yo uso ANTLR para construir un árbol (Common Tree) como Follwing (lenguaje: JAVA):

  Parser.prog_return r = parser.prog();
  CommonTree t = (CommonTree) r.getTree();

Ahora, necesito pasar "t" como parámetro, y hacer algunos cambios sin afectar el árbol original. Sin embargo, con el puntero de Java, esto no se pudo haber hecho, así que necesito duplicar el árbol.

He estado buscando en Internet, lo que pude encontrar es el método dupTree () de la clase ASTFactory.

¡Cualquier sugerencia o consejo sobre cómo lograr esto sería apreciada!

EDITAR

@Bart Kiers, gracias por su respuesta, ¡absolutamente funciona!

Veo que está haciendo una primera caminata de profundidad sobre el árbol y crea un objeto CommonTree para cada nodo que fue visitado.

Mi pregunta es ahora, ¿cuál es la relación entre CommonToken y CommonTree, y qué hacen estos atributos?

cTok.setCharPositionInLine(oTok.getCharPositionInLine());
cTok.setChannel(oTok.getChannel());
cTok.setStartIndex(oTok.getStartIndex());
cTok.setStopIndex(oTok.getStopIndex());
cTok.setTokenIndex(oTok.getTokenIndex());

Answer 1

Pruebe algo como esto:

public static CommonTree copyTree(CommonTree original) {
  CommonTree copy = new CommonTree(original.getToken());
  copyTreeRecursive(copy, original);
  return copy;
}

private static void copyTreeRecursive(CommonTree copy, CommonTree original) {
  if(original.getChildren() != null) {
    for(Object o : original.getChildren()) {

      CommonTree originalChild = (CommonTree)o;

      // get the token from the original child node
      CommonToken oTok = (CommonToken)originalChild.getToken();

      // create a new token with the same type & text as ''oTok'' 
      CommonToken cTok = new CommonToken(oTok.getType(), oTok.getText());

      // copy all attributes from ''oTok'' to ''cTok''  
      cTok.setLine(oTok.getLine());
      cTok.setCharPositionInLine(oTok.getCharPositionInLine());
      cTok.setChannel(oTok.getChannel());
      cTok.setStartIndex(oTok.getStartIndex());
      cTok.setStopIndex(oTok.getStopIndex());
      cTok.setTokenIndex(oTok.getTokenIndex());

      // create a new tree node with the ''cTok'' as token
      CommonTree copyChild = new CommonTree(cTok);

      // set the parent node of the child node
      copyChild.setParent(copy);

      // add the child to the parent node
      copy.addChild(copyChild);

      // make a recursive call to copy deeper
      copyTreeRecursive(copyChild, originalChild);
    }
  }
}

...

// get the original tree
CommonTree tree = (CommonTree)parser.parse().getTree();

// create a copy of the tree
CommonTree copy = copyTree(tree);

// change the contents of the right node of the right node of the root 
((CommonTree)tree.getChild(1).getChild(1)).getToken().setText("X");

System.out.println(tree.toStringTree());
System.out.println(copy.toStringTree());

que produciría:

(&& a (|| b X)) (&& a (|| b c))

para la entrada "a && (b || c)" . Es decir, el tree tiene X , pero la copy tendrá los contenidos originales: c .

Tenga en cuenta que elijo los objetos CommonTree y CommonToken porque esas son las implementaciones Token y Tree defecto. Si eliges crear tu propio Token y / o Tree , es probable que subclases las clases CommonTree y CommonToken , en cuyo caso mi sugerencia no se romperá.

Un CommonTree no es más que un contenedor alrededor de un CommonToken , que contiene un poco de información adicional: un nodo padre y nodos secundarios. Es por eso que también copio toda la información de los objetos de CommonToken .

Answer 2

Tuve el mismo problema tropezando con dupTree() , que parecía estar en desuso y luego la publicación de Bart, que me condujo en la dirección correcta. Finalmente terminé con lo siguiente, que es usar el constructor de CommonTree aceptando un CommonTree , abstrayéndolo de la necesidad de copiar los campos individuales.

  private static CommonTree copyTreeRecursive(CommonTree original) {

    CommonTree copy = new CommonTree(original); // Leverage constructor

    if(original.getChildren() != null) {
      for(Object o : original.getChildren()) {
        CommonTree childCopy  = copyTreeRecursive((CommonTree)o);
        childCopy.setParent(copy);
        copy.addChild(childCopy);
      }
    };
    return copy;
  }

NB: Me quedé con la convención de nomenclatura de Bart.