Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars
Collection editors:
de Lara, Juan; Plump, Detlef
Title of conference publication:
Graph Transformation - 10th International Conference, ICGT 2017, Held as Part of STAF 2017
Subtitle of conference publication:
Marburg, Germany, July 18-19, 2017, Proceedings
Series title:
Lecture Notes in Computer Science
Series volume:
10373
Conference title:
International Conference on Graph Transformations (10., 2017, Marburg)
Venue:
Marburg
Year of conference:
2017
Date of conference beginning:
18.07.2017
Date of conference ending:
19.07.2017
Place of publication:
Marburg, Germany
Publisher:
Springer
Year:
2017
Pages from - to:
106-122
Language:
Englisch
Abstract:
Graph languages defined by hyperedge replacement grammars can be NP-complete. We study predictive shift-reduce (PSR) parsing for a subclass of these grammars, which generalizes the concepts of SLR(1) string parsing to graphs. PSR parsers run in linear space and time. In comparison to the predictive top-down (PTD) parsers recently developed by the authors, PSR parsing is more efficient and more general, while the required grammar analysis is easier than for PTD parsing.