Esta página ou seção carece de contexto. Este artigo (ou seção) não possui um contexto definido, ou seja, não explica de forma clara e direta o tema que aborda. Se souber algo sobre o assunto edite a página/seção e explique de forma mais clara e objetiva o tema abordado.(outubro de 2023)
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.
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.
