ANALISIS SEMANTICO

LENGUAJES Y AUTOMATAS II

ANALISIS SEMÁNTICO

competencia especifica

Diseña mediante el uso de reglas semánticas dirigidas por sintaxis, un analizador semántico para un compilador.

temas

1.1 ARBOLES DE EXPRESIONES

1.2 Acciones semánticas de un analizador sintáctico.

1.6 Generación de la tabla de símbolo y tabla de direcciones.

1.3 Comprobaciones de tipos en expresiones.

1.7 Manejo de errores semanticos

1.4 Pila semántica en un analizador sintáctico.

1.5 esquema de traducción

"La semántica se refiere a los aspectos del significado, sentido o interpretación del significado de un determinado elemento, símbolo, palabra, expresión o representación formal."

Martínez López, F. (2015).

introducción

analizador semántico

¿qué es?

El analizador semántico es una componente clave de un compilador, que se encarga de procesar la estructura sintáctica de un programa fuente una vez que ha sido analizada por el analizador sintáctico o parser. Su función principal es comprobar que la estructura sintáctica que ha sido reconocida cumple con las reglas semánticas del lenguaje de programación, lo cual incluye la validación de contextos y significados que no pueden ser capturados por las reglas de gramática sintáctica .

FUNCIONES PRINCIPALES

analizador semántico

Las rutinas semánticas deben de realizar la evaluación de los atributos de las gramáticas siguiendo las reglas semánticas asociadas a cada producción de la gramática. Por ejemplo, para una expresión como:

(A+B)*(C+D)

El analizador semántico debe determinar que acciones pueden realizar los operadores aritméticos (+,*) sobre las variables A, B, C y D. Cuando el Analizador sintático reconoce un operador, llama a una rutina semántica que especifica que acción puede llevar a cabo. Esta rutina puede comprobar que los dos operandos han sido declarados, y que son del mismo tipo, también puede comprobar si a los operandos se les ha asignado previamente algún valor.

Interacción del analizador

semántico con el resto de las fases del compilador

El análisis semántico es un proceso concurrente con las fases léxica y sintáctica. Se realiza en paralelo, utilizando una representación actualizada del árbol de análisis del programa.El analizador semántico enriquece el árbol de análisis con información semántica y anota errores detectados, contribuyendo a la exactitud de la compilación y a la generación de código intermedio.

1.1 aRBOLES DE EXPRESIONES

ARBOL DE ANALISIS DECORADO

Es una representación visual del árbol de análisis sintáctico de un programa, al cual se le han añadido detalles adicionales, es decir, los valores de los atributos semánticos calculados para cada nodo.

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

arboles de expresiones

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 un pequeña expresión.

arboles de expresiones

Mediante gramáticas atribuidas se implementan analizadores semánticos a partir del AST o del Árbol Sintáctico.

Para implementar un analizador semántico debemos decorar el AST con la siguiente información:Las expresiones tendrán asociadas un atributo tipo que indique si son reales o enteras. En una declaración se deberá insertar el identificador en una tabla de símbolos con su tipo declarado, para poder conocer posteriormente el tipo de cualquier identificador en una expresión. Es, por tanto, necesario asignar un atributo nombre a un identificador. Finalmente –aunque más enfocado a la fase de generación de código o interpretación que al análisis semántico – se le asigna un valor entero o real a las constantes del lenguaje.

¿QUÉ ES UN ATRIBUTO?

INFO

Es un campo asociado a un Terminal o No Terminal. Es cualquier propiedad de una construcción del lenguaje de programación. Por ejemplo:

El tipo de datos de una variableEl valor de una expresión La ubicación de una variable en memoria El código objeto de un procedimiento El número de dígitos significativo en un número.

1.3 COMPROBACIÓN DE TIPOS DE EXPRESIONES

acciones semánticas

INFO

Las acciones semánticas suelen estar incrustadas en la gramática de atributos como parte de las reglas de producción. Cuando se procesa una regla de producción durante el análisis sintáctico, las acciones semánticas asociadas se ejecutan para realizar las comprobaciones y transformaciones necesarias. Por ejemplo, en una regla que combine dos expresiones aritméticas, la acción semántica correspondiente podría verificar que las expresiones sean del mismo tipo numérico y, si es necesario, realizar una conversión de tipo o emitir un error de compilación.

acciones semánticas

INFO

Las acciones semánticas se encargan de manipular el contenido de los atributos para verificar que existe un significado correcto en la relación de los símbolos Terminales y No Terminales entre sí. Por ejemplo, tenemos a var x : integer;

El proceso de asociar información a una construcción de lenguaje de programación proporcionando atributos a los símbolos de la gramática que representa la construcción se le denomina semántica dirigida por sintáxis.

definiciones dirigidas por la

sintaxis

Una Definición dirigida por sintaxis es una generalización de una gramática libre de contexto en la que a cada símbolo se le asocia un conjunto de atributos. Las reglas semánticas fijan unas dependencias entre los atributos que se rán epresentan mediante un grafo de dependencias.

definiciones dirigidas por la

sintaxis

grafo de dependencias

En una gramática atribuida, cada producción se asocia a un grafo de dependencias locales que establece, mediante un grafo dirigido, las dependencias entre todos los atributos presentes en la producción [Wilhelm95]. A partir de este grafo, podemos deducir el orden de evaluación de las reglas semánticas, lo que nos permite obtener el valor de los atributos de los nodos del Árbol de análisis.

definiciones dirigidas por la

sintaxis

grafo de dependencias

definiciones dirigidas por la

sintaxis

Los atributos se clasifican según su cálculo: Un atributo es sintetizado si su valor depende de los atributos de sus hijos, calculándose durante el análisis sintáctico ascendente LR. Por ejemplo: el valor de una variable en una expresión. Un atributo es heredado si su valor depende de los atributos de su padre y/o hermanos. Por ejemplo: el tipo de una variable.

definiciones dirigidas por la

sintaxis

Utiliza una GIC para especificar la estructura sintáctica de la entrada. A cada símbolo de la gramática le asocia un conjunto de atributos y a cada producción, un conjunto de reglas semánticas para calcular valores de los atributos asociados con los símbolos que aparecen en esa producción. Si X es un símbolo y a es uno de sus atributos, entonces escribimos X.a para denotar el valor de a en el nodo específico de un árbol de análisis sintáctico, etiquetado como X.

INFO

gramaticas atribuidas

Se denomina gramática de atributos a una extensión de las GLC a la cual se añadirá un sistema de atributos. Dicho sistema de atributos estará formado por:

Un conjunto de atributos semánticos, que se asocia a cada símbolo de la gramática. Los datos globales de la gramática, accesibles desde cualquiera de sus reglas, pero que no están asociados a ningún símbolo en concreto. Un conjunto de acciones semánticas, distribuidas por las reglas de producción.

Ejemplo: Considérese la gramática para la generación de expresiones aritméticas simples: ¿Qué atributos nos interesan en esta gramática?

GRAMATICAS ATRIBUIDAS

Las gramáticas de atributos suelen escribirse en forma tabular, con una parte donde aparecen las producciones y otra donde aparecen las reglas semánticas (o ecuaciones de atributos) que permitan calcular los atributos.

𝐸→𝐸+𝑇|𝐸−𝑇|𝑇𝑇→𝑇∗𝐹|𝐹𝐹→(𝐸)|𝒏𝒖𝒎

El valor numérico de la expresión lo denotaremos por 𝑣𝑎𝑙. Las reglas semánticas para el cálculo de este atributo serían:

ejemplo 1.

ejemplo 1

Los atributos se colocan al lado de los nodos del árbol de análisis sintáctico y se dibujan las dependencias entre ellos. Una flecha que va desde los atributos que aparecen en la parte derecha de la ecuación hacia el lado izquierdo. Por ejemplo, para la entrada (4-3)*2, el árbol sería:

ejemplo 2.

La gramática para la declaración de variables en C. ¿Qué atributos nos interesan en esta gramática?

𝐷𝑒𝑐𝑙→𝑇𝑦𝑝𝑒 𝑉𝑎𝑟_𝐿𝑖𝑠𝑡 𝑇𝑦𝑝𝑒→𝑖𝑛𝑡|𝑓𝑙𝑜𝑎𝑡 𝑉𝑎𝑟_𝐿𝑖𝑠𝑡→𝒊𝒅, 𝑉𝑎𝑟 _ 𝐿𝑖𝑠𝑡|𝒊𝒅

El tipo de variable lo denotaremos por Type. Las reglas semánticas para el cálculo de este atributo serían:

ejemplo 2.

actividad en clase

ESQUEMAS DE TRADUCCIÓN

Un esquema de traducción es una gramática atribuida en la que hay intercalados en el lado derecho de las reglas de producción, fragmentos de código en un lenguaje de programación, que implementan acciones semánticas.Un ETDS es un diagrama dirigida por la sintaxis (DDS) en que se da una orden en la ejecución de las acciones semánticas, las cuales se sitúan a la derecha de los símbolos a los que se refieren y entre llaves.

1.4 Pila semántica en un analizador sintáctico.

Normalmente, los lenguajes de programación mantienen tipos primitivos de datos y permiten crear nuevos tipos a partir de los primitivos. También es generalizado el empleo de variables que pertenecen algunos de los tipos primitivos o definidos por el usuario. Aparte de las variables, suelen utilizarse subprogramas. Tanto las variables como los subprogramas son generalmente creados por el programador y se les suele llamar símbolos. Por lo tanto, debemos mantener básicamente dos estructuras de información: referente a los tipos de lenguaje y a los símbolos de este.

GENERACION DE TABLA DE SIMBOLOS y tipos

GENERACION DE TABLA DE SIMBOLOS y tipos

La tabla de tipos es una estructura de datos crucial utilizada en el proceso de compilación, especialmente durante el análisis semántico, para llevar un registro de todos los tipos de datos definidos en un programa, así como sus propiedades y relaciones.

CARACTERÍSTICAS Almacena información sobre los tipos de datos definidos por el usuario y los tipos primitivos del lenguaje de programación, incluyendo su tamaño, estructura, y los operadores aplicables. Mantiene la jerarquía y las relaciones entre los tipos, como las clases base y derivadas en lenguajes orientados a objetos, permitiendo al compilador verificar la correcta herencia y la sobrecarga de métodos. Ayuda al compilador a verificar la compatibilidad de tipos durante la asignación de valores, operaciones, y pasaje de argumentos en llamadas a funciones, asegurando que las operaciones entre diferentes tipos sean válidas. Registra reglas de conversión de tipos para permitir conversiones implícitas y explícitas entre tipos compatibles, facilitando la generación de código correcto para estas operaciones.

GENERACION DE TABLA DE SIMBOLOS y tipos

USO EN EL PROCESO DE COMPILACIÓN La tabla de tipos se utiliza en varias fases del proceso de compilación, principalmente en: Análisis Semántico: Es utilizada intensivamente para verificar que las operaciones y asignaciones en el código sean semánticamente correctas, basándose en la información de tipos. Por ejemplo, el compilador puede verificar que no se estén realizando operaciones aritméticas con tipos no numéricos o que la asignación entre tipos sea permitida. Generación de Código: Durante la generación de código, la tabla de tipos ayuda al compilador a determinar cómo implementar operaciones específicas para diferentes tipos de datos, como la suma de números enteros versus la concatenación de cadenas. Optimización: La información en la tabla de tipos puede ser utilizada para optimizaciones específicas de tipos, como la elección de instrucciones de máquina más eficientes para tipos de datos particulares.

GENERACION DE TABLA DE SIMBOLOS y tipos

Tabla de símbolos

La tabla de símbolos es una estructura de datos utilizada durante varias fases del proceso de compilación en programación. Su propósito principal es almacenar información sobre los identificadores (como variables, funciones, clases, etc.) encontrados en el código fuente de un programa.

GENERACION DE TABLA DE SIMBOLOS y tipos

CARACTERISTICAS DE LA TABLA DE SÍMBOLOS

Almacenamiento de Identificadores: La tabla de símbolos guarda los nombres de los identificadores y otra información relevante, como su tipo, alcance, ubicación de memoria (si está asignada), y cualquier otra información de atributos necesaria para la compilación y enlace. Soporte para Alcance y Contexto: Maneja el alcance (scope) de los identificadores, permitiendo que el mismo nombre sea utilizado en diferentes contextos sin conflicto, mediante el almacenamiento de información de alcance para cada identificador. Búsqueda Rápida: Está optimizada para inserciones rápidas y búsquedas, permitiendo al compilador encontrar rápidamente la información sobre un identificador.

GENERACION DE TABLA DE SIMBOLOS y tipos

USO EN EL PROCESO DE COMPILACIÓN

Análisis Léxico y Sintáctico: Durante estas fases, el compilador identifica los tokens (léxico) y estructuras (sintáctico) en el código fuente. Cuando se encuentra un identificador, se agrega a la tabla de símbolos con su información inicial. Análisis Semántico: En esta fase, el compilador verifica que los identificadores se utilicen correctamente según su tipo, alcance, y otras reglas del lenguaje de programación. La tabla de símbolos es esencial aquí para validar la semántica del programa. Generación de Código: Durante la generación de código, el compilador utiliza la información de la tabla de símbolos para asignar ubicaciones de memoria a las variables, resolver referencias a funciones y variables, y optimizar el código generado. Optimización: En la fase de optimización, el compilador puede necesitar revisar y modificar la tabla de símbolos para realizar optimizaciones basadas en el uso de los identificadores.

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 1. Inicialmente, se añaden los tipos básicos a la tabla de tipos.

TABLA DE TIPOS

TABLA DE SIMBOLOS

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 2. Se añade el tipo vector con integer como tipo base de datos.

TABLA DE TIPOS

TABLA DE SIMBOLOS

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 3. Se añaden los identificadores v y x

TABLA DE TIPOS

TABLA DE SIMBOLOS

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 1.

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 3 y 4.

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 7

GENERACION DE TABLA DE SIMBOLOS y tipos

EJEMPLO:

PROCESANDO LA LINEA 12

GENERACION DE TABLA DE SIMBOLOS y tipos

PROCESANDO LA LINEA 16

EJEMPLO:

GENERACION DE TABLA DE SIMBOLOS y tipos

PROCESANDO LA LINEA 20

EJEMPLO:

manejo de errores semántico

Los errores semánticos ocurren cuando las instrucciones del código fuente no tienen sentido dentro del contexto del lenguaje de programación, aunque la sintaxis sea correcta. A diferencia de los errores sintácticos, que son violaciones de la gramática del lenguaje, los errores semánticos implican la incorrecta utilización de los operadores, tipos de datos, y estructuras de control, entre otros aspectos.

manejo de errores semántico

Ejemplo de errores:

Asignación de tipos incompatibles. Asignar un valor de un tipo a una variable de otro tipo incompatible, por ejemplo, asignar un valor booleano a una variable entera sin una conversión de tipo explícita.

Operación con tipos incompatibles. Intentar realizar una operación entre tipos que no la soportan, como dividir una cadena de texto por un número.

manejo de errores semántico

Referencias a identificadores no definidos. Usar una variable o función que no ha sido declarada.

Uso incorrecto de alcance. Acceder a una variable fuera de su alcance.

Violación de restricciones de acceso. Intentar acceder a un miembro privado de una clase desde fuera de la clase.

Errores en las llamadas y funciones. Pasar el número incorrecto de argumentos o tipos de argumentos incompatibles a una función.

manejo de errores semántico

Estrategias de manejo de errores semánticos:

Detección: El compilador utiliza la tabla de símbolos y la tabla de tipos para detectar inconsistencias. Por ejemplo, si se intenta asignar un tipo a otro incompatiblemente, el compilador puede mirar en la tabla de tipos para determinar si la asignación es válida.

Reporte: Cuando se detecta un error semántico, el compilador informa al usuario. Esto generalmente incluye la ubicación del error (archivo, línea, columna), una descripción del problema y, posiblemente, una sugerencia para corregirlo.

Recuperación: Después de informar un error, el compilador intenta recuperarse para continuar analizando el resto del código. Esto puede implicar ignorar la parte del código donde ocurrió el error, asumir un valor predeterminado o realizar una corrección supuesta.

manejo de errores semántico

Estrategias de manejo de errores semánticos:

Análisis Contextual: El compilador también realiza un análisis contextual para asegurarse de que los elementos del código se utilizan en contextos adecuados, por ejemplo, verificar que las llamadas a métodos correspondan a las definiciones de clases.

Comprobaciones en Tiempo de Ejecución: Algunos errores semánticos solo se pueden detectar en tiempo de ejecución, como la división por cero o la desreferenciación de punteros nulos. El compilador puede insertar código para realizar estas comprobaciones y manejar los errores apropiadamente.

recursos

bibliograficos

Teoria, diseño e implementación de compiladores de lenguajes

Compiladores y procesadores de lenguajes:

Jiménez Millán, J. A. (2014). Compiladores y procesadores de lenguajes: ( ed.). Cádiz, Spain: Servicio de Publicaciones de la Universidad de Cádiz. Recuperado de https://elibro.net/es/ereader/tlajomulco/33847

Martínez López, F. (2015). Teoría, diseño e implementación de compiladores de Lenguajes: ( ed.). RA-MA Editorial. https://elibro.net/es/ereader/tlajomulco/106460

dISEÑO DE COMPILADORES MODERNOS

Compiladores: principios, tecnicas y herramientas

Aho, A. V., Sethi, R., & Ullman, J. D. (1990). Compiladores: principios, técnicas y herramientas. Pearson Educación.

Grune, D., Bal, H., Jacobs, C., & Lagendoen, K. (2007). Diseño de compiladores modernos. McGraw-Hill.

Acciones semánticas

Son trozos de código en un lenguaje de programación concreto que manipulan los símbolos y sus atributos. Son operaciones que se ejecutan durante el análisis semántico para enriquecer la información sintáctica obtenida por el analizador sintáctico con significado semántico. Esto incluye la evaluación de las reglas y restricciones semánticas del lenguaje de programación que van más allá de la estructura gramatical.

Acciones semánticas

Son trozos de código en un lenguaje de programación concreto que manipulan los símbolos y sus atributos. Son operaciones que se ejecutan durante el análisis semántico para enriquecer la información sintáctica obtenida por el analizador sintáctico con significado semántico. Esto incluye la evaluación de las reglas y restricciones semánticas del lenguaje de programación que van más allá de la estructura gramatical.

Un atributo es...

Cualquier propiedad de una construcción de un lenguaje de programación. Varían en función del tipo de información que contienen, su complejidad de cálculo y el momento en que son calculados (en tiempo de compilación - atributos estáticos - o de ejecución -dinámicos). Algunos ejemplos son: Nombre, tipo, ámbito o posición de memoria de una variable; valor de una expresión, número de argumentos de una función, un fragmento de código, etc.

Funciones principales:

• Comprobación de Tipos
• Alcance de variables.
• Uso de identificadores.
• Control de flujo.
• Análisis de definición de uso.
• Generación de Tablas de Símbolos.
• Comprobación de asignaciones
• Análisis de acceso a miembros.

Basado en el Ejemplo del documento en el enlace, página 37 y 50