llclib

A llclib é uma biblioteca de funções para a manipulação e parsing de linguagens livres do contexto em python.

Apresentada como trabalho final da disciplina de Linguagens Formais e Autômatos, inf05505, ministrada pelo Prof. Dennis Giovani na UFRGS.

Estruturas / Objetos

Grammar

Representa uma gramática livre do contexto. Possui os atributos:

• nonterminals: uma lista de strings, cada elemento representa um não-terminal.
• terminals: uma lista de strings, cada elemento representa um terminal.
• productions: dicionário de produções.
• start: não-terminal inicial.

Para a gramática com as produções:

S -> 01 | 10

O dicionário productions é:

{
    'S': [ ['0', '1'],
           ['1', '0']]
}

O objeto Grammar também possui um teste de consistência, chamado pelo método test(), o qual executa testes básicos para verificar a validade da gramática livre do contexto abstraída.

Simplifier

É um objeto com métodos para a simplificação e transformação de uma GLC para a forma normal de Chomsky. Dado um objeto Grammar, os métodos que podem ser executados sob a gramática representada são:

• Simplifier(grammar).remove_empty(): remove as produções vazias da gramática.
• Simplifier(grammar).remove_unit(): remove as produções unitárias.
• Simplifier(grammar).remove_useless(): remove as produções inúteis ou inalcançáveis.
• Simplifier(grammar).fnc(): transforma a gramática para a forma normal de Chomsky.

Todos os métodos foram implementados a partir dos algoritmos descritos no livro Linguagens Formais e Autômatos do Paulo Blauth de Menezes.

Parser

Objeto com métodos para reconhecimento e geração de uma árvore de derivação para uma dada gramática livre do contexto.

É uma implementação do algoritmo de Earley para parsing de linguagens naturais descrito no livro de D. Jurafsky e James H. Martin, "Speech and Language Processing: An introduction to natural language processing, computational linguistics, and speech recognition".

Há algumas diferenças entre o algoritmo original e a implementação, devido ao original descrever um algoritmo para o parsing de linguagens naturais.

Para executar o parsing de uma palavra 1111:

# carrega o objeto Parser a partir da gramática "grammar"
parse = llclib.Parser(grammar)

# executa o algoritmo de Earley
parse.run('1111')

# preenche uma lista com estados completados
c = parse.get_completeds()

# se, ao menos 1 foi completado, a palavra foi reconhecida
if len(c) > 0:
    # caso len(c) > 1, a gramática possuí mais de uma árvore de 
    # derivação para a palavra
    print 'Reconhecida!'    

    # constrói uma árvore a partir do primeiro estado completado
    print make_node(c[0]) 

Objetos relacionados:

• Row: estado de Earley.
• Table: lista de estados de Earley.

Reader

É um importador de uma gramática em arquivo de texto para uma estrutura Grammar. Um exemplo de arquivo de texto aceito:

#Terminais
[ 1 ]           # comentários são permitidos
[ + ]
[ * ]
#Variaveis
[ P ]   a
[ S ]
[ M ]
[ T ]
#Inicial
[ P ]           # apenas um estado final
#Regras
[ P ] > [ S ]
[ S ] > [ S ] [ + ] [ M ]
[ S ] > [ M ]
[ M ] > [ M ] [ * ] [ T ]
[ M ] > [ T ]
[ T ] > [ 1 ]

Instalação

Usando o pipy

pip install llclib 

Manualmente

git clone https://github.com/antedeguemon/llclib.git
cd llclib && python setup.py

Links

Alguns projetos/páginas que ajudaram no desenvolvimento da llclib:

• loup-vaillant.fr: para a construção da árvore de derivação e ambiguidades
• earley_bird
• pep