Top

Published in:

2017 | OriginalPaper | Chapter

Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars

Authors : Frank Drewes, Berthold Hoffmann, Mark Minas

Published in: Graph Transformation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Graph languages defined by hyperedge replacement grammars can be NP-complete. We study predictive shift-reduce (PSR) parsing for a subclass of these grammars, which generalizes the concepts of SLR(1) string parsing to graphs. PSR parsers run in linear space and time. In comparison to the predictive top-down (PTD) parsers recently developed by the authors, PSR parsing is more efficient and more general, while the required grammar analysis is easier than for PTD parsing.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Fusion Grammars: A Novel Approach to the Generation of Graph Languages

next chapter Granularity of Conflicts and Dependencies in Graph Transformation Systems

This result has been exploited for parsing natural language in the system Bolinas [2].

We assume that this order is provided with the HR grammar. Finding an appropriate order for PSR parsing automatically can be done by dataflow analysis, but is outside the scope of this paper.

In general, we may have to introduce fresh names for non-parameter nodes in the closure items as well in order to avoid name clashes, but this is not necessary in the present example.

The Grappa tool is available at www.unibw.de/inf2/grappa; the examples mentioned in Table 1 can be found there as well.

Aalbersberg, I., Ehrenfeucht, A., Rozenberg, G.: On the membership problem for regular DNLC grammars. Discrete Appl. Math. 13, 79–85 (1986)MathSciNetCrossRefMATH

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 of the Association for Computational Linguistic. Long Papers, vol. 1, pp. 924–932 (2013)

Costagliola, G., De Lucia, A., Orefice, S., Tortora, G.: A parsing methodology for the implementation of visual systems. IEEE Trans. Softw. Eng. 23, 777–799 (1997)CrossRef

DeRemer, F.L.: Simple LR(k) grammars. Commun. ACM 14(7), 453–460 (1971)MathSciNetCrossRefMATH

Drewes, F.: Recognising \(k\)-connected hypergraphs in cubic time. Theor. Comput. Sci. 109, 83–122 (1993)MathSciNetCrossRefMATH

Drewes, F., Hoffmann, B.: Contextual hyperedge replacement. Acta Informatica 52, 497–524 (2015)MathSciNetCrossRefMATH

Drewes, F., Hoffmann, B., Minas, M.: Contextual hyperedge replacement. In: Schürr, A., Varró, D., Varró, G. (eds.) AGTIVE 2011. LNCS, vol. 7233, pp. 182–197. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34176-2_16 CrossRef

Drewes, F., Hoffmann, B., Minas, M.: Predictive top-down parsing for hyperedge replacement grammars. In: Parisi-Presicce, F., Westfechtel, B. (eds.) ICGT 2015. LNCS, vol. 9151, pp. 19–34. Springer, Cham (2015). doi:10.1007/978-3-319-21145-9_2 CrossRef

Drewes, F., Hoffmann, B., Minas, M.: Approximating Parikh images for generating deterministic graph parsers. In: Milazzo, P., Varró, D., Wimmer, M. (eds.) STAF 2016. LNCS, vol. 9946, pp. 112–128. Springer, Cham (2016). doi:10.1007/978-3-319-50230-4_9 CrossRef

10.

Franck, R.: A class of linearly parsable graph grammars. Acta Informatica 10(2), 175–201 (1978)MathSciNetCrossRefMATH

11.

Habel, A.: Hyperedge Replacement: Grammars and Languages. LNCS, vol. 643. Springer, Heidelberg (1992). doi:10.1007/BFb0013875

12.

Hoffmann, B.: Cleaned SLL(1) grammars are SLR(1). Technical Report 17–1, Studiengang Informatik, Universität Bremen (2017). http://www.informatik.uni-bremen.de/~hof/papers/sllr.pdf

13.

Johnson, S.C.: Yacc: Yet another compiler-compiler. Computer Science Technical Report 32, AT&T Bell Laboratories (1975)

14.

Kaul, M.: Practical applications of precedence graph grammars. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph Grammars 1986. LNCS, vol. 291, pp. 326–342. Springer, Heidelberg (1987). doi:10.1007/3-540-18771-5_62 CrossRef

15.

Knuth, D.E.: On the translation of languages from left to right. Inf. Control 8(6), 607–639 (1965)MathSciNetCrossRefMATH

16.

Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Informatica 27, 399–421 (1990)MathSciNetCrossRefMATH

17.

Lewis II, P.M., Stearns, R.E.: Syntax-directed transduction. J. ACM 15(3), 465–488 (1968)CrossRefMATH

18.

Ludwigs, H.J.: A LR-like analyzer algorithm for graphs. In: Wilhelm, R. (ed.) GI - 10. Jahrestagung, Proceedings of the Saarbrücken, 30 September - 2 Oktober 1980. Informatik-Fachberichte, vol. 33, pp. 321–335 (1980)

19.

Minas, M.: Diagram editing with hypergraph parser support. In: Proceedings of the 1997 IEEE Symposium on Visual Languages (VL 1997), Capri, Italy, pp. 226–233 (1997)

20.

Sippu, S., Soisalon-Soininen, E.: Parsing Theroy I: Languages and Parsing, EATCS Monographs in Theoretical Computer Science, vol. 15 (1988)

21.

Vogler, W.: Recognizing edge replacement graph languages in cubic time. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol. 532, pp. 676–687. Springer, Heidelberg (1991). doi:10.1007/BFb0017421 CrossRef

Title: Predictive Shift-Reduce Parsing for Hyperedge Replacement Grammars
Authors: Frank Drewes
Berthold Hoffmann
Mark Minas
Publisher: Springer International Publishing
Book: Graph Transformation
Print ISBN: 978-3-319-61469-4

Electronic ISBN: 978-3-319-61470-0

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-61470-0_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner