Skip to content

Latest commit

 

History

History
47 lines (32 loc) · 1.87 KB

README.md

File metadata and controls

47 lines (32 loc) · 1.87 KB

PAPAGENO

PArallel PArser GENeratOr based on Floyd's Operator Precedence Grammars

PAPAGENO is a functional and efficient parallel parser generator.

It generates parallel C parsers starting from a grammar specification with the same syntax as Bison.

The generated parsers are self-contained and can be used with a common GNU Flex generated lexer without further effort.

The generated parsers have been tested successfully on x86_64 and ARM architectures.

PAPAGENO is realized in Python 2.x.

Authors and Contributors

Acknowledgements

We acknowledge the support of Ermes Viviani for the development of the initial codebase.

References and Publications

The performances attained with a PAPAGENO-generated JSON parser scale almost linearly with the number of threads you are willing to employ. The properties of Floyd's operator precedence grammars allow to split the parsing work among different threads without wasting computation effort when combining the results (no partial reparsing needed). You can find some benchmarks in:

Alessandro Barenghi, Ermes Viviani, Stefano Crespi Reghizzi, Dino Mandrioli and Matteo Pradella. PAPAGENO: a parallel parser generator for operator precedence grammars in Proceedings of the 5th International Conference on Software Language Engineering,
Lecture Notes in Computer Science, volume 7745, pp 264-274, Springer, ISBN:978-3-642-36088-6. PDF Draft

A description of the algorithm employed in PAPAGENO is available in:

Alessandro Barenghi, Stefano Crespi Reghizzi, Dino Mandrioli, Matteo Pradella, Parallel Parsing of Operator Precedence Grammars Information Processing Letters, 2013, ISSN 0020-0190 PDF