Algoritmo Earley

O algorítimo de análise gramatical Earley é um tipo de programa que subdivide uma entrada (input) para que um outro possa atuar sobre ela mais comumente usado em linguística computacional, nomeado após seu inventor, Jay Earley. O algoritmo faz uso de programação dinâmica.

Os analisadores gramaticais Earley são interessantes porque podem analisar todas as linguagens livre de contexto. O algoritmo Earley tem tempo de execução O(n³) (onde n é o comprimento da cadeia de caracteres analisada), no caso geral, tempo quadrático (O(n²)) para gramáticas não ambígua, e tempo linear para quase toda as gramáticas LR(k)^?. Seu desempenho é relativamente bom quando as regras são escritas de forma recursivamente.

Exemplos

• Considerar a seguinte gramática simples para expressões aritiméticas:

 P → S      # the start rule
 S → S + M
    | M
 M → M * T
    | T
 T → number

• Com as entradas:

 2 + 3 * 4

• Esta é a seqüência do estado conjuntos:

 (state no.) Production          (Origin) # Comment
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # start rule
 (2)  S → • S + M     (0)    # predict from (1)
 (3)  S → • M         (0)    # predict from (1)
 (4)  M → • M * T     (0)    # predict from (3)
 (5)  M → • T         (0)    # predict from (3)
 (6)  T → • number    (0)    # predict from (5)
 
 == S(1): 2 • + 3 * 4 ==
 (1)  T → number •    (0)    # scan from S(0)(6)
 (2)  M → T •         (0)    # complete from S(0)(5)
 (3)  M → M • * T     (0)    # complete from S(0)(4)
 (4)  S → M •         (0)    # complete from S(0)(3)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)
 
 == S(2): 2 + • 3 * 4 ==
 (1)  S → S + • M     (0)    # scan from S(1)(5)
 (2)  M → • M * T     (2)    # predict from (1)
 (3)  M → • T         (2)    # predict from (1)
 (4)  T → • number    (2)    # predict from (3)
 
 == S(3): 2 + 3 • * 4 ==
 (1)  T → number •    (2)    # scan from S(2)(4)
 (2)  M → T •         (2)    # complete from S(2)(3)
 (3)  M → M • * T     (2)    # complete from S(2)(2)
 (4)  S → S + M •     (0)    # complete from S(2)(1)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)
 
 == S(4): 2 + 3 * • 4 ==
 (1)  M → M * • T     (2)    # scan from S(3)(3)
 (2)  T → • number    (4)    # predict from (1)
 
 == S(5): 2 + 3 * 4 • ==
 (1)  T → number •    (4)    # scan from S(4)(2)
 (2)  M → M * T •     (2)    # complete from S(4)(1)
 (3)  M → M • * T     (2)    # complete from S(2)(2)
 (4)  S → S + M •     (0)    # complete from S(2)(1)
 (5)  S → S • + M     (0)    # complete from S(0)(2)
 (6)  P → S •         (0)    # complete from S(0)(1)

• O estado (P → S •, 0) representa um parse concluído. Este estado também aparece em S (3) e S (1), que são frases completas.

Etapa 1: construção de D0: primeiro conjunto de produções

• produções que partem de S (1)
• produções que podem ser aplicadas (2)
• em sucessivas derivações mais à esquerda (a partir de S)

 D0 = ∅
 para toda S → α ∈ P (1)
 faça D0 = D0 ∪ { S → •α/0 }
 repita para toda A → •Bβ/0 ∈ D0 (2)
 faça para toda B → φ ∈ P
 faça D0 = D0 ∪ { B → •φ/0 }
 até que o cardinal de D0 não aumente

Etapa 2: construção dos demais conjuntos de produção

• n = w conjuntos de produção a partir de D0
• ao gerar ar, constrói Dr: produções que podem gerar ar+1

 para r variando de 1 até n (1)
 faça Dr = ∅;
 para toda A → α•arβ/s ∈ Dr-1 (2)
 faça Dr = Dr ∪ { A → αar•β/s };
 repita
 para toda A → α•Bβ/s ∈ Dr (3)
 faça para toda B → φ ∈ P
 faça Dr = Dr ∪ { B → •φ/r }
 para toda A → α•/s de Dr (4)
 faça para toda B → β•Aφ/k ∈ Ds
 faça Dr = Dr ∪ { B → βA•φ/k }
 atéque o cardinal de Dr não aumente

1. cada ciclo gera um conjunto de produções Dr
2. gera o símbolo ar
3. produções que podem derivar o próximo símbolo
4. uma subpalavra de w foi reduzida à variável A

• inclui em Dr todas as produções de Ds que referenciaram •A;

Etapa 3: condição de aceitação da entrada.

• uma produção da forma S → α•/0 pertence a Dn
• w foi aceita
• S → α•/0 é uma produção que
• parte do símbolo inicial S
• foi incluída em D0 ("/0")
• todo o lado direito da produção foi analisado com sucesso
• ("•" está no final de α)

• Otimização do Algoritmo de Early
• ciclos repita-até
• podem ser restritos exclusivamente às produções recentemente incluídas em Dr ou em D0 ainda não-analisadas.

Referências

• J. Aycock and R.N. Horspool. Practical Earley Parsing. The Computer Journal, 45:6:620-630, 2002.