umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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: 10th International Conference, ICGT 2017, Held as Part of STAF 2017, Marburg, Germany, July 18-19, 2017, Proceedings / [ed] Detlef Plump, Juan de Lara, Cham: Springer, 2017, p. 106-122Conference paper, Published 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
Cham: Springer, 2017. p. 106-122
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 10373
Keywords [en]
Hyperedge replacement grammar, Graph parsing, Grammar analysis
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-133408DOI: 10.1007/978-3-319-61470-0_7ISI: 000433250400007Scopus ID: 2-s2.0-85025122681ISBN: 978-3-319-61469-4 (print)ISBN: 978-3-319-61470-0 (electronic)OAI: oai:DiVA.org:umu-133408DiVA, id: 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: 2018-06-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Drewes, Frank

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 135 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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