Algoritmo Earley

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde junho de 2009).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Ambox question.svg
Esta página ou seção carece de contexto (desde outubro 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 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[editar | editar código-fonte]