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
Extending Predictive Shift-Reduce Parsing to Contextual Hyperedge Replacement Grammars
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
2019 (English)In: Graph Transformation: 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15–16, 2019, Proceedings / [ed] Esther Guerra, Fernando Orejas, Springer, 2019, p. 55-72Conference paper, Published paper (Refereed)
Abstract [en]

Parsing with respect to grammars based on hyperedge replacement (HR) is NP-hard in general, even for some fixed grammars. In recent work, wehave devised predictive shift-reduce parsing (PSR), a very efficientalgorithm that applies to a wide subclass of HR grammars. In thispaper, we extend PSR parsing to contextual HR grammars, a moderateextension of HR grammars that have greater generative power, and aretherefore better suited for the practical specification of graph anddiagram languages. Although the extension requires considerablemodifications of the original algorithm, it turns out that theresulting parsers are still very efficient.

Place, publisher, year, edition, pages
Springer, 2019. p. 55-72
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 11629
Keywords [en]
contextual hyperedge replacement grammar, graph parsing, grammar analysis
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-158625DOI: 10.1007/978-3-030-23611-3_4ISBN: 978-3-030-23610-6 (print)ISBN: 978-3-030-23611-3 (electronic)OAI: oai:DiVA.org:umu-158625DiVA, id: diva2:1313406
Conference
ICGT 2019: 12th International Conference on Graph Transformation, July 15-16, 2019, Eindhoven, The Netherlands
Available from: 2019-05-03 Created: 2019-05-03 Last updated: 2019-07-16Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

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: 139 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