Algoritmo de Earley

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 19:57 13 nov 2019 por НСНУ (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.
Ir a la navegación Ir a la búsqueda

El algoritmo de Earley[1]​ es un algoritmo no determinista de análisis sintáctico para las gramáticas libres de contexto descrito originalmente por el informático estadounidense Jay Earley en 1970. 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 deterministas 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.