Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Modern Aspects of Complexity Within Formal Languages Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars

verfasst von : Berthold Hoffmann, Mark Minas

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Parsing for graph grammars based on hyperedge replacement (HR) is in general NP-hard, even for a particular grammar. The recently developed predictive shift-reduce (PSR) parsing is efficient, but restricted to a subclass of unambiguous HR grammars. We have implemented a generalized PSR parsing algorithm that applies to all HR grammars, and pursues severals parses in parallel whenever decision conflicts occur. We compare GPSR parsers with the Cocke-Younger-Kasami parser and show that a GPSR parser, despite its exponential worst-case complexity, can be much faster.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Complexity of Regex Crosswords
Nächstes Kapitel Transformation of Petri Nets into Context-Dependent Fusion Grammars
Fußnoten
1
In the graph parser generator Grappa, available at www.​unibw.​de/​inf2/​grappa.
 
2
\(V_{\!\gamma }\) may contain isolated nodes that are not attached to any edge in \(\gamma \).
 
3
I.e., a match \(\mu \) makes sure that the nodes of \(\alpha ^\mu \) that do not occur in \(\bar{A} = A^\mu \) do not collide with the other nodes in \(\gamma \).
 
4
We silently assume that input graphs do not have isolated nodes. This is no real restriction as one can add special edges to such nodes.
 
5
Actually, series-parallel graphs do also have a unique sink (without outgoing edges), which could be used as a second start node bound to y. However, this variation of the grammar would exhibit less peculiarities of the GPSR parser.
 
6
This property can be determined by the parser generator as well. However, it does not hold for the grammar of series-parallel graphs.
 
Literatur
1.
Chiang, D., Andreas, J., Bauer, D., Hermann, K.M., Jones, B., Knight, K.: Parsing graphs with hyperedge replacement grammars. In: Proceedings of the 51st Annual Meeting Association for Computational Linguistics, vol. 1, pp. 924–932 (2013)
2.
3.
4.
5.
6.
7.
Groschwitz, J., Koller, A., Teichmann, C.: Graph parsing with s-graph grammars. In: Proceedings of the 53rd Annual Meeting Association for Computational Linguistics, ACL 2015, Volume 1: Long Papers, pp. 1481–1490. The Association for Computer Linguistics (2015)
8.
9.
10.
Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Inf. 27, 399–421 (1990)MathSciNetCrossRef
11.
Minas, M.: Concepts and realization of a diagram editor generator based on hypergraph transformation. Sci. Comput. Program. 44(2), 157–180 (2002)CrossRef
12.
Tomita, M.: An efficient context-free parsing algorithm for natural languages. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence, pp. 756–764. Morgan Kaufmann (1985)
Metadaten
Titel
Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars
verfasst von
Berthold Hoffmann
Mark Minas
Copyright-Jahr
2019
Buch
Language and Automata Theory and Applications

Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-13435-8_17