Analizador Sintáctico SLR

En este post explicaré paso a paso el proceso de análisis sintáctico usando el Simple LR, más fácil de implementar y basandose en el LR0

INTRODUCCIÓN

Se compone de 3 partes:

1. El conjunto de elementos LR(0).
2. El conjunto de tablas de análisis
3. La rutina del controlador. (PARSER)

Un parser es una máquina lógica que reconoce el lenguaje generado a partir de una gramática. En este

trabajo, implementaremos un generador de analizador sintáctico para una clase particular de gramáticas sin contexto.

Conocidas como gramáticas simples de LR (K) [SLR (K)].

LR(0)

• L: Proceso de la entrada de izquierda a derecha
• R: Derivación más a la derecha
• 0: Símbolo para decidir la producción a aplicar.

Aunque es el menos potente de la familia LR, tiene la ventaja de ser fácilmente comprensible y servir de base para entender el resto.

Pero demasiado trabajo construir un analizador sintáctico LR.

FASES:

1. Se obtiene la colección canónica de conjuntos de elemento.
2. Se obtiene el autómata reconocedor de prefijos viables.
3. Cada conjunto de la colección (Ii ) es un estado del analizador (i).
4. Contenido de la sección Ir_a de la tabla de análisis:

       Cada transición Ir_a(Ii,<A>) = Ij , siendo <A> un símbolo no terminal de la gramática, significa         colocar el valor j en la celda Ir_a(i,<A>).

El algoritmo LR(0) no requiere de la consideración de ningún token de preanálisis (de ahí el 0). 

Conflictos LR(0): 

• Los conflictos aparecen cuando una determinada celda de la sección Acción de la tabla puede rellenarse con varios valores. 
• Estos conflictos significan que la gramática no es LR(0). Puede que la gramática sea ambigua, o que sea LALR o LR(1).

SLR(1)

El algoritmo de análisis SLR es un análisis de LR que escanea la entrada de izquierda a derecha y construye una derivación a la derecha en reversa. Estas técnicas de construcción de parser son prácticas tanto en velocidad de la construcción del analizador, en el tamaño y velocidad de los analizadores

(Por lo tanto, el nombre SLR).

EJEMPLO

Gramática" G " a utilizar con reglas:

E → E+T | T
T → T∗F | F
F → (E) | id

Convertimos a la gramática " G' " agregando un nuevo estado inicial de la siguiente manera:

E' → E
E → E+T
E → T
T → T∗F
T → F
F → (E)
F → id

Colocamos un identificador con simbolo '.' al inicio de cada regla

(0) E' → .E
(1) E → .E+T
(2) E → .T
(3) T → .T∗F
(4) T → .F
(5) F → .(E)
(6) F → .id

Construir la colección canónica LR(0) 

C = {I0,...,In} (estados del AFD).

I0:

 E' → .E
 E → .E+T
 E → .T
 T → .T∗F
 T → .F
 F → .(E)
 F → .id

I1 → (I0 → E)

 E' → E.
 E → E.+T

I2 → (I0 → T)

 E → T.
 T → T.∗F

I3 → (I0 → F)

 T → F.

I4 → (I0 → ( )

Como es símbolo terminal, si después del '.' existe un símbolo no terminal, se coloca las reglas que contengan ese símbolo no terminal que se encuentra al lado izquierdo de la producción, si una de sus producciones lee otro símbolo no terminal, repetir lo anterior:

 F → (.E) 

Después del '.' se encuentra el símbolo no terminal 'E'. Entonces se agregan las producciones que contengan el símbolo no terminal 'E'

 E → .E+T

 E → .T

La producción E → .T se encuentra en la parte izquierda un símbolo no terminal, por lo que nuevamente se colocan las producciones cuya parte izquierda contengan el símbolo no terminal 'T'

 T → .T∗F

 T → .F

La producción T → .F se encuentra en la parte izquierda un símbolo no terminal, por lo que nuevamente se colocan las producciones cuya parte izquierda contengan el símbolo no terminal 'F'

F → .(E)
F → .id

I5 → (I0 → id)

F → id.

I6 → (I1 → +)

E → E+.T

La producción E → E+.T se encuentra en la parte izquierda un símbolo no terminal, por lo que nuevamente se colocan las producciones cuya parte izquierda contengan el símbolo no terminal 'T'

 T → .T∗F

 T → .F

La producción T → .F se encuentra en la parte izquierda un símbolo no terminal, por lo que nuevamente se colocan las producciones cuya parte izquierda contengan el símbolo no terminal 'F'

F → .(E)
F → .id

I7 → (I2 → *)

T → T∗.F

La producción T → T∗.F se encuentra en la parte izquierda un símbolo no terminal, por lo que nuevamente se colocan las producciones cuya parte izquierda contengan el símbolo no terminal 'F'

F → .(E)
F → .id

I8 → (I4 → E)

 F → (E.)
 E → E.+T

*I4 → T = I2*I4 → F = I3
*I4 → ( = I4
*I4 → id = I5

I9 → (I6 → T)

E → E+T.
T → T.∗F

*I9 → * = I7
*I6 → F = I3
*I6 → ( = I4
*I6 → id = I5

I10 → (I7 → F)

T → T∗F.

*I7 → ( = I4
*I7 → id = I5

I11 → (I8 → ))

 F → (E).

*I8 → + = I6

AUTÓMATA

REDUCCIONES R's

Todas las Ik que hallan leido una producción pertenecerán a R's

I1

 E' → E.
 E → E.+T

I2

 E → T.
 T → T.∗F

I3

  T→ F.

I5

 F → id.

I9

 E → E+T.
 T → T.∗F

I10

 T → T∗F.

I11

 F → (E).

CONSTRUCCIÓN DE LA TABLA

(0) E' → E
(1) E → E+T
(2) E → T
(3) T → T∗F
(4) T → F
(5) F → (E)
(6) F → id

PRIMEROS Y SIGUIENTES

PRIMEROS(ɑ)={a / a∈⅀ ∧ ɑ → +aβ} ∪ {Ɛ} si  ɑ → Ɛ donde ɑ∈(⅀∪N)*

PRIMEROS (E')={ ( , id }
PRIMEROS (E)={ ( , id }
PRIMEROS (T)={ ( , id }
PRIMEROS (F)={ ( , id }

SIGUIENTES(A)={a / a∈⅀ ∧ S→*ɑAaβ} ∪ {$} si A → Ɛ donde A∈N

SIGUIENTES(E')={ $ }
SIGUIENTES(E)={ ),+,$}
SIGUIENTES(T)={ ),+,∗,$}
SIGUIENTES(F)={ ),+,∗,$}

Lo primero para la creación de la tabla es colocar cada símbolo por columna, a la izquierda los terminales y a la izquierda los no terminales.
Colocar en filas la cantidad de estados Ik.

Ahora llenamos la tabla:
Por cada estado Ik al leer un terminal colocamos en la tabla un Sk (k número del Ik al que finaliza)

Ejemplo:

I0 → id = I5 (S5 en la intersección de 0 con id).
En el caso de los estados Ik que leen un no terminal, solo se coloca el número de el estado Ik al que finaliza.

Ejemplo:

I0 → E = I1 (1 por el estado Ik al que llega).
Las reducciones Rk se usan para los estados finales

Ejemplo:

En I9 se encuentra:

E → E+T.

y esa es la producción (1) de:

(0) E' → E
(1) E → E+T
(2) E → T
(3) T → T∗F
(4) T → F
(5) F → (E)
(6) F → id

Por lo que en la fila 9 (I9) se coloca la reducción R1 en las columnas '),+,$' que son los siguientes de E (parte izquierda de la producción).

SIGUIENTES(E)={ ),+,$}

Como I1 contiene el primer no terminal, es un estado de aceptación en la columna $ que son los siguientes de E' (parte izquierda de la producción).

SIGUIENTES(E')={ $ }

REFERENCIAS

http://www.uhu.es/francisco.moreno/talf/docs/analisis_ascendente.pdf

http://slideplayer.es/slide/3401533/