Resumen: Semana del 22 al 29 de mayo

(1/8)

Parsing ascendente

• A diferencia del método descendente, arma el árbol gramatical desde las hojas hacia la raíz, reduciendo la hilera a un símbolo de aceptación
• El método más común para parsing ascendente se conoce como reducción-desplazamiento

(2/8)

Algoritmo de reducción-desplazamiento

• Llamado así por las operaciones que pueden realizarse en este
• Al iniciar, se crea una pila que inicia con un símbolo $
• Al reducir, se reemplaza una sección de la hilera que coincida con el lado derecho de la producción (handle/mango) por su lado izquierdo
• Al desplazar, se inserta una sección de la hilera en la pila
• El ciclo se repite hasta que la pila sólo contenga $ y la hilera esté vacía, o hasta que se encuentre la instrución de aceptar o de error

(3/8)

Gramáticas LR(k)

• Escanean de izquierda a derecha (L), generan una derivación más derecha en reversa (R) y puede revisar k elementos por adelantado en la hilera
• Es el método más general para parsing de reducción-desplazamiento, y puede implementarse tan eficientemente como otros métodos
• Utiliza una tabla interna donde cada combinación de estado/entrada especifica una reducción, un desplazamiento o una aceptación a realizar
• Por separado se tiene una lista de reducciones, en el formato A → B

(4/8)

Ejemplo de sistema LR(1)

(5/8)

Algoritmo LR(1)

• Se crea una pila que inicia con $, como al inicio
• Si la acción [tope de pila · símbolo más izquierdo de la hilera] es:
  • Desplazar con X: colocar el símbolo más izquierdo, luego el estado X indicado por el desplazamiento, en la pila
  • Reducir con X: revisar la lista de reducciones y obtener la reducción A → B correspondiente, luego sacar todos los símbolos de B de la pila, incluyendo sus estados correspondientes, luego insertar los símbolos de A, luego el estado correspondiente a los símbolos insertados en la pila
  • Aceptar: terminar el parsing y aceptar la hilera
  • Cualquier otra cosa: parar por error

(6/8)

Algoritmo LR(1)

• Ejemplo: id * id

(7/8)

Tipos de gramáticas LR

• Existen múltiples niveles de gramáticas LR canónicas:
  • La LR(0) simplemente usa un símbolo especial (usualmente un punto · ) para determinar por dónde va el parsing del lado derecho
  • La LR(1) fue la anteriormente discutida, y ve hacia adelante un solo elemento
  • La LR(2) en adelante ve 2 o más elementos por turno hacia adelante; la gramática se amplía acordemente
• También están las gramáticas SLR y Look-Ahead LR (LALR)

(8/8)

Generación de tablas de gramática LR

• Desafortunadamente, la principal desventaja de las gramáticas LR es la complejidad para crear las tablas de gramática correspondientes, en especial a mano
• Para ello se desarrollaron herramientas computacionales, como lo son yacc y bison