[Cup e Jflex]Grammatica che riconosca il linguaggio C

[ceccoggi]

Salve a tutti, in questi giorni sto sclerando abbastanza per creare un traduttore che formatti un programma scritto in C e compia determinate operazioni.
Dopo aver perso un po' di tempo a crearmi una grammatica che riconoscesse TUTTO il linguaggio C, sento il professore il quale mi dice che posso utilizzare una grammatica già fatta che si trova online.

Qualcuno sa dove posso trovare online una scanner e un parser che mi riconoscano tutto il linguaggio C?!

[anx721]

per lex e yacc che sono la versione C di jlex e cup:

http://www.lysator.liu.se/c/ANSI-C-grammar-l.html
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html

prova anche acercare sul sito si antlr


Ad ogni modo la cosa nn è molto semplice se devi effettuare il parsing di programmi reali perchè se trovi un parser c lo trovi funzionante per una qualche versione standard come l'ansi c. Per effettuare il parsing di un programma C è necessrio che sia nota la definizione dei tipi. a Ad esempio la dichiarazione:

typedef int a;
a(b);

definisce b come una variabile di tipo a, ovvero int, mentre:

typedef int b;
a(b);

a(b) è considerato il prototipo della funzione a che riceve un unico
argomento di tipo b, mentre il tipo di ritorno non è specificato e per default
è int.


Quindi senza la dichiarazione del typedef non puoi parsare la dichiarazione a(b) !

Per includere la definizione dei tipi in un file devi prima effetuare la fase di preprocessing (che ad esempio inserisce nel file sorgente i file. h necessari in cui sono psesso definiti tipi e macro) e sul risultato di tale fase puoi fare il parsing. Pero quando fai il preprocessing i compilatori reali inseriscono varie istruzioni e costrutti che non sono riconducibili a una versione standard del C (anche parole chiavi proprie e tipi predefiniti del compilatore). Quindi un parser per l'ansi C non riesce a parsare il programma ottenuto. Io non sono riuscito a trovatre un parser in grado di parsare programmi reali sottoposti a preprocessing con gcc o vc. Il fatto è che andrebbe usato il parser stesso del compilatore che effettua il preprocessing per essere sicuro di riuscire a parsare il file ottenuto. Il che non è possibile. Se invece devi solo parsare programmini semplici a scopo di dattico uno dei parser disponibili online potrebbe esserti sufficiente.

[ceccoggi]

Grazie mille, mi sei stato molto d'aiuto!

In ogni caso, il traduttore che devo fare è a scopo didattico, e non prevede il riconoscimento di un file c che richiami altri files. Nelle specifiche inoltre non viene richiesto un parsing sulle direttive preprocessore, in quanto comunque anche i compilatori "veri" lasciano appunto quelle direttive al preprocessore...

L'unica cosa è che sto traduttore deve riconoscere le definizioni di nuovi tipi mediante typedef.
Ora il problema è questo: i tipi conosciuti me li riconosce lo scanner e li passa al parser come simboli non terminali.
Ma per i nuovi tipi come potrei fare?

Mi era venuta in mente un'idea ma non so come portarla a termine.
Immaginiamo una cosa tipo:
typedef struct newstr nuovotipo.

Per fare una cosa del genere mi creo una regola nella grammatica tipo:
ntipo ::= TYPEDEF STRUCT ID ID
dove le parole in maiuscolo sono simboli terminali (ossia riconosciuti dallo scanner) e quelli in minuscolo quelli non terminali.
Una volta fatto questo, aggiungerei a destra della regola un'azione che mi inserisca in una HashMap il nuovo tipo definito.
Il problema qual'è?
Che se per riconoscere un tipo normalmente faccio una cosa tipo:

type ::= SIGN_MODIFIER TYPE
    	| LENG_MODIFIER TYPE
    	| SIGN_MODIFIER LENG_MODIFIER TYPE
    	| TYPE
;

ossia con tutta la parte destra della regola fatta da simboli terminali passati dallo scanner, come faccio a mettere una regola che mi dica, non solo di cercare tra quei terminali, ma anche nella mia HashMap?

Questo è il mio problema principale, purtroppo il mio materiale didattico si riduce a pochissime slides, e il tempo per portare a termine questo progetto è molto stringente e non mi permette di leggere tutta la documentazione che potrei trovare online.

Grazie mille x un eventuale aiuto

[anx721]

Costruire un parser completo per il C, come per qualsiasi linguaggio di programmazione, non è affatto banale e comuqnue non riesci a farlo in poco tempo se non hai già buona dimestichezza con grammatiche, parser e gli strumenti che producono riconoscitori lessicali e parser. La sintassi del C è più complessa di quella che sembra; le dichiarazioni del C nella loro forma più generale sono ricorsive e a volte molto complicate da leggere ad occhio nudo, sebbene nella maggior parte dei casi venga usata la forma più semplice.
Inoltre la sintassi per le dichiarazioni è talmente generale che comprende in sè la dichiarazione di tipi, di variabili e di funzioni come casi particolari. per cui si veuoi scriverti la grammatica a mano ti consiglio di seguire pari pari quella del link che ti ho riportato e che è basata sulla grammatica del Ritchie.

Poichè è un po che non mi occupo di queste cose non so darti una soluzione certa, pero ad esempio a livello di parsing la grammatica che ti ho linkato riporta come ultima regola per la risoluzione dei tipi:

type_specifier
: VOID
| CHAR
| SHORT
| INT
| LONG
| FLOAT
| DOUBLE
| SIGNED
| UNSIGNED
| struct_or_union_specifier
| enum_specifier
| TYPE_NAME
;

dove TYPE_NAME è linkato a questa funzione:

int check_type(){
// it actually will only return IDENTIFIER
return(IDENTIFIER);
}

cioè a livello di parsing puoi considerare un identificatore come un nome di tipo. Dopo che hai effettuato il parsing e hai un albero di sintassi astratta effettui il controllo semantico tramite visita dell'albero per verificare che tutti gli identificatori usati come tipi siano stati correttamente definiti in dichiarazioni typedef.

[Tonyony]

se lysator non è raggiungibile la stessa grammatica si può trovare anche qui

http://www.quut.com/c/ANSI-C-grammar-l.html
http://www.quut.com/c/ANSI-C-grammar-y.html