O trabalho será baseado no código em Python para análise gramatical desenvolvido pelo Prof. Andrew McCallum. O trabalho deve ser desenvolvido totalmente em Python em grupos de no máximo 2 alunos. A data de entrega é 10/12/08 (até às 23:59h). O trabalho pode ser entregue por e-mail. Uma breve apresentação (10 minutos) sobre o trabalho deve ser feita em aula no dia 11/12/08.

O primeiro passo é baixar o módulo cfg.py. Este módulo contém uma gramática em Forma Normal de Chomsky e algumas funções. Por exemplo, a função generate gera uma frase aleatória a partir da gramática. A função printsentence, chama a função generate e imprime a frase gerada na tela. A função generate_tree também gera uma frase da gramática, mas inclui a notação de colchetes para indicar que regras foram usadas na geração.

As seguintes tarefas devem ser realizadas:

Terminar a implementação da função parse usando o algoritmo CKY (capítulo 13 do livro-texto). Ela deve retornar Verdadeiro se a frase de entrada estiver na linguagem especificada pela gramática, caso contrário deve retornar Falso.

(Tarefa "extra") Fazer a função retornar ao invés de True uma lista com todas as árvores de parse encontradas para a frase.

Adicionar mais alguns não-terminais e terminais à gramática, modelando outras construções linguísticas tais como conjunções ("e" e "ou"), advérbios, imperativos, etc. Lembre que a gramática tem que ficar em Forma Normal de Chomsky.

Escrever um pequeno relatório mostrando exemplos de frases gramaticais e não-gramaticais e a resposta dada pelo algoritmo.