| Publication type: |
Article in Collection |
| Author: |
Frank Drewes, Berthold Hoffmann, Mark Minas |
| Editor: |
Francesco Parisi-Presicce, Bernhard Westfechtel |
| Title: |
Predictive Top-Down Parsing for Hyperedge Replacement Grammars |
| Book / Collection title: |
Graph Transformation |
| Volume: |
9151 |
| Page(s): |
19 – 34 |
| Year published: |
2015 |
| Publisher: |
Springer International Publishing |
| Abstract: |
Graph languages defined by hyperedge replacement grammars can be NP-complete. We invent predictive top-down (PTD) parsers for a subclass of these grammars, similar to recursive descent parsers for string languages. The focus of this paper lies on the grammar analysis that computes neighbor edges of nonterminals, in analogy to the first and follow symbols used in SLL(1) parsing. The analysis checks whether a grammar is PTD parsable and yields all information for generating a parser that runs in linear space and quadratic time. |
| ISBN: |
978-3-319-21144-2 |
| Internet: |
http://dx.doi.org/10.1007/978-3-319-21145-9_2 |
| Status: |
Reviewed |
| Last updated: |
05. 08. 2015 |
