Resumen: Semana del 5 al 12 de junio

(1/8)

Introducción al SLR

• El Simple LR (o SLR) es un método simplificado para implementar gramáticas LR
• Se caracteriza porque cada objeto utiliza un símbolo (usualmente un punto) para determinar dónde se encuentra la hilera (por ejemplo, A → B·CD)
• Primeramente crea grupos de elementos que equivalen a los estados de las gramáticas LR
• Al igual que con otras gramáticas LR, usa la producción inicial S' → S

(2/8)

Operaciones en la gramática SLR

• La gramática SLR requiere de dos operaciones, la de clausura y la de desplazamiento
  • La clausura genera grupos de elementos
  • El desplazamiento (mejor conocido como "ir a") genera transiciones entre esos grupos de elementos, a partir de símbolos gramaticales

(3/8)

Operación de clausura

• Para cada grupo I, la clausura de I se conforma de:
  • Primero, todos los elementos de I
    • Luego, si hay un A→α·Bβ (donde haya una derivación de Bβ) tal que siga una producción B→γ (donde haya una derivación de γ), se agrega recursivamente B→·γ (en términos más sencillos, si queda una derivación para lo que haya después del punto)

(4/8)

Operación de desplazamiento (ir a...)

• Se define "ir a (I, X)" para todo grupo I tal que contenga un A→α·Xβ
• En ese caso ir a(I, X) = A→αB·β
• Se puede definir como "avanzar" el punto a través de un símbolo gramatical

(5/8)

Generación de colección canónica

• Una colección canónica C contiene todos los posibles elementos de una gramática SLR
  • A partir de S' → ·S y hasta que no queden elementos que agregar a C:
    • Por cada conjunto I en C, y cada X en la gramática:
      • Si ir a(I, X) no es parte de C aún, y no es vacío, agregar ir a(I, X) a C

(6/8)

Estados de la gramática SLR

• El estado I(0) es el inicial, y contiene la clausura de todos los elementos de S' → ·S
  • Cada transición a otro estado es etiquetada con un símbolo X de la gramática, y se genera a partir de un ir a(I, X)

(7/8)

Elementos válidos

• Un elemento A→β1·β2 es válido para un prefijo αβ1, si hay una derivación S'⇒αAw⇒αβ1β2w
• Los estados tienen la utilidad de que si tienen una transición (β2 ≠ ϵ), implican un desplazamiento con ese símbolo; y si no tienen transición alguna (β2 = ϵ), implican reducir por el elemento de ese grupo

(8/8)

Creación de la tabla de parsing SLR

• Con la gramática, podemos generar la tabla SLR, donde los estados se marcan con i y los símbolos con a:
  • Primero se genera la colección C
  • Para cada estado i:
    • Si hay un estado A→α·aβ, hay una transición para "ir a(I[i], a)" que vaya a un I[j], y a es una terminal, entonces la acción para (i, a) es desplazar a j.
    • Si hay un estado A→α· (es decir, que no pueda avanzar), entonces la acción para todo a en Siguiente(A) es reducir A→α (siempre que A no sea S')
    • Si hay un estado S' → S· se acepta la hilera
  • Luego se realizan transiciones "ir a" para todos los no terminales A: si hay un "ir a(I[i], a) = I[j]" entonces "ir a[i, A] = j"
  • Cualquier entrada vacía es un espacio de error.
  • El estado inicial, como se dijo, es el que contiene al elemento S' → ·S.
• Si hay acciones conflictivas en la tabla, la gramática no es SLR, en forma similar a las gramáticas LL.