Minhas Aventuras com "Parsing": Earley Parser

Earley Parser é um algorítimo capaz de analisar linguagens livres de contexto. Não é um algorítimo particularmente rápido no caso mais genérico: o tempo de execução é proporcional ao cubo do tamanho do texto a analisar. Em outras palavras, um texto com o dobro do tamanho demora oito vezes mais para ser analisado; um texto 10 vezes maior demora 1000 vezes mais. Este desempenho melhora em casos específicos como gramáticas não-ambíguas (onde um texto pode ser derivado de uma única forma) e as chamadas gramáticas LR(k) (falaremos mais sobre elas no futuro).

Obs: Recomendo a leitura do post anterior para entender a nomenclatura usada.

A Ideia Básica

O Earley Parser analisa o texto da esquerda para a direita, considerando um caracter adicional de cada vez. Na sua análise, vai montando uma relação das regras da gramática que potencialmente podem ser aplicadas no reconhecimento do texto. À medida que a análise prossegue, verifica-se que algumas regras não são compatíveis com o texto e devem ser abandonadas, enquanto que outras podem ser aplicadas para reconhecer outros trechos. Se, num certo instante, nenhuma regra puder ser aplicada, o texto é inválido; se o texto todo atender a uma regra do não terminal raiz, o texto é válido.

Se você experimentar fazer algo parecido no papel, verá que a ideia é boa mas a sua implementação não é trivial.

Linguagem Aumentada

Um primeiro truque para facilitar a análise é acrescentar uma regra adicional à gramática:

S' -> S

onde S é o não terminal raiz original. S' passa a ser a nova raiz da gramática, com a vantagem de ter uma única regra de produção. Desta forma o nosso objetivo é verificar esta única regra (ao invés de considerar explicitamente as potencialmente várias regras de produção da raiz original).

O Estado do Parsing

Para representar a situação do reconhecimento de uma regra X -> uv em um dado instante, Early usa a notação

X -> u • v

o ponto na notação separa a parte que já foi reconhecida (u) do que é esperado (v).

Um estado no algorítimo é composto de três partes:

• A regra sendo analisada (X -> uv)
• A posição do ponto que indica quanto da regra já foi reconhecida
• Um índice que indica a partir de qual posição no texto foi feito o reconhecimento

Este estado pode ser representado por

(X -> u • v , i)

Conjuntos de Estados

Voltando à ideia básica, vamos analisar o texto caracter a caracter da esquerda para a direita. Em cada passo teremos um conjunto de estados que contém as regras que podem ser aplicadas até este momento. Para um texto com n caracteres teremos n+1 conjuntos de estado, correspondendo do momento em que não analisamos nenhum caracter até o momento em que analisamos todos. Representaremos estes conjuntos por S(0) a S(n).

Ao acrescentar um estado em um conjunto é preciso tomar o cuidado de não duplicá-lo se já estiver no conjunto.

Começamos colocando em S(0) o estado

(S' -> • S, 0)

Isto indica que a regra básica pode ser aplicada ao texto, nada foi reconhecido ainda e estamos partindo do primeiro caracter.

O Algorítmo

O nosso algorítimo vai percorrer o texto da esquerda para direita. Estaremos variando o índice k do caracter a examinar de 0 até n-1, onde n é o número de caracteres no texto.

Em cada passo vamos examinar os estados no conjunto atual S(k). Dependendo do que observarmos, vamos acrescentar novos estados ao conjunto atual ou ao conjunto seguinte S(k+1). Os estados acrescentados ao conjunto atual serão também examinados no passo atual; somente quando não tivermos mais estados a acrescentar e analisar no passo atual passaremos para o seguinte.

No nosso exame dos estados vamos procurar identificar uma das seguintes três situações (exclusivas entre si):

• Completion: Um não terminal foi reconhecido. Isto é indicado pelo ponto estar no final da regra: (X -> u •, j). O tratamento desta situação consiste em acrescentar ao conjunto atual S(k) estados do conjunto S(j) atualizados para indicar este reconhecimento. Sendo mais específico, para cada estado em S(j) que tenha o formato (Y -> u • X v, i) vamos incluir no conjunto atual S(k) um estado (Y -> u X • v, i).
• Prediction: Acrescentar as regras referentes aos não terminal que são esperados. Isto é indicado pelo ponto estar na frente de um não terminal: (X -> u • Y v, j). O tratamento desta situação consiste em incluir no conjunto atual S(k) o estado (Y -> •y, k) para cada regra Y -> y de produção de Y na gramática
• Scanning: Reconhecer um não terminal. Isto ocorre quanto temos no conjunto atual S(k) um estado no formato (X -> u • a v, j) e o próximo caracter no texto é o não terminal a. O tratamento desta situação consiste em colocar no conjunto seguinte S(k+1) o estado (X -> u a • v, j) que indica o reconhecimento.
  

O estado (S' -> S •, 0) no passo n indica que o texto foi reconhecido (é válido).

Se, ao concluirmos um passo 0 a n-1, o conjunto de estados para o passo seguinte está vazio é sinal que o texto é inválido.

No próximo post veremos uma implementação direta deste algorítimo em C.

Referências

Wikipedia: http://en.wikipedia.org/wiki/Earley_parser
Uma apresentação (em formato pdf): http://www.sfs.uni-tuebingen.de/~fr/teaching/ws06-07/cl2/slides/EarleyParser.pdf
Uma apresentação bem mais clara (também em pdf): http://www.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/Earley-Parsing.pdf