[JAVA] Riconoscimento di 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

[Andrea1979]

Non serve fare niente, salvo non sia un altro di quegli (inutili) esercizi scolastici, visto che java come tutti i linguaggi di programmazione, implementa in modo nativo un ottimo motore per le espressioni regolari....

http://java.sun.com/j2se/1.5.0/docs/...x/Pattern.html

[Xidius]

perfetto, questo 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.....

[lelefante]

Direi che un giretto su questo sito può fare al caso tuo

[Xidius]

lo conosco, ma vogliono che facciamo tutto a mano

[Ascia75]

cioè data una grammatica e una stringa, scopo del programma è controllare se la grammatica può generare quella stringa?

Butto li' una soluzione pensata 5 minuti, probabilmente nemmeno troppo efficiente, ma che descriverebbe appieno il problema in stile java:

definire un tipo di oggetto Simbolo
definire un tipo di oggetto NonTerminale che estende Simbolo
definire un tipo di oggetto Terminale che estende Simbolo

definire un tipo di oggetti Transizioni con due campi:
- il NonTerminale di partenza
- una lista di simboli (quindi terminali e non terminali) generati dal NonTerminale

notando che una transizione del tipo:
B -> CD | a | b
equilvarebbe a tre diversi oggetti Transizione per come ho descritto la soluzione.

Alternativamente, puoi inserire negli oggetti Transizione una lista di liste di simboli (una lista di simboli per ogni diversa produzione dallo stesso NonTerminale) cosi' da avere un solo oggetto Transizione per ogni NonTerminale che genera qualcosa.

In questo modo hai sotto forma di oggetti tutto quello che ti serve per procedere con la soluzione del tuo problema. Io non so come si fa a dire se una certa stringa appartiene ad un linguaggio, ma immagino tu abbia gli strumenti (teorici) per farlo.