Versão Final do Código sem Erros

A versão final do código já está no servidor.
O erro que estava causando era por falta de uma produção que não havia implementado.
Adicionei a produção e os erros acabam.

Segue o link para download do projeto: http://code.google.com/p/simpleregex/downloads/detail?name=SistemaReescrita.zip&can=2&q=

Código

Pessoal,

Coloquei o código no servidor svn do google, é possível acessar o link pelo lado direito no fim, mas segue o link: http://code.google.com/p/simpleregex/

O código ficou com 3.171 linhas porém falta corrigir um bug.
Estarei resolvendo o problema até sexta-feira conforme o professor nos disse.

Apresentacao - Atualizacao

Senhores,

Na apresentacao fizemos diversas mudancas neste momento, sendo que estou escrevendo aqui para documentar ao professor.

- Felipe: Modificou a parte do parser e da gramática ambigua, adicionando alguns slides e modificando a ordenacao dos mesmos para facilitar a explicacao
- Manasseis: Arrumou as imagens borradas e melhorou o visual da apresentacao, bem como diminuiu o texto da parte 'Estado da Arte'
- Vitor: Me auxiliou na criação de um exemplo para explicar as 'Especificidades' da implementação na Introdução e me enviou a parte que já criou para explicar o custo computacional -> Ainda falta fazermos o merge desta parte

Abracos,

Apresentacao

Senhores,

Estou conversando com o Vitor no skype e acabei de enviar a versao final da apresentacao... Ele ainda vai dar umas adicionadas, mas seria legal todos verem se concordam com a proposta que fiz:

- Slides 1-4: Introducao e Problema -> Rodrigo
Vou resumir TUDO que foi feito no projeto.

- Slides 5-8: Felipe
Conceitos base para entendimento

- Slides 9-11: Manasseis
Estado da arte

- Slides 13-14: Felipe
Conversao para Gramatica e Casamento por analisador sintatico

- Slides 15-21: Vitor
Parser para gramatica ambigua (backtracking) e solucao proposta

- Slides 22-23: Rodrigo
Conclusao e trabalhos relacionados

Paper Final e Apresentacao

Senhores,

Acabo de enviar a versao final do paper para ultima revisao com todas as observacoes que trocamos via email (principalmente mudancas referntes a formatacao).

A apresentacao esta baseada no que o Manasseis enviou, com pequenas adicoes.

Gostaria de lembrar a todos alguns pontos:
- Muitos detalhes nao fazem sentido de serem apresentados em uma apresentacao como esta, pois as pessoas nao sao especialista no tema e o paper esta bem completo
- Devemos focar no que foi feito e por que foi tao dificil fazer (por exemplo, as mudancas que tivemos de fazer no parser para suportar ambiguidade quando vimos que propomos uma linguagem ambigua, os ciclos gerados, a otimizacao com a validacao via gramatica, a melhoria no parser realizada ao se identificar os simbolos terminais com base na string de entrada, problemas encontrados com a JVM devido aos ciclos do problema, etc).
- Na conclusao falarei dos trabalhos relacionados rapidamente, dizendo que ninguem implementou algo tao genericamente como o nosso, nem que de as derivacoes da entrada.

Classes

Olá Felipe,

Falta ainda a implementação da classe Follow e do preenchimento da Tabela LL1?
A classe First não está completa, falta os casos onde deve ser considerado o terminal epsilon, caso derive AB e A derive epsilon, entao o first deve contemplar tambem a variavel B.
Descobri somente este problema, mas olhei somente a classe First pois estou sem tempo, olhei bem rápido também. Faça os testes ai porque não vou conseguir testar. Fallow

Apresentação

Prezados,
Enviei para o e-mail de vocês a versão 1,0 da apresentação.

Boa Noite Pessoal,

Consegui desenvolver um algorítmo para calcular o conjunto First de uma gramática. Para isto utilizei as classes de Gramatica, Producao, Terminal e Variavel que o Vitor havia criado anteriormente.

Sendo assim criei uma classe chamada Tabela como segue a seguir:

package sistema.expressaoRegular.TabelaFirstFollow;

import sistema.expressaoRegular.gramatica.Gramatica;

public class Tabela {

public First first;
public Follow follow;

public Tabela(Gramatica grm)
{
if(grm == null)
return;

first = new First(grm);
}

}


Criei Também duas classes, uma chamada First e outra chamada Follow, segue a implementação da classe First:

package sistema.expressaoRegular.TabelaFirstFollow;

import java.util.HashMap;
import java.util.Vector;

import javax.smartcardio.TerminalFactory;

import sistema.expressaoRegular.gramatica.Gramatica;
import sistema.expressaoRegular.gramatica.Producao;
import sistema.expressaoRegular.gramatica.Simbolo;
import sistema.expressaoRegular.gramatica.Terminal;
import sistema.expressaoRegular.gramatica.Variavel;

public class First {

public HashMap> itens;
private Gramatica gramaticaOrigem;
public First(Gramatica grm)
{
gramaticaOrigem = grm;
itens = new HashMap>();

for (Producao prod : grm._P) {

Vector terminais = new Vector();
PreencherTerminais(prod,terminais);

if(!itens.containsKey(prod._V))
itens.put(prod._V, terminais);
else
itens.get(prod._V).addAll(terminais);

}
}


private void PreencherTerminais(Producao prod , Vector pterminais)
{

if(pterminais == null)
pterminais = new Vector();

for (int i = 0; i < prod._Corpo.size(); i++) {
if(prod._Corpo.get(i).isTerminal())
{
Terminal t = new Terminal(prod._Corpo.get(i)._caractere);
pterminais.add(t);
}
else if (prod._Corpo.get(i).isVariavel()) {
Vector prodfounds = getProducaobyVariavel(prod._Corpo.get(i)._caractere);
if(prodfounds != null && prodfounds.size()>0)
{
for (int j = 0; j < prodfounds.size(); j++) {
PreencherTerminais(prodfounds.get(j) , pterminais);
}

}
}
}
}

private Vector getProducaobyVariavel (Character variavel)
{
Vector prods = new Vector();
for (int i = 0; i < gramaticaOrigem._P.size(); i++) {
if(gramaticaOrigem._P.get(i)._V._caractere.equals(variavel))
{
prods.add(gramaticaOrigem._P.get(i));
}
}
return prods;
}
}

A classe first gera o Conjunto de terminais que podem iniciar uma seqüência de símbolos a a partir de uma gramática. O método reponsável por este processo é PreencherTerminais que a patir de uma determinada produção A é capaz de gerar o conjunto first(A).

Para que este processo ocorrece corretamente, foi necessário alterar o constrututor da classe Variavel, para que o os objetos originados desta classe armazenassem o caracter desta variável junto com o simbolo Debug, como segue:

public Variavel(char simbDebug) { //Debug
super(simbDebug);

simboloDebug = simbDebug;
}

Utilizei a seguinte rotina abaixo para testar o algorítimo:

package sistema.expressaoRegular.TabelaFirstFollow;

import java.util.HashMap;
import java.util.Set;
import java.util.Vector;

import sistema.expressaoRegular.gramatica.Gramatica;
import sistema.expressaoRegular.gramatica.Producao;
import sistema.expressaoRegular.gramatica.Terminal;
import sistema.expressaoRegular.gramatica.Variavel;
import sistema.expressaoRegular.gramatica.Simbolo;

public class TesteFF {

/**
* @param args
*/
public static void main(String[] args) {

/**
*
* Criação da Gramatica a ser testada Manualmente
S --> AC
S --> B
S --> s
A --> a
A --> b
B --> c
B --> d
C --> e

Resultados esperados para First:
First(S) = {a,b,c,d,e,s}
First(A) = {a,b}
First(B) = {c,d}
First(C) = {e}
*/
Gramatica g = new Gramatica();

g._P = new Vector();
g._T = new Vector();
g._V = new Vector();

Terminal ta = new Terminal('a');
Terminal tb = new Terminal('b');
Terminal tc = new Terminal('c');
Terminal td = new Terminal('d');
Terminal te = new Terminal('e');
Terminal ts = new Terminal('s');

g._T.add(ta);
g._T.add(tb);
g._T.add(tc);
g._T.add(td);
g._T.add(te);
g._T.add(ts);

Variavel vS = new Variavel('S');
Variavel vA = new Variavel('A');
Variavel vB = new Variavel('B');
Variavel vC = new Variavel('C');

g._V.add(vS);
g._V.add(vA);
g._V.add(vB);
g._V.add(vC);

Producao pSAC = new Producao(vS, null);
pSAC._Corpo = new Vector();
pSAC._Corpo.add(vA);
pSAC._Corpo.add(vC);

Producao pSB = new Producao(vS, null);
pSB._Corpo = new Vector();
pSB._Corpo.add(vB);

Producao pSs = new Producao(vS, null);
pSs._Corpo = new Vector();
pSs._Corpo.add(ts);

Producao pAa = new Producao(vA, null);
pAa._Corpo = new Vector();
pAa._Corpo.add(ta);

Producao pAb = new Producao(vA, null);
pAb._Corpo = new Vector();
pAb._Corpo.add(tb);

Producao pBc = new Producao(vB, null);
pBc._Corpo = new Vector();
pBc._Corpo.add(tc);

Producao pBd = new Producao(vB, null);
pBd._Corpo = new Vector();
pBd._Corpo.add(td);

Producao pCe = new Producao(vC, null);
pCe._Corpo = new Vector();
pCe._Corpo.add(te);


g._P.add(pSAC);
g._P.add(pSB);
g._P.add(pSs);
g._P.add(pAa);
g._P.add(pAb);
g._P.add(pBc);
g._P.add(pBd);
g._P.add(pCe);

Tabela tbl = new Tabela(g);

for(Variavel item : tbl.first.itens.keySet()) {
System.out.println("First(" + item._caractere.toString() +") {" );
for (int i = 0; i < tbl.first.itens.get(item).size(); i++) {

Terminal t = tbl.first.itens.get(item).get(i);
System.out.print(t._caractere.toString() + ", ");
}
System.out.println("}");

}

//g._P.add(arg0)

}

}


Assim obtive a seguinte saída do compilador:


First(B) {
c, d, }
First(A) {
a, b, }
First(S) {
a, b, e, c, d, s, }
First(C) {
e, }


Logo o algorítmo está funcionando corretamente, mas deve ser testado com muitas outras gramáticas, inclusive as geradas pelas classes de conversão de expressão regular.

Agora estou implementando o algorítimo de para gerar os simbolos do conjuntos das produções para Follow, para em seguida termos a tabela de parser LL.

Dúvidas. Me avisem pessoal.

Abraços.

JVM

Retirei o problema da JVM por código mesmo mudando a estrutura do programa.
Agora roda em qualquer JVM.

JVM Padrao

Galera,

Vamos tomar como base a JVM da IBM? Vitor, imagino que seja esta que esteja utilizando... Nao vi o problema da recursao na mesma.


Abracos,

Aplicações

Vitor,

Conforme já discutimos vejo que desenvolver uma aplicação para utilizar nossa biblioteca não é realmente necessário.

A biblioteca por si só é extremamente complexa e prova todos os conceitos que elencamos no paper. Infelizmente a idéia de aplicação que tivemos não pode, pois como você bem postou gera uma linguagem que não tratamos (LC).

Dividimos a apresentação conforme email em:
- Eu farei a introducão do problema, das técnicas que desenvolvemos em nossa proposta e o que consiste nossa biblioteca, desenvolvida para provar as idéias do paper
- O Felipe irá falar do conhecimento base para entendimento do assunto
- O Manasseis falará da história do assunto, com as referências e evolução
- Vitor falará dos detalhes da técnica e desafios enfrentados

Conforme concordamos eu estarei responsável por condensar as apresentações que vão me enviar em uma única, para a apresentação. Me enviem até domingo (meia-noite).


Abracos,

Aplicações

Olá Pessoal,

Não tem como fazer a aplicação das derivadas pois nosso sistema casa com ER e ER não casa linguagens livres de contexto. Para trabalhar com derivadas precisamos de () para definir o escopo de um operador.
Caso alguém tenha alguma idéia de aplicação poste do blog.


Falow

Nova gramática

Olá,

Tive que implementar a produção T->{a} na gramática para contemplar algumas regras de reescrita que podem ocorrer.

Nova gramática

Olá Pessoal,

Encontrei um erro na gramática e vou precisar adicionar mais algumas produções.
Quando tiver completo passo para o blog.

Recursão em Java

Olá Pessoal,

O problema de memória que estava ocorrendo é devido à JVM da Sun, a JVM da Sun não possui suporte para conversão de funções recursivas de forma satisfatória.
Agora o erro não ocorre mais devido ao recurso de poda, entretanto o problema pode ser solucionado também através de alguma outra JVM com este tipo de tecnologia ou melhorando o core.
Depurem o código e caso encontrem erros me avisem, pois não uso o JVM da Sun.

Poda no parser

Olá Pessoal,

Estava encontrando problemas de memória no algoritmo do parser e resolvi implementar um recurso de poda de derivação pois o parser estava esgotando minha memória.
Ao derivar uma forma sentencial "{A+B}c" ele não irá continuar a derivação caso a string a ser casada seja "{bb+cc*+ed}" pois logo após o caractere } não existe um caractere c na string a ser casada.
O algoritmo pode ser melhorado e basicamente funciona percorrendo os terminais de uma forma sentencial com base no string de entrada.
Para mais informações veja o código da função podarDerivacao() em ParserConversor.java


Falow

Ajuda

Olá Pessoal,

Vou precisar de ajuda. O código ficou um pouco mais extenso do que pensei e não foi implementado quase nada ainda.

O código já tem 40 arquivos e só o que implementei foi:
- Gramática para ER
- Conversão de ER para gramática
- Parser para validação da ER e parser proposto em nosso paper.
- Já está também implementado o esqueleto do sistema e das conversões.

Para piorar tive que mudar algumas coisas e implementar outras que não tinhamos previsto e não estou conseguindo tempo para realizar testes em todo o código.

Será que alguém se compromete a realizar os testes e reportar.

Manasseis e Felipe, precisamos dos algoritmos o quanto antes, temos que fazer todo o resto ainda e para implementar o resto precisamos desta primeira parte, pelo menos a criação das tabelas LL1 para parser.

Aguardo sua opiniões.

Dúvida implementação

Olá Pessoal,

Estava fazendo a implementação da primeira parte de conversão e fui adicionar as funcionalidades de /n e {n}
Ainda não fiz o /n, mas o {n} quando fui fazer me surgiu uma dúvida. A princípio achei melhor fazer por gramática e encontrei a seguinte gramática:


S->A|B|C|D|T|{A}|{B}|{C}|{D}
A->F+F|F+FX|{F+F}X|F+{FX}
X->+FX|+F|+{FX}
B->GY|G{Y}
Y->G|GY|G{Y}
C->(A)*|(B)*|(C)*|(D)*|T*|({A})*|({B})*|({C})*|({D})*
D->(A)~|(B)~|(C)~|(D)~|T~|({A})~|({B})~|({C})~|({D})~
F->B|C|D|T|{B}|{C}|{D}|T
G->(A)|C|D|T|({A})|{C}|{D}|T
T->a

Não sei se está correta esta gramática, queria pedir uma ajuda verificar se está correta.
Outra maneira seria implementar a funcionalidade {n} por algoritmo mesmo, mas creio que seria tão complicado quanto.

Outra dúvida que me surgiu é que estou pensando em copiar o código do parser e fazer um parser customizado para a conversao de ER para gramática. Creio que será mais fácil, pois de outra forma irá sujar muito o código de nosso parser.

Aguardo opiniões.

Novo Draft - Versao Final?

Senhores,

A ultima versao do paper foi enviada:
- Adicionei nosso diferencial de validacao da expressao recebida com gramatica especifica antes da geracao das cadeias
- Deixei claro que geramos gramaticas ambiguas, mas nao recursao a esquerda, embora tenhamos uma tecnica para o caso de recursao a esquerda ser necessario/desejado
- Nao coloquei as modificacoes propostas pelo Vitor, pois ainda nao sei se vao entrar no sistema -> Por favor validem tecnicamente que esta ok
- O comparativo com as ferramentas vistas eu procurei fazer de uma forma mais na funcionalidade em relacao a teoria do que a usabilidade pratica (afinal, nao iremos parsear uma linguagem para geracao de compiladores).


Aguardo feedback ;)


Rodrigo.

Artigo - Mudancas

Vitor,

Irei deixar claro que nao geramos recursao a esquerda nao sera causada, mas deixarei como um subtopico o que escrevemos, pois acho que foi uma das questoes que pensamos e resolvemos.

Vou reestruturar o artigo um pouco para ficar mais claro e mais academico, ainda mais que agora como viram tirei a parte de cronograma de implementacao que fazia com que o artigo nao pudesse ser tao academico...

Melhorei as questoes das cadeias ja e adicionei os itens que recomendou... Ainda hoje envio a nova versao para todos.


Abracos,