Sintactico ascendente

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO[pic 1][pic 2]

[pic 3]

FACULTAD DE INGENIERIA[pic 4][pic 5][pic 6]

PROYECTO COMPILADORES

ANALIZADOR SINTACTICO ASCENDENTE

HECHO POR LOS ALUMNOS:

Andrés Amadeus Gallardo Tinoco Lira Navarro Juan Arturo Martínez García Isaac

P        R        E        S        E        N        T        A        N:

[pic 7]         Semestre 2021-2

CONSTRUCCIÓN DE UN ANALIZADOR ASCENDENTE

Objetivos

› Comprender el análisis ascendente por reducción desplazamiento

› Aprender el algoritmo general de análisis ascendente

› Conocer la arquitectura general de un analizador sintáctico ascendente

› Aprender a construir analizadores ascendentes en complejidad creciente

Introducción

El analizador sintáctico ascendente construye árboles desde las hojas hasta las raíces. Funciona mediante reducción-desplazamiento, lo que significa que si puede, aplicará la regla (reducir), y si no puede, reemplazar el token pasado a su pila de trabajo por el analizador léxico. El análisis sintáctico del árbol que construye es lo opuesto a lo que obtiene cuando construye un árbol descendente aplicando la derivación a la derecha.

¿Cómo construir el árbol?

Se trata de moverse a través de la entrada hasta encontrar la subcadena simbólica que representa la parte derecha de la producción. En este punto, usamos esta subcadena para reemplazar el símbolo no terminal en la parte izquierda correspondiente de la producción, y lo reducimos.

Gramática LR

Puede usar la gramática LR para construir un analizador sintáctico ascendente eficiente. La capacidad expresiva de la gramática LR es suficiente para generar la mayor parte de la estructura sintáctica de un lenguaje de programación. El analizador sintáctico ascendente LR (k), mirando hasta k símbolos terminales (los siguientes k tokens pasadospor el analizador sintáctico al analizador sintáctico ascendente), puede determinar con certeza qué acción tomar. Específicamente, usaremos la sintaxis LR (1), por lo que solo necesitamos saber cuál es el siguiente token en la cadena de entrada. Este analizador utiliza una pila de trabajo auxiliar, que implícitamente construye un árbol de derivación, y tiene una tabla de análisis, que tiene dos partes: la tabla ACCIÓN y la tabla GOTO.

En la pila de trabajo se van insertando símbolos gramaticales y estados, de tal forma que encima de cada símbolo hay un estado (en la cima hay un estado), Inicialmente, la pila tiene un símbolo de fondo de pila.

En cada instante, el analizador analiza el estado y el token actual en la parte superior de la pila y accede a la tabla ACTION para saber qué hacer. La tabla ACCIÓN muestra posibles estados en filas y terminadores gramaticales (marcas) en columnas; sus celdas contienen acciones. La tabla GOTO tiene estados posibles en filas, no terminales en columnas gramaticales y contiene estados. En cada celda de

...