[C] Algoritmo di parsing

[Y3PP4]

Sera a tutti,

premetto che quanto stò per chiedervi non è riferito al contest aperto pochi giorni fà (sull'implementazione di un interprete), ma sto sempre continuando con il mio parser iniziato qualche tempo fà e su cui ho postato diversi topic (per aiuti vari).

Oggi sono qui a chiedervi, secondo voi come dovrei procedere nell'analisi lessicale.
Mi sono venute in mente due possibili soluzioni, delle quali preferisco la prima.

Dunque, la prima prevede l'analisi dei singoli caratteri della riga e in base al carattere trovato decidere cosa mi aspetto dopo. Se dopo segue un carattere non previsto restituisco l'errore. Questo mi piace sia per la possibilità di semplificare al minimo le funzioni (KISS rule) sia perchè analizzo solo fino a che non trovo un carattere inaspettato.
Ovviamente bisogna poi prevedere delle eccezioni gravi e non (i classici errors e warning).

Aggiungo anche che il parser mi serve per un piccolo linguaggio di configurazione che potrei in seguito usare in qualche progetto, e mi piacerebbe farlo elegantemente - non è un vero e proprio linguaggio con tutti i suoi costrutti ed elementi, l'unico costrutto esistente è il for che serve per analizzare delle variabili globali - che permettono di definire delle keywords da usare, per comodità, per definirci poi i parametri, insomma per essere chiari, se il linguaggio viene usato con il programma X permetto di definire i parametri dichiarando una stringa come valore di una variabile, e quindi usare quella stringa per accedere alle proprietà necessarie - .

La seconda ipotesi che mi è venuta in mente (ma che non mi piace granchè) è provare a usare la funzione strtoken sulla stringa: se mi restituisce un valore pari alla lunghezza della stringa -1 (\0) non è stato possibile "tokenizzare" e provo con un'altro carattere, se non trova nessun token aspettato (o = o . per accedere ai parametri) restituisce errore. Ovviamente questa seconda soluzione prevede la ripetizione di token sulla stessa stringa, perdendo tempo, e restituendo in certe condizioni in un errore generico "expected = or ." etc...

Concludo dicendo che per accedere ai parametri e come modello di configurazione mi stò basando sulla documentazione di configurazione di lighttpd, che ha un linguaggio snello e utile. (non sul loro codice perchè voglio farlo io - coi miei metodi -).

Voi cosa ne pensate? Avete qualche idea o soluzione migliore ?

Grazie mille,

buona serata a tutti.

[Vincenzo1968]

A me piace la prima ipotesi. Puoi implementare uno scanner a mano utilizzando un automa a stati finiti come ho fatto io nel contest(file scanner.h e scanner.c).
In alternativa puoi utilizzare un generatore automatico di scanner:

Per Windows:
http://gnuwin32.sourceforge.net/packages/flex.htm

Per Linux:
http://flex.sourceforge.net/

Si tratta di specificare una serie di espressioni regolari; a partire da queste, Flex genera l'analizzatore lessicale.

Per il parser puoi utilizzare Bison:

Per Windows:
http://gnuwin32.sourceforge.net/packages/bison.htm

Per Linux:
http://www.gnu.org/software/bison/

I manuali contengono una serie di esempi che illustrano molto bene l'utilizzo di questi preziosi strumenti(utilizzerò Flex/Bison nella seconda parte del contest).

;)

[Y3PP4]

A me piace la prima ipotesi. Puoi implementare uno scanner a mano utilizzando un automa a stati finiti come ho fatto io nel contest(file scanner.h e scanner.c).
In alternativa puoi utilizzare un generatore automatico di scanner:

Per Windows:
http://gnuwin32.sourceforge.net/packages/flex.htm

Per Linux:
http://flex.sourceforge.net/

Si tratta di specificare una serie di espressioni regolari; a partire da queste, Flex genera l'analizzatore lessicale.

Per il parser puoi utilizzare Bison:

Per Windows:
http://gnuwin32.sourceforge.net/packages/bison.htm

Per Linux:
http://www.gnu.org/software/bison/

I manuali contengono una serie di esempi che illustrano molto bene l'utilizzo di questi preziosi strumenti(utilizzerò Flex/Bison nella seconda parte del contest).

;)

Anzitutto grazie mille per la risposta (seguendo altri due topic ancora poco e mi perdevo il mio -.-), almeno qualcuno mi ha degnato di un cenno :p.

In effetti stò cercando di realizzare la prima ipotesi, il fatto è che volendo semplificare il processo, ho creato una funzione che mi restituisce il carattere successivo, una che in base alla variabile (costante) passata stampa il tipo di errore ed esce (tutte le funzioni sono di tipo void, in caso di errore si termina da li, non ritorno valori per errore e uso puntatori ovunque posso per passare le variabili per riferimento e mantenere il programma soft-senza tante copie dello stesso valore.

Attualmente il parser prevede -piuttosto semplicisticamente, ma ora punto a un mockup su cui studiare le tecniche - un while principale che mi restituisce le linee (una alla volta).
Quindi rimuovo commenti, \t, blank spaces, e il \n di fine linea. (userò lo \0 per contare il fine stringa.
Il primo problema da risolvere, che mi è venuto in mente col senno di poi, è che se non lascio il \n devo settare una variabile che mi dica: la stringa che hai preso era la riga intera o no (cosi da prevedere eventuali stringhe non concluse spezzate con \ su più righe. In assenza di questo ritorno l'errore e se lo uso su una riga non completa - che deve continuare - è errore per via di un carattere inaspettato).

Poi la stringa ripulita deve essere analizzata dal parser, quindi dichiaro una variabile char e ci metto il primo carattere. Lo analizzo e se trovo un carattere (tramite un if di comparazione) dovrei metterci dentro un'altro if e così via? Sò che questa non è la soluzione giusta, perchè manca in genialità, estensibilità e funzionalità.
Pseudocodice:
indice = 0;
char = stringa[indice];
Se char == "C":
char = stringa[++indice];
Se char == "I":
char = stringa[++indice];
// continuo cosi fino a verificare la parola"CIAO"
Se char == "O":
nuovavar = // contienimi la parola.

Ovviamente non mi piace questo modo - e sono certo che non è il modo giusto - (anche se io uso la funzione gimmeNextChar( &stringa, &carattere, &indice ) ).

Proverò a dare una occhiata ai link che hai postato nell'altro topic, sperando di capire il metodo giusto.Intanto guarderò anche il source della tua soluzione (in verità ho già guardato il parser e ho tratto ispirazione su come ottenere il token seguente (anche se non ho letto la tua implementazione, ma lo farò).
Infatti la mia gimmeNextChar è semplicemente una definizione come segue:
*(i++);
carattere = stringa[i];


Lo sò non è una implementazione funzionale o brillante ma sono in fase di apprendimento :D

Una ultima domanda che vorrei proprio risolvere: come fà un parser a tenere in memoria (parlando molto semplicemente - per quanto possibile -) a tenere in memoria n variabili del tipo x, y, z senza sapere a priori quante ne ha nel sorgente ?
Come fà il codice C a diventare una cosa così dinamica da (non solo) allocare dinamicamente lo spazio (che è il minimo, trovando l'occorrenza lo fà) ma a tenerne traccia per quando verrà chiamata in seguito ? non posso dichiarare mille variabili aspettandomene max mille nel sorgente e poi conservare li i riferimenti :s

Grazie mille (vado a scaricarmi i pdf).

Ps. voglio - per ora - implementarlo da zero per un semplice motivo: voglio imparare.
Altrimenti imparerei come usare flex e mi troverei un sorgente pronto, ma non saprei perchè fà quello e non saprei a cosa sbatti in contro scrivendo un parser (che un domani potrebbe servire per la sua versatilità).

[cdimauro]

Il mio consiglio è di utilizzare ANTLR (http://www.antlr.org/), che trovo molto semplice e intuitivo per realizzare analizzatori lessicali, sintattici e di AST.

E' in grado di generare anche codice C (oltre a diversi altri linguaggi), ed è stato sviluppato un comodissimo tool (http://www.antlr.org/works/index.html) per la scrittura, il testing e la generazione di codice.

Con ANTLR è veramente una pacchia scrivere parser. :p

[Y3PP4]

Il mio consiglio è di utilizzare ANTLR (http://www.antlr.org/), che trovo molto semplice e intuitivo per realizzare analizzatori lessicali, sintattici e di AST.

E' in grado di generare anche codice C (oltre a diversi altri linguaggi), ed è stato sviluppato un comodissimo tool (http://www.antlr.org/works/index.html) per la scrittura, il testing e la generazione di codice.

Con ANTLR è veramente una pacchia scrivere parser. :p

Uh! Comodo conoscerne l'esistenza. Per ora voglio imparare ciò che ci stà sotto ad un parser - per quanto semplice le basi son le stesse - ma devo assolutamente provare questo ANTLR, sembra molto interessante :D (potrebbe servirmi in mooolti progetti).
http://www.faccine.eu/smiles/1145789664-Felici%20(53).gif
(notare la, seppur minima, somiglianza dello smile con la posa dei tipi nelle foto sul loro sito ci ho messo un po' a cercarla... v.v godetevela per lo meno)...

Grazie mille!

[PGI-Bis]

Io per il contest ho usato un approccio diverso (ho iniziato, poi ho ripreso, poi ho buttato via tutto e ho ri-ripreso perchè lo sto usando come scusa per maneggiare un linguaggio che sto ancora imparando).

Anzichè un parser unico che esamina il sorgente ho tanti parser quanti sono gli enunciati della grammatica.

Ogni parser applica sè stesso all'intero sorgente e quanto trova un "match" lo comunica a accumulatore di segnali.

I parser sono massimamente specifici nel senso che, ad esempio, ne ho uno che cerca tutti gli identificatori (lettera e (lettera o cifra)*), uno che cerca tutte le stringhe, uno che cerca tutti i commenti eccetera.

Quando l'accumulatore riceve un segnale verifica se l'enunciato o la parte di enunciato trovata e segnalata si sovrappone ad un enunciato precedente.

Ad esempio nella linea:

/* Questa non è una "stringa" */

Il parser che va a caccia dei commenti segnala la porzione

/* Questa non è una "stringa" */

Il parser che va a caccia delle stringhe segnala:

"stringa"

L'accumulatore verifica la sovrapposizione dei due segnali (calcolata semplicemente in base ai limiti del segnale nel codice sorgente) ed elimina il segnale sovrapposto "più debole". Nel caso di stringhe e commenti ho specificato all'accumulatore che le stringhe cedono di fronte ai commenti.

Lo stesso accumulatore si occupa poi di ordinare i segnali "sopravvissuti" in base al loro punto di inizio.

Il tutto ha l'obiettivo di effettuare l'analisi del codice in parallelo (i parser e l'accumulatore sono gestiti da un pool di Thread).

Il parsing funzionava. Ero quasi arrivato alla compilazione ma poi ho avuto la bella pensata di riscrivere tutto perchè non era abbastanza elegante (manco fossi Ferrè alla sfilata di Parigi).

[Y3PP4]

Io per il contest ho usato un approccio diverso (ho iniziato, poi ho ripreso, poi ho buttato via tutto e ho ri-ripreso perchè lo sto usando come scusa per maneggiare un linguaggio che sto ancora imparando).

Anzichè un parser unico che esamina il sorgente ho tanti parser quanti sono gli enunciati della grammatica.

Ogni parser applica sè stesso all'intero sorgente e quanto trova un "match" lo comunica a accumulatore di segnali.

I parser sono massimamente specifici nel senso che, ad esempio, ne ho uno che cerca tutti gli identificatori (lettera e (lettera o cifra)*), uno che cerca tutte le stringhe, uno che cerca tutti i commenti eccetera.

Quando l'accumulatore riceve un segnale verifica se l'enunciato o la parte di enunciato trovata e segnalata si sovrappone ad un enunciato precedente.

Ad esempio nella linea:

/* Questa non è una "stringa" */

Il parser che va a caccia dei commenti segnala la porzione

/* Questa non è una "stringa" */

Il parser che va a caccia delle stringhe segnala:

"stringa"

L'accumulatore verifica la sovrapposizione dei due segnali (calcolata semplicemente in base ai limiti del segnale nel codice sorgente) ed elimina il segnale sovrapposto "più debole". Nel caso di stringhe e commenti ho specificato all'accumulatore che le stringhe cedono di fronte ai commenti.

Lo stesso accumulatore si occupa poi di ordinare i segnali "sopravvissuti" in base al loro punto di inizio.

Il tutto ha l'obiettivo di effettuare l'analisi del codice in parallelo (i parser e l'accumulatore sono gestiti da un pool di Thread).

Il parsing funzionava. Ero quasi arrivato alla compilazione ma poi ho avuto la bella pensata di riscrivere tutto perchè non era abbastanza elegante (manco fossi Ferrè alla sfilata di Parigi).
Uhm... ma non perdi tempo utile a prendere una stringa che poi potrebbe essere cancellata?
Va bene che esegui con multithreading ma intanto quel thread potrebbe leggere qualcos'altro.
Magari savare la posizione in cui inizia un commento (dove il cursore deve fermarsi di leggere la riga). Ma no... mi sembra anche troppo complesso.

Mi piace comunque la soluzione, la trovo una cosa che sà il suo perchè.
C'è solo sta cosa della possibilità di un lavoro nullo (il risultato viene cancellato) che non mi quadra... l'interprete dovrebbe essere "as fast as possible". Sicuro che con script complessi e pieni di commenti non perdi in prestazioni ?
PS. mi ricordi tanto i miei numerosi progetti. Anche io faccio spesso così. Lo faccio per imparare, ma spesso mi rammarico di non averne completati molti - è anche vero che i progetti che scelgo sono sempre ambiziosi per le mie capacità di quel momento -. Ma io a studiare soltanto non ci riesco. Voglio farlo per risolvere un problema, per verificare l'esistenza di soluzioni migliori... non mi accontento facilmente. (e infatti spesso ce l'ho in quel posto).

[Vincenzo1968]

Se non vuoi utilizzare tools automatici, la scelta migliore è un parser predittivo a discesa ricorsiva.
Una delle principali attrattive di questo metodo è proprio la facilità d'implementazione manuale: van Rossum (http://it.wikipedia.org/wiki/Guido_van_Rossum), per esempio, il suo parser l'ha implementato a mano, senza l'ulilizzo di strumenti come ANTLR ;)

Esempio:


L ::= A [b] C
A ::= a {a}
C ::= c {c}


Nella grammatica precedente abbiamo:

Simboli non terminali: L, A, C
Simboli terminali: a, b, c
Start symbol: L

La grammatica specifica che il nostro linguaggio è costituito da una stringa che comincia per una o più 'a'; può opzionalmente seguire una 'b'; la stringa deve concludersi con una o più 'c'.

L'implementazione di un parser predittivo a discesa ricorsiva prevede una funzione per ogni simbolo non terminale. Si comincia leggendo il primo carattere della stringa che diventa il cosiddetto token di lookahead. Si chiama la funzione che implementa lo start symbol.
Per ogni regola grammaticale si agisce come segue:
- per ogni terminale si controlla che corrisponda al token di lookahead. Nel caso positivo si legge il token successivo(che diventa il token di lookahead). Nel caso negativo si riporta un errore.
- per ogni simbolo non terminale si chiama la funzione corrispondente.

Ecco il codice, in C, che implementa il parser per la grammatica del nostro esempio:


#include <stdio.h>
#include <stdlib.h>

#define EOS '\0'

char g_lookahead;
int g_pos = 0;

char GetNextToken(char *s)
{
if ( s[g_pos] != EOS )
{
return s[g_pos++];
}
else
return EOS;
}

void match(char *s, char expected)
{
if ( g_lookahead == expected )
{
g_lookahead = GetNextToken(s);
return;
}

printf("Colonna %d : Errore di sintassi.\nlookahead : %c\nexpected : %c\n", g_pos, g_lookahead, expected);

exit(1);
}

void A(char *s)
{
match(s, 'a');
while ( g_lookahead == 'a' )
match(s, 'a');
}

void C(char *s)
{
match(s, 'c');
while ( g_lookahead == 'c' )
match(s, 'c');
}

void L(char *s)
{
A(s);
if ( g_lookahead == 'b' )
match(s, 'b');
C(s);
}

void Parse(char *s)
{
g_lookahead = GetNextToken(s);

L(s);
}

int main()
{
char * szProva = "aaaaaabccc";
//char * szProva = "xaaaaaabccc";
//char * szProva = "baaaaaabccc";
//char * szProva = "aaaaaaccc";

//char * szProva = "abc";
//char * szProva = "abbc";
//char * szProva = "bc";
//char * szProva = "ab";

Parse(szProva);
printf("\nLa stringa %s e' valida.\n", szProva);

return 0;
}


Nel nostro semplicissimo esempio, ogni token è costituito da un singolo carattere e, dunque, l'implementazione dell'analizzatore lessicale(funzione GetNextToken) si riduce alla restituzione del successivo carattere della stringa in input.

[PGI-Bis]

Se il linguaggio lo permette e non si vuole provare una cosa strampalata come la mia consiglierei invece un parser-combinator.

Un parser-combinator è come dice il termine un parser, cioè qualcosa che analizza il sorgente, combinabile. Lo scopo è quello di scrivere il parser semplicemente replicando la grammatica del linguaggio che si vuole esaminare. Ad esempio per la grammatica d'esempio Vincenzo1968 il parser espresso tramite combinatori è:

def L = A & b.opt & C
def A = a & (a*)
def C = c & (c*)
def a = Terminal("a")
def b = Terminal("b")
def c = Terminal("c")

&, opt e * sono tutti metodi del Parser che restituiscono combinazioni di Parser che sono a loro volta dei Parser. Un esempio completo è:

import java.nio.CharBuffer;

object Main {

def L = A & b.opt & C
def A = a & (a*)
def C = c & (c*)
def a = Terminal("a")
def b = Terminal("b")
def c = Terminal("c")

def main(args:Array[String]) = {
val source = CharBuffer.wrap(args(0))
var error = false;
while(!error && source.hasRemaining()) {
error = !L.apply(source)
}
if(error) {
println("Errore in: " + source.position);
} else {
println("La stringa e' corretta")
}
}
}

trait Parser {

def apply(buffer:CharBuffer) : Boolean;

def &(that:Parser) = new And(this,that);

def *() = new ZeroOrMoreTimes(this);

def opt() = new Opt(this);

def emit : (String=>Unit) = println;
}

class Terminal(token:String) extends Parser {

def apply(buffer:CharBuffer) = {
val pos = buffer.position;
val done = token.forall(c=>buffer.hasRemaining() && c == buffer.get());
if(!done) {
buffer.position(pos);
} else {
emit(token)
}
done;
}
}
object Terminal {
def apply(s:String) = new Terminal(s);
}

class Opt(a:Parser) extends Parser {

def apply(buffer:CharBuffer) = {
a.apply(buffer);
true;
}
}

class And(a:Parser, b:Parser) extends Parser {

def apply(buffer:CharBuffer) = {
val pos = buffer.position;
val done = a.apply(buffer) && b.apply(buffer);
if(!done) buffer.position(pos);
done;
}
}

class ZeroOrMoreTimes(p:Parser) extends Parser {

def apply(buffer:CharBuffer) = {
while(p.apply(buffer)) {}
true;
}
}

Qui manca un combinatore classico che è l'or che sarebbe:

class Or(a:Parser,b:Parser) extends Parser {
def apply(buffer:CharBuffer) = {
a.apply(buffer) || b.apply(buffer)
}
}

Ha il pregio della riciclabilità nel senso che una volta definiti quei tre o quattro combinatori di base puoi esprimere una gamma relativamente ampia di produzioni. C'è il vantaggio mimetico: tra la grammatica e il parser risultante c'è una corrispondenza visiva tanto elevata che i parser di questo tipo sono definiti grammatiche eseguibili.

[PGI-Bis]

Uhm... ma non perdi tempo utile a prendere una stringa che poi potrebbe essere cancellata?
Va bene che esegui con multithreading ma intanto quel thread potrebbe leggere qualcos'altro.
Magari savare la posizione in cui inizia un commento (dove il cursore deve fermarsi di leggere la riga). Ma no... mi sembra anche troppo complesso.

La soluzione che percorro io non è affatto vantaggiosa in termini di prestazioni perchè è vero che più thread concorrono al parsing ma ognuno di essi si accolla l'analisi di tutto il codice sorgente quindi anzichè avere un thread che fa una lettura ho dieci, venti, trenta Thread che fanno ognuno una lettura. Sarebbe vantaggioso separare il codice sorgente in blocchi e mandarli in analisi separatamente, cosa peraltro facile da realizzare nel sistema di cui parliamo perchè non c'è alcun vincolo di sequenzialità.

Quello che volevo sperimentare era invece il suo vantaggio in termini di flessibilità. Idealmente dovrei arrivare al punto in cui aggiungere una produzione alla grammatica si traduce nella creazione di un parser che emette un segnale con la priorità corretta e aggiugerlo al pool dei parser. A questo punto l'accumulatore riceverà i segnali del parser come già fa per ogni altro.

Cosa che al momento non posso sperimentare perchè al momento sto ancora scrivendo i parser lessicali.

[cdimauro]

Se non vuoi utilizzare tools automatici, la scelta migliore è un parser predittivo a discesa ricorsiva.
Una delle principali attrattive di questo metodo è proprio la facilità d'implementazione manuale: van Rossum (http://it.wikipedia.org/wiki/Guido_van_Rossum), per esempio, il suo parser l'ha implementato a mano, senza l'ulilizzo di strumenti come ANTLR ;)
Sì, ma dalla versione 2.5 Python utilizza un tool per la generazione automatica
del parser (http://www.python.org/dev/peps/pep-0339/). Vedi, in particolare, i primi file di questo (http://www.python.org/dev/peps/pep-0339/#important-files).

Inoltre, dalla pagina di ANTLR:

Testimonials

Kudos
Guido van Rossum
I'm actually really liking ANTLR! I have a pretty darn good velocity with...

;)

Comunque vedo che PGI è scatenato ormai con Scala. Chi lo ferma più. :D

[Y3PP4]

Anzitutto grazie a tutti per le risposte :)

Se non vuoi utilizzare tools automatici, la scelta migliore è un parser predittivo a discesa ricorsiva.
Una delle principali attrattive di questo metodo è proprio la facilità d'implementazione manuale: van Rossum (http://it.wikipedia.org/wiki/Guido_van_Rossum), per esempio, il suo parser l'ha implementato a mano, senza l'ulilizzo di strumenti come ANTLR ;)

Esempio:


L ::= A [b] C
A ::= a {a}
C ::= c {c}


Per adesso credo che guarderò questo tipo di parser, anche se dovrò poi implementare un semplice riconoscimento per delle keywords che mi permettano di accedere a valori del programma e settarne i parametri.

Nella grammatica precedente abbiamo:

Simboli non terminali: L, A, C
Simboli terminali: a, b, c
Start symbol: L

Dove posso guardare per qualche dettaglio sulla definizione della grammatica del linguaggio? ( per chiarirci :
L ::= A C
A ::= a {a}
C ::= c {c}
).

La grammatica specifica che il nostro linguaggio è costituito da una stringa che comincia per una o più 'a'; può opzionalmente seguire una 'b'; la stringa deve concludersi con una o più 'c'.

Ok

L'implementazione di un parser predittivo a discesa ricorsiva prevede una funzione per ogni simbolo non terminale. Si comincia leggendo il primo carattere della stringa che diventa il cosiddetto token di [b]lookahead. Si chiama la funzione che implementa lo start symbol.


Chiarissimo.

Per ogni regola grammaticale si agisce come segue:
- per ogni terminale si controlla che corrisponda al token di lookahead. Nel caso positivo si legge il token successivo(che diventa il token di lookahead). Nel caso negativo si riporta un errore.
- per ogni simbolo non terminale si chiama la funzione corrispondente.


Chiarissimo, soprattutto grazie all'esempio :D,
Ecco il codice, in C, che implementa il parser per la grammatica del nostro esempio:


Nel nostro semplicissimo esempio, ogni token è costituito da un singolo carattere e, dunque, l'implementazione dell'analizzatore lessicale(funzione GetNextToken) si riduce alla restituzione del successivo carattere della stringa in input.
Perfetto. Qualora avessi delle keywords agisco sempre char a char o si "tokenizza"?


La soluzione che percorro io non è affatto vantaggiosa in termini di prestazioni perchè è vero che più thread concorrono al parsing ma ognuno di essi si accolla l'analisi di tutto il codice sorgente quindi anzichè avere un thread che fa una lettura ho dieci, venti, trenta Thread che fanno ognuno una lettura. Sarebbe vantaggioso separare il codice sorgente in blocchi e mandarli in analisi separatamente, cosa peraltro facile da realizzare nel sistema di cui parliamo perchè non c'è alcun vincolo di sequenzialità.

Quello che volevo sperimentare era invece il suo vantaggio in termini di flessibilità. Idealmente dovrei arrivare al punto in cui aggiungere una produzione alla grammatica si traduce nella creazione di un parser che emette un segnale con la priorità corretta e aggiugerlo al pool dei parser. A questo punto l'accumulatore riceverà i segnali del parser come già fa per ogni altro.

Cosa che al momento non posso sperimentare perchè al momento sto ancora scrivendo i parser lessicali

Chiaro. Beh vista così sempra una cosa molto interessante, in termine di flessibilità ed estensione.
Bisognerebbe solo vedere se perdi tanto o poco in velocità rispetto a una soluzinoe alternativa.
Comunque complimenti per la soluzione :D

Se il linguaggio lo permette e non si vuole provare una cosa strampalata come la mia consiglierei invece un parser-combinator.

Uhm. Adesso mi guardo ben bene il tuo esempio cosi capisco bene bene come realizza la cosa - il concetto mi è chiaro -.

Se il linguaggio lo permette e non si vuole provare una cosa strampalata come la mia consiglierei invece un parser-combinator. :D
:D Quoto.

[Vincenzo1968]

Sì, ma dalla versione 2.5 Python utilizza un tool per la generazione automatica
del parser (http://www.python.org/dev/peps/pep-0339/). Vedi, in particolare, i primi file di questo (http://www.python.org/dev/peps/pep-0339/#important-files).

Inoltre, dalla pagina di ANTLR:

Testimonials

Kudos
Guido van Rossum
I'm actually really liking ANTLR! I have a pretty darn good velocity with...

;)


Non lo sapevo. Grazie per i link e le info. Comunque, ritengo che l'implementazione manuale dia, per così dire, più soddisfazione: hai più flessibilità rispetto all'uso di un tool automatico. Puoi gestire le azioni semantiche come più ti piace e sei libero di usare le strutture dati che preferisci. E, onestamente, mi sono divertito molto nello sviluppo del parser per il contest.
Ovviamente parliamo di piccoli progetti, come quello del contest. In caso contrario l'uso di tool automatici diventa quasi obbligatorio.


Comunque vedo che PGI è scatenato ormai con Scala. Chi lo ferma più. :D

Interessante il metodo utilizzato da PGI.


...
sono tutti metodi del Parser che restituiscono combinazioni di Parser che sono a loro volta dei Parser.
...


@PGI-Bis: è un metodo che ti sei inventato o esiste in letteratura?

[Vincenzo1968]

...
Dove posso guardare per qualche dettaglio sulla definizione della grammatica del linguaggio? ( per chiarirci :
L ::= A [b] C
A ::= a {a}
C ::= c {c}
).
...


Per le grammatiche puoi vedere questo pdf(paragrafo 3.2 grammatiche libere dal contesto):

http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/GramTopDown.pdf

Ti consiglio di studiartele bene, ché risultano indispensabili per l'implementazione di un parser(anche nel caso di un linguaggio semplice semplice).
La grammatica utilizzata nel pdf è di tipo BNF (http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form). La grammatica del nostro esempio è invece una grammatica EBNF (http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form).
In pratica, nelle grammatiche EBNF, si utilizza l'operatore {} per esprimere zero o più ripetizioni; l'operatore [] si usa per esprimere opzionalità.
Per esempio, {a} significa zero o più occorrenze del token 'a'. [x] significa che il token 'x' è opzionale.


Perfetto. Qualora avessi delle keywords agisco sempre char a char o si "tokenizza"?
...


Devi tokenizzare. Dammi il tempo di preparare qualche immagine e ti spiego il funzionamento di un DFA (http://en.wikipedia.org/wiki/Deterministic_finite-state_machine) adatto allo scopo.

[PGI-Bis]

E' un metodo troppo raffinato per venire dalle mie meningi :D.

Io sono partito da questo documento

http://bracha.org/executableGrammars.pdf

nella bibliografia ci sono un tot di altri riferimenti.

Concordo in pieno sul fatto che il fai da te sia molto più divertente oltre che propedeutico.

[Vincenzo1968]

E' un metodo troppo raffinato per venire dalle mie meningi :D.

Io sono partito da questo documento

http://bracha.org/executableGrammars.pdf

nella bibliografia ci sono un tot di altri riferimenti.

Concordo in pieno sul fatto che il fai da te sia molto più divertente oltre che propedeutico.

Grazie mille per il link. A prescindere da metodi e strumenti utilizzati, io trovo l'argomento molto affascinante: cosa c'è di più stimolante, per un programmatore, dell'implementazione di un proprio linguaggio di programmazione?

:)

[Y3PP4]

Per le grammatiche puoi vedere questo pdf(paragrafo 3.2 grammatiche libere dal contesto):

http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/GramTopDown.pdf

Ti consiglio di studiartele bene, ché risultano indispensabili per l'implementazione di un parser(anche nel caso di un linguaggio semplice semplice).
La grammatica utilizzata nel pdf è di tipo BNF (http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form). La grammatica del nostro esempio è invece una grammatica EBNF (http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form).
In pratica, nelle grammatiche EBNF, si utilizza l'operatore {} per esprimere zero o più ripetizioni; l'operatore [] si usa per esprimere opzionalità.
Per esempio, {a} significa zero o più occorrenze del token 'a'. [x] significa che il token 'x' è opzionale.
Devi tokenizzare. Dammi il tempo di preparare qualche immagine e ti spiego il funzionamento di un DFA (http://en.wikipedia.org/wiki/Deterministic_finite-state_machine) adatto allo scopo.
:-* mille grazie davvero - sia per BNF che per il DFA.
Grazie mille per il link. A prescindere da metodi e strumenti utilizzati, io trovo l'argomento molto affascinante: cosa c'è di più stimolante, per un programmatore, dell'implementazione di un proprio linguaggio di programmazione?

Una idea mi verrebbe... :D
PS. mi sto leggendo il pdf.

[Vincenzo1968]

Ecco i diagrammi di transizione per alcuni costrutti tipici dei linguaggi di programmazione:

Riconoscimento di operatori relazionali:
http://www.guidealgoritmi.it/images/ImgForums/lexer01.jpg

Riconoscimento di identificatori o keyword:
http://www.guidealgoritmi.it/images/ImgForums/lexer02.jpg

Riconoscimento di costanti numeriche(numeri in virgola mobile):
http://www.guidealgoritmi.it/images/ImgForums/lexer03.jpg

Riconoscimento di commenti in stile C(/* */):
http://www.guidealgoritmi.it/images/ImgForums/lexer04.jpg

Un automa a stati finiti deterministico si può rappresentare, graficamente, con un diagramma di transizione.
Lo stato iniziale dell'automa è rappresentato da un circoletto con una freccia entrante non proveniente da nessuno stato. Per esempio, nella prima immagine, lo stato iniziale è rappresentato dal circoletto etichettato dal numero 0. Un circoletto doppio indica uno stato finale(o accettante).

Con riferimento alla prima immagine, vediamo come si agisce .
Nello stato iniziale ancora non abbiamo letto nessun carattere dalla stringa di input. Leggiamo il primo carattere. Se è un '<' l'automa transita nello stato 1. Leggiamo il carattere successivo. Se è un '=' l'automa transita nello stato 2 che è uno stato accettante(abbiamo riconosciuto l'operatore relazionale '<=').
La funzione GetNextToken restituisce il token LE.
Facciamo un passo indietro e torniamo allo stato 1(abbiamo appena letto, dalla stringa di input, il carattere '<'. Se il carattere successivo è '>', l'automa transita nello stato 3 e restituisce il token NE(diverso da, '<>').
Torniamo nuovamente allo stato 1. Se il carattere successivo non è né '=', né '>', l'automa ritorna il token LT(minore, '<'). In quest'ultimo caso, la funzione GetNextToken deve ritornare l'ultimo carattere letto alla stringa di input(nel grafico questa cosa viene indicata dal simbolo * accanto al circoletto).

Veniamo adesso al riconoscimento di identificatori o keywords(seconda immagine). Nello stato iniziale, se il primo carattere letto dalla stringa è un carattere alfabetico(a-zA-Z) l'automa transita nello stato 10. Leggendo i caratteri successivi, l'automa permane nello stato 10 (questa cosa si rappresenta con una freccia uscente che ritorna nello stesso circoletto) finché non incontra un carattere diverso da una lettera o un numero. In questo caso si ritorna l'ultimo carattere letto alla stringa di input e, con la stringa appena letta, si fa una ricerca nella hashtable delle keywords. Se la stringa appartiene alle keyword, l'automa ritorna il token KEYWORD; altrimenti la stringa viene ritornata come IDENTIFIER.

La terza e la quarta immagine illustrano il riconoscimento di, rispettivamente, costanti numeriche(numeri in virgola mobile, compresa la rappresentazione scientifica) e commenti multiriga in stile C(/* */). Il funzionamento è analogo a quanto visto sopra.

L'implementazione in C è molto semplice. Si tratta di una funzione che legge, in un ciclo while, i caratteri della stringa in input uno per volta, e in base al carattere corrente transita da uno stato all'altro.

Per esempio, puoi vedere i file "scanner.h" e "scanner.c" della mia soluzione per il contest.

Puoi verificarne il funzionamento col seguente programma:


#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "scanner.h"

int main(int argc, char **argv)
{
Token token;

if ( argc < 2 )
{
printf("Specificare il nome di un file, prego\n");
return -1;
}

if ( !LeggiFile(argv[1]) )
return -1;

token.Value.vString = NULL;
GetNextToken(&token);
while ( token.Type != T_EOF )
{
switch( token.Type )
{
case T_ERROR:
break;
case T_UNKNOWN:
printf("carattere non riconosciuto: %c\n", token.Value.vChar);
break;
case T_ID:
if ( token.Value.vString != NULL )
printf("ID: %s\n", token.Value.vString);
break;
//case T_CHAR:
// printf("carattere: %c\n", token.Value.vChar);
// break;
case T_OPAREN:
printf("parentesi tonda aperta: (\n");
break;
case T_CPAREN:
printf("parentesi tonda chiusa: )\n");
break;
case T_QOPAREN:
printf("parentesi quadra aperta: [\n");
break;
case T_QCPAREN:
printf("parentesi quadra chiusa: ]\n");
break;
case T_SEMICOLON:
printf("punto e virgola: ;\n");
break;
case T_STRING_LITERAL:
printf("letterale stringa: %s\n", token.Value.vString);
break;
case T_INT_LITERAL:
printf("letterale intero: %d\n", token.Value.vInt);
break;
case T_REAL_LITERAL:
printf("letterale reale: %lf\n", token.Value.vDouble);
break;
case T_COMMA:
printf("virgola: ,\n");
break;
case T_KW_IF:
printf("T_KW_IF: if\n");
break;
case T_KW_ELSE:
printf("T_KW_ELSE: else\n");
break;
case T_KW_WHILE:
printf("T_KW_WHILE: while\n");
break;
case T_KW_DO:
printf("T_KW_DO: do\n");
break;
case T_KW_BEGIN:
printf("T_KW_BEGIN: begin\n");
break;
case T_KW_END:
printf("T_KW_END: end\n");
break;
case T_KW_ARRAY:
printf("T_KW_ARRAY: array\n");
break;
case T_KW_OF:
printf("T_KW_OF: of\n");
break;
case T_KW_STRING:
printf("T_KW_STRING: string\n");
break;
case T_KW_INT:
printf("T_KW_INT: int\n");
break;
case T_KW_REAL:
printf("T_KW_REAL: real\n");
break;
case T_KW_BOOL:
printf("T_KW_BOOL: bool\n");
break;
case T_KW_FALSE:
printf("T_KW_FALSE: false\n");
break;
case T_KW_TRUE:
printf("T_KW_TRUE: true\n");
break;
case T_KW_PRINT:
printf("T_KW_PRINT: print\n");
break;
case T_KW_READ:
printf("T_KW_READ: read\n");
break;
case T_OP_ASSIGN:
printf("T_OP_ASSIGN: =\n");
break;
case T_OP_AND:
printf("T_OP_AND: &\n");
break;
case T_OP_OR:
printf("T_OP_OR: |\n");
break;
case T_OP_NOT:
printf("T_OP_NOT: !\n");
break;
case T_OP_LT:
printf("T_OP_LT: <\n");
break;
case T_OP_LE:
printf("T_OP_LE: <=\n");
break;
case T_OP_EQ:
printf("T_OP_EQ: ==\n");
break;
case T_OP_NE:
printf("T_OP_NE: !=\n");
break;
case T_OP_GT:
printf("T_OP_GT: >\n");
break;
case T_OP_GE:
printf("T_OP_GE: >=\n");
break;
case T_OP_PLUS:
printf("T_OP_PLUS: +\n");
break;
case T_OP_MINUS:
printf("T_OP_MINUS: -\n");
break;
case T_OP_MULT:
printf("T_OP_MULT: *\n");
break;
case T_OP_DIV:
printf("T_OP_DIV: /\n");
break;
}

GetNextToken(&token);
}

FreeInputbuffer();

return 0;
}


L'output prodotto per il programma


real myVar;

begin
myVar = 8.25478E-5;
print myVar;
end


è il seguente:

http://www.guidealgoritmi.it/images/ImgForums/contest17img10.jpg

[cdimauro]

Non lo sapevo. Grazie per i link e le info. Comunque, ritengo che l'implementazione manuale dia, per così dire, più soddisfazione: hai più flessibilità rispetto all'uso di un tool automatico. Puoi gestire le azioni semantiche come più ti piace e sei libero di usare le strutture dati che preferisci. E, onestamente, mi sono divertito molto nello sviluppo del parser per il contest.
Diciamo che per un programmatore è un passaggio quasi obbligatorio quello dello scriversi il parser di un linguaggio a manina senza l'aiuto di nessuno strumento. :p
Ovviamente parliamo di piccoli progetti, come quello del contest. In caso contrario l'uso di tool automatici diventa quasi obbligatorio.
E li si apprezza meglio dopo essersi fatto il mazzetto. :D

[Y3PP4]

:eek:
Wow!

Che spiegazione esaustiva.
Mille grazie :D

Adesso provo a leggermi ben bene tutto il codice e se c'è qualcosa che non capisco mi prendo la libertà di postartelo qui - intendo qualcosa dell'algoritmo che non mi torna chiaro-.

Ti ringrazio per il tempo che hai dedicato alla spiegazione.
Adesso, intanto, mi scarico i tuoi file del contest per avere una visione completa del progetto.

Ciao!:yeah: