AST: (Abstract Syntax Tree)

Es una representación abstracta de la sintaxis de un código fuente y es abstracta por qué representa con detalle la sintaxis de un lenguaje de programación

La Idea de una AST es que cada nodo se refiere a una construcción del código fuente por ejemplo existe el nodo If, While, asiganción. etc.

Al final de las hojas se encuentran los terminales de una gramática por ejemplo las variables, operadores, literales etc.

Ahora, porque AST y no colocar las acciones semánticas en la gramática:

1. que todo necesitamos de las Acciones Semánticas para construir el árbol (pero para nada más)
2. Raramente las herramientas para generar parser soportan atributos heredados y trasformar la gramática o utilizar la una pila es un tanto complicado.
3. si se quiere interpretar un lenguaje la única forma (sin quebrarnos la cabeza) es con el AST.
4. si se tiene N gramáticas es más fácil escribir acciones semánticas para construir el AST que traducir directamente.

Así por ejemplo el árbol de la gramática (usual) de asignación

asingacion::= ID '=' Exp:a1 {:RESULT=new NodoAsignacion(ID,a1);:}

exp::= Exp:a1 '+' literal:a2 {:RESULT=new NodoExp(a1,'+',a2) :} //el Símbolo + podría cambiar por cualquier operador binario. se construye de la misma manera

|literal:a3

literal::= Num {:RESULT=new NodoLiteral(Num);:}

|ID {:RESULT=new NodoLiteral(ID);:}

Se podría agregar información extra (A las clases) como por ejemplo el No Línea, No Columna para poder identificar los Errores cuando se esté generando código o interpretando. Así como también apuntadores a la Tabla de Símbolos y al manejador de Errores.

c=a+5;

El árbol quedaría de la siguiente manera:

Note que el árbol se construirá de acuerdo a la gramática del lenguaje. Ahora para poder interpretar o genera código se haría un recorrido (o varios) en orden del AST.

He aquí un repositorio de un ejemplo (espero bastante completo) para que se hagan una idea de cómo implementa un AST de acuerdo a sus necesidades.

http://code.google.com/p/compi2jbattleship/

Acerca del ejemplo es un juego de naves que compila un subconjunto del lenguaje de Java hacia Código de 3 direcciones (TAC: Three Address Code) y luego interpreta El TAC para poder jugar de acuerdo el código.