El algoritmo de Earley se basa en tres operaciones o acciones que se realizan iterativamente a lo largo del análisis de la cadena de entrada:
ØPredecir. Si tenemos un estado {A --> ... ·B ..., i} es que necesitamos desarrollar B, y por tanto, debemos recorrer las reglas del tipo B --> ... para predecir lo que buscamos.
ØCompletar. Si hemos llegado a un estado completo {A --> ...·, i}, algún estado previo debe haber predicho A y necesitará que le avancemos el puntero · quedando {B --> ...A·..., i}.
ØAvanzar. Una vez realizadas todas las posibles predicciones de símbolos terminales, debemos comprobar que la cadena de entrada posee alguno de ellos y avanzar el puntero correspondiente del elemento {A --> ...a·..., i).
Earley en su forma básica
[Inicialización]
Para cada regla S --> ...
Nuevos = Añadir Elemento({S --> ·...,0}, Agenda[0])
Realizar
Nuevos = 0
Para cada elemento {A --> ...·B...,0} de Agenda[0]
Para cada regla B --> ...
Nuevos = Añadir Elemento({B --> ·...,0}, Agenda[0])
Para cada elemento {A --> ...·,0} de Agenda[0]
Para cada elemento {B --> ...·A...,0} de Agenda[0]
Nuevos = Añadir Elemento({B --> ...A·...,0}, Agenda[0])
mientras Nuevos = 1
[Iteración]
Para
Nuevos = 0
Para cada elemento {A --> ...·a...,i} de Agenda[j-1]
Si a pertenece a Entrada[j]
Nuevos = Añadir Elemento({A --> ...a·...,i}, Agenda[j])
Si Nuevos = 0
Devolver ERROR
Realizar
Nuevos = 0
Para cada elemento {A --> ...·B...,i} de Agenda[j]
Para cada regla B --> ...
Nuevos = Añadir Elemento({B --> ·...,j}, Agenda[j])
Para cada elemento {A --> ...·,i} de Agenda[j]
Para cada elemento {B --> ...·A...,k} de Agenda[i]
Nuevos = Añadir Elemento({B --> ...A·...,k}, Agenda[j])
mientras Nuevos = 1
Si existe algún elemento {S --> ...·,0} en Agenda[N]
Devolver BIEN
si no existe Ç
Devolver ERROR
Ejemplo
P → S # La regla de principio
S → S + M
| M
M → M * T
| T
T → número
La cadena vacía requiere un tratamiento especial, será un símbolo no terminal que no necesita de la operación completar para el avance de su puntero. Cada vez que añadamos un elemento a Agenda[i] del tipo {A --> ...· ..., j} donde el puntero · queda a la izquierda de una cadena vacía, añadiremos también el elemento {A --> ... · ..., j}. Al reconstruir la estructura de la cadena de entrada, en el bucle que recorre los símbolos de la parte derecha de una regla B --> B1 ... Bm debemos distinguir no sólo los terminales y no terminales sino también la cadena vacía, y al llegar al símbolo nulo del elemento {A --> ... ..., j} reduciremos sólo k y proseguiremos.
Algoritmo de reconstrucción del árbol sintáctico del algoritmo de Earley en ausencia de ambigüedades
Reconstruye({A --> B1 B2 ... Bm ·,i}, j)
Añade a Lista De Reglas el elemento (A --> B1 B2 B3 ... Bm)
k = m
l = j
Realizar
Si Bk es terminal
k = k-1
l = l-1
si no
Si existe en Agenda[l] un {Bk --> ·, r} tal que en
Agenda[r] esté {A --> B1 B2 ...·Bk, i}
Reconstruye({B --> ·, r}, l)
k = k-1
l = r
mientras k>0
