Change search
ReferencesLink to record
Permanent link

Direct link
Predictive Top-down Parsing for Hyperedge Replacement Grammars
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2015 (English)In: Graph Transformation (ICGT 2015): 8th International Conference, ICGT 2015, Held as Part of STAF 2015, L'Aquila, Italy, July 21-23, 2015. Proceedings / [ed] Francesco Parisi-Presicce, Bernhard Westfechtel, Springer Publishing Company, 2015, Vol. 9151, 19-34 p.Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer Publishing Company, 2015. Vol. 9151, 19-34 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 9151
National Category
Computer Science
URN: urn:nbn:se:umu:diva-102929DOI: 10.1007/978-3-319-21145-9_2ISI: 000364104800002ISBN: 978-3-319-21144-2ISBN: 978-3-319-21145-9OAI: diva2:811240
8th International Conference on Graph Transformation (ICGT 2015), L'Aquila, Italy, July 21-23, 2015

Best Paper Award for the best theoretical paper at ICGT (

Available from: 2015-05-11 Created: 2015-05-11 Last updated: 2015-11-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 297 hits
ReferencesLink to record
Permanent link

Direct link