Relatório para software gerador de gramatica

Manipulador de Gramáticas Regulares e Gramáticas Livres de Contexto

Gabriel Edson Werner Bittencourt

Curso de Ciência da Computação – Universidade de Santa Cruz do Sul (UNISC)

Av. Independência, 2293 - Bairro Universitário – Santa Cruz do Sul – RS – Brasil.

[e-mail]

Abstract. This article aims to bring a detailed report on the implementation of a tool that enables the handling grammars type 2 and 3 and in a second part of work with the recognition of finite automata. All development has been designed in order to bring the user a simple and uncomplicated and all programming in Java language interface. Combining the theoretical concepts necessary for the practical part we have such work to be presented.

Resumo. O presente artigo objetiva trazer um relatório detalhado da implementação de uma ferramenta que possibilite a manipulação de gramáticas do tipo 2 e 3(Gramáticas Regulares e Gramáticas Livres de Contexto). Todo o desenvolvimento foi pensado de modo a trazer ao usuário uma interface simples e sem complicações e com toda a programação em linguagem Java. Aliando os conceitos teóricos necessários à parte prática temos o referido trabalho que será apresentado.

 

1. Alfabeto

Paulo Blauth Menezes menciona em seu livro Linguagens Formais e Autômatos que, um alfabeto é um conjunto finito de símbolos. Assim, um conjunto vazio também é um alfabeto ou parte de um. Um símbolo é uma entidade abstrata básica a qual não é definida formalmente. Letras e dígitos são exemplos de símbolos frequentemente usados.


2. Gramática

Uma gramática é uma quádrupla ordenada G = (V, T, P, S) onde:

V: Conjunto de símbolos Não-Terminais que englobam a gramática.

T: Conjunto de símbolos Terminais que englobam a gramática.

P: Símbolo do conjunto de produções.

S: Símbolo de início de produção.

        

Em sua teoria, o estudo de linguagens formais, define que um conjunto de gramática formal ( em algumas literaturas definida somente por gramática), é definida como um conjunto de regras de produção de cadeias em uma linguagem formal, ou seja, objeto que permite especificar uma linguagem ou língua. Regras descrevem como formar as cadeiras – partindo do alfabeto da linguagem – que sofrem validação de acordo com a sintaxe da linguagem.


3. Gramaticas Regulares

Gramaticas Regulares possuem a estrutura composta por dessemelhança entre seus lados. O lado esquerdo é composto unicamente por símbolos não terminais, e o seu contrário, composto por uma cadeia vazia, ou simplesmente símbolo terminal, ou também um símbolo terminal seguido de um símbolo não terminal, e limitasse a isso.

Todas as linguagens geradas pela gramática regular podem ser reconhecidas em tempo linear por uma maquina de estados finitos. Entretanto, são utilizadas, no modo prático, as expressões regulares.


4. Gramaticas Livres de Contexto

Definidas como gramáticas do Tipo 2 na hierarquia de Chomsky, as gramáticas livres de contexto são aquelas em que é realizado o levantamento do condicionamento das substituições impostas pelas regras definidas pelas produções.

Gramaticas livres de contexto, ou gramáticas independentes de contexto, também podem ser apresentadas como gramáticas algébricas, são gramáticas formais cuja regra de produção é representada por V → W.

V representa o símbolo Não-Terminal, e w é uma cadeia composta de terminas e/ou de Não-Terminais. A definição de livre de contexto foi proposta a partir da possibilidade de um símbolo Não-Terminal V poder ser substituído por w sem qualquer alteração de contexto.


5. Desenvolvimento do Manipulador de Gramáticas

 

O software de manipulação de gramática desenvolvido possui todas as características necessárias para a geração da gramática, validação da mesma e definição do tipo de gramática, ações realizadas a partir de um algoritmo que analisa um conjunto de produções inseridas previamente na interface do software. Toda a ferramenta foi desenvolvida em linguagem Java, possuindo como principal base o HashList.

Levou-se em conta cuidados para desenvolver uma interface simples onde o usuário precisasse da menor interação possível e o algoritmo fizesse tudo que fosse necessário para trazer as informações.

O próprio código se responsabiliza pela analise de todos os erros que podem ser causados por alguma entrada indevida de usuário, e caso isso ocorra, é apresentado instantaneamente um aviso sobre o problema.

Foi definido o símbolo de vazio como sendo representado pelo caractere “&”.

A Imagem 1, apresenta a interface inicial do software desenvolvido, com todos os campos de entrada de dados.

[pic 1]
Imagem 1

Situação a ser observada, é a proibição de símbolo de inicio igual à outra letra que já está definida como parte do alfabeto.

No conjunto de produções que engloba a gramática, o símbolo que separa o que está no “lado esquerdo/lado direito” é  o símbolo “>”. Saliento o caractere “|” para separações no lado direito.


6. Apresentação de resultados.

Primeiramente, testando uma gramática válida do tipo Regular, definida a seguir:

Símbolos Não-Terminais: ABC

Símbolos terminais: abc

Símbolo do conjunto de produções: P

Símbolo de início de produção: S

Conjunto de produções que engloba a gramática:

S > a|bC
A > c|b
B > cA|aC
C > c|B

[pic 2]
Imagem 2