Analizador Sintáctico Ascendente

Analizador Sintáctico Ascendente

• Un A.St. Ascendente construye un árbol de análisis desde las hojas hasta la raíz.
• Utiliza una estrategia de reducción-desplazamiento, donde se aplica una regla de reducción cuando es posible y, de lo contrario, se desplaza el siguiente token a la pila de trabajo.
• Las gramáticas LR son lo suficientemente expresivas para manejar la mayoría de las construcciones sintácticas de los lenguajes de programación.
• Un analizador LR(k) utiliza un máximo de k símbolos terminales para determinar la acción a realizar.
• Los analizadores LR(1) solo necesitan conocer el siguiente token de la cadena de entrada.
• Se utiliza una pila auxiliar que almacena símbolos gramaticales y estados.
• El analizador posee una tabla de análisis con dos partes: ACCIÓN y GOTO.
• La tabla ACCIÓN contiene acciones a realizar para cada estado y símbolo terminal.
• La tabla GOTO contiene estados para cada estado y símbolo no terminal.
• Las posibles acciones en la tabla ACCIÓN son: Aceptar, Reducir, Desplazar o Error.
• Los conflictos surgen cuando se obtienen dos o más acciones diferentes para una misma celda de la tabla, lo que indica que la gramática no es LR(1).
• El algoritmo del analizador se ejecuta hasta que se alcanza una acción de aceptar o de error.
• El método SLR (Simple LR(1)) es un método sencillo para construir las tablas ACCIÓN y GOTO.
• Para construir las tablas, se utilizan conceptos como gramática aumentada, forma sentencial, prefijo viable, ítem LR(0), cierre de un conjunto de ítems, Goto de un conjunto de ítems con un símbolo gramatical, y la construcción de la colección canónica de ítems LR(0).
• La gramática aumentada G’ se obtiene agregando un símbolo inicial S’ y una producción S’→S.
• Una forma sentencial es una secuencia de símbolos terminales y no terminales que se puede obtener del axioma mediante las reglas de la gramática.
• Una cadena o sentencia es una forma sentencial que solo contiene símbolos terminales.
• Un prefijo viable es un prefijo de una forma sentencial derecha que no excede el extremo derecho del consecuente de la regla a aplicar.
• El estado inicial del analizador se construye a partir del conjunto de ítems que contiene [S’→ · S].
• La colección canónica de ítems LR(0) se obtiene calculando los estados a partir del cierre de un conjunto de ítems y aplicando la operación Goto.
• El conjunto Follow(A) contiene los símbolos terminales que pueden seguir al no terminal A en una forma sentencial.
• La tabla SLR se construye utilizando la colección canónica de ítems LR(0) y los conjuntos Follow.
• Si no hay conflictos en la tabla SLR (solo una entrada por celda), entonces la gramática es SLR.

Este cuestionario explora el funcionamiento de un analizador sintáctico ascendente, que construye un árbol de análisis desde las hojas hasta la raíz. Se centra en el uso de gramáticas LR y la tabla de análisis que contiene las acciones y los estados. Asimismo, se discuten las diferencias entre los analizadores LR(k) y LR(1).