O algoritmo 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.J. Aycock and R.N. Horspool. Practical Earley Parsing. The Computer Journal, 45:6:620-630, 2002.
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 recursiva.
Exemplos
Considerar a seguinte gramática simples para expressões aritmé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
cada ciclo gera um conjunto de produções Dr gera o símbolo ar produções que podem derivar o próximo símbolo 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.
Categoria:Algoritmos Categoria:Programação dinâmica