• Author / Uploaded
• Gustavo Salgado

• Categories
• Lenguaje de programación
• Compilador
• Analizando
• Sintaxis
• Ingeniería Informática

Citation preview

Instituto Tecnológico De Acapulco. Ingeniería en sistemas computacionales

Lenguaje y Autómatas II Maestro: Mario Jiménez Vázquez

Trabajo :pila semántica en un analizador sintáctico Alumno: Gustavo Salgado Martínez. No. De Control: 10320171 LUNES 24 DE FEBRERO DEL 2014

Definición:

Las pilas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación estas estructuras pueden implementarse mediante arrays o listas enlazadas. La pila es una colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope. Las pilas tienen dos operaciones básicas: Push:para insertar un elemento. Pop:para extraer un elemento. Su característica fundamental es que al extraer se obtiene siempre el último elemento que acaba de insertarse. Por esta razón también se conocen como estructuras de datos LIFO (del inglés Last in Firits out ) Una posible implementación mediante listas enlazadas seria insertando y extrayendo siempre por el principio de la lista gracias a las pilas es posible el uso de la recursividad la variable que llama al mismo procedimiento en el que esta habrá que guardarla así como el resto de variables de la nueva llamada para a la vuelta de la recursividad ir sacándolas esto es posible a la implementación de pilas . Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia por ejemplo la gestión de ventas en Windows (cuando cerramos una ventana siempre recuperamos la que teníamos detrás) Las pilas y las colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación estas estructuras pueden implementarse mediante arrays o listas enlazadas al utilizar arreglos para impletar pilas se tiene la limitación de que se debe reservar el espacio con anticipación una vez dado un máximo de capacidad a la pila no es posible insertar un número de elementos mayor que el máximo establecido Si esto ocurre en otras palabras si la pila está llena y se intenta insertar un nuevo elemento se producirá un error conocido como desbordamiento –overflow una posible solución a este tipo de inconvenientes consiste en definir pilas de gran tamaño pero esto resulta ineficiente y costos no siempre es viable saber con exactitud saber con exactitud el número de elementos a tratar y siempre existe la posibilidad de que ocurra un error de desbordamiento.

Las colas también son llamadas FIFO (First in first out) que quiere decir el primero que entra el primero que sale. 1._Colas simples. Se insertan por un sitio y se saca por otro en el caso de la cola simple se inserta por el final y se saca por el principio para gestionar este tipo de cola hay que recordar siempre cual es el siguiente elemento que se va leer y cuál es el último elemento que se ha introducido. 2._Colas circulan En las colas circulantes se considera que después del último elemento se accede de nuevo al primero. De esta forma se reutilizan las posiciones extraídas el final de la cola es a su vez el principio creándose un circuito cerrado 3._Colas con prioridad. Las colas con prioridad se implementan mediante listas o arrays ordenados no nos interesa en este caso que salgan en orden de entrada si no con una prioridad que le asignemos puede darse el caso que existan varios elementos con la misma prioridad en este caso saldrá aquel que primero llegue (FIFO). Analizador sintáctico: Es un Autómata de pila que se reconoce la estructura de una cadena de componentes léxicos en general el analizador sintáctico inicializa el compilador y para cada símbolo de entrada llama al analizador morfológico y proporciona el siguiente símbolo de entrada analiza el símbolo, la pila y el estado del autómata, el analizador sintáctico produce las estructuras necesarias para la siguiente etapa y en el caso de compilación dirigida por la sintaxis invocadas llamadas directas al analizador semántico y al generador de código escribe mensaje de error y trata de limitar el efecto de estos errores. Al decir pila semántica no se refiere a que hay varios tipos de pila hace referencia hay varios tipos de pila; hace referencia a que se debe programar única y exclusivamente en un solo lenguaje es decir no podemos mezclar código c++ con visual basic ya que se trabaja con los mismos comandos. El objetivo teórico es construir un árbol de análisis sintáctico este raramente se construye como tal, sino que las rutinas semánticas integradas van generando el árbol de sintaxis abstracta. Se especifica mediante una gramática libre de contexto. Análisis semántico: Detecta la validez semántica de las sentencias aceptadas por el analizador sintáctico. El analizador semántico suele trabajar simultáneamente al analizador sintáctico y en estrecha cooperación. Se entiende por semántica como el conjunto de reglas que especifica e

significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje; las rutinas semánticas deben 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. El análisis sintáctico es la fase en la que se trata determinar el tipo de los resultados intermedios comprobar que los argumentos que tienen un operador pertenece al conjunto de los operadoras posible y si son compatibles entre si etc. En definitiva comprobara que el significado de lo que se va leyendo es válido. La salida teórica de la fase de análisis semántico seria un árbol semántico consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe de tener se compone de un conjunto de rutinas independientes llamadas por los analizadores morfológicos y sintáctico El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticos y preparar la generación de código. Las rutinas semánticas suelen hacer uso de una pila (la pila semantica) que contiene la información semántica asociada alos operadores (y a veces alos operadores) en forma de registro semánticos Reglas Semánticas. Son el conjunto de normas y especificaciones que definen al lenguaje de programación y están dadas por la sintaxis del lenguaje las reglas semánticas asignan un significado lógico a ciertas expresiones definidas en la sintaxis del lenguaje. La evaluación de ñas reglas semánticas define los valores de los atributos en nodos del árbol de análisis sintáctico para la cadena de entrada. Una regla semántica también puede tener efectos colaterales por ejemplo imprimir un valor o actualizar una variable global. Compatibilidad de tipos: Durante la fase de análisis semántico el compilador debe verificar que los tipos y valores asociados alos objetos de un programa se utilizan de acuerdo con la especificación del lenguaje. Además debe detectar conversiones implícitas de tipos para efectuarlas o insertar el código apropiado para efectuarlas así como almacenar información relativa alos tipos de los objetos y aplicar las reglas de verificación de tipos. Analizadores descendentes: Parten del axioma inicial de la gramática se va descendiendo utilizando las derivaciones izquierdas hasta llegar a construir la cadena analizada.

Analizadores ascendentes: Se va construyendo el árbol desde sus nodos terminales. Es decir se construye desde los símbolos de la cadena hasta llegar al axioma de la gramática. Bottom up: Es un principio de muchos años del estilo de programación que los elementos funcionales de un programa no deben de ser demasiado grandes si un cierto componente de un programa crece más allá de la etapa donde esta fácilmente comprensible se convierte en una masa de la complejidad que encubre errores tan fácilmente como una gran ciudad grande encubre a fugitivos Técnica top-Down este método consiste en dividir los problemas en subproblemas más sencillos para conseguir una solución mas rápida el diseño descendente es un método para resolver el problema que posteriormente se traducirá a un lenguaje comprensible por la computadora. Conclusiones la pila semántica contiene información semántica asociada alos operadores en forma de registro semánticos Una pila tiene 4 operaciones:    

Insertar un elemento-push Eliminar-pop Pila_vacia Pila_llena