Instituto

Tecnológico de Pachuca

Lenguajes y Autómatas II

“Mapa unidad 1”

Mati. Arturo Gonzales CeronMillán Valdés Gabriel 12200642

13-septiembre- 2015

e

Analisis Semantico

Análisis semántico

Es la fase encargada de detectar la validez semántica de las sentencias aceptadas por el analizador sintáctico

Por lo tanto:

Es la fase posterior a la de análisis sintáctico

Es el conjunto de reglas formales que especifican la estructura de los programas pertenecientes a dicho lenguaje

Semántica de un lenguaje de programación: es el conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente valida

Es una estructura de datos en la cual cada uno de los elementos están

relacionados entre sí a través de ramas

Un árbol cuenta con un conjunto finito de elementos llamados nodos y un conjunto de líneas dirigidas denominadas ramas

PADRE: es un nodo que tiene nodos sucesores

Hermanos: Dos o mas nodos con el mismo padre

Hoja: es un nodo que no tiene hijos

Nivel: distancia de ubicación hasta la raíz del árbol Camino: secuencia de nodos en que cada nodo es adyacente al siguiente

Altura o profundidad: es el nivel de la hoja del camino mas largo desde la raíz mas uno

ALTURA = NIVELES+1

ARBOLES BINARIOS

Árbol en el que ningún nodo puede tener más de dos subárboles

Cada nodo puede tener 0, 1,2 hijos

Árbol degenerado: lista enlazada

Árbol completo Árbol lleno

Tipos de arboles

Que es una expresión?

Es una secuencia de tokens que sigue unas reglas especificas

La prioridad se determina solo por paréntesis

La expresión completa se sitúa con paréntesis

Recorrido de un árbol

Se usa para visualizar o consultar los datos almacenados en un árbol, también conocido como visitar los nodos del mismo. Al contrario que las listas enlazadas, los arboles binarios no tienen realmente un primer valor, un segundo valor, un tercer valor, etc.

Tipos de recorrido

El recorrido de un árbol binario requiere que cada nodo del árbol sea procesado (visitado) una vez, y solo una, en una secuencia predeterminada. Existen dos enfoques generales para la secuencia de recorrido:

ACCIONES SEMANTICAS DE UN ANALIZADOR SINTACTICO

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 entre sí

Es decir, comprobara que el significado de lo que va leyendo es válido.

Acciones Semánticas

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ímbolosSentencias 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ónConstantes: comprobar que no se utilicen en la parte izquierda de una asignación

COMPROBACIONES DE TIPOSComprobación estática.- un compilador debe comprobar si el programa fuente sigue tanto las convenciones sintácticas como las semánticas del lenguaje fuente.Los ejemplos de comprobación estática incluyen.-

-comprobaciones de tipos comprobaciones del flujo de control -comprobaciones relacionadas con nombres

Tipos básicos y construidos Los tipos básicos son los tipos atómicos sin estructura interna Entre los tipos construidos se pueden considerar a apuntadores

y las funciones

EXPRESIONES DE TIPOS Una expresión de tipo, es un tipo básico o se forma aplicando un operador llamado constructor de tipos a otras expresiones de tipos.Expresiones de tipos más comunes:

tipos simples: son expresiones de tipos los tipos simples del lenguaje, y algunos tipos especiales

Integer Real Char Boolean Void

Sistemas de tipos

Un sistema de tipos es una serie de reglas para asignar expresiones de tipos a las distintas partes de un programa y verificar su corrección.

Un sistema de tipos incluye tanto comprobaciones estáticas como dinámicas, según si se realiza en tiempo de compilación o en tiempo de ejecución.

Sintaxis de un lenguaje de programación

Arboles binarios

TIPOS DE ARBOLES

ARBOL EQUILIBRADO ARBOL PERFECTAMENTE

EQUILIBRADO

Recorrido en profundidad:El proceso exige un camino desde la raíz a través de un hijo, al descendiente más lejano del primer hijo antes de proseguir a un segundo hijo. En otras palabras en el recorrido en profundidad, todos los descendientes de un hijo se procesan antes del siguiente hijo.

Recorrido en anchura: el proceso se realiza horizontalmente desde la raíz a todos sus hijos; a continuación, a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En el recorrido en anchura, cada nivel se procesa totalmente antes de que comience el siguiente nivel.

Recorrido en anchura: el proceso se realiza horizontalmente desde la raíz a todos sus hijos; a continuación, a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados. En el recorrido en anchura, cada nivel se procesa totalmente antes de que comience el siguiente nivel.

Recorrido en profundidadSe pueden definir tres tipos de secuencia de un recorrido en profundidad.

Recorrido preorden Recorrido en orden Recorrido en

postorden

La comprobación realizada por un compilador es estática, mientras que la comprobación hecha al ejecutar el programa objeto se denomina dinámica

ee

Pila Semántica En Un Analizador Sintáctico

La pila es la estructura de datos que va guardando información que le permite ir haciendo las operaciones de reducción que necesita

Las rutinas semánticas suelen hacer uso de una pila (la pila semántica)

Construcción de analizadores sintácticos

Ascendente: Se va construyendo el árbol desde sus nodos terminales

Descendente: Parten del axioma inicial de la gramática

Pilas

Estructura de datos lineal donde los elementos pueden ser añadidos o removidos solo por un extremo

Operaciones básicas con pilas:

Push (insertar).- agrega un elemento a la pila en el extremo llamado tope

Pop (remover).- remueve el elemento de la pila que se encuentra en el extremo llamado tope

Vacía.- Indica si la pila contiene o no contiene elementos

Llena.- Indica si es posible o no agregar nuevos elementos a la pila

Tabla de Símbolos: estructura de datos que almacenan toda la información de los identificadores del lenguaje fuente

La información almacenada en la TS depende directamente del tipo de elementos del lenguaje específico a procesar y de las características de dicho lenguaje

En los traductores y compiladores las TS existen únicamente en tiempo de compilación

Las palabras reservadas no están en la TS

La implementación de pilas se puede dar usando arreglos, en donde se define el arreglo de una dimensión (vector) donde se almacenan los elementos.

Aplicación en compiladores

Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel.

Esquema de traducción:

Es una gramática independiente del contexto en el cual se han insertado fragmentos de código en las partes derechas de sus reglas de producción.

Aplicación en compiladores

Muchos compiladores utilizan una pila para analizar la sintaxis de las expresiones, bloques de programa, etc. Antes de traducir el código de bajo nivel.

Los fragmentos de código así insertados se denominan acciones semánticas.

Se caracteriza por que el desarrollador especifica el momento en el que se ha de ejecutar el código.

RUTINAS SEMANTICAS

Las rutinas semánticas son fragmentos de codigo que el desarrollador del compilador escribe normalmente entre llaves {}.

Los esquemas de traducción ejecutan las rutinas semánticas de modo imperativo.

ESQUEMAS DE TRADUCCION AVANZADOS

Se caracterizan por la posibilidad de procesar tanto gramáticas correctas como gramáticas abstractas.

En un compilador de varias pasadas la TS se crea durante el análisis léxico y sintáctico

El analizador léxico separa el programa fuente en tokens que compara con las palabras reservadas

Contenido de la TS

Los símbolos se guardan en la tabla con su nombre y una serie de atributos opcionales que dependerán del lenguaje y de los objetivos del procesador.

Operaciones con la TS

Las dos operaciones que se llevan a cabo generalmente en las TS son la inserción y la búsqueda

Provocados

Parte Importante de un compilador, que debe tener presente el diseñador del compilador.

Manejo de Errores

Semánticos

Producir un mensaje de errorRecuperarse de erroresDetectar errores

Indispensable Un compilador no puede detectar todos los tipos de errores

Mostrar donde ocurrió el error

Ambiente amigable y bien diseñado

EjemploErrores al diseñar un lenguaje de programación.

Características Considerar Manejo de Errores por el compilador

Provocados

Clases

Errores que ocurren por omitir requisitos formales del lenguaje de programación

Errores de ortografía

Pueden ser detectados por el compilador o al menos por el sistema de ejecución.

Errores visibles

Por decisiones erróneas en las especificaciones o mala formulación de algoritmos

Son aquellos que no puede detectar el compilador.

Errores invisibles

Clasificación de Errores

Omisión de declaraciones

Símbolo incorrecto al que acaba de leer

Uso de carácter inválido

Errores Semánticos

Errores Sintácticos

Errores Léxicos

Se informa del error y se detiene la ejecución del programa

El compilador proporciona el código generado con ciertas acciones para estos casos.

Errores en el sistema de ejecución

Clasificación

En el código fuenteSe refleja

Nombres ilegales de identificadores.

Números inválidos.

Cadenas incorrectas de caracteres.

Errores de ortografía en palabras reservadas.

Etiquetas ilegales.

Fin de archivos.

Típicos

Manejo de errores en el análisis léxico

Se deben

Descuidos del programador.

Principales

Manejo de errores en el análisis

semántico Identificadores no definidos.

Operadores y operandos incompatibles.

Revisión de tabla de símbolosDetectados

Paréntesis o corchetes omitidos.

Operadores u operando omitidos.

Delimitadores omitidos.

Manejo de errores en el análisis

sintáctico

Típicos

Recuperación de emergencias (o en modo pánico).

Recuperación por inserción, borrado y reemplazo.

Recuperación por expansión de gramática.

Estrategias

No debe presentarse en un buen sistema de compilación

No reconoce

Continua

Detiene

Efectos de los errores

Facetas

CONCLUSIONES

Los aprendizajes obtenidos en esta unidad tan extensa sobre Análisis semánticos fueron los siguientes. Se comprendió que un árbol binario es una estructura de datos en la cual todos los elementos están relacionados, que están compuesto de un conjunto finito de nodos y ramas. De igual forma existen varios tipos de árboles binarios, que son árbol degenerado árbol completo y árbol lleno, de igual forma existe diversas maneras de poder recorrer los caminos de cada uno de estos tipos de árboles. También se estudió lo que era la pila semántica, otra estructura de datos que trabaja bajo la filosofía LIFO. Las pilas son usadas generalmente cuando se utiliza una rutina semántica, junto a esto viene lo que es la tabla de símbolos que al igual que la pila y los arboles binarios es otra estructura de datos que almacena toda la información de los identificadores del lenguaje fuente. Por último se estudió el manejo de errores semánticos que es una parte de mucha importancia dentro de un compilador ya que esta parte se encarga de manejar los errores que se generen al crear un programa y poder interpretarlos al usuario de manera que pueda comprender que está pasando y como resolverl.