[Java] Realizzare un analizzatore sintattico

[TardoFreak]

Buon pomeriggio,

Anni addietro (tanti ), per imparare bene il Pascal ho realizzato un analizzatore sintattico. Analizzava la sintassi del pascal con il solito metodo ricorsivo basato sui grafi sintattici. C'erano quindi a disposizione il simbolo da analizzare, il simbolo successivo e l' analisi veniva fatta, appunto, richiamando ricorsivamente le procedure di analisi (AnalizzaEspressione, AnalizzaBlocco, ecc.).
Mi piacerebbe, come esercizio, fare una cosa analoga utilizzando Java, magari analizzando proprio un sorgente in Pascal come ho gia' fatto quella volta.
Di primo acchito penserei ad una classe all' interno della quale ci sono tutte le funzioni di lettura dei simboli e di analisi scritte come metodi privati. Funzionerebbe ma mi chiedevo, o meglio lo chiedo a Voi, se questo e' l' approccio giusto, se e' questo lo stile preferibile, soprattutto parlando di ricorsione.

Ringrazio anticipatamente.

[c1b8]

La cosa funziona ma così facendo non sfrutti la caratteristica di Java di essere ad oggetti.
Io creerei una classe Analizza dalla quale implementare le classi specifiche: AnalizzaEspressione, AnalizzaBlocco, ecc. Una per ogni tipologia di analisi da effettuare.
Ogni classe potrebbe quindi avere un unico metodo che verrebbe di volta in volta sviluppato in funzione dello specifico compito da svolgere.
Una classe principale poi decide quale oggetto/oggetti instanziare e richiamare per l'analisi del codice.

E' comunque una idea da sviluppare...

[TardoFreak]

Grazie per la risposta.
A questo punto si dovrebbe implementare anche un oggetto (diciamo statico) che restituisce i simboli letti dallo stream di ingresso (simbolo successivo e successivo+1) perche' ogni oggetto ne avrebbe bisogno.
Conviene fare una cosa del genere?

[c1b8]

Secondo me conviene di certo e ti spiego il mio punto di vista, come preferisco operare io, sperando che vi siano altri contributi. Sappiamo che ci sono ottimi programmatori in questo forum e sapranno consigliarti sicuramente meglio di me.

Prima cosa cerco di evitare il più possibile oggetti statici, sono fine a se stessi ed utilizzandoli i vantaggi di una programmazione ad oggetti viene notevolmente limitata. A volte sono inevitabili, ma nel tuo caso ne farei proprio a meno.
Seconda cosa, non vedere il problema da risolvere (quindi il programma da scrivere) solo nel suo complesso, ma, e sopratutto, in piccoli sotto problemi ognuno con una ben precisa definizione e non troppo estesi.
Cerco di spiegarmi seguendo quanto vuoi realizzare, devi:
- leggere dati da un file
- interpretare questi dati spezzandoli in simboli
- elaborare ogni simbolo
ecc.
Ognuna delle righe precedenti è una classe base, che prevede o meno di essere estesa. Ad esempio la lettura di dati da file potrebbe trasformarsi in lettura di un stream generico di dati e questa diventare 2 o più classi per la lettura da file, da seriale, da periferica qualsiasi. E' eccessivo per lo scopo che ti sei prefisso, ma a mio avviso si devono comunque fare questi esercizi di pensiero.
Elaborare i simboli diventa quella classe base, poi estesa da una classe specifica per ogni simbolo, che dicevo nel messaggio precedente. Se questa/e classi hanno bisogno del simbolo successivo e/o il successivo+1 ecc, riceveranno come parametro anche l'oggetto (realizzato alla riga 2, non alla 1) che si incarica di suddividere i simboli letti in input.
Dicevo anche di dividere la cosa in problemi il più possibile ben definiti, avremmo ad esempio potuto unire la suddivisione dei dati con la lettura degli stessi in un unico oggetto, ma questo rende l'oggetto meno immune a modifiche di una o dell'altra parte. Avendo due oggetti potresti modificarli/estenderli o portali in altri ambiti con più facilità.

Come detto prima questa visione potrebbe essere eccessiva per il tuo esempio, ma un buon esercizio non fa di certo male.

[TardoFreak]

E' tutta la sera che ci penso ma non riesco a vedere vantaggi nello sviluppare un programma del genere utilizzando gli oggetti. Questo e' il classico esempio dove la ricorsione e' praticamente indispensabile, e forse il mio schema mentale e' troppo rigido.
In pratica si potrebbe implementare una classe e chiamare l' istanza ad un singolo oggetto che restituisce il simbolo tramite un metodo. Dopo aver letto il primo simbolo deve per forza sapere da quale posizione nel file (o nella stringa di ingresso) leggere il simbolo successivo, quindi non deve essere distrutto ma deve persistere per tutto il processo di analisi.
Con un linguaggio strutturato gli si passa un puntatore al carattere della stringa, utilizzando un oggetto questa informazione dovrebbe tenerserla lui, al suo interno e, da quanto ho capito, non e' necessario che sia un oggetto statico, basta "tenerlo in vita"
Non riesco pero' a pensare come analizzare ad esempio un blocco tramite oggetti, visto che un blocco ne puo' contenere un altro e quell' altro altri ancora per un numero di livelli che non si conosce a priori.
O forse bisogna pensare a questi oggetti come a delle funzioni?
E, una volta che l' oggetto (funzione) ha terminato il suo lavoro e' necessario rimuoverlo? Penso di si.
Ma a questo punto non sarebbe meglio scrivere una classe per un siingolo oggetto che analizza tutto quanto?

Scusatemi, sto cercando di capire, di imparare il giusto approccio per usare al meglio il linguaggio.

[xyz]

Lo stack non è vietato usarlo in un linguaggio OO compresa una sua implementazione con classi.

Prova a vedere se questi programmi ti possono aiutare:

http://jflex.de/
http://www2.cs.tum.edu/projects/cup/
http://sakharov.net/fsm.html
http://unimod.sourceforge.net/fsm-framework.html
http://www.nunnisoft.ch/nunnifsmgen/
...

o altri basta cercare.

[TardoFreak]

Lo stack non è vietato usarlo in un linguaggio OO compresa una sua implementazione con classi.

Quindi (questa cosa non mi fa dormire) cerco di pensare ad oggetti e non a funzioni.
Tutto parte da un sorgente ASCII che e' l' oggetto base. Bisogna quindi capire se questo oggetto e' veramente un programma verificando la correttezza della sintassi, quindi in effetti l' oggetto e' il programma e su questo bisogna lavorare.
Quando si crea l' oggetto della classe "programma" questi e' vuoto e quindi ci deve essere un metodo che inserisca una stringa tipo MioProgramma.setSourceString(String s).
Poi ci sara' un metodo che mi dira' se il sorgente e' sintatticamente corretto MioProgramma.isCorrect() che ritorna un vero o falso.
E qui l' analizzatore sintattico ha fatto il suo lavoro, quindi e' interno all' oggetto programma.
Gli sviluppi futuri possono essere, ad esempio nel caso di un editor:
- un metodo per avere la lista degli identificatori, il che e' utile per navigare attraverso il sorgente.
- Un metodo per avere una stringa RTF con i simboli colorati.
- Un meotodo per ottenere il primo errore di sintassi in modo da visualizzarlo quando si edita.
- Altre ed eventuali.
- Se vogliamo fare i fighi un metodo per caricare un file da disco passandogli il nome completo del file.
E se bisognera' compilarlo (da analisi a sintesi il passo e' breve ... OK sto divagando ):
- Un metodo per avere, chesso', un sorgente in assembler.
- Un file di cross reference
- e cosi' via.
Le funzioni di lettura simboli e loro interpretazione restano cose che interessano solo l' oggetto, quindi possono essere implementate nel modo tradizionale all' interno della classe.

Mi pare sia l' approccio giusto.

Spero.

o altri basta cercare.

Sapessi cosa e (piu' o meno) dove cercare lo farei, ma non ho ancora le idee chiare , quindi ti ringrazio per i links.

[c1b8]

Se ho capito bene tu pensi di realizzare una unica classe Programma che contiene tutte le funzioni necessarie alla lettura ed alla interpretazione dei simboli, la cosa è sicuramente corretta, ma vediamo quali problemi potrebbe presentare, i primi che mi vengono in mente.
La funzione isCorrect() della classe dovrà compiere le seguenti attività:
- richiamare una funzione getSimbolo() per prelevare il prossimo simbolo dalla stringa sorgente
- riconoscere il tipo di simbolo e richiamare la specifica funzione di controllo
- la funzione di controllo dovrà a sua volta richiamare la getSimbolo() se necessita di un ulteriore simbolo
- ....
mi fermo qui perché non mi vengono in mente altre cose.....

Tutto perfetto, domani devi però implementare questo programma per elaborare una sorgente diversa da una semplice stringa. La prima cosa che mi viene in mente è che la getSimbolo() dovrà essere modificata per prevedere di leggere dati da sorgenti diverse, o comunque richiamare funzioni di lettura diverse in funzione della sorgente dati (quindi if al suo interno). Se poi dovesse cambiare il sistema di recupero del simbolo si dovrebbe implementare la getSimbolo() o creare una seconda getSimbolo() e modificare tutte le funzioni che la richiamano (le funzioni di controllo) per differenziare la chiamata (quindi altre if all'interno delle funzioni). Questi sono solo le prime due situazioni che mi vengono in mente.
Il risultato è insomma una più complessa manutenzione del codice in caso di implementazioni future, implementazioni che, almeno per me, sono difficilmente pianificabili alla prima stesura del programma.
Di soluzioni alla cosa probabilmente se ne possono trovare molte, ma una iniziale implementazione con "tante" classi ti consente di prevenire...
Se ad esempio la getSimbolo() fosse un metodo della classe Dati, creando ed instanziando la classe Dati2, che estende la Dati, con lo stesso metodo getSimbolo() implementato diversamente, non dovresti cambiare nulla nel resto del codice perché per le varie funzioni (o classi) di controllo è come se richiamassero sempre la stessa funzione. Le due diverse getSimbolo() saranno più semplici perché ognuna svolge il proprio compito senza dover avere if per differenziare le diverse situazioni.
Allo stesso modo se cambia la sorgente dati, creo una classe specifica che utilizzo senza dover modificare nulla nel resto del codice.
Spero di essere riuscito a spiegare la mia idea...

[TardoFreak]

Si, ti sei spiegato benissiimo ed e' un' ottima idea.

Ora ho le idee un po' piu' chiare e diverse cose su cui lavorare.

[TardoFreak]

Bene bene, ci sto lavorando.
Per non sprecare tempo sto realizzando una specie di preprocessore per crearmi le funzioni in C che definiscono le macchine a stati. In buona sostanza avro' un file sorgente con alcune mie parole chiave dove ci mettero' i sorgenti in C di ogni stato di funzionamento ed il preprocessore mi costruira' lo scheletro con lo switch, le varie label e la gestione del numero della fase. Niente di che ... pero', mentre mi studio il Java, mi creo una utility che mi rendera' la vita piu' semplice. Dopo di questo implementero' qualcosa di piu' corposo.
Ho quindi scritto la classe "Programma" come menzionato nel post prima, la quale ha un metodo "compila" che mi costruisce lo scheletro.

Cio' detto,
Vorrei avere la possibilita' di impostare il compilatore (o l' analizzatore o qualsiasi altra diavoleria) in modo da tenere la classe come e', e quando creo un' istanza specificare dopo, tramite apposito metodo o proprieta', il compilatore da usare.
In C gli passerei il puntatore ad una funzione (il compilatore) e quando compilera', invece di richiamare la funzione tramite il suo nome, chiamera' la funzione tramite il puntatore. Avrei cosi' la possibilita' di scrivermi un tot di funzioni a seconda di cosa dovrei compilare e la funzione chiamante non saprebbe nemmeno cosa sta chiamando perche' non serve saperlo.

In Java e' possibile fare una cosa del genere?
E se si, come?