Analisis semantico. ARBOLES DE EXPRESIONES

INTRODUCCION

En esta investigación entenderemos que el análisis semántico no es más que la salida de un resultado, estos debes ser correcto ya que este análisis detecta los errores que pueda contener el programa.

El análisis semántico se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles ente si, comprobará que el significado do lo que se va leyendo es válido.

Podremos apreciar en cada fase del proceso de compilación se pueden encontrar errores pero el análisis semántico detecta el error, la fase puede tratar el error, de manera que el compilador pueda continuar, permitiendo así que se puedan detectar errores posteriores. Un compilador que se detenga cuando encuentre el primer error no es muy eficaz.

ANÁLISIS SEMANTICO

     En el análisis semántico se detectan errores relacionados con la validez del programa. Se puede decir que estos errores son de tipo sintáctico-semántico, pero no pueden ser detectados por el analizador sintáctico, ya que se relacionan con interdependencias entre las diferentes partes de un programa que no son reflejadas en un análisis gramatical. El analizador semántico recibe la información resultado del análisis sintáctico que puede ser un árbol jerárquico con la información relativa a la organización de los tokens en la instrucción que se está analizando.

     Durante el análisis semántico de un lenguaje de fuerte chequeo de tipos el árbol sintáctico debe ser modificado para reflejar el análisis de los tipos de los datos. Note que haciendo un chequeo de tipos la constante 7, al ser una constante entera debe ser convertida a real para poder ser operada y las demás variables no tienen dificultad alguna para ser utilizadas al ser todas reales.

     El análisis semántico se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles ente si, etc. En definitiva, comprobará que el significado do lo que se va leyendo es válido.

    El análisis semántico se realiza posteriormente al sintáctico y mucho más difícil de formalizar que éste.

La salida “teórica” de la fase de análisis semántico sería un árbol semántico.

[pic 2]

1.1 ARBOLES DE EXPRESIONES

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y.

Un árbol de expresión sirve para evaluar expresiones del tipo: (a + b)*c/d.

Para que un árbol represente una expresión se deben tomar en cuenta 2 características muy importantes:

• Cualquier hoja está etiquetada sólo con un operando.
• Cualquier nodo interior n está etiquetado por un operador.

[pic 3]

Al introducir la expresión debemos de tomar en cuenta las siguientes características:

∙ La raíz siempre debe ser un operador.

∙ Las hojas siempre deben ser operandos.

∙ Los nodos deben estar etiquetados por operadores.

∙ Si un operador tiene mayor prioridad que la raíz se coloca como hijo.

∙ Si un operador tiene igual o menor prioridad que un nodo se coloca como padre.

∙ Un nodo puede contener como hijo otro subárbol que contiene una pequeña expresión.

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

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

Finalmente, el inorden de una expresión en un árbol de expresión nos da la expresión infijo en sí misma, pero sin paréntesis

Construcción de un árbol de expresión

Algoritmo

∙ Mientras carácter diferente de nulo

∙ Leer carácter de la lista

∙ Si es paréntesis pasar al siguiente carácter

∙ Crear un nodo nuevo que contenga ese carácter Operando

∙ Si el árbol está vacío hacer raíz a nuevo, si no recorrer el árbol por la derecha hasta llegar a un nodo con hojas, si la hoja izquierda, no está etiquetada colocar operando, si no colocarlo en la hoja derecha.

Operador

∙ Si la raíz es un operando, insertar nuevo en ese nodo, y convertir el operando en el hijo izquierdo, si no si hay un paréntesis abierto insertar nuevo en la última hoja derecha y colocar operando como hijo izquierdo.

∙ Si el carácter anterior es paréntesis izquierdo si el siguiente carácter es paréntesis derecho si solo hay un operador en el árbol nuevo se convierte en raíz, si no se inserta en el último nodo derecho, y el nodo se convierte en hijo izquierdo.

∙ Si no se cumple ninguna de las condiciones anteriores si la raíz es de igual prioridad o menor prioridad convertir la raíz en el hijo izq. de nuevo si no la prioridad del nodo raíz es mayor al de nuevo insertar nuevo como hijo derecho y colocar el nodo reemplazado como hijo izquierdo.

[pic 4]

1.2 ACCIONES SEMÁNTICAS DE UN ANALIZADOR SINTÁCTICO

Dependiendo del tipo de sentencias, las acciones semánticas pueden agruparse en:

• Sentencias de Declaración: completar la sección de tipos de la Tabla de Símbolos.
• Sentencias “ejecutables”: realizar comprobaciones de tipos entre los operandos implicados.
• Funciones y procedimientos: comprobar el número, orden y tipo de los parámetros actuales en cada llamada a una función o procedimiento.
• Identificación de variables: comprobar si identificador ha sido declarado antes de utilizarlo.
• Etiquetas: comprobar si hay etiquetas repetidas y validación.
• Constantes: comprobar que no se utilicen en la parte izquierda de una asignación.
•  Conversiones y equivalencias de tipo: verificación.
• Sobrecarga de operadores y funciones: detectar y solventar.

La verificación de los tipos de datos se hace asignando el valor de tipo de cada una de los componentes léxicos. Estos valores se comparan para verificar que los tipos de datos coincidan y sean congruentes, de lo contrario no se pueden realizar los cálculos.

Definición de un analizador sintáctico: es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce.

...