Olá pessoal
Eu e meu grupo temos que implementar em Java, um programa que reconheça expressões lógicas.
Temos que construir uma gramática ( GLC - Gramática Livre de Contexto ) e depois implementá-la em java.
Segue abaixo, algumas informações de como deverá ser nosso trabalho:
Descrição do problema
O tema da pesquisa é a Hierarquia de Chomsky, seus elementos com suas definições e relações. Além disto, deve ser feita uma implementação no contexto da gramática livre de contexto, usando a técnica da análise preditiva para produção de um software de reconhecimento de expressões lógicas.
Estas expressões devem ser terminadas por EOL, ou seja, aparecer uma em cada linha de um arquivo texto de entrada e podem conter: números binários de 1 dígito (0 ou 1) ou identificadores (ambos sem sinal), e as seguintes operações lógicas: conjunção ( ^ ), disjunção( v ), negação ( ? ), condicional ( -> ) e bicondicional ( <-> ).
São possíveis também parênteses e colchetes balanceados. Se acontecerem de forma aninhada, o colchetes devem estar sempre mais externos do que o parênteses.
Os identificadores devem ser formados apenas por letras.
A unidade de leitura da entrada de dados é o caractere, sendo assim a GLC deverá prever, através de regras próprias, a construção de todos os elementos usados no reconhecimento: números, identificadores, operadores, etc.
A saída do programa deverá ser o resultado da avaliação de cada expressão: se ok ou não. Em caso de erro (não reconhecimento da expressão), apresente além da mensagem de erro o número da linha que contém o erro, o caractere que provocou o erro e ainda qual(is) o(s) caractere(s) seriam esperados no ponto do erro.
Exemplo de arquivo de entrada:
1 v 0
x v (y -> z)
z <-> [x v (y ^ z)?]
Valor
1
1 ^
x ? y
(x <-> [y v x])
Saída:
-
1 v 0
ok! -
x v (y -> z)
ok! -
z <-> [x v (y ^ z)?]
ok! -
Valor
ok! -
1
ok! -
1 ^
erro na linha 6: foi encontrado fim de linha, mas era esperado um identificador, abre parênteses ou constante (1 ou 0) -
x ? y
erro na linha 7: foi encontrado ?y?, mas era esperado um ?>? -
(x <-> [y v x])
erro na linha 8: foi encontrado um ?[? mas era esperado um abre parênteses, uma constante (1 ou 0), ou um identificador.
Sugestões:
· O primeiro passo é a construção de uma gramática que reconheça uma expressão.
· O segundo passo é a reescrita desta gramática eliminando possíveis recursividades à esquerda e conflitos.
· Use o método readLine da classe BufferedReader para ler linha-a-linha do arquivo de entrada.
· Os métodos transformados a partir das variáveis da gramática serão estáticos. O processamento irá ser concentrado no main.
· O método reconheça, também estático, deverá trabalhar fazer a leitura caractere-a-caractere sobre a string que representa a expressão.
http://geocities.yahoo.com.br/hmcristovao/mapas/
Exemplo de aplicação da análise preditiva (explicado em aula)
Suponha a GLC:
S -> A <EOF> | <EOF>
A -> aA | bA | Bg
B -> cC
C -> B | DE
D -> dD | λ
E -> e | f
A expressão regular que denota a linguagem gerada é:
((a|b)c+d(e|f)g)?<EOF>
Esta GLC não tem conflito, ambigüidade e recursividade à esquerda, portanto pode-se aplicar a técnica da análise preditiva para geração do algoritmo:
função S() {
se(próxCaracter==?a? ou próxCaracter==?b? ou próxCaracter==?c?)
A(); reconhece(<EOF>);
senão se(próxCaracter==<EOF>)
reconhece(<EOF>);
senão
imprime(?erro?);
)
função A() {
se(próxCaracter==?a?)
reconhece(?a?); A();
senão se(próxCaracter==?b?)
reconhece(?b?); A();
senão se(próxCaracter==?c?)
B(); reconhece(?g?);
)
função B() {
reconhece(?c?); C();
)
função C() {
se(próxCaracter==?c?)
B();
senão se(próxCaracter==?d? ou próxCaracter==?e? ou próxCaracter==?f?)
D(); E();
}
função D() {
se(próxCaracter==?d?)
reconhece(?d?); D();
senão
;
}
função E() {
se(próxCaracter==?e?)
reconhece(?e?);
senão se(próxCaracter==?f?)
reconhece(?f?);
}
Obs.: A função reconhece tem o objetivo de verificar se o próximo caractere é de fato o que foi passado como argumento. Se sim então lê o próximo caracter e põe em próxCaracter, senão dispara uma mensagem de erro.
função reconhece(caracter c) {
se(próxCaracter == c)
próxCaracter = lêPróximoCaracterDoArquivo();
senão
imprime(?erro?);
sai_do_programa;
}
Nossa gramática livre de contexto está ficando assim até agora:
<binario> -> 1|0
<ident> -> A|…|Z|…|a|…|z| <ident> | <binario>
<op> -> ^|v|’|->|<->
<parente> -> (<parente>) | <ident> <op> <ident> ==> errado !!!
<colchete> -> [<colchete>] | <colchetes> <op> <colchete> | <ident>
<exp> -> <colchete> | <wcpar>
<wcpar> -> <parente> | x
<eol> -> <separa>
Então , é justamente esta gramática que a gente deve implementar em Java, ela ainda nao está pronta e está com erros, mas é mais ou menos assim que deve ficar.
Alguém pode nos ajudar ?
Alguém já fez algo parecido ?
Obrigado
t+
:
[/color]