Parallel parsing made practical
| Autor: | Stefano Crespi Reghizzi, Matteo Pradella, Federica Panella, Dino Mandrioli, Alessandro Barenghi |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Parsing
Programming language Memoization Computer science Parsing expression grammar computer.software_genre Top-down parsing Parallel parsing algorithms Syntax analysis Parallel parser Operator precedence grammar TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Parser combinator Top-down parsing language S-attributed grammar computer Software Bottom-up parsing |
| Zdroj: | Science of Computer Programming. 112:195-226 |
| ISSN: | 0167-6423 |
| DOI: | 10.1016/j.scico.2015.09.002 |
| Popis: | The property of local parsability allows to parse inputs through inspecting only a bounded-length string around the current token. This in turn enables the construction of a scalable, data-parallel parsing algorithm, which is presented in this work. Such an algorithm is easily amenable to be automatically generated via a parser generator tool, which was realized, and is also presented in the following. Furthermore, to complete the framework of a parallel input analysis, a parallel scanner can also combined with the parser. To prove the practicality of a parallel lexing and parsing approach, we report the results of the adaptation of JSON and Lua to a form fit for parallel parsing (i.e. an operator-precedence grammar) through simple grammar changes and scanning transformations. The approach is validated with performance figures from both high performance and embedded multicore platforms, obtained analyzing real-world inputs as a test-bench. The results show that our approach matches or dominates the performances of production-grade LR parsers in sequential execution, and achieves significant speedups and good scaling on multi-core machines. The work is concluded by a broad and critical survey of the past work on parallel parsing and future directions on the integration with semantic analysis and incremental parsing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect