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.