PAPAGENO: a Parallel Parser GeneratOr
Research Area:
Research Lines:
Research Lines:
Responsible:
Horizon 2020
-
Start date: 2014-00-00
-
Project abstract
The increasing use of multicore processors has deeply transformed computing paradigms and applications.
The wide availability of multicore systems had an impact also in the field of compiler technology, although the research on deterministic parsing did not prove to be effective in exploiting the architectural advantages, the main impediment being the inherent sequential nature of traditional LL and LR algorithms. PAPAGENO, an automated parser generator, instead exploits the local parsability property which is peculiar of operator precedence grammars (OPG) to produce parallel parsers. Such parsers have shown highly significant results in terms of spped-up w.r.t. traditional sequential parsing.
The wide availability of multicore systems had an impact also in the field of compiler technology, although the research on deterministic parsing did not prove to be effective in exploiting the architectural advantages, the main impediment being the inherent sequential nature of traditional LL and LR algorithms. PAPAGENO, an automated parser generator, instead exploits the local parsability property which is peculiar of operator precedence grammars (OPG) to produce parallel parsers. Such parsers have shown highly significant results in terms of spped-up w.r.t. traditional sequential parsing.
Project results
After developing a parallel parsing algorithm based on the local parsability property of the operator precedence grammars, a tool, PAPAGENO, able to generate automatically syntactic analyzers was developed. The tool accepts a syntax specification in a format similar to Bison, and generates a syntax analyzer in C.
So far the tool has been used to generate parallel parsers for the languages LUA and JSON. Further applications are going on; integration with semantic evaluation (through attribute grammars) and application to incremental analysis are also under development.
The PAPAGENO tool is freely available at
https://github.com/PAPAGENO-devels/papageno.
Publications:
So far the tool has been used to generate parallel parsers for the languages LUA and JSON. Further applications are going on; integration with semantic evaluation (through attribute grammars) and application to incremental analysis are also under development.
The PAPAGENO tool is freely available at
https://github.com/PAPAGENO-devels/papageno.
Publications:
- 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, to appear.