Speeding up Generalized PSR Parsers by Memoization Techniques

Mark Minas

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 Rachid Echahed and Detlef Plump: Proceedings Tenth International Workshop on Graph Computation Models (GCM 2019), Eindhoven, The Netherlands, 17th July 2019, Electronic Proceedings in Theoretical Computer Science 309, pp. 71–86.
Published: 20th December 2019.

ArXived at: http://dx.doi.org/10.4204/EPTCS.309.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org