| Publication type: |
Article in Proceedings |
| Author: |
Frank Drewes, Berthold Hoffmann, Mark Minas |
| Editor: |
Juan de Lara, Detlef Plump |
| Title: |
Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars |
| Book / Collection title: |
Graph Transformation - 8th International Conference, ICGT 2017. Proceedings |
| Volume: |
10373 |
| Page(s): |
106 – 122 |
| Series: |
Lecture Notes in Computer Science |
| Year published: |
2017 |
| Publisher: |
Springer-Verlag Berlin Heidelberg |
| 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. |
| Internet: |
https://link.springer.com/chapter/10.1007%2F978-3-319-61470-0_7 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~hof/papers/ICGT2017.pdf |
| Status: |
Reviewed |
| Last updated: |
10. 01. 2018 |
