Construcción y recorrido del árbol de sintaxis abstracta

Question

No tengo claro la estructura de los árboles sintácticos abstractos. Para ir "hacia abajo (hacia adelante)" en la fuente del programa que representa el AST, ¿va directamente al nodo superior o baja? Por ejemplo, ¿el programa de ejemplo

a = 1 
b = 2 
c = 3 
d = 4 
e = 5 

resultado en un AST que tiene este aspecto:

o esto:

Cuando en la primera, va "derecho" en el main node lo guiará a través del programa, pero en el segundo, simplemente siguiendo el puntero next en cada nodo hará lo mismo.

Parece que el segundo sería más correcto ya que no necesita algo así como un tipo de nodo especial con una matriz potencialmente extremadamente larga de punteros para el primer nodo. Aunque, puedo ver que el segundo se vuelve más complicado que el primero cuando te metes en los bucles for y las ramas if y cosas más complicadas.

Answer 1

La primera representación es la más típica, aunque la segunda es compatible con la construcción de un árbol como estructura de datos recursiva, como se puede usar cuando la plataforma de implementación es funcional en lugar de imperativa.

considerar:

Este es su primer ejemplo, excepto acortado y con el nodo de "principal" (un hombre de paja conceptual) llamado más apropiadamente "bloque", para reflejar el constructo común de una "bloque" que contiene una secuencia de enunciados en un lenguaje de programación imperativo. Diferentes tipos de nodos tienen diferentes tipos de niños, ya veces esos niños incluyen colecciones de nodos auxiliares cuyo fin es importante, como es el caso de "bloque."Lo mismo podría surgir de, digamos, una inicialización de la matriz:

int[] arr = {1, 2} 

considerar cómo esto podría ser representado en un árbol sintáctico:

En este caso, el nodo de tipo literal matriz también tiene varios hijos de un mismo tipo cuyo orden es importante.

Answer 2

Depende del idioma. En C, usted tendría que usar la primera forma de captar la noción de un bloque, ya que un bloque tiene un ámbito de variable:

{ 
    { 
     int a = 1; 
    } 
    // a doesn't exist here 
} 

El alcance variable sería un atributo de lo que se llama el "nodo principal ".

Answer 3

Sugerencia: Cuando se trata de estructuras de datos de árboles, wheter es AST o de otro tipo relacionados con el compilador, utilice siempre un solo nodo "raíz", que puede ayudarle a realizar las operaciones y tener más control:

class ASTTreeNode { 
    bool isRoot() {...} 

    string display() { ... } 
    // ... 
} 

void main() 
{ 
    ASTTreeNode MyRoot = new ASTTreeNode(); 

    // ... 

    // prints the root node, plus each subnode recursively 
    MyRoot.Show(); 
} 

Aclamaciones.

Answer 4

Creo que su primera versión tiene más sentido, por un par de razones.

En primer lugar, la primera demuestra más claramente el "anidamiento" del programa, y ​​también se implementa claramente como un árbol con raíz (que es el concepto habitual de un árbol).

La segunda y más importante razón es que su "nodo principal" realmente podría haber sido un "nodo de sucursal" (por ejemplo), que simplemente puede ser otro nodo dentro de un AST más grande. De esta forma, su AST se puede ver en un sentido recursivo, donde cada AST es un nodo con otros AST cuando es un niño. Esto hace que el diseño del primero sea mucho más simple, más general y muy homogéneo.

Answer 5

Cuando en la primera, va "derecho" en el nodo principal le adelantará a través del programa, pero en el segundo uno simplemente siguiendo el siguiente puntero en cada nodo hará lo mismo.

Parece que el segundo sería más correcto ya que no es necesario algo así como un especial tipo de nodo con un potencial extremadamente largo matriz de punteros para el primer nodo de

Casi siempre preferiría el primer enfoque, y creo que te resultará mucho más fácil construir tu AST cuando no necesites mantener un puntero al siguiente nodo.

creo que es generalmente más fácil tener todos los objetos descienden de una clase base común, similar a esto:

abstract class Expr { } 

class Block : Expr 
{ 
    Expr[] Statements { get; set; } 
    public Block(Expr[] statements) { ... } 
} 

class Assign : Expr 
{ 
    Var Variable { get; set; } 
    Expr Expression { get; set; } 
    public Assign(Var variable, Expr expression) { ... } 
} 

class Var : Expr 
{ 
    string Name { get; set; } 
    public Variable(string name) { ... } 
} 

class Int : Expr 
{ 
    int Value { get; set; } 
    public Int(int value) { ... } 
} 

AST resultante es como sigue:

Expr program = 
    new Block(new Expr[] 
     { 
      new Assign(new Var("a"), new Int(1)), 
      new Assign(new Var("b"), new Int(2)), 
      new Assign(new Var("c"), new Int(3)), 
      new Assign(new Var("d"), new Int(4)), 
      new Assign(new Var("e"), new Int(5)), 
     });