umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Predictive Top-down Parsing for Hyperedge Replacement Grammars
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
2015 (Engelska)Ingår i: 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, s. 19-34Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Springer Publishing Company, 2015. Vol. 9151, s. 19-34
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9151
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:umu:diva-102929DOI: 10.1007/978-3-319-21145-9_2ISI: 000364104800002ISBN: 978-3-319-21144-2 (tryckt)ISBN: 978-3-319-21145-9 (tryckt)OAI: oai:DiVA.org:umu-102929DiVA, id: diva2:811240
Konferens
8th International Conference on Graph Transformation (ICGT 2015), L'Aquila, Italy, July 21-23, 2015
Anmärkning

Best Paper Award for the best theoretical paper at ICGT (http://www.eatcs.org/index.php/best-icgt-paper)

Tillgänglig från: 2015-05-11 Skapad: 2015-05-11 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Drewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Drewes, Frank
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 1350 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf