Ejemplo Earley

Con esta gramática:
Sp -> S
S -> a S b b
S -> a S b
S -> a S
S -> a

Para la cadena u =aabb, la derivación que describe el software “Kakuy” es:
=> utilizando (Sp -> S )
=> a b b utilizando (S -> a S b b )
=> a a b b utilizando (S -> a )

El árbol que dibuja “Kakuy” es:







Los conjuntos son:(note que en vez de “I1“dice “a:1”, etc.) (note que el puntito • aquí es un guión bajo “_”)























Y tiene una ventana llamada “historial” donde se ve esta larga salida.
(note que le llama kernel a un conjunto de ítemes, símbolop distinguido al símbolo raís, etc.)

Técnica de Jay Earley
Operaciones realizadas durante el reconocimiento de la hilera: a a b b

Estado: Inicial
El Iniciador construye esteestado sin procesar ningún símbolo de la cadena de entrada.
Los items que constituyen el kernel del Estado Inicial se conforman tomando todas las reglas de la gramática en cuyo lado izquierdo aparece el Símbolo Distinguido. El punto se coloca antes del primer símbolo de cada uno de los lados derechos, y el puntero vale 0 dado que las predicciones se están realizando precisamente en este estado.Nuevo kernel:
[Sp -> • S ,0]

Se clausura el ítem 1 del estado 0.
El Predictor crea un ítem por cada regla de la gramática que tenga al símbolo S en el lado izquierdo. El punto se posiciona inmediatamente antes del primer símbolo del lado derecho, y el puntero vale 0, dado que la predicción se está realizando en este estado.
Resultado de la operación:
[S -> • a S b b ,0][S -> • a S b ,0]
[S -> • a S ,0]
[S -> • a ,0]

Dado que en el ítem 2 del estado 0 el punto se encuentra antes de un terminal (a), no se realiza ninguna acción.
Dado que en el ítem 3 del estado 0 el punto se encuentra antes de un terminal (a), no se realiza ninguna acción.
Dado que en el ítem 4 del estado 0 el punto se encuentra antes de un terminal (a), no se realizaninguna acción.
Dado que en el ítem 5 del estado 0 el punto se encuentra antes de un terminal (a), no se realiza ninguna acción.

Dado que aún quedan símbolos en la cadena de entrada, se crea el estado 1.
El Scanner crea el kernel del estado 1 con los items del estado anterior (0) que presentan el punto inmediatamente antes del símbolo "a", pero desplaza el punto un lugar hacia la derecha.
Nuevokernel:
[S -> a • S b b ,0]
[S -> a • S b ,0]
[S -> a • S ,0]
[S -> a • ,0]

Se clausura el ítem 1 del estado 1.
El Predictor crea un ítem por cada regla de la gramática que tenga al símbolo S en el lado izquierdo. El punto se posiciona inmediatamente antes del primer símbolo del lado derecho, y el puntero vale 1, dado que la predicción se está realizando en esteestado.
Resultado de la operación:
[S -> • a S b b ,1]
[S -> • a S b ,1]
[S -> • a S ,1]
[S -> • a ,1]

Se clausura el ítem 2 del estado 1.

El Predictor crea un ítem por cada regla de la gramática que tenga al símbolo S en el lado izquierdo. El punto se posiciona inmediatamente antes del primer símbolo del lado derecho, y el puntero vale 1, dado que la predicción seestá realizando en este estado.
Resultado de la operación:
[S -> • a S b b ,1]
[S -> • a S b ,1]
[S -> • a S ,1]
[S -> • a ,1]

Se clausura el ítem 3 del estado 1.
El Predictor crea un ítem por cada regla de la gramática que tenga al símbolo S en el lado izquierdo. El punto se posiciona inmediatamente antes del primer símbolo del lado derecho, y el puntero vale 1,dado que la predicción se está realizando en este estado.
Resultado de la operación:
[S -> • a S b b ,1]
[S -> • a S b ,1]
[S -> • a S ,1]
[S -> • a ,1]

Se completa el ítem 4 del estado 1.
Dado que el ítem 4 del estado 1 fue predicho en el estado 0, el Completer copia del estado 0 todos los items que tienen el punto inmediatamente antes del No Terminal S y...

Leer documento completo

Regístrate para leer el documento completo.