<div class="csl-bib-body">
<div class="csl-entry">Chiari, M., Giornetta, M., Mandrioli, D., & Pradella, M. (2025). Boosting Parallel Parsing through Cyclic Operator Precedence Grammars. In <i>SLE ’25 : Proceedings of the SLE 2025 : 18th ACM SIGPLAN International Conference on Software Language Engineering</i> (pp. 44–56). Association for Computing Machinery. https://doi.org/10.1145/3732771.3742712</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/217251
-
dc.description.abstract
Deterministic parsing of tree-structured data is usually performed sequentially left-to-right. Recently however, also motivated by the need to process extremely large data sets, a parallel version thereof has been devised which, thanks to the theoretical features of operator precedence languages (OPL) particularly well-suited to split the input into separate chunks, provided high improvements w.r.t. traditional sequential parsing. Further investigation pointed out a restriction imposed on the OPL formalism that prevents from fully exploiting parallelism and proposed an improvement of the original algorithm which proved effective in many practical cases. Stimulated by the above contribution here we remove the mentioned restriction on OPL and build a new parallel parser generator based thereon. We conducted a comparative experimentation among the three parallel algorithms that showed a consistent further improvement w.r.t. both the previous ones (with an exception in the case of purely sequential execution). Based on these early results, we believe that the horizon of parallel parsing large tree-structured data promises dramatic gains of efficiency in the analysis of this fundamental data structure.
en
dc.description.sponsorship
European Commission
-
dc.language.iso
en
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
operator precedence
en
dc.subject
Parallel parsing
en
dc.subject
regular expressions
en
dc.title
Boosting Parallel Parsing through Cyclic Operator Precedence Grammars