Como reconstruo a floresta de árvores de sintaxe a partir do vetor Earley?

Usar o vetor Earley como reconhecedor é bastante direto: quando o final da string é atingido, basta verificar se uma produção axiomática concluída foi iniciada na posição 0. Se você tiver pelo menos uma, a string será aceita.

Usar o vetor Earley para reconstruir a (s) árvore (s) de análise é menos óbvio. Na verdade, não consigo descobrir como funcionaria um procedimento algorítmico; além disso, as únicas referências que encontrei eram vagas ou super-técnicas. Alguém poderia lançar alguma luz sobre isso?

Estou usando terminologia e anotações do trabalho de Earley . É possível que a descrição que você leu seja diferente.

Parece frequente que algoritmos gerais de análise de CF sejam apresentados pela primeira vez na forma de um reconhecedor e, em seguida, o gerenciamento de informações necessário para realmente construir árvores de análise e florestas de análise seja adicionado como uma reflexão tardia. Um motivo pode ser que manter as informações necessárias para construir a floresta compartilhada exija espaço cúbico que é o comprimento da cadeia de entrada que está sendo analisada, mas o requisito de espaço é apenas quadrado para reconhecimento , quando essas informações não são preservadas. A razão para esse aumento da complexidade do espaço é bastante simples: o tamanho da floresta de análise pode ser cúbico.$O(n^3)$$n$$O(n^2)$

A pior complexidade do tempo do caso é , como é bem conhecido.$O(n^3)$

A melhor referência para o algoritmo de Earley é , obviamente, o artigo de Earley , mas não é muito explícito sobre a construção da floresta de análise. Isso pode realmente ser um negócio confuso, muito mais do que a conversa rápida da seção 7 página 101 vai aparecer. Para ser verdade, Earley não fala de floresta de análise, ou de floresta, mas de " uma representação fatorada de todas as possíveis árvores de análise ". E há uma boa razão para isso: se ele tentasse produzir uma floresta de acordo com sua gramática, sua complexidade de espaço (daí o tempo) aumentaria para onde é o tamanho do maior governar do lado direito. É por isso que outros algoritmos usam gramáticas na forma binária (não necessariamente na forma normal de Chomsky (CNF)).$O(n^{s+1})$$s$

Na verdade, Earley usa a forma binária implicitamente , porque isso é necessário para a complexidade do tempo cúbico. Esse é um dos principais papéis da regra nos estados. Mas essa forma binária implícita produz análise e florestas de acordo com a gramática binarizada, não com a gramática original, que, temo, é uma importante fonte de obscuridade. Isso é detalhado mais abaixo.

Uma boa maneira de entender como a floresta é obtida é provavelmente analisá-la em um caso mais simples, o algoritmo CYK . Também é frequentemente descrito como um reconhecedor, e o aspecto do analisador é adicionado no final. Você pode olhar para a descrição na wikipedia. A informação necessária para construir a floresta é o que eles armazenam na tabela de "indicadores retroativos". Backpointers são essencialmente indicadores de substrings (um símbolo associado) que formam os constituintes de uma string de acordo com alguma regra. Eles oferecem todas as formas possíveis de analisar uma substring. Lembre-se de que o CYK usa a forma binária, geralmente CNF, para que as coisas sejam mais simples. O analisador CYK tem fundamentalmente a mesma estrutura de programação dinâmica que Earley, mas é muito mais simples. Portanto, entendê-lo bem pode ser uma ajuda significativa.

Voltando ao algoritmo de Earley, não acredito que você precise do vetor Earley para decidir a aceitação ou construir árvores e florestas de análise. O que Earley chama de vetor em seu artigo aparece apenas na página 97, no terceiro parágrafo da implementação. É apenas um dispositivo para acelerar a pesquisa de estados apontando para uma determinada posição de string k, a fim de obter uma melhor complexidade. Mas todas as informações estão nos conjuntos de estados, implementados como listas de estados. No entanto, essas informações não são suficientes para construir a floresta de árvores de análise, porque o algoritmo não acompanha o (s) caminho (s) que um estado pode ser obtido. De fato, o vetor é usado para descartar eficientemente um estado já encontrado, independentemente de como foi encontrado.

Na seção 7 do artigo de Earley, ele explica que, para "transformar o reconhecedor em um analisador", ou seja, para recuperar árvores de análise, é necessário acompanhar o modo como as conclusões são feitas.

Cada vez que executamos a operação completa, adicionamos um estado (ignorando lookahead), construímos um ponteiro da instância de nesse estado para o estado que nos levou a realizar a operação. Isso indica que foi analisado como . Caso D seja ambíguo, haverá um conjunto de indicadores, um para cada operação completa que causou a ser adicionado ao conjunto de estados específico. Cada símbolo no também terá ponteiros a partir dele (a menos que seja terminal), e assim por diante, o que representa a árvore de derivação para .$E\rightarrow \alpha D.\beta \; g$$D$$D\rightarrow \gamma. \; f$$D$$\gamma$$E\rightarrow \alpha D.\beta \; g$$\gamma$$D$

Observe que, neste texto, e são índices na sequência analisada, apontando onde o reconhecimento da regra do lado esquerdo começou (como o símbolo do lado direito havia sido previsto.) Então, é o índice da sequência na qual o reconhecimento de iniciado e terminou no índice Esses "indicadores de conclusão" são o equivalente de Earley dos indicadores retroativos descritos (não muito bem na wikipedia) para a versão do analisador do CYK.$f$$g$$f$$D\rightarrow \gamma$$g$

A partir desse ponteiro (como descrito na citação), sabemos que o na instância da regra próprio pode ser desenvolvido em uma árvore (ou floresta) que analisa a sequência de entrada do índice para o índice , que observamos . Os nós imediatamente abaixo de são dados pela regra . Procurando a conclusão que leva a podemos encontrar outros indicadores que indicam como o último símbolo de$D$$E\rightarrow \alpha D.\beta \; g$$w$$f+1$$g$$w_{f+1:g}$$D$$D\rightarrow \gamma$$D\rightarrow \gamma. \; f$$D$foi obtido e, portanto, mais informações sobre as possíveis árvores de análise. Também observando a conclusão que reconheceu o símbolo antes da última em um conjunto de estados anteriores, você encontra como ele foi obtido e assim por diante.

Supondo que você tenha mantido todos os ponteiros necessários, conforme indicado no documento, é possível obter todas as representações em árvore compartilhadas a partir do último símbolo reconhecido pelo analisador, que é, obviamente, o símbolo inicial da gramática.

Mas eu também pulei a parte bagunçada . Suponha que você tenha uma regra , que eu escolho com o lado direito maior que 2 símbolos, e outra regra , para uma gramática ambígua.$U\rightarrow XYZ$$W\rightarrow UV$

Pode acontecer que o analisador analise em , em e ambos e em . Assim, com a regra , Ambos e parse em .$w_{f+1:g}$$X$$w_{g+1:h}$$Y$$w_{h+1:i}$$w_{h+1:j}$$Z$$U\rightarrow XYZ$$w_{f+1:i}$$w_{f+1:j}$$U$

Em seguida, ele também pode ser que ambos e tanto de análise em . Então, com a regra , a string analisada em de duas maneiras diferentes, o que corresponde a uma ambiguidade da gramática. w j + 1 : k V W → U V w f + 1 : k$w_{i+1:k}$$w_{j+1:k}$$V$$W\rightarrow UV$$w_{f+1:k}$$W$

Obviamente, para evitar repetir cálculos, o algoritmo de Earley tentará compartilhar o máximo possível dos dois cálculos de análise. O que vai realmente partes é, obviamente, o reconhecimento (e análise) de e em e . Mas, na verdade, fará um pouco mais: também compartilhará o início das duas análises distintas que reconhecem com a regra . O que quero dizer é que o estado será encontrado apenas uma vez (com relação ao que estou descrevendo), no conjunto de estados . Será uma parte comum das duas análises. Obviamente, as coisas divergirão temporariamente ao analisar o w g + 1 : H X Y L L → X Y Z U → X Y . $w_{f+1:g}$$w_{g+1:h}$$X$$Y$$U$$U\rightarrow XYZ$S H Z W → L V $U\rightarrow XY.Z \; f$$S_h$$Z$ pois correspondem a substratos distict, até que convergem novamente quando tudo é analisado em W, quando o estado é produzido duas vezes no conjunto de estados .S $W\rightarrow UV. \; f$$S_k$

Portanto, a floresta de árvores de sintaxe pode ser muito estranha, com tipos de subárvores gêmeas siamesas que podem compartilhar as duas primeiras arestas de algum nó, mas não a terceira aresta. Em outras palavras, pode ser uma estrutura muito estranha. Isso pode explicar por que Earley a chama de " uma representação fatorada de todas as árvores de análise possíveis ", sem ser mais específica.

Qualquer tentativa de separar cirurgicamente os gêmeos siameses, sem alterar a gramática, resultará em maior complexidade. A maneira certa de fazer isso é binarizar a gramática.

Eu espero que isso te ajude. Avise-se me. Mas insisto que um bom entendimento da análise de CYK pode ajudar. Existem outros algoritmos, mais simples que os de Earley, que podem analisar todas as linguagens de CF com eficiência.

Você pode encontrar informações mais gerais sobre esse problema de floresta de análise em duas outras respostas que eu dei: /cstheory/7374#18006 e https://linguistics.stackexchange.com/questions/4619#6120 . Mas eles não entram em detalhes específicos do algoritmo de Earley.