(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.