Diagrama Earley

Es un algoritmo no determinístico de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por Jay Earley. Se ordena, a los lados de los algoritmos CYK y GLR, entre los algoritmos que usan la noción de reparto (de cálculos y de estructuras) y que construyen todos los análisis posibles de una frase (y no sólo uno de estos análisis). Es uno de los algoritmos no determinísticos que usan ideas de la programación dinámica.

En caso de que la gramática fuese ambigüa (algo habitual en gramáticas del lenguaje natural), el tiempo de reconocimiento será proporcional al cubo de la longitud de la cadena de entrada, aunque para ciertas gramáticas el tiempo medio se puede reducir a cuadrático e incluso lineal.

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