Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars
Herausgeber Sammlung:
de Lara, Juan; Plump, Detlef
Titel Konferenzpublikation:
Graph Transformation - 10th International Conference, ICGT 2017, Held as Part of STAF 2017
Untertitel Konferenzpublikation:
Marburg, Germany, July 18-19, 2017, Proceedings
Reihentitel:
Lecture Notes in Computer Science
Bandnummer Reihe:
10373
Konferenztitel:
International Conference on Graph Transformations (10., 2017, Marburg)
Tagungsort:
Marburg
Jahr der Konferenz:
2017
Datum Beginn der Konferenz:
18.07.2017
Datum Ende der Konferenz:
19.07.2017
Verlagsort:
Marburg, Germany
Verlag:
Springer
Jahr:
2017
Seiten von - bis:
106-122
Sprache:
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.