tda - tipos de datos abstractos en programacion orientada a objetos

Representando un árbol sintáctico abstracto en C

Question

Estoy implementando un compilador para un lenguaje de juguete simple en C. Tengo un escáner y un analizador sintáctico, y un trasfondo razonable sobre la función / construcción conceptual de un AST. Mi pregunta está relacionada con la forma específica de representar un AST en C. He encontrado tres estilos con bastante frecuencia en diferentes textos / recursos en línea:

Una estructura por tipo de nodo.

Tiene una "clase" de nodo base (struct) que es el primer campo en todas las estructuras secundarias. El nodo base contiene una enumeración que almacena el tipo de nodo (constante, operador binario, asignación, etc.). Se accede a los miembros de la estructura utilizando un conjunto de macros, con un conjunto por estructura. Se ve algo como esto:

struct ast_node_base {
enum {CONSTANT, ADD, SUB, ASSIGNMENT} class;
};
struct ast_node_constant {
struct ast_node_base *base;
int value;
};
struct ast_node_add {
struct ast_node_base *base;
struct ast_node_base *left;
struct ast_node_base *right;
};
struct ast_node_assign {
struct ast_node_base *base;
struct ast_node_base *left;
struct ast_node_base *right;
};
#define CLASS(node) ((ast_node_base*)node)->class;
#define ADD_LEFT(node) ((ast_node_add*)node)->left;
#define ADD_RIGHT(node) ((ast_node_add*)node)->right;
#define ASSIGN_LEFT(node) ((ast_node_assign*)node)->left;
#define ASSIGN_RIGHT(node) ((ast_node_assign*)node)->right;

Una estructura por diseño de nodo.

Esto parece ser mayormente el mismo que el anterior, excepto que en lugar de tener ast_node_add y ast_node_assign tendría un ast_node_binary para representar ambos, porque el diseño de las dos estructuras es el mismo y solo difieren por los contenidos de base-> class . La ventaja de esto parece ser un conjunto más uniforme de macros (IZQUIERDA (nodo) para todos los nodos con un lado izquierdo y derecho en lugar de un par de macros por), pero la desventaja parece ser que la comprobación del tipo C no será tan útil (No habría forma de detectar una ast_node_assign donde solo debería haber un ast_node_add, por ejemplo).

Una estructura total, con una unión para contener diferentes tipos de datos de nodo.

Una mejor explicación de esto de lo que puedo dar se puede encontrar here . Usando los tipos del ejemplo anterior, se vería así:

struct ast_node {
enum { CONSTANT, ADD, SUB, ASSIGNMENT } class;
union { int value;
struct { struct ast_node* left;
struct ast_node* right; } op;
};

Me inclino a preferir la tercera opción porque hace que el recorrido recursivo sea mucho más fácil (en el sentido de que se evitan muchos lanzamientos de punteros a favor de la unión), pero tampoco aprovecha la verificación de tipo C. La primera opción parece ser la más peligrosa ya que depende de punteros a las estructuras que se lanzan para acceder al miembro de cualquier nodo (incluso diferentes miembros del mismo nodo que requieren diferentes casos para acceder (base vs. izquierda)), pero estos lanzamientos son de tipo revisado para que pueda ser discutible. La segunda opción para mí parece ser la peor de ambos mundos, aunque tal vez me esté perdiendo algo.

¿Cuáles de estos tres esquemas son los mejores y por qué? ¿Hay una cuarta mejor opción que aún no he encontrado? Supongo que ninguna de ellas es una solución de "talla única", así que si importa el lenguaje que estoy implementando es un lenguaje imperativo de tipo estático, casi un pequeño subconjunto de C.

Una pregunta específica que tengo sobre el tercer diseño (unión). Si uso solo el campo de valor, ¿habrá espacio vacío después del valor para acomodar la posibilidad de que se escriba?

Answer 1

Ira Baxter le dio una buena answer simple y prospectiva, especialmente de los problemas que encontrará en el futuro, así que me centraré en esta pregunta:

¿Hay una cuarta mejor opción que aún no he encontrado?

Está utilizando el lenguaje imperativo para escribir un compilador y tiene problemas para diseñar la estructura de datos para el concepto de nodo en el AST. En el mundo de los lenguajes funcionales como ML, OCaml, Haskell, F # uno usaría una unión etiquetada para mantener todos los diferentes tipos de nodos en una estructura de datos, que es básicamente lo que usted ha creado.

No espero que el OP cambie a un lenguaje funcional para este problema, pero si otros tratan con árboles regularmente, puede ser útil aprender un lenguaje funcional y usarlo para problemas relacionados con los árboles.

Answer 2

Puedes hacer cualquiera de estos trabajos.

Prefiero el diseño de la unión, porque entonces todos los nodos tienen "el mismo" diseño.

[Puede que le resulte útil tener una opción de "sublista de niños", por ej., Y una matriz de niños enormemente dinámica y arbíaria, en lugar de tener listas de izquierda o derecha).

Descubrirá que este problema no es el que dificulta la construcción de su compilador. Por el contrario, está teniendo tablas de símbolos, realizando varios tipos de análisis, eligiendo un IR a nivel de máquina, construyendo un generador de código y optimizando los códigos. Entonces te encontrarás con usuarios reales y descubrirás lo que realmente hiciste mal: -}

Elegiría uno y correría con él, para que tuvieras la oportunidad de acercarte a los otros problemas.