Recuperando uma floresta de análise de um analisador Earley?

25

Recentemente, eu estava lendo o analisador Earley e acho que é um dos algoritmos mais elegantes que já vi até hoje. No entanto, o algoritmo em seu sentido tradicional é um reconhecedor e não um analisador, o que significa que ele pode detectar se uma sequência corresponde a um CFG específico, mas não produz uma árvore de análise para ele. Minha pergunta é como recuperar não uma árvore de análise , mas a floresta de análise de todos os possíveis analisa a sequência de entrada fornecida.

Em "Técnicas de análise: um guia prático" de Grune e Jacob, eles ilustram um algoritmo que pode ser usado para recuperar uma floresta de análise a partir do resultado do reconhecedor Earley, mas é baseado no método de análise de Unger, cujo tempo de execução é O (n k + 1 ), onde k é a duração da maior produção na gramática. Isso significa que o tempo de execução não é um polinômio no tamanho da gramática. Além disso, o artigo original de Earley sobre o algoritmo, que sugere um algoritmo para recuperar florestas de análise, está incorreto (consulte, por exemplo, página 762 deste artigo de Tomita), embora muitas fontes ainda o citem como a maneira apropriada de recuperar a floresta de análise .

Minha pergunta é se é possível, em tempo polinomial, recuperar uma floresta de análise para uma determinada string de entrada. Eu encontrei um documento aqui que fornece um algoritmo para produzir representações de floresta de análise de tamanho cúbico para qualquer análise usando uma simulação de um PDA; portanto, parece que isso deve ser possível, mas ainda não encontrei nenhuma maneira de fazer isso. Idealmente, eu gostaria de fazer isso sem converter a gramática de entrada em CNF (o que realmente resolveria o problema), já que a floresta de análise resultante seria bastante confusa.

Obrigado por qualquer ajuda que você pode oferecer!

templatetypedef
fonte
Ele precisa ser um algoritmo baseado na análise de Earley ou você não se importaria de usar outro analisador geral de CFG?
Alex dez Brink
1
Eu preferiria um algoritmo baseado no analisador Earley. Eu tenho ministrado um curso de compiladores e passei alguns dias tentando localizar uma resposta para essa pergunta, e isso está realmente me incomodando.
templatetypedef
Os tempos de execução exponenciais não são surpreendentes, pois as palavras podem ter exponencialmente muitas árvores de análise. De fato, eles podem ter muitos infinitos se você permitir CFGs arbitrários.
Raphael
3
@Raphael O papel das florestas de análise é precisamente ter um mecanismo de compartilhamento que permita representar todas as árvores, mesmo infinitas, com uma estrutura finita, com pequena complexidade de espaço. Obviamente, isso pode deixar algum trabalho para os lenhadores.
babou
Você pode querer olhar para Marpa . É um módulo Perl e uma biblioteca C que implementa um analisador Earley e tem suporte total à floresta de análise.
Hippietrail 19/09/2014

Respostas:

14

Fazer isso naturalmente dependeria da representação correta para uma "floresta compactada" que representa todas as árvores de análise para uma determinada frase.

Eu acho que o lugar que você quer começar a procurar é a tese de Joshua Goodman (analisando de dentro para fora, Harvard, 1999). Basicamente, a idéia é que você pode definir um algoritmo de análise sob um certo semirramento. Dependendo da semirrada, você seria capaz de calcular todo tipo de quantidades e estruturas em vez da árvore de análise simples (como reconhecedor ou analisador). Um semi-contrato que você pode definir (o que Goodman faz em sua tese) é um semi-contrato em que os valores são conjuntos de análises. Quando você termina de analisar uma frase, você obtém todas as árvores de análise no nó principal de análise.

Novamente, você deve ter cuidado ao tornar isso possível através da representação correta.

gmmodeler
fonte
Obrigado pela referência! Parece um ótimo recurso e vou passar algum tempo olhando para ele.
templatetypedef
8

Há um documento que descreve como fazê-lo:

Análise ao estilo SPPF da Earley Recognisers de Elisabeth Scott

Ele descreve como construir uma floresta de análise binarizada em tempo cúbico.

Angelo Borsotti
fonte
2
Esse link agora parece estar quebrado agora. Você tem uma referência (título do trabalho, onde publicado, lista de autores) e / ou um link atualizado?
DW
1
Veja web.archive.org/web/20130508170633/http://thor.info.uaic.ro/… : "Análise ao estilo SPPF dos reconhecedores Earley", Elizabeth Scott. Outro link: dinhe.net/~aredridel/.notmine/PDFs/… .
a3nm
Esta é a resposta correta para a pergunta "como obter uma floresta de análise de um reconhecedor Earley".
tjvr
Há uma boa implementação disso em JS aqui: joshuagrams.github.io/pep
tjvr
O que se entende por binarizado neste contexto?
Bruce Adams
6

Você nunca precisa de CNF. Ele tem a desvantagem de alterar a estrutura gramatical. Mas você precisa introduzir não terminais intermediários para que nenhum lado direito seja maior que 2 (formato 2), pois o comprimento do RHS determina a complexidade. A melhor tentativa de explicar intuitivamente é, se a memória serve, um artigo de Beau Shiel, "Observations on Context Free Parsing", publicado em 1976 em uma conferência lingüística computacional. O algoritmo de Earley usa 2 formas implicitamente. Está apenas oculto no algoritmo. Com relação à recuperação e manuseio da floresta de análise, você deve consultar a web em "analisando a floresta de interseção". Na verdade, é muito direto. Muitos artigos estão na Web, se você obtiver (de citações ou tabelas de conteúdo) os títulos ou autores para pesquisá-los diretamente.

Na verdade, você pode fazer muito mais que o CF e ainda obter florestas de análise em tempo polinomial. A questão é, às vezes: o que você pode fazer com isso depois de ter?

Um objetivo do último artigo mencionado é mostrar que algoritmos complexos (como GLR) não estão necessariamente comprando nada no tempo ou no espaço e podem alterar sua floresta de análise.

Uma observação sobre o ensino. Acho que Earley, seminal como era, é muito complicado para o ensino e pode ser substituído por algoritmos mais simples, com essencialmente o mesmo conteúdo educacional. Ensinar é sobre conceitos ou tecnologia. No algoritmo de Earley, os conceitos essenciais estão ocultos na complexidade dos detalhes e, do ponto de vista da tecnologia, estão desatualizados. Foi um ótimo artigo, mas não significa que seja a melhor abordagem pedagógica.

Pode haver mais informações na literatura de linguística computacional do que nos canais usuais de ciência da computação. Eu não tenho o livro de Ceriel-Grune-Jacobs, mas ficaria surpreso se eles não tivessem todas as referências apropriadas (embora eu não tenha certeza sobre seus critérios de seleção).


Complemento após uma solicitação em um comentário (7 de julho de 2013)

Esse complemento diz respeito à existência de algoritmos mais simples que os de Earley.

Como eu disse, pesquisar na web em "analisar floresta de interseção" deve fornecer rapidamente referências, das quais você pode ir além.

A idéia básica é que todos os caminhos que analisam a construção de uma floresta compartilhada nada mais são do que a antiga construção de interseção de Bar Hillel, Perles e Shamir para uma linguagem regular e uma linguagem livre de contexto, usando um autômato finito e uma gramática livre de contexto. Dada a gramática CF, você aplica a construção a um autômato trivial que reconhece apenas sua sequência de entrada. Isso é tudo. A floresta compartilhada é apenas a gramática da interseção. Está relacionado à gramática original através de um homomorfismo, reconhece apenas a sequência especificada, mas com todas as árvores de análise da gramática original até esse homomorfismo (isto é, renomeação simples de não terminais).

A gramática resultante contém muitas coisas inúteis, não terminais e regras, inacessíveis ao axioma (que não podem ser encontradas em uma sequência derivada do símbolo inicial) ou que não são produtivas (não podem ser derivadas em um terminal corda).

Então, você precisa limpá-lo com uma boa escova no final (possivelmente longa, mas algoritmicamente simples), ou pode tentar melhorar a construção para que haja menos cotão inútil a ser escovado no final.

Por exemplo, a construção do CYK é exatamente isso, mas organizada para que todas as regras e não terminais criados sejam produtivos, embora muitos possam ser inacessíveis. Isso é de se esperar de uma técnica de baixo para cima.

Técnicas de cima para baixo (como as baseadas em LR (k)) evitarão regras inacessíveis e não terminais, mas criarão improdutivas.

Muito da escovação pode ser alcançada com o uso adequado de ponteiros, eu acho, mas não vejo isso há muito tempo.

Todos os algoritmos existentes realmente seguem essencialmente esse modelo. Então esse é realmente o cerne da questão, e é muito simples. Então, por que enterrá-lo em complexidade?

Muitas "otimizações" são propostas na literatura, muitas vezes baseadas na família de construção de analisadores LR (k), LL (k), possivelmente com algum fatoramento estático dessas construções (Earley não possui fatoramento estático). Na verdade, poderia ser aplicado a todas as técnicas conhecidas, incluindo os antigos analisadores de precedência. Coloquei "otimização" entre aspas, porque geralmente não está claro o que você está otimizando, ou mesmo se você está realmente otimizando ou se o benefício da melhoria vale a complexidade adicional do seu analisador. Você encontrará poucos dados objetivos, formais ou experimentais, sobre isso (há alguns), mas muitas outras reivindicações. Não estou dizendo que não há nada de interessante. Existem algumas idéias inteligentes.

Agora, depois de conhecer a idéia básica, as "otimizações" ou melhorias podem ser introduzidas estaticamente (possivelmente incrementalmente) construindo um autômato push-down a partir da gramática, seguindo o tipo de técnica de construção do analisador em que você está interessado e aplicando a construção de produtos cruzados para interseção com esse autômato (quase o mesmo que fazer com a gramática) ou com uma gramática derivada desse autômato.

Então você pode introduzir sinos e assobios, mas isso é principalmente detalhes tecnológicos.

O Philosophiæ Naturalis Principia Mathematica de Isaac Newton é declaradamente uma grande peça de física e matemática. Eu não acho que esteja na lista de leitura de muitos estudantes. Todas as outras coisas são iguais, não acho que seja muito útil ensinar o algoritmo de Earley, embora seja uma peça histórica importante. Os alunos têm o suficiente para aprender como é. Correndo o risco de ser derrubado por muitas pessoas, penso o mesmo no artigo de Knuth LR (k). É uma excelente peça de análise teórica e provavelmente uma leitura importante para um teórico. Duvido fortemente que seja tão essencial para a construção de analisadores, dado o estado atual da tecnologia, tanto de hardware quanto de software. Os tempos são passados ​​em que a análise era uma parte significativa do tempo de compilação, ou quando a velocidade dos compiladores era um problema crítico (eu conhecia uma empresa que morreu de custos de compilação há cerca de 30 anos). O especialista em análise pode querer aprender que o conhecimento especializado em algum momento, mas o estudante médio em ciência da computação, programação ou engenharia não precisa dele.

Se os alunos precisam dedicar mais tempo à análise, existem outras extensões que podem ser mais úteis e formativas, como as usadas na lingüística computacional. O primeiro papel do ensino é extrair as idéias simples que estruturam o conhecimento científico, não forçar os alunos a sofrer o que os cientistas da pesquisa sofreram (exceto os alunos de doutorado: é um rito de passagem :-).

Licença CC BY-SA 3.0 do autor

babou
fonte
2
"Earley ... é muito complicado para o ensino e pode ser substituído por algoritmos mais simples ...". Você poderia fornecer um exemplo de um algoritmo tão simples?
Wjl
@wjl Eu respondo a você em um adendo à resposta acima. Não aponto para um algoritmo específico, embora você possa encontrar alguns na literatura se fizer alguma pesquisa, como recomendo. Tentei explicar por que é muito fácil criar algoritmos mais simples e eficientes. Earley's é provavelmente o mais complexo de todos. Explicando o Bar Hillel et al. construção é de cerca de meia página do livro, digamos uma página com a prova.
babou 07/07/2013
@wjl Responder ao seu pedido levou algum tempo. Isso te ajudou? . . . . . Se você queria um algoritmo real, existe um no último link da pergunta inicial.
babou 9/07/2013
Sim obrigado; Aprecio os detalhes extras. Estou trabalhando em uma biblioteca analisadora generalizada para algum trabalho que estou fazendo e tenho feito uma tonelada de pesquisas em diferentes algoritmos. Atualmente, estou inclinado a uma implementação no estilo Early, pois, para mim, parecia ser um algoritmo muito fácil de entender e é fácil estender para gramáticas conjuntivas e terminais "caixa preta" (possivelmente sensíveis ao contexto). Eu deslizei e imprimi alguns dos papéis que você apontou; mas ainda não os li a sério.
Wjl
@wjl Se é isso que você está fazendo, observe os seguintes tópicos: linguagens levemente sensíveis ao contexto, sistemas de reescrita linear sem contexto (LCFRS) e gramáticas de concatenação de intervalo. Não tenho certeza se entendi o que é um terminal "black box". - - email: babou em inbox.com. - -
babou
5

O artigo que descreve como construir uma floresta de análise binarizada em tempo cúbico (mencionado no post de Angelo Borsotti) é: "Análise de estilo SPPF de reconhecedores de Earley", de Elizabeth Scott. Você pode encontrá-lo aqui: http://dx.doi.org/10.1016/j.entcs.2008.03.044

Neste artigo, é descrita a construção de uma floresta de análise empacotada compartilhada (SPPF), que representa todas as possíveis árvores de análise. As subárvores são compartilhadas sempre que possível e os nós correspondentes a diferentes derivações da mesma substring da mesma não-terminal são combinados.

êider
fonte
Obrigado pelo ponteiro. Construir florestas de análise binarizadas em tempo cúbico é padrão. A binarização é a única maneira de obter tempo cúbico, de modo que a observação do OP sobre a complexidade do tamanho da gramática é irrelevante. Outra questão é entender de que maneira a floresta de análise é binarizada. Isso pode depender do algoritmo. Outras questões são a quantidade de compartilhamento na floresta compartilhada e a eficiência prática da estratégia de análise (Earley pode ser uma má idéia). Tudo isso é desenvolvido na última referência do OP. Uma visão formal geral da questão é esboçada em minha resposta.
babou
1

Gostaria de repetir as respostas acima, sugerindo que você leia este documento:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Eu gostaria de me qualificar dizendo que implementei o algoritmo neste documento e acredito que há um erro. Em particular, a primeira frase do segundo parágrafo da seção 4. Os rótulos anteriores que você cria para o que Earley chamaria de fase de "varredura" devem apontar de p para q e não o contrário.

Em particular, a seguinte linha:

Defina E0 como os itens (S :: = · α, 0). Para i> 0 inicialize Ei adicionando o item p = (A :: = αai · β, j) para cada q = (A :: = α · aiβ, j) i Ei − 1 e, se α =, criando um ponteiro predecessor rotulado i - 1 de q para p

Deve ler "de p para q" e não "de q para p"

Eu implementei o algoritmo como é originalmente declarado, o que me deu erros em alguns casos de teste criados à mão, que foram corrigidos depois que eu mudei a direção do ponteiro aqui.

Jeremy Dohmann
fonte