Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars
2017 (English)In: Graph Transformation (ICGT 2017): 8th International Conference, ICGT 2015, Held as Part of STAF 2015, L'Aquila, Italy, July 21-23, 2015. Proceedings / [ed] Detlef Plump, Juan de Lara, Springer Publishing Company, 2017Conference paper (Refereed)
Graph languages defined by hyperedge replacement (HR) grammars can beNP-complete. We study predictive shift-reduce (PSR) parsing for a subclass ofthese grammars, which generalizes the concepts of SLR(1) string parsing tographs. PSR parsers run in linear space and time. In comparison to thepredictive top-down (PTD) parsers recently developed by the authors, PSRparsers are more efficient, and allow parsing for a wider class of HR grammars,while the analysis of PSR parsability is easier than for PTD parsing.
Place, publisher, year, edition, pages
Springer Publishing Company, 2017.
Lecture Notes in Computer Science, ISSN 0302-9743
IdentifiersURN: urn:nbn:se:umu:diva-133408OAI: oai:DiVA.org:umu-133408DiVA: diva2:1087712
10th International Conference on Graph Transformation (ICGT 2017), Marburg, Germany, July 18-19, 2017