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,

Implementação

Olá Pessoal,

Ainda não acabei mas acho que já dá para conseguirmos dividir as tarefas um pouco sem causar problemas.
No arquivo expressaoRegular.java existem as seguintes linhas no construtor da classe:

_ER = expressaoRegular;
_G = ConversaoER_Gramatica.criarGramaticaDeExpressaoRegular(this);

ou seja, depois de ler a expressao regular e guardar na classe, na segunda linha é interpretada a expressao regular e convertida para uma gramatica através de um parser ambiguo e analise do parser com o algoritmo de conversao proposto no paper. Como eu teria que fazer um parser ambiguo pois a gramatica de expressao regular é uma gramatica ambigua, ja aproveitei e estou implementado o nosso parser ao mesmo tempo.

Algumas etapas que não iriam atrapalhar a estrutura do programa eu pulei, como a implementação da criação do grupo FIRST and FOLLOW e o algoritmo para retirar ambiguidade a esquerda.

Sobre a recursao a esquerda, creio que não precisamos implementar, pois nosso algoritmo de conversão nunca gera recursao a esquerda. É até um ponto para podermos falar para o Rodrigo retirar do paper já que não tem coerência.

Sobre a pergunta do Rodrigo de onde acho melhor adicionar a secção do parser para gramática, creio que seja na seção B "Conversão de Expressão Regular para Gramática", indicar a gramática que estamos utilizando para interpretar a ER. OBS.: A gramática é ambigua e precisa de um parser ambíguo.
Nesta mesma secção está a explicação de como retirar recursão à esquerda, ao invés disto, mostrar que as regras nunca geram recursão a esquerda, pois sempre a esquerda existem símbolos terminais.

Mais uma coisa, mudei a sintaxe da cadeia de substituição:

/n casa com o caractere n
/nnn.../ onde n é somente digitos, casa com o índice nnn...

Desta forma, é possível criar expressoes regulares mais complexas com mais de 10 grupos.

Para o pessoal que vai me ajudar a implementar o código, dêem uma estudada na classe Gramatica e criem o algoritmo para criacao dos grupos First and Follow. Pode ser uma classe que implementa um método estático mesmo. O resultado desta classe vai ser utilizado para preencher a TabelaLL1, caso queiram dar uma estuda la também seria legal.
OBS.: Só lembrando, para gerar a tabela LL(1) é utilizado o seguinte procedimento:
Para uma producao A->alfa e para a TabelaLL1 onde cada célula da pode ser identificada como (A,a) sendo A uma variável e a um terminal. Preenchemos as células (A,a) da tabela TabelaLL1 adicionando alfa de A->alfa, para todo "a" em (A,a) em que "a" estiver em FIRST(alfa FOLLOW(A)).
Ou seja, seria interessante se o resultado do algoritmo fosse um vetor de terminais (Vector) para cada produção, para ficar melhor a implementação vocês poderiam:
1 - Adicionar public Vector _FirstFollow na classe Producao.
2 - Criar o algoritmo FIRST e o FOLLOW para cada producao e depois realizar o casamento preenchendo para cada producao o vetor _FirstFollow criado.

Falow

SVN

Olá pessoal,

Coloquei no Google o código que implementei até agora, não acabei ainda e não está funcional nada.
É melhor esperar para mudar alguma coisa, mas caso queiram já ir dando uma olhada.
Talvez eu mude muito coisa, então caso estejam ocupados, esperem até o próximo commit.

Falow

Artigo Draft final 1

Senhores,

Enviei o draft final 1 do artigo:
- Fiz as mudancas em todo o artigo para refletir a mudanca nas secoes
- Adicionei rapidamente uma secao de comparacao (com as referencias conforme o professor disse sentir falta)
- Adicionei conforme eu recomendei uma nova secao falando do parser para o caso da gramatica ambigua e os problemas que ja determinamos em tal parser (basicamente uma melhorada no que o Vitor propos e que ja debatemos)

O que falta:
- Colocar a parte da geracao de ER para gramatica conforme o Vitor colocou no Blog e que ja valida as regras de reescrita (Vitor: Onde vc acha que esta parte se encaixa melhor?).

Trabalhos Relacionados

Senhores,

Achei alguns trabalhos relacionados para compararmos no artigo:

oops -> http://ccl.pku.edu.cn/doubtfire/NLP/Parsing/Parsing_Algorithm/Top-down/An_Object_Oriented_LL%281%29parser_generator.pdf

ANTLR -> http://java-source.net/open-source/parser-generators/antlr

SABLECC -> http://java-source.net/open-source/parser-generators/sablecc

Tem varios outros no site:
http://java-source.net/open-source/parser-generators

Importante e bom para voces tambem verem e usarem como base, os codigos sao em java... Seria legal se pudessem me dizer o que acham que nossa implementacao vai diferir destes.

Artigo...

Pessoal,

Estou finalizando diversas questoes do artigo, mas o mais complicado esta encontrar elementos relacionados...

Seria legal fazermos uma lista do que é relacionado ao nosso trabalho, para que eu possa melhorar este item.

Conversão de ER para gramática

Estive pensando na madeira mais fácil de começarmos e cheguei a seguinte conclusão, depois espero as opiniões de vocês.

Nosso software irá receber primeiro uma lista de regras de reescrita, que define nosso sistema não determinístico, ocorrerá um processamento destas regras de reescrita e logo após será fornecida uma entrada para ser processada pelas regras.

Preferi partir então para a primeira etapa: a do processamento das regras de substituição. Como proposto no artigo, para cada regra de substituição pegamos sua expressão regular e a transformamos em uma gramática.

Na segunda parte, após o processamento das regras de reescrita, e já com a entrada para processamento, realizamos o parser de cada string com todas as gramáticas, que irá retornar diversas árvores de derivação. Percorremos as árvores de derivação que casaram criamos as novas strings de acordo com a cadeia de substituição da regra de reescrita específica.

Voltando à primeira etapa....

Para realizar a conversão da expressão regular em uma gramática através do método proposto no paper teremos interpretar a expressão regular de alguma forma. Lembrei quando o Rodrigo alertou na sala que teríamos que aceitar somente regras de reescrita válidas e resolvi matar dois coelhos com uma pancada só.

A descrição acima é de duas gramáticas que validam expressões regulares, se não casar, não é uma expressão regular válida, se casar percorremos sua árvore de derivação e aplicamos as regras de conversão propostas no paper.

Estas gramáticas estão no paper Enumerating Regular Expressions and Their Languages e podemos alterá-las para se adequarem a nossa gramática de expressão regular. Por exemplo, podemos não querer aceitar o símbolo vazio da variável C.

Porém antes de tudo, precisamos definir a versão final de nossa gramática de expressões regulares.

Abaixo segue minhas alterações das duas gramáticas acima para aceitar a gramática de expressões regulares proposta no paper, por favor verifiquem se está certo.

Exemplo de precedência entre os operadores

Abaixo segue uma gramática para interpretação de precedência entre os operadores * / + - diferenciando também número de variável:

Expression = Term [ExpressionRest] ;

ExpressionRest = "+" Expression
               | "-" Expression ;

Term = Factor [TermRest] ;

TermRest = "*" Term
         | "/" Term ;

Factor = Atom
       | "(" Expression ")" ;

Atom = NUMBER
     | IDENTIFIER ;

Aplicação

Pessoal,

Acredito que a idéa da derivação é bastante interessante, e também um tanto quanto mais passível de implementação em poucas semanas.

Imagino que podemos trabalhar com outros operadores como radiciação e/ou potenciação e assim termos precedência de operadores entre este e a multiplicação e adição.

Vamos procurar amadurecer o mais rápio póssível a idéia.

Att.
Felipe.

Aplicações

Olá Pessoal,

Estive pensando sobre a aplicação de nosso trabalho e acho que seria legal fazermos umas 3 aplicações simples apresentando os recursos desta técnica.
Duas aplicações que acho muito legais para trabalharmos é a de derivação automática e montagem do cubo mágico.

Sobre a derivação, podemos fazer alguma coisa parecida com o exemplo do paper. No paper ele deriva somente com os operadores soma e multiplicação. Podemos extender para mais alguns operadores, mas não precisa ser todos, e fornecendo uma expressão chagamos a sua derivada. Acho muito legal isto.

Sobre o cubo mágico, as regras de reescritas são os movimentos que podemos fazer no cubo, cada reescrita é um movimento. Para economizar memória diminuimos a quantidade de movimentos possíveis e podemos ir podando a árvore de possibilidades através de heurísticas. A heurística poderia ser alguma coisa como a quantidade de cores iguais na vizinhança de um quadradinho do cubo. Podemos melhorar também colocando as quinas do cubo mágico e o quadradinho do centro também com pesos diferentes, enfim ...
O sistema para de realizar movimentos quando o cubo estiver montado. Pode demorar um pouco para encontrar a solução, mas acho legal a nível de aplicação para exemplificar nosso trabalho.
Um outro problema que podemos fazer também é o problema da torre de hanoi, acho que é assim que escreve, ou qualquer outro problema combinatório.

Não sei se ficará muito corrido, mas se der podemos também mostrar nosso sistema provando teoremas a partir de algumas listas de axiomas ou então fornecendo uma lista de relacionamentos "a é pai de b" encontramos se c é pai de d, embora eu ache um pouco mais bobo.

Enfim, aguardo opiniões sobre as aplicações.

Falow

Chat Finalizacao do Artigo

Prof.,

Como fizemos um chat para discutir os aspectos finais do artigo e unir o que cada um fez, achei melhor fazer uma unica postagem. Fiquei meio surpreso que a participacao no projeto seja avaliada pelo blog, entao aqui vai :) hum... espero que nao tenhamos falado mal do professor, hueheheheh


Conversation with msn chat@hotmail.com at 5/3/2010 6:44:52 PM on rodrigofws@hotmail.com (msn)
(6:44:53 PM) ITA Manasseis Grupo entered the room.
(6:44:53 PM) rodrigofws@hotmail.com entered the room.
(6:44:53 PM) ITA - Felipe Grupo entered the room.
(6:45:16 PM) ITA Manasseis Grupo: O felipe esta de volta
(6:45:32 PM) ITA - Felipe Grupo: Boa noite senhores, desculpe a demora
(6:45:33 PM) ITA - Vitor Curtis - Grupo ITA entered the room.
(6:45:45 PM) ITA Manasseis Grupo: Agora vai rsrs
(6:47:21 PM) ITA - Felipe Grupo: Estou devendo a remoção de ambiguidade de uma gramática, que deve ser adicionado ao item IV - C
(6:47:38 PM) ITA - Felipe Grupo: Mas já estou ha algum tempo trabalhando nisso
(6:47:53 PM) ITA - Felipe Grupo: Está um pouco difícil, mas termino em instantes
(6:48:57 PM) ITA - Vitor Curtis - Grupo ITA: ok,
(6:49:15 PM) ITA - Felipe Grupo: ( Um Parser LL só pode trabalhar com gramáticas não ambuiguas sem infinitas recursoes a esquerda)
(6:49:22 PM) ITA - Vitor Curtis - Grupo ITA: estou lendo tbm sobre gramatica, mas comecei agora a estudar o que é gramática e já entendi o que é recursao a direita e a esquerda
(6:49:38 PM) ITA - Vitor Curtis - Grupo ITA: o metodo proposto para conversao de ER pra gramatica gera recursao pela direita
(6:50:04 PM) ITA - Vitor Curtis - Grupo ITA: e nao pela esquerda
(6:50:34 PM) ITA - Vitor Curtis - Grupo ITA: se a gramatica for recursiva a direita pode?
(6:50:42 PM) ITA - Vitor Curtis - Grupo ITA: eu acho q n hein!
(6:50:44 PM) Rodrigo (BSDaemon): ae, agora sim
(6:50:57 PM) ITA - Felipe Grupo: eu tambem acho q sim
(6:51:07 PM) ITA - Felipe Grupo: pelo que li o parser vai pela esquerda
(6:51:11 PM) ITA - Vitor Curtis - Grupo ITA: acha q n pode ou q pode?
(6:51:17 PM) Rodrigo (BSDaemon): q n
(6:51:41 PM) Rodrigo (BSDaemon): eu estou revisando a escrita... estou na pagina 3 e adicionando agora a parte do Manasseis referente ao estado da arte
(6:51:47 PM) Rodrigo (BSDaemon): estou colocando as referencias tbm
(6:52:04 PM) ITA - Vitor Curtis - Grupo ITA: c tiver recursao , e ele anda pela esquerda, uma hora irá cair na direito pelo backtracking, se tiver uma recursao pela direita no backtracking ele entra em loop, ou estou errado?
(6:52:09 PM) Rodrigo (BSDaemon): vi q vcs mencionam em algumas partes do paper algumas referencias, mas tem outras q como achei q faltava adicionei
(6:52:19 PM) ITA Manasseis Grupo: show
(6:52:28 PM) Rodrigo (BSDaemon): seria legal se vcs me falassem quais sao as referencias 1-4 q tinham pensado pois chamam no texto e nao tenho como asber qual dos papers seriam ;)
(6:52:42 PM) ITA - Felipe Grupo: então vitor
(6:53:01 PM) ITA - Felipe Grupo: pega esse exemplo:
(6:53:16 PM) ITA - Vitor Curtis - Grupo ITA: estas referencia 1-4 estao em qual texto?
(6:53:25 PM) ITA Manasseis Grupo left the room.
(6:54:53 PM) ITA Manasseis Grupo left the room.
(6:56:04 PM) ITA - Vitor Curtis - Grupo ITA: ?
(6:56:28 PM) ITA - Felipe Grupo: um minuto
(6:56:41 PM) ITA - Vitor Curtis - Grupo ITA: ok
(6:56:57 PM) ITA - Vitor Curtis - Grupo ITA: Rodrigo, as referencias de 1-4 sao de qual texto?
(6:57:00 PM) ITA - Vitor Curtis - Grupo ITA: o q eu passei?
(6:59:12 PM) Rodrigo (BSDaemon): Vitor, sim sim
(6:59:15 PM) Rodrigo (BSDaemon): tem 1-3 e depois 4
(6:59:27 PM) Rodrigo (BSDaemon): mas perae q jah mando pra vcs a versao revisada e ai soh vai faltar adicionar a referencia no final, saka?
(6:59:33 PM) Rodrigo (BSDaemon): jah estou colocando as chamadas as referencias
(6:59:41 PM) Rodrigo (BSDaemon): e criando um 'texto' pro estado da arte
(7:00:25 PM) ITA Manasseis Grupo: ok
(7:01:09 PM) ITA - Vitor Curtis - Grupo ITA: c for o meu texto, junto com o template, enviei um doc com o mesmo texto
(7:01:13 PM) ITA - Vitor Curtis - Grupo ITA: la tem as referencias
(7:02:02 PM) Rodrigo (BSDaemon): galera, rewriting via constraints pode ser traduzido (mantendo a ideia original) como reescrita via restricoes?
(7:02:36 PM) ITA - Felipe Grupo: sim
(7:03:15 PM) Rodrigo (BSDaemon): vitor seu ultimo email soh tem um anexo
(7:03:38 PM) Rodrigo (BSDaemon): achei aki o email q vc mandou com um ITA.docx
(7:03:39 PM) ITA - Vitor Curtis - Grupo ITA: acho q esta no anteriores, provavelmente o primeiro q enviei tem os dois
(7:03:57 PM) Rodrigo (BSDaemon): yeah, achei
(7:04:02 PM) Rodrigo (BSDaemon): ok, vou ver oq dah pra fazer, huahuahuahua
(7:07:09 PM) Rodrigo (BSDaemon): preciso de 2 referencias (se puderem tentar achar enquanto to terminando): Sistemas de substituicao sendo utilizados para resolucao de problemas combinatoriais
(7:07:20 PM) Rodrigo (BSDaemon): e para prova mecanica de teoremas
(7:09:01 PM) Rodrigo (BSDaemon): no final da secao B tem um comentario: Citar que este metodo gera uma gramatica com recursao pela direita
(7:09:06 PM) Rodrigo (BSDaemon): quem adicionou isto?
(7:10:03 PM) ITA - Vitor Curtis - Grupo ITA: eu
(7:10:28 PM) ITA - Vitor Curtis - Grupo ITA: o metodo de conversao gera recursao pela direita e nao sabia q pode ser utilizada uma gramatica assim no parser
(7:10:40 PM) ITA - Vitor Curtis - Grupo ITA: o felipe q esta pro dentro, estou estudadno ainda sobre gramatica
(7:10:44 PM) ITA - Vitor Curtis - Grupo ITA: para depois ler sobre parser
(7:12:50 PM) ITA - Felipe Grupo: Vitor e eu estamos acertando algumas coisas senhores, aguardem um instante que teremos a resposta para este item "Citar que este metodo gera uma gramatica com recursao pela direita"
(7:13:59 PM) ITA - Vitor Curtis - Grupo ITA: entao felipe, como eu estava t falando ...
(7:14:14 PM) ITA - Vitor Curtis - Grupo ITA: para o parser LL funcionar realmente não pode existir uma recursão pela direita
(7:14:32 PM) ITA - Vitor Curtis - Grupo ITA: quero dizer, pela esquerda
(7:14:44 PM) ITA - Vitor Curtis - Grupo ITA: serão entraria em um loop infinito, pois iria derivar pela esquerda no mesmo não-terminal e assim por diante
(7:16:01 PM) ITA - Vitor Curtis - Grupo ITA: porém, quando vc faz o parser sobre uma cadeia vc encontra um caminho para comprovar que a cadeia pertence a linguagem
(7:16:47 PM) ITA - Vitor Curtis - Grupo ITA: o que quero dizer é que em nosso caso, apos encontrar o caminho, teremos que percorre-lo e trocar os não-terminais correspondentes da forma como estará definido na cadeia de substituição
(7:16:49 PM) ITA - Vitor Curtis - Grupo ITA: dai q fode tudo
(7:17:06 PM) Rodrigo (BSDaemon): temos agradecimentos? vou tirar isto ok?
(7:17:15 PM) ITA - Vitor Curtis - Grupo ITA: porque desta forma, nós iríamos gerar string que casaram no parser através de apenas um caminho
(7:17:36 PM) ITA - Vitor Curtis - Grupo ITA: e na verdade teríamos q fazer todos os caminhos possiveis dentro da arvore de derivacao
(7:17:38 PM) ITA - Vitor Curtis - Grupo ITA: entendeu?
(7:17:59 PM) ITA - Vitor Curtis - Grupo ITA: pois uma cadeia, pode casar com uma expressao regular de diversas formas
(7:18:00 PM) ITA - Felipe Grupo: issoo!!! dai vem o BackTracking
(7:18:19 PM) ITA - Vitor Curtis - Grupo ITA: e um parser LL casa pelo caminho mais pela esquerda, logo faltam tbm todos os outros caminhos
(7:19:08 PM) ITA - Vitor Curtis - Grupo ITA: entao, mas caso estivermos utilizando um parser LL e a gramatica tenha recursao pela direita, náo vai entrar em loop pela direita pelo backtracking?
(7:19:15 PM) ITA - Felipe Grupo: mas se ele for recursivo e descendente ele faz toda a arvore
(7:19:54 PM) ITA - Vitor Curtis - Grupo ITA: hummm, pois é ... eu n entendi nada, mas realmente talvez funcione!
(7:20:05 PM) ITA - Vitor Curtis - Grupo ITA: putz, preciso ler para entender melhor
(7:20:16 PM) ITA - Vitor Curtis - Grupo ITA: vou tentar ler sobre gramatica e parser ainda hj
(7:20:21 PM) ITA - Felipe Grupo: olha o que o Ulman diz:
(7:21:48 PM) ITA - Vitor Curtis - Grupo ITA: acho q estou entendendo agora
(7:22:17 PM) ITA - Felipe Grupo: A análise sintatica top-down pode ser vista como a tentativa de se encontrar uma devivação mais a esquerda para uma cadeia de entrada. Equivalente pode ser vista como uma tentativa de se contruir uma arvore gramatical me pré-ordem...
(7:22:17 PM) Rodrigo (BSDaemon): pelo q eu li oq o Felipe diz esta certo, pq o backtracking garante q ele faz tda a arvore
(7:22:20 PM) ITA - Felipe Grupo: gramátiica:;
(7:22:50 PM) ITA - Felipe Grupo: S--> cAd
(7:23:05 PM) ITA - Felipe Grupo: A--> ab|a
(7:24:01 PM) ITA - Vitor Curtis - Grupo ITA: mas agora n estou entendendo entao o porque q o professor disse no e-mail q n pode ter recursao pela direita
(7:24:14 PM) ITA - Felipe Grupo: hummm.....
(7:24:22 PM) ITA - Vitor Curtis - Grupo ITA: sera q ele se enganou e quiz dizer esquerda:
(7:24:23 PM) ITA - Vitor Curtis - Grupo ITA: ?
(7:24:27 PM) ITA - Felipe Grupo: acho q sim
(7:24:42 PM) ITA - Felipe Grupo: é o que diz todas as leituras que fiz
(7:24:48 PM) ITA - Felipe Grupo: inclusive o Ulmman
(7:25:04 PM) ITA - Felipe Grupo: Olha o que ele diz:
(7:26:02 PM) ITA - Felipe Grupo: "Uma gramática recursiva a esquerda pode levar um analisador sintático de descendencia recursiva , mesmo com retrocesso, a um laço infinito...
(7:26:12 PM) ITA - Vitor Curtis - Grupo ITA: acho q entendi, ao fazer o casamento pelo parser, quando ele encontrar uma recursao pela direita ele irá matar toda a derivacao recursiva a direita porque não casará com a cadeia e seguirá com o backtracking para um vertice acima ne?
(7:27:11 PM) ITA - Felipe Grupo: vou ao banheiro e volto em um instante
(7:28:15 PM) ITA - Felipe Grupo: vitor não tenho certeza se ele mata toda a derivação abaixo
(7:28:59 PM) ITA - Felipe Grupo: mas o backtracking vai faze-lo subir cedo ou tarde
(7:29:05 PM) ITA - Vitor Curtis - Grupo ITA: Tipo A->aA|b vou tentar simular o parser LL com backtracking aqui na mao
(7:29:08 PM) ITA - Felipe Grupo: volto já
(7:29:12 PM) ITA - Vitor Curtis - Grupo ITA: ok
(7:29:27 PM) Rodrigo (BSDaemon): Manasseis: tah faltando uma bibliografia sua
(7:29:31 PM) Rodrigo (BSDaemon): ;/ hum, ok, ele nao tha aki
(7:29:31 PM) Rodrigo (BSDaemon): huahuahuahua
(7:29:36 PM) ITA - Felipe Grupo: para isso crie a arvore de dervação desta gramatica
(7:33:35 PM) Rodrigo (BSDaemon): meu, nao acho de forma alguma referencia pra isto q ele colocou
(7:33:36 PM) Rodrigo (BSDaemon): :/
(7:34:01 PM) ITA Manasseis Grupo: Fala rodrigo
(7:34:37 PM) ITA - Felipe Grupo: qual é o meu desafio agora: Ulman e outros autores afirmam que o parser LL não é capaz de trabalhar com uma gramática ambuigua. Se durante a conversão uma EX REG para GRAM, a gramática for ambuigua o sistema deverá converte-la???
(7:35:38 PM) ITA - Felipe Grupo: ( gramatica ambuiguas são gramaticas que podem gerar arvores de derivação a esquer e direita ao mesmo tempo )
(7:36:24 PM) ITA Manasseis Grupo: Matthew W Crocker- Local ambiguity: a parse derivation may fail later
(7:36:33 PM) ITA - Felipe Grupo: • Se uma gramática tem mais do que uma derivação mais à esquerda ou a direita, então a gramática é ambígua • Se houver mais do que uma árvore gramatical, então a gramática é ambígua Exemplo clássico — o problema do if-then-else
(7:37:38 PM) ITA - Felipe Grupo: Gramática:LL(1) e LR(1):Técnicas de parsing Top-down parsers (LL(1) derivação mais a esquerda, recursivo descendente) • Inicia na raiz da árvore e cresce em direção as folhas • Obtém uma produção e tenta associar a entrada • Se escolha errada pode tentar retroceder (backtrack) • Algumas gramáticas são livre de retrocesso (parsing preditivos ) • Não podem tratar com gramáticas recursivas a esquerda Bottom-up parsers LR(1) • L é porque a entrada é da esquerda para a direita • R é porque é feito usando derivação mais a direita e o 1 porque avalia um token adiante • Inicia nas folhas e cresce até a raiz • Inicia em um estado válido para os primeiros tokens
(7:39:27 PM) Rodrigo (BSDaemon): manasseis: esta eh a referencia?
(7:40:58 PM) ITA Manasseis Grupo: C. Kirchner, H. Kirchner, and M. Rusinowitch. Deduction with symbolic constraints. Revenue Fran caise d'Intelligence Arti cielle, 4, special issue on automated deduction:9{52, 1991.
(7:41:09 PM) ITA Manasseis Grupo: era esta que vc estava procurando?
(7:42:11 PM) ITA Manasseis Grupo: ITA Manasseis Grupo has nudged you!
(7:42:14 PM) ITA Manasseis Grupo: ops
(7:42:19 PM) ITA Manasseis Grupo: C. Kirchner, H. Kirchner, and M. Rusinowitch. Deduction with symbolic constraints. Revenue Française d'Intelligence Artificielle, 4, special issue on automated deduction:9-52, 1991.
(7:42:35 PM) Rodrigo (BSDaemon): era sim
(7:42:36 PM) Rodrigo (BSDaemon): beleuza
(7:42:41 PM) ITA Manasseis Grupo: show
(7:43:45 PM) Rodrigo (BSDaemon): faltam 2 referencias q precisamos
(7:43:54 PM) Rodrigo (BSDaemon): [1] Sistemas de substituições são utilizados na solução de problemas combinatoriais [2] e também podem ser utilizados para prova mecânica de teoremas
(7:43:57 PM) Rodrigo (BSDaemon): estas duas
(7:44:59 PM) Rodrigo (BSDaemon): gostaria de dizer pra vcs q curti o paper viu
(7:45:01 PM) Rodrigo (BSDaemon): esta muito legal
(7:45:09 PM) Rodrigo (BSDaemon): fiz mudancas minimas de escrita
(7:45:14 PM) ITA - Felipe Grupo: Q bom!!!
(7:45:33 PM) Rodrigo (BSDaemon): vamos fechar isto? oq falta alem da questao da recursao a direita
(7:45:34 PM) Rodrigo (BSDaemon): ?
(7:45:36 PM) ITA - Felipe Grupo: Preciso apenas ver a parte das Gramáticas ambiguas
(7:45:42 PM) Rodrigo (BSDaemon): ok
(7:46:00 PM) ITA - Felipe Grupo: O sistema deverá converter a gramática ambigua???
(7:46:06 PM) Rodrigo (BSDaemon): e este da questao da recursao a direita? querem comentar algo?
(7:46:11 PM) ITA - Felipe Grupo: se sim, estou vendo como
(7:46:11 PM) Rodrigo (BSDaemon): Felipe: Minha opiniao: Nao precisamos
(7:46:20 PM) Rodrigo (BSDaemon): podemos colocar como um fator limitante de nossa proposta
(7:46:22 PM) ITA - Vitor Curtis - Grupo ITA: voltei
(7:46:27 PM) ITA - Felipe Grupo: perfeito
(7:46:42 PM) ITA - Felipe Grupo: Vou comer e volto em meia hora?
(7:46:51 PM) ITA - Vitor Curtis - Grupo ITA: estou passando um pdf
(7:46:54 PM) Rodrigo (BSDaemon): nao rola fecharmos? falta tao pouco
(7:47:03 PM) Rodrigo (BSDaemon): mas se quizerem comer eu tbm vou ;)
(7:47:08 PM) ITA - Felipe Grupo: acredito que devemos ficar com a ideia da recursão a direita
(7:47:16 PM) Rodrigo (BSDaemon): almocar eh otimo
(7:47:22 PM) ITA - Vitor Curtis - Grupo ITA: n tem como passar por aqui?
(7:47:25 PM) ITA - Felipe Grupo: e eliminação de infinitas reciursoes a esquerda
(7:47:33 PM) ITA - Felipe Grupo: vitor--> não
(7:47:37 PM) ITA - Felipe Grupo: já tentei
(7:47:40 PM) Rodrigo (BSDaemon): Vitor: mandei via email o paper revisado, nao sei se jah viram
(7:47:43 PM) ITA - Felipe Grupo: manda no e-mail
(7:47:47 PM) ITA - Vitor Curtis - Grupo ITA: vou passar por email
(7:47:48 PM) ITA - Vitor Curtis - Grupo ITA: ok
(7:47:49 PM) Rodrigo (BSDaemon): considero aq enviei a ultima versao
(7:47:56 PM) Rodrigo (BSDaemon): entao se editarem algo, editem nela
(7:47:59 PM) ITA - Felipe Grupo: volto logo e fechamos a recursão
(7:48:05 PM) ITA - Felipe Grupo: até já.
(7:48:12 PM) Rodrigo (BSDaemon): esta versao foi baseada na Versao que o Vitor mandou por ultimo, com a adicao doq o Felipe enviou e doq o Manasseis enviou
(7:48:15 PM) Rodrigo (BSDaemon): vejam oq acham
(7:48:26 PM) Rodrigo (BSDaemon): deixei em vermelho a qeustao da citacao (que deve ou nao esr retirada/complementada)
(7:48:48 PM) ITA - Vitor Curtis - Grupo ITA: queria saber c isso é um parser LL?
(7:48:58 PM) ITA - Vitor Curtis - Grupo ITA: andando pela esquerda da arvore
(7:49:45 PM) ITA - Vitor Curtis - Grupo ITA: sobre a ambiguidade, acho que podemos somente citar que precisa ser tirada e no outro paper nos descrevemos o paper
(7:49:49 PM) ITA - Vitor Curtis - Grupo ITA: o metodo*
(7:50:01 PM) ITA Manasseis Grupo: muda a referência 13
(7:50:51 PM) Rodrigo (BSDaemon): ja mudei
(7:51:08 PM) Rodrigo (BSDaemon): onde acham q devemos falar da ambiguidade? no comeco antes da tecnica?
(7:51:27 PM) ITA - Vitor Curtis - Grupo ITA: acho que na secao do parser
(7:51:39 PM) ITA - Vitor Curtis - Grupo ITA: dizer q precisa tirar a ambiguidade e recursao pela esquerda
(7:51:54 PM) ITA - Vitor Curtis - Grupo ITA: acho q a recursao pela direita nao ira nos causar problema, EU ACHO
(7:52:20 PM) Rodrigo (BSDaemon): ja falamos na verdade da ambiguidade
(7:52:23 PM) ITA Manasseis Grupo: Qual será nosso plano de execução?
(7:52:31 PM) ITA - Vitor Curtis - Grupo ITA: eu estava brincando e descobri um jeito tambem de descobrir confluencia em nosso sistema, mas deixa para o outro paper
(7:52:39 PM) ITA - Vitor Curtis - Grupo ITA: hummm
(7:52:44 PM) Rodrigo (BSDaemon): Antes de efetuar a operação de casamento sobre uma determinada regra de reescrita, o parser deve verificar se a gramática utilizada para realizar a respectiva operação de casamento possui ou não infinitas produções recursivas à esquerda ou se a mesma é ambígua, pois estes tipos de gramáticas podem levar o analisador a um ciclo infinito, impedindo que as demais regras de reescrita sejam aplicadas a uma determinada cadeia.
(7:52:45 PM) Rodrigo (BSDaemon): esta assim
(7:52:47 PM) Rodrigo (BSDaemon): ok por vcs?
(7:52:50 PM) ITA - Vitor Curtis - Grupo ITA: sei la entao rs... ja mandou o paper para podermos ver?
(7:52:58 PM) Rodrigo (BSDaemon): sim sim
(7:53:04 PM) Rodrigo (BSDaemon): soh faltou a referencia 13 na versao q enviei
(7:53:11 PM) ITA - Vitor Curtis - Grupo ITA: por mim, blz
(7:53:23 PM) Rodrigo (BSDaemon): eu acho q ficou legal tbm
(7:53:24 PM) ITA Manasseis Grupo: blz
(7:53:26 PM) Rodrigo (BSDaemon): pra mim tah fechado assim
(7:53:34 PM) Rodrigo (BSDaemon): e o comentario q tinha lah (Citar ...) vamos tirar?
(7:54:42 PM) ITA - Vitor Curtis - Grupo ITA: acho q pode tirar
(7:54:45 PM) ITA - Vitor Curtis - Grupo ITA: sei la rs..
(7:55:01 PM) ITA - Vitor Curtis - Grupo ITA: vou ler hoje a noite antes de ir para a aula e amanha t falo rs...
(7:55:27 PM) ITA - Vitor Curtis - Grupo ITA: inclusive, eu ACHO que o metodo para retirar a recursao pela esquerda pode ser tirado tbm
(7:55:38 PM) ITA - Vitor Curtis - Grupo ITA: pq eu ACHO q o metodo n gera recursao pela esquerda
(7:55:45 PM) ITA - Vitor Curtis - Grupo ITA: nem diretamente e nem indiretamente
(7:56:14 PM) Rodrigo (BSDaemon): a analise de convergencia nao vamos falar, certo?
(7:56:22 PM) ITA Manasseis Grupo: e o plano de execução?
(7:56:23 PM) ITA - Vitor Curtis - Grupo ITA: alias, o metodo para retirar recursao indireta a esquerda é este tbm?
(7:56:29 PM) ITA - Vitor Curtis - Grupo ITA: deixa pra depois
(7:57:30 PM) ITA - Vitor Curtis - Grupo ITA: o plano serve qualquer coisa, n vamos seguir mesmo rs..
(7:57:42 PM) ITA Manasseis Grupo: rs
(7:57:47 PM) Rodrigo (BSDaemon): falta o plano e o diferencial/conclusao soh
(7:57:50 PM) ITA Manasseis Grupo: coloca qualquer coisa lá
(7:57:51 PM) Rodrigo (BSDaemon): huahuhuahuahua
(7:58:21 PM) Rodrigo (BSDaemon): alguem tem MS Project ai? eh legal fazer akeles diagramas de uso de recursos
(7:58:21 PM) Rodrigo (BSDaemon): uhahuahua
(7:58:27 PM) ITA Manasseis Grupo: não
(7:58:52 PM) ITA - Vitor Curtis - Grupo ITA: nem, rs... quem vai ter coragem de fazer no excel? rs...
(7:59:10 PM) Rodrigo (BSDaemon): cara, vou por uma enrolacao aki e jah mando pra vcs ;)
(7:59:17 PM) ITA - Vitor Curtis - Grupo ITA: blz
(7:59:18 PM) ITA Manasseis Grupo: show
(7:59:29 PM) ITA - Vitor Curtis - Grupo ITA: deixa pra la o cronograma
(8:02:15 PM) ITA - Vitor Curtis - Grupo ITA: vcs acham legal colocar no cronograma a analise de convergencia e de confluencia?
(8:02:21 PM) ITA - Vitor Curtis - Grupo ITA: deixa queto ne?
(8:02:28 PM) ITA - Vitor Curtis - Grupo ITA: vai q n da certo rs...
(8:03:14 PM) Rodrigo (BSDaemon): alguem achou referencia pra estes 2 itens:
(8:03:15 PM) Rodrigo (BSDaemon): [1] Sistemas de substituições são utilizados na solução de problemas combinatoriais [2] e também podem ser utilizados para prova mecânica de teoremas
(8:03:23 PM) Rodrigo (BSDaemon): entao, eu nao colocaria NEM fudendo
(8:03:24 PM) Rodrigo (BSDaemon): huahuahua
(8:04:33 PM) ITA - Vitor Curtis - Grupo ITA: rs...
(8:04:44 PM) ITA - Vitor Curtis - Grupo ITA: isto eu peguei de um livro, so n lembro d onde rs...
(8:04:46 PM) ITA Manasseis Grupo: tira de lá
(8:04:47 PM) ITA - Vitor Curtis - Grupo ITA: dizia isto
(8:05:55 PM) Rodrigo (BSDaemon): O método apresentado possui vantagens em relação a performance devido a redução da complexidade de regras e também na formação das cadeias de derivação baseadas nas regras de substituição.  A análise do estado da arte relativo a reescrita e regras de substituição realizada demonstra que as limitações existentes referem-se ao não determinismo do problema e a obtenção de todas as cadeias de derivação fornecida pelo método proposto algo extremamente desejável.
(8:05:58 PM) Rodrigo (BSDaemon): nao estou muito empolgado
(8:06:07 PM) Rodrigo (BSDaemon): Manasseis:l nao da pra tirar nao
(8:06:13 PM) Rodrigo (BSDaemon): fica ruim falar isto sem a referencia, serio
(8:06:16 PM) Rodrigo (BSDaemon): seria legal vc lembrar o livro
(8:06:17 PM) Rodrigo (BSDaemon): ;/
(8:06:22 PM) Rodrigo (BSDaemon): ou vamos googlar
(8:06:23 PM) Rodrigo (BSDaemon): huauhahua
(8:09:21 PM) ITA - Vitor Curtis - Grupo ITA: acho q tem aqui mas n tenho certeza, to olhando
(8:09:26 PM) ITA - Vitor Curtis - Grupo ITA: M. Davis, Computability and Unsolvability. Dover Publications, New York (1982). H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions. Springer, New York, (1969).
(8:10:21 PM) Rodrigo (BSDaemon): achei
(8:10:27 PM) Rodrigo (BSDaemon): Combinatorial Optimization: Algorithms and Complexity [Unabridged] (Paperback) ~ Christos H. Papadimitriou Christos H. Papadimitriou (Author) › Visit Amazon's Christos H. Papadimitriou Page Find all the books, read about the author, and more. See search results for this author Are you an author? Learn about Author Central (Author), Kenneth Steiglitz (Author)
(8:10:33 PM) Rodrigo (BSDaemon): pronto, pra um e outro pro outro
(8:16:45 PM) ITA - Vitor Curtis - Grupo ITA: acharam tudo ai?
(8:16:54 PM) ITA - Vitor Curtis - Grupo ITA: ou falta sobre os problemas combinatoriais?
(8:21:16 PM) ITA - Vitor Curtis - Grupo ITA: n achei mesmo essa porcaria
(8:24:51 PM) ITA Manasseis Grupo: olha o que achei sobre estado da arte: O Estado da Arte em
(8:26:00 PM) ITA - Vitor Curtis - Grupo ITA: vai mandar por aqui?
(8:26:08 PM) ITA - Vitor Curtis - Grupo ITA: ou para olhar no paper q o rodrigo passou?
(8:26:40 PM) ITA Manasseis Grupo: por aqui
(8:28:30 PM) ITA Manasseis Grupo: Ao estudar os métodos apresentados,, nota-se a existência de diversas dificuldades e que, em cada proposta, os autores precisam propor critérios próprios durante o processo de inferência de gramáticas, tais como:
(8:28:36 PM) ITA Manasseis Grupo: características de exemplos, critérios de junção de estados, critérios para realizar tratamento de casos não determinísticos e ambiguidades, alem de utilização de geradores de parses para validação entre outros.
(8:30:14 PM) ITA - Vitor Curtis - Grupo ITA: eu estou viajando agora, rs... o que cada um está fazendo?
(8:30:19 PM) ITA Manasseis Grupo: Nem sempre os critérios que auxiliam em um método podem ser úteis para determinados casos e podem prejudicar o desempenho em outros
(8:30:30 PM) ITA Manasseis Grupo: O que vocês acham?
(8:31:18 PM) ITA - Vitor Curtis - Grupo ITA: isto seria no estado da arte?
(8:33:12 PM) ITA Manasseis Grupo: estranho né. O tema dela é: Um estudo dos processos de inferência de gramáticas Regulares e livres de contexto baseados em modelos adaptativos
(8:34:01 PM) ITA - Vitor Curtis - Grupo ITA: vixi maria, n estou entendendo nada
(8:34:11 PM) ITA - Vitor Curtis - Grupo ITA: 6 podem me cituar ai?
(8:34:42 PM) ITA Manasseis Grupo: Estava tentando melhorar o estado da arte e achei isto.
(8:35:01 PM) ITA - Vitor Curtis - Grupo ITA: humm
(8:35:31 PM) ITA Manasseis Grupo: até que achei que tem a ver com nossas dificuldades
(8:35:32 PM) ITA Manasseis Grupo: rs
(8:36:19 PM) ITA - Vitor Curtis - Grupo ITA: este paper esta aonde?
(8:37:39 PM) ITA Manasseis Grupo: http://www.pcs.usp.br/~lta/artigos/ivone_dissertacao.pdf
(8:38:34 PM) ITA Manasseis Grupo: pg 35
(8:42:46 PM) ITA Manasseis Grupo: faz um merge....
(8:45:14 PM) ITA - Vitor Curtis - Grupo ITA: acho q o trabalho é um pouco diferente
(8:45:24 PM) ITA Manasseis Grupo: sim
(8:45:36 PM) ITA - Vitor Curtis - Grupo ITA: neste trabalho ele pega um monte de cadeias e tenta descobrir qual gramatica q gera elas
(8:45:38 PM) ITA Manasseis Grupo: merge do estado da arte
(8:45:42 PM) ITA Manasseis Grupo: rs
(8:45:46 PM) ITA - Vitor Curtis - Grupo ITA: rs..
(8:45:50 PM) ITA - Vitor Curtis - Grupo ITA: aaa ta
(8:48:40 PM) ITA Manasseis Grupo: senhores, vou desconectar e quando chegar em casa (Daqui 1 hora) eu conecto novamente
(8:49:11 PM) ITA Manasseis Grupo: Quem vai imprimir?
(8:50:29 PM) ITA - Vitor Curtis - Grupo ITA: rodrigo, sobre o metodo mecânico, pode citar rsp.pdf, parsing techniques - a pratical guide e hand-final.pdf
(8:50:33 PM) ITA - Vitor Curtis - Grupo ITA: caso n tenha alguma me diga
(8:50:55 PM) ITA - Vitor Curtis - Grupo ITA: tem q imprimir ou podemos mandar via e-mail?
(8:51:33 PM) ITA Manasseis Grupo: boa pergunta
(8:52:33 PM) ITA Manasseis Grupo: fui
(8:53:06 PM) ITA Manasseis Grupo left the room.
(10:57:15 PM) Unable to send message.