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

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!

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.

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.

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

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.

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.