| Publication type: |
Article |
| Author: |
Frank Drewes, Berthold Hoffmann, Mark Minas |
| Title: |
Formalization and Correctness of Predictive Shift-Reduce Parsers for Graph Grammars based on Hyperedge Replacement |
| Volume: |
104 |
| Page(s): |
303 – 341 |
| Journal: |
Journal on Locical and Algebraic Methods for Programming |
| Year published: |
2019 |
| Abstract: |
Hyperedge replacement (HR) grammars can generate NP-complete graph languages, which makes parsing is hard even for fixed HR languages. Therefore, we study predictive shift-reduce (PSR) parsing that yields efficient parsing for a subclass of HR grammars, by generalizing the concepts of SLR(1) string parsing to graphs. We formalize the construction of PSR parsers and show that it is correct. SR parsers run in linear space and time, and are more efficient than predictive top-down (PTD) parsers recently developed by the authors. |
| Internet: |
https://arxiv.org/abs/1812.11927}{https://arxiv.org/abs/1812.11927 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~hof/papers/JLAMP19.pdf |
| Status: |
Reviewed |
| Last updated: |
15. 03. 2019 |
