PAPAGENO: un generatore automatico di parser paralleli
Responsabile:
Horizon 2020
-
Data inizio: 00/00/2014
-
Sommario
L’uso crescente di processor multicore ha prodotto una forte spinta verso la costruzione di algoritmi paralleli su diversi fronti applicativi. Il caso del parsing (analisi sintattica) deterministico costituisce allo stato dell’arte un’eccezione dovuta alla natura intrinsecamente sequenziale dell’analisi sintattica legata a gramamtiche LL o LR. PAPAGENO, al contrario sfrutta la proprietà di parsabilità locale posseduta dalle grammatiche a precedenza di operatori ottenendo significativi risultati in termini di speed-up.
Risultati del progetto ed eventuali pubblicazioni scientifiche/brevetti
In seguito allo sviluppo di un algoritmo di parsing parallelo basato sulla proprietà di parsabilità locale delle grammatiche a operatori, è stato realizzato un tool, PAPAGENO, in grado di generare automaticamente analizzatori sintattici. Lo strumento accetta una specifica sintattica simile a quella del generatore di parser stato dell' arte, GNU Bison, e genera una libreria di analisi sintattica in C.
Sono stati condotti esperimenti generando con successo parser paralleli per il linguaggio di descrizione dati JSON e il linguaggio di programmazione Lua. Ulteriori sviluppi in corso coinvolgono l'integrazione con la valutazione semantica dell'input (attraverso grammatiche ad attributi) e l'applicazione all' analisi incrementale di testi.
PAPAGENO è disponbile liberamente, sotto licenza GPL all' indirizzo https://github.com/PAPAGENO-devels/papageno.
Pubblicazioni:
Sono stati condotti esperimenti generando con successo parser paralleli per il linguaggio di descrizione dati JSON e il linguaggio di programmazione Lua. Ulteriori sviluppi in corso coinvolgono l'integrazione con la valutazione semantica dell'input (attraverso grammatiche ad attributi) e l'applicazione all' analisi incrementale di testi.
PAPAGENO è disponbile liberamente, sotto licenza GPL all' indirizzo https://github.com/PAPAGENO-devels/papageno.
Pubblicazioni:
- A. Barenghi, S. Crespi-Reghizzi, D. Mandrioli, F. Panella, and M. Pradella. The PAPAGENO parallel-parser generator. In A. Cohen, editor, Compiler Construction - 23rd International Conference, CC 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5-13,. Proceedings, volume 8409 of Lecture Notes in Computer Science, pages 192–196. Springer, 2014.
- A. Barenghi, S. Crespi Reghizzi, D. Mandrioli, and M. Pradella. Parallel parsing of operator precedence grammars, Inf. Process. Lett., 113(7):245–249, 2013.
- A. Barenghi, S. Crespi Reghizzi, D. Mandrioli, F. Panella, and M. Pradella. Parallel Parsing Made Practical, Science of Computer Programming (in pubblicazione).
