Speeding up Generalized PSR Parsers by Memoization Techniques
| Autor: | Mark Minas |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Performance Parsing Speedup Formal Languages and Automata Theory (cs.FL) Computer science LR parser Memoization lcsh:Mathematics Computer Science - Formal Languages and Automata Theory lcsh:QA1-939 computer.software_genre lcsh:QA75.5-76.95 Graph Running time Performance (cs.PF) TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Rule-based machine translation lcsh:Electronic computers. Computer science computer Algorithm |
| Zdroj: | GCM@STAF Electronic Proceedings in Theoretical Computer Science, Vol 309, Iss Proc. GCM 2019, Pp 71-86 (2019) |
| ISSN: | 2075-2180 |
| Popis: | Predictive shift-reduce (PSR) parsing for hyperedge replacement (HR) grammars is very efficient, but restricted to a subclass of unambiguous HR grammars. To overcome this restriction, we have recently extended PSR parsing to generalized PSR (GPSR) parsing along the lines of Tomita-style generalized LR parsing. Unfortunately, GPSR parsers turned out to be too inefficient without manual tuning. This paper proposes to use memoization techniques to speed up GPSR parsers without any need of manual tuning, and which has been realized within the graph parser distiller Grappa. We present running time measurements for some example languages; they show a significant speed up by some orders of magnitude when parsing valid graphs. But memoization techniques do not help when parsing invalid graphs or if all parses of an ambiguous input graph shall be determined. In Proceedings GCM 2019, arXiv:1912.08966 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|