Lenguaje y Compiladores - Parsing Bottom Up #1

Anteriormente, vimos la derivación descendente, a continuación aprenderemos la reducción que consiste en ir desde la cadena de entrada hasta el símbolo inicial del árbol sintáctico.

Parsing Bottom-Up:

Es una estrategia general. Siendo determinista es decir, sin backtracking. Es mas eficiente que el método predictivo debido a que no utiliza backtracking, es usado por la mayoría de generadores de analizadores sintácticos conocidos como Java, C++, etc.

Usa la gramática en su versión mas natural por lo que no es necesaria la factorizacion a diferencia del top down.

Establece reglas de prioridad y asociatividad de los operadores. Podemos asociarlo con una operación matemática.

5x8x3

Para nosotros no es difícil determinar que el orden de los factores no alterara el producto, sin embargo, el computador no tiene esa capacidad, por lo que debemos establecer reglas de prioridad y asociatividad indicando en que dirección se hará las operaciones. Esto se hace para evitar la ambigüedad en la gramática.

Recordando, una gramática es ambigua cuando genera dos arboles sintácticos para una misma entrada.

La estrategia:

La idea es construir el árbol sintáctico de abajo hacia arriba, desde las hojas (tokens de entrada) hasta la raíz (símbolo no terminal de inicio). Esto se hace con el método de reducción, distinto al top down que usa producción.

Algo a notar es que la reducción se debe hacer por la derecha.

Reducción por desplazamiento:

Si hacemos las derivaciones por la derecha, debe haber una secuencia de símbolos terminales por la derecha, y por la izquierda símbolos tanto terminales como no terminales.

Si lo tuviéramos que visualizar, seria como una barra que atraviesa la cadena de entrada. Podemos indicar también el área a la derecha de la barra como área no examinada.

|int * int + int -> int * T | + int

Para la reduccion por desplazamiento, existen dos movimientos.

Movimientos reduce: reemplaza la parte derecha de una produccion por la parte izquierda de un paso de reduccion.

Movimientos shift: basicamente rueda la barra a la derecha. Generalmente se hace al no encontrar produccion, se hace hasta no haber mas entrada sin analizar.

Si se puede hacer hacer shift/reduce en un paso, esto se puede resolver con precedencia.

Si es un caso en el que se puede hacer reduce/reduce este sera mas complicado, para el proximo articulo se indicara la forma de resolver el problema.

Recurso usado:

- Lamina: Parsing Bottom-Up 

Terminos a investigar:

- Prefijo viable

- Item: implementa un algoritmo con los automatas finitos deterministas.