Minhas Aventuras com "Parsing" - Gramáticas

Estou retomando os problemas do SPOJ Brasil (em preparação para o Google Code Jam deste ano) e o primeiro que eu revi foi o "ET Phone Home". Eu já tinha tentado este problema antes, sem sucesso. Hora de estudar um pouco de teoria... Este problema envolve parsing - a análise de textos com base em uma gramática. Eu já falei um pouco sobre isto aqui no blog, mas dentro do contexto de compilar uma linguagem de programação adequadamente simples.

Os livros sobre o assunto são caros (versões "físicas" acima de US$100 e versões eletrônicas acima de US$50 na Amazon). Existe bastante material na web porém a maior parte é confusa e existe pouco código de exemplo. Daí a origem desta série de posts para organizar as minhas ideias e, se tudo der certo, ajudar a outros interessados.

Google Code Jam 2010: Making Chess Boards

Making Chess Boards (fazendo tabuleiros de xadrez) foi o terceiro e último problema da rodada !C do Google Code Jam 2010. Segundo a análise oficial, seria uma combinação de parsing, programação dinâmica e truques espertos. Embora eu tenha resolvido com sucesso o problema, minha solução envolve somente parsing e força bruta.

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

Minhas Aventuras com "Parsing": Implementando o Earley Parser

Passada a "Semana ZX81", é hora de retomar esta série de posts, apresentando uma implementação em C do algorítimo Earley Parser.

O programa apresentado supõe entrada e saída no formato do problema "ET Phone Home". O arquivo de teste original pode ser baixado de http://www.ime.usp.br/~cef/Xmaratona/problems/io/. Entretanto, o código apresentado aqui não é uma solução adequada, por ser muito lento.

Minhas Aventuras com "Parsing": LR Parser (parte 1)

Embora o Earley Parser seja capaz de analisar uma gama bastante grande de gramáticas, o seu desempenho pode deixar a desejar. Minha próxima opção é o LR Parser.

Este algorítimo é bastante usado em compiladores reais, com o auxílio de pequenos truques devido às excentricidades das linguagens de programação reais.

Minhas Aventuras com "Parsing": LR Parser (parte 2)

Continuando a minha descrição do LR parser, vejamos a sua arquitetura e o algorítimo básico. Um LR Parser é normalmente implementado como um autômato descendente (ou autômato com pilha), que é (digamos) uma máquina de estados "turbinada" com uma pilha, movido por duas tabelas.

Balanço Anual do Blog: 2011

No começo do mês o DQSoft completou seis anos de vida. É hora do tradicional balanço anual.