umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Predictive Shift-Reduce 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
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)
Abstract [en]

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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-133408OAI: oai:DiVA.org:umu-133408DiVA: diva2:1087712
Conference
10th International Conference on Graph Transformation (ICGT 2017), Marburg, Germany, July 18-19, 2017
Available from: 2017-04-10 Created: 2017-04-10 Last updated: 2017-04-10

Open Access in DiVA

No full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

Total: 21 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf