Analisis Semantico

1.1 Árboles de expresiones

Una importante aplicación de los árboles en la informática es la representación de árboles sintácticos,es decir,árboles que contienen las derivaciones de una gramática necesarias para obtener una determinada frase de un lenguaje.

Podemos etiquetar los nodos de un árbol con operandos y operadores de manera que un árbol represente una expresión.Por ejemplo. en la figura 5 se representa un árbol con la expresión aritmética (x-y)*(z/t).

Para que un árbol represente una expresión,hay que tener en cuenta que:

• Cualquier hoja está etiquetada con uno y sólo un operando.

• Cualquier nodo interior n está etiquetado por un operador.

En los árboles de expresión,la sucesión del preorden de etiquetas nos da lo que se conoce como la forma prefijo de una expresión, en la que el operador precede a su operando izquierdo y su operando derecho.En el ejemplo de la figura 5,el preorden de etiquetas del árbol es *-xy/zt .

Análogamente,la sucesión postorden de las etiquetas de un árbol expresión nos da lo que se conoce como la representación postfijo de una expresión.Así en el ejemplo,la expresión postfijo del árbol es xy-zt/*.

Finalmente,el inorden de una expresión en un árbol de expresión da la expresión infijo en sí misma,pero sin paréntesis.En el ejemplo,la sucesión inorden del árbol anterior es x-y*z/t.

1.2 Acciones semánticas de un analizador sintáctico

Un analizador sintáctico (o parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación.

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.

El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.

Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintáticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc, GNU bison y javaCC.

1.3 Comprobaciones de tipos en expresiones

Comprobación de tipo en expresiones

E à literal {E.tipo = char}

E à num {E.tipo = entero}

E à id {E.tipo = Consultar_TS(id.entrada)}

E à id [E1] {id.tipo

...