Algoritmo Earley

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes (desde junho de 2009). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Ambox question.svg
Esta página ou seção carece de contexto (desde dezembro de 2014).

Este artigo (ou seção) não possui um contexto definido, ou seja, não explica de forma clara e dire(c)ta 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.

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[editar | editar código-fonte]

  • 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


  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[editar | editar código-fonte]