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.

Vamos começar falando um pouco sobre o que são estas gramáticas de um ponto de vista mais formal.

Gramáticas x Linguagens

Ok, eu tenho certeza que vou confundir estas duas coisas nestes textos, mas aqui vai uma descrição formal. A gramática é o conjunto de regras que dizem quais textos são válidos. A linguagem é o conjuntos destes textos válidos.

Terminais e Não Terminais

A base para as gramáticas (e portanto do parsing) são os símbolos terminais. Eles são os símbolos elementares, indivisíveis do ponto de vista da gramática. Nestes posts vou seguir a tradição de representá-los por letras minúsculas, porém na prática eles podem ser tanto caracteres isolados como palavras. Por exemplo, nas linguagens de programação os símbolos terminais são as palavras reservadas, caracteres especiais, constantes e identificadores.

Os símbolos não terminais são sequências de terminais e não terminais, construídas conforme as regras da gramática. Vou representá-los por letras maiúsculas.

Vejamos um exemplo simples. Consideremos como não terminais as letras 'a' e 'b'. Um texto válido na nossa gramática será composto por um não terminal 'S'. As regras desta gramática serão:

• Um não terminal S é composto por um 'a' seguido de um não terminal 'A'
• O não terminal A é composto por um 'b' ou por um 'a' seguido de um não terminal 'A'

Note que a segunda regra envolve uma recursão (isto é, um não terminal 'A' pode conter um 'A'). É este tipo de regra que complica as coisas.

Alguns exemplos de texto válido: "ab", "aab", "aaab". Por outro lado, esta gramática não permite gerar textos como "b" e "aba".

Em alguns trechos vou precisar me referir a textos que podem ser terminais, não terminais ou uma combinação deles; a tradição manda usar as últimas letras do alfabeto em minúsculas e itálico com u, v e w.

Descrevendo as Regras de Uma Gramática

Existem várias formas de se descrever as regras de uma gramáticas. Vamos usar aqui as chamadas regras de produção, que possuem a seguinte forma geral:

u -> v

Esta regra indica que a sequência u é produzida através da sequência v. Ou, olhando no sentido inverso, que a sequência v é uma forma válida de escrever a sequência u.

Apesar da aparente simplicidade, estas regras permitem criar gramáticas altamente complexas. Vejamos como colocar neste formato a gramática que usei anteriormente como exemplo:

S -> aA
A -> b
A -> aA

Reparar que temos duas regras para produzir o não terminal A; o uso de múltiplas regras define sintaxes alternativas.

O não terminal que representa um texto válido na gramática (o S no nosso exemplo) é chamado de símbolo inicial ou raiz.

Tipos de Gramática

A classificação que vamos adotar aqui está diretamente ligada à forma como a gramática pode ser analisada. De uma forma geral, uma restrição no formato das regras e, consequentemente, na diversidade da gramática, irá permitir usar algorítimos mais simples e/ou mais eficientes para fazer o parsing.

Esta classificação é chamada de hieraquia de Chomsky. Cada tipo engloba os seguintes (ou seja, um algorítimo que analisa corretamente o tipo i irá analisar também o tipo i+1):


A forma genérica das regras apresentada acima (u -> v) gera linguagens irrestritas (tipo 0). Mais exatamente, gera todas as linguagens que podem ser reconhecidas por uma Máquina de Turing.

Restringindo as regras para o formato uAv -> uxv, com u e v podendo ser vazios mas x não, obtemos as linguagens sensíveis ao contexto (tipo 1).

O meu interesse nestes posts começa no tipo seguinte, as linguagens livre de contexto (tipo 2). As regras para a gramática destas linguagens seguem o formato A -> v.

Por último temos as linguagens regulares (tipo 3). Existe duas formas possíveis para as regras da gramática:

• A -> a e A -> aB
• A ->a e A -> Ba

Todas as regras da gramática regular devem ser do mesmo tipo (isto é, não podem existir simultaneamente regras do tipo A ->aB e regras do tipo A -> Ba). As gramáticas regulares podem ser analisadas por uma máquina de estados finitos.