Algoritmo de Earley

El algoritmo de Earley^[1] 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.

Notas

1. ↑ Jay Earley, An efficient context-free parsing algorithm, Communication of the ACM, 13(2), 1970

Ejemplo

Considere la siguiente gramática simple para expresiones aritméticas:

 P → S      # La regla de principio
 S → S + M
    | M
 M → M * T
    | T
 T → número

Con la entrada:

 2 + 3 * 4

Esto es la secuencia de conjuntos de estados:

 (declare no.) Producción       (Origen) # Comentario
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # regla de principio
 (2)  S → • S + M     (0)    # predecir de (1)
 (3)  S → • M         (0)    # predecir de (1)
 (4)  M → • M * T     (0)    # predecir de (3)
 (5)  M → • T         (0)    # predecir de (3)
 (6)  T → • número    (0)    # predecir de (5)
 
 == S(1): 2 • + 3 * 4 ==
 (1)  T → número  •   (0)    # scan de S(0)(6)
 (2)  M → T •         (0)    # completo de S(0)(5)
 (3)  M → M • * T     (0)    # completo de S(0)(4)
 (4)  S → M •         (0)    # completo de S(0)(3)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)
 
 == S(2): 2 + • 3 * 4 ==
 (1)  S → S + • M     (0)    # scan from S(1)(5)
 (2)  M → • M * T     (2)    # predecir de (1)
 (3)  M → • T         (2)    # predecir de (1)
 (4)  T → • número    (2)    # predecir de (3)
 
 == S(3): 2 + 3 • * 4 ==
 (1)  T → número  •   (2)    # scan from S(2)(4)
 (2)  M → T •         (2)    # completo de S(2)(3)
 (3)  M → M • * T     (2)    # completo de S(2)(2)
 (4)  S → S + M •     (0)    # completo de S(2)(1)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)
 
 == S(4): 2 + 3 * • 4 ==
 (1)  M → M * • T     (2)    # scan from S(3)(3)
 (2)  T → • número    (4)    # predecir de (1)
 
 == S(5): 2 + 3 * 4 • ==
 (1)  T → número  •   (4)    # scan from S(4)(2)
 (2)  M → M * T •     (2)    # completo de S(4)(1)
 (3)  M → M • * T     (2)    # completo de S(2)(2)
 (4)  S → S + M •     (0)    # completo de S(2)(1)
 (5)  S → S • + M     (0)    # completo de S(0)(2)
 (6)  P → S •         (0)    # completo de S(0)(1)

El estado (P → S •, 0) representa un análisis completado. Este estado también aparece en S(3) y S(1), que son sentencias completas.