[Java] Java e grammatiche...

[Xidius]

Salve ragazzi, il mio problema ha a che fare col riconoscimento delle grammatiche, cioè di queste cose qui: http://it.wikipedia.org/wiki/Grammatica_regolare

La mia idea è quella di riuscire a far riconoscere alla macchina delle espressioni del tipo:

S -> A
A -> b | c ( | sta per oppure )

e di farci con esse metodi di sostituzione ( si parte dalla S e si deve arrivare a delle lettere piccole in questo caso b o c )
Il mio problema è proprio quello di fare tutto ciò col Java...
Il dubbio mio principale è: come fare a fargli capire che "A" è diverso da "a". ( domanda lecita dato che devo lavorare con caratteri piccoli e grandi ).
Sinceramente nn so dove cominciare; nn so se devo rappresentare tutto con le stringhe, cercando una mezza specie di classificazione per fargli capire che le stringhe a sinistra hanno delle funzioni e quelle a destra altre... nn so come fargli capire il termine "->"...
Insomma ho i soliti dubbi di chi come me parte da zero...
Potreste darmi una mano? Grazie

[lovaz]

Tempo fa ho fatto una piccola classe che rappresenta una grammatica,
con relativo calcolo degli insiemi nullable, first, follow.
Se vuoi nel pomeriggio te lo posto.

[Xidius]

magari, ti ringrazio

ho letto sulla documentazione java2 questo http://java.sun.com/j2se/1.5.0/docs/api/java/util/regex/Pattern.html

Potrebbe essermi utile?

[Angus]

Se non devi necessariamente fare tutto da solo ma puoi utilizzare delle librerie ti consiglio di partire dai seguenti link:

JFlex (http://jflex.de/)
CUP (http://www2.cs.tum.edu/projects/cup/)
javaCC (https://javacc.dev.java.net/)

[pisto]

magari, ti ringrazio

ho letto sulla documentazione java2 questo http://java.sun.com/j2se/1.5.0/docs/api/java/util/regex/Pattern.html

Potrebbe essermi utile?
penso proprio di sì, che mi risulti è il package fatto apposta per ottenere informazioni da un stringa

[Xidius]

Putroppo devo fare da solo, senza l'ausilio di qualche strumento esterno...
nn so se mi conviene usare array multidimensionali o vettori per memorizzare queste stringhe....

comunque quel package potrebbe fare al caso mio; vorrei quindi memorizzare queste "stringhe" in una struttura per poi farci degli opportuni controlli e sostituzioni...
l'idea è questa:

S->ABB
AB->bc
B->b
A->a

ad esempio, concettualmente potrei sostituire AB con bc e B con b, cosi da avere bcb
oppure le due B con le due b piccole e la A con la a, cosi da avere abb

nn so se mettere tutto in un array multidimensionale dove in prima colonna metto S, AB, B, A e nelle righe metto ABB, bc, b, a; poi scannerizzo la prima parte delle righe successive a S, cioè, AB, B, A e vedo se ognuna appartiene al lato destro di S ( ad esempio trovo che AB è contenuto in ABB ), se lo trovo sostituisco fino a farmi venire alla fine di tutto una stringa di caratteri piccoli ( quindi ad ogni passo dovrò fare una specie di controllo carattere ).

Su per giu l'idea è questa, solo che la pratica.....

[lovaz]

Cioe' vuoi generare stringhe a caso?

Comunque ti posto il mio codice di un po' di tempo fa,
senza calcolo degli insiemi, tanto non ti interessa.

Prima di tutto ho fatto una classe che rappresenta una produzione NT -> T:

class Prod
{
private char left;
private String right;

public Prod(char l, String r)
{
left = l;
right = r;
}

public char getLeft()
{
return left;
}

public String getRight()
{
return right;
}

public String toString()
{
return "" + left + " -> " + right;
}
}

Come vedi il non terminale a sinistra è rappresentato da un carattere,
tu in una ne metti due, mi suona strano...

Poi la classe che rappresenta la grammatica:

public class Gram
{
private Set<Character> terminali, nonTerminali;
private Prod[] produzioni;
private char simboloIniziale;

public Gram(char simboloIniziale, Prod... produzioni) // varargs
{
this.simboloIniziale = simboloIniziale;

terminali = new HashSet<Character>();
nonTerminali = new HashSet<Character>();

this.produzioni = produzioni;

for(Prod p : produzioni)
nonTerminali.add(p.getLeft());

for(Prod p : produzioni) {
String r = p.getRight();

for(int c = 0; c<r.length(); c++)
if( !nonTerminali.contains(r.charAt(c)) )
terminali.add(r.charAt(c));
}
}

/* stampa la produzioni */
public String toString()
{
String pr = "";
for(Prod p : produzioni)
pr = pr + "\t" + p + "\n";

return pr;
}


La prima grammatica che hai scritto la costruisci con:
Gram gr = new Gram( 'S', // simbolo iniziale
new Prod( 'S', "A" ), // "S -> A"
new Prod( 'A', "b" ), // "A -> b"
new Prod( 'A', "c" ) // "A -> c"
);

[Xidius]

tu in una ne metti due, mi suona strano...

le grammatiche di tipo 0 e di tipo 1, a sinistra possono avere anche piu caratteri, le grammatiche di tipo 2 e di tipo 3, a sinistra hanno solo un carattere

detto ciò, devo supporre che a sinistra ci stiano anche più di un carattere, appartenenti all'unione dell'alfabeto sia terminale che non ( quindi possono esserci sia maiuscole che minuscole ).

per curiosità, hai fatto anche tu degli studi/progetti su queste cose?

[mad_hhatter]

avevo realizzato un generatore di stringhe terminali a partire da una grammatica letta da un file, ma dovrei cercare il codice... in ogni caso il fulcro della questione e' che una produzione e' rappresentata da un oggetto con 2 campi: il membro di sinistra e quello di destra. Mi pare che in java 'A' sia sempre diverso da 'a' quindi non dovresti aver problemi. Per la generazione avevo usato derivazioni leftmost...

[lovaz]

Quel programmino lo avevo fatto per Compilatori, ma usavamo
anche javacup, jlex (mi sembra si chiamassero cosi') e altri.

Se devi gestire piu' caratteri a sinistra usa comunque una classe
con campi tipo stringhe o array, non ti consiglio di "impelagarti" con array multidimensionali.

[Xidius]

Quel programmino lo avevo fatto per Compilatori, ma usavamo
anche javacup, jlex (mi sembra si chiamassero cosi') e altri.

Se devi gestire piu' caratteri a sinistra usa comunque una classe
con campi tipo stringhe o array, non ti consiglio di "impelagarti" con array multidimensionali.

jlex l'ho sentito... però questo lavoro purtroppo devo farlo tutto a mano e senza strumenti esterni :)
Inoltre mi hanno chiesto pure di usare ricorsione e backtracking, il che, aggrava ancora di piu le cose... comunque, certo, potrei creare proprio classi con all'interno array di stringhe del tipo ['S->A','A->b', 'AA'], anche se il problema è fargli capire la stringa AA e fargli capire la sostituzione di stringhe, quando le scannerizza...
Percaso potresti postare il codice di quel programma, magari potrebbe servirmi come esempio per avere una qualche idea...

[lovaz]

Eccolo qua; non e' niente di speciale comunque, rispetto a quello che
ho postato aggiunge solo il calcolo degli insiemi.
Carica la grammatica da file di testo - vedi commento in testa al main.