Earley parser - Earley parser

Na ciência da computação , o analisador Earley é um algoritmo para analisar strings que pertencem a uma determinada linguagem livre de contexto , embora (dependendo da variante) ele possa sofrer problemas com certas gramáticas anuláveis. O algoritmo, que leva o nome de seu inventor, Jay Earley , é um analisador de gráficos que usa programação dinâmica ; é usado principalmente para análise em linguística computacional . Foi introduzido pela primeira vez em sua dissertação em 1968 (e mais tarde apareceu em uma forma abreviada e mais legível em um jornal).

Os analisadores Earley são atraentes porque podem analisar todas as linguagens livres de contexto, ao contrário dos analisadores LR e analisadores LL , que são mais comumente usados ​​em compiladores, mas que só podem lidar com classes restritas de linguagens. O analisador Earley executa em tempo cúbico no caso geral , onde n é o comprimento da string analisada, tempo quadrático para gramáticas não ambíguas e tempo linear para todas as gramáticas livres de contexto determinísticas . Ele tem um desempenho particularmente bom quando as regras são escritas recursivamente à esquerda .

Reconhecedor Earley

O algoritmo a seguir descreve o reconhecedor Earley. O reconhecedor pode ser facilmente modificado para criar uma árvore de análise conforme ele reconhece e, dessa forma, pode ser transformado em um analisador.

O algoritmo

Nas descrições a seguir, α, β e γ representam qualquer sequência de terminais / não terminais (incluindo a sequência vazia ), X e Y representam não terminais únicos e a representa um símbolo terminal.

O algoritmo de Earley é um algoritmo de programação dinâmica de cima para baixo . A seguir, usamos a notação de pontos de Earley: dada uma produção X → αβ, a notação X → α • β representa uma condição na qual α já foi analisado e β é esperado.

A posição de entrada 0 é a posição anterior à entrada. A posição de entrada n é a posição após aceitar o n- ésimo token. (Informalmente, as posições de entrada podem ser consideradas como locais nos limites do token .) Para cada posição de entrada, o analisador gera um conjunto de estados . Cada estado é uma tupla (X → α • β, i ), consistindo em

  • a produção atualmente sendo combinada (X → α β)
  • a posição atual nessa produção (representada pelo ponto)
  • a posição i na entrada em que o casamento desta produção começou: a posição de origem

(O algoritmo original de Earley incluía um look-ahead no estado; pesquisas posteriores mostraram que isso tinha pouco efeito prático na eficiência da análise e, subsequentemente, foi descartado da maioria das implementações.)

O estado definido na posição de entrada k é denominado S ( k ). O analisador é propagado com S (0) consistindo apenas na regra de nível superior. O analisador então executa repetidamente três operações: previsão , varredura e conclusão .

  • Predição : Para cada estado em S ( k ) da forma (X → α • Y β, j ) (onde j é a posição de origem como acima), adicione (Y → • γ, k ) a S ( k ) para cada produção na gramática com Y do lado esquerdo (Y → γ).
  • Varredura : Se a é o próximo símbolo no fluxo de entrada, para cada estado em S ( k ) da forma (X → α • a β, j ), adicione (X → α a • β, j ) a S ( k +1).
  • Conclusão : Para cada estado em S ( k ) da forma (Y → γ •, j ), encontre todos os estados em S ( j ) da forma (X → α • Y β, i ) e adicione (X → α Y • β, i ) para S ( k ).

Estados duplicados não são adicionados ao conjunto de estados, apenas novos. Essas três operações são repetidas até que nenhum novo estado possa ser adicionado ao conjunto. O conjunto é geralmente implementado como uma fila de estados a serem processados, com a operação a ser executada dependendo do tipo de estado.

O algoritmo aceita se (X → γ •, 0) acaba em S ( n ), onde (X → γ) é o nível superior-regra e n o comprimento de entrada, caso contrário, rejeita.

Pseudo-código

Adaptado de Speech and Language Processing por Daniel Jurafsky e James H. Martin, 

DECLARE ARRAY S;

function INIT(words)
    S ← CREATE_ARRAY(LENGTH(words) + 1)
    for k ← from 0 to LENGTH(words) do
        S[k] ← EMPTY_ORDERED_SET

function EARLEY_PARSE(words, grammar)
    INIT(words)
    ADD_TO_SET((γ → •S, 0), S[0])
    for k ← from 0 to LENGTH(words) do
        for each state in S[k] do  // S[k] can expand during this loop
            if not FINISHED(state) then
                if NEXT_ELEMENT_OF(state) is a nonterminal then
                    PREDICTOR(state, k, grammar)         // non_terminal
                else do
                    SCANNER(state, k, words)             // terminal
            else do
                COMPLETER(state, k)
        end
    end
    return chart

procedure PREDICTOR((A → α•Bβ, j), k, grammar)
    for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do
        ADD_TO_SET((B → •γ, k), S[k])
    end

procedure SCANNER((A → α•aβ, j), k, words)
    if a ⊂ PARTS_OF_SPEECH(words[k]) then
        ADD_TO_SET((A → αa•β, j), S[k+1])
    end

procedure COMPLETER((B → γ•, x), k)
    for each (A → α•Bβ, j) in S[x] do
        ADD_TO_SET((A → αB•β, j), S[k])
    end

Exemplo

Considere a seguinte gramática simples para expressões aritméticas: 

<P> ::= <S>      # the start rule
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"

Com a entrada: 

2 + 3 * 4

Esta é a sequência de conjuntos de estados:

(estado no.) Produção (Origem) Comente
S (0): • 2 + 3 * 4
1 P → • S 0 regra de início
2 S → • S + M 0 prever de (1)
3 S → • M 0 prever de (1)
4 M → • M * T 0 prever de (3)
5 M → • T 0 prever de (3)
6 T → • número 0 prever de (5)
S (1): 2 • + 3 * 4
1 T → número • 0 digitalizar de S (0) (6)
2 M → T • 0 completo de (1) e S (0) (5)
3 M → M • * T 0 completo de (2) e S (0) (4)
4 S → M • 0 completo de (2) e S (0) (3)
5 S → S • + M 0 completo de (4) e S (0) (2)
6 P → S • 0 completo de (4) e S (0) (1)
S (2): 2 + • 3 * 4
1 S → S + • M 0 digitalizar de S (1) (5)
2 M → • M * T 2 prever de (1)
3 M → • T 2 prever de (1)
4 T → • número 2 prever de (3)
S (3): 2 + 3 • * 4
1 T → número • 2 digitalizar de S (2) (4)
2 M → T • 2 completo de (1) e S (2) (3)
3 M → M • * T 2 completo de (2) e S (2) (2)
4 S → S + M • 0 completo de (2) e S (2) (1)
5 S → S • + M 0 completo de (4) e S (0) (2)
6 P → S • 0 completo de (4) e S (0) (1)
S (4): 2 + 3 * • 4
1 M → M * • T 2 digitalizar de S (3) (3)
2 T → • número 4 prever de (1)
S (5): 2 + 3 * 4 •
1 T → número • 4 digitalizar de S (4) (2)
2 M → M * T • 2 completo de (1) e S (4) (1)
3 M → M • * T 2 completo de (2) e S (2) (2)
4 S → S + M • 0 completo de (2) e S (2) (1)
5 S → S • + M 0 completo de (4) e S (0) (2)
6 P → S • 0 completo de (4) e S (0) (1)

O estado (P → S •, 0) representa uma análise completa. Este estado também aparece em S (3) e S (1), que são sentenças completas.

Construindo a floresta de análise

A dissertação de Earley descreve resumidamente um algoritmo para construir árvores de análise, adicionando um conjunto de ponteiros de cada não terminal em um item de Earley de volta aos itens que fizeram com que ele fosse reconhecido. Mas Tomita percebeu que isso não leva em consideração as relações entre os símbolos, então se considerarmos a gramática S → SS | be a string bbb, apenas observa que cada S pode corresponder a um ou dois b's e, portanto, produz derivações espúrias para bb e bbbb, bem como as duas derivações corretas para bbb.

Outro método é construir a floresta de análise conforme você avança, aumentando cada item Earley com um ponteiro para um nó de floresta de análise compactada compartilhada (SPPF) rotulado com um triplo (s, i, j) onde s é um símbolo ou um LR (0 ) item (regra de produção com ponto), ei e j fornecem a seção da string de entrada derivada por este nó. O conteúdo de um nó é um par de ponteiros filhos dando uma única derivação ou uma lista de nós "empacotados", cada um contendo um par de ponteiros e representando uma derivação. Os nós SPPF são únicos (há apenas um com um determinado rótulo), mas podem conter mais de uma derivação para análises ambíguas . Portanto, mesmo se uma operação não adicionar um item Earley (porque ele já existe), ela ainda pode adicionar uma derivação à floresta de análise do item.

  • Os itens previstos têm um ponteiro SPPF nulo.
  • O scanner cria um nó SPPF que representa o não terminal que está digitalizando.
  • Então, quando o scanner ou completador avança um item, eles adicionam uma derivação cujos filhos são o nó do item cujo ponto foi avançado e aquela para o novo símbolo que foi avançado (o item não terminal ou concluído).

Os nós SPPF nunca são rotulados com um item LR (0) completo: em vez disso, eles são rotulados com o símbolo que é produzido para que todas as derivações sejam combinadas em um nó, independentemente da produção alternativa de onde vêm.

Otimizações

Philippe McLean e R. Nigel Horspool em seu artigo "A Faster Earley Parser" combinam a análise Earley com a análise LR e alcançam uma melhoria em uma ordem de magnitude.

Veja também

Citações

Outros materiais de referência

Implementações

C, C ++

Haskell

Java

  • [1] - uma implementação Java do algoritmo Earley
  • PEN - uma biblioteca Java que implementa o algoritmo Earley
  • Pep - uma biblioteca Java que implementa o algoritmo Earley e fornece gráficos e árvores de análise como artefatos de análise
  • digitalheir / java-probabilistic-earley-parser - uma biblioteca Java que implementa o algoritmo probabilístico de Earley, que é útil para determinar a árvore de análise mais provável a partir de uma frase ambígua

C #

JavaScript

OCaml

  • Earley simples - Uma implementação de um algoritmo de análise simples do tipo Earley, com documentação.

Perl

  • Marpa :: R2 - um módulo Perl . Marpa é um algoritmo de Earley que inclui as melhorias feitas por Joop Leo e por Aycock e Horspool.
  • Parse :: Earley - um módulo Perl implementando o algoritmo original de Jay Earley

Pitão

  • Lark - uma implementação procedural orientada a objetos de um analisador Earley, que gera um SPPF.
  • NLTK - um kit de ferramentas Python com um analisador Earley
  • Spark - uma pequena estrutura de linguagem orientada a objetos para Python implementando um analisador Earley
  • spark_parser - versão atualizada e empacotada do analisador Spark acima, que é executado em Python 3 e Python 2
  • earley3.py - uma implementação autônoma do algoritmo em menos de 150 linhas de código, incluindo geração da floresta de análise e amostras
  • tjr_python_earley_parser - um analisador Earley mínimo em Python

Lisp Comum

Esquema, Raquete

Volfrâmio

  • ProperEarleyParser - Uma implementação mínima básica de um analisador Earley na linguagem de programação Wolfram com alguns casos de teste essenciais.

Recursos