Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Lautemann’s result has been exploited for parsing natural language in the system Bolinas [2].
- 2.
We assume that the order of edges in a right-hand side is provided with the HR grammar. Finding an appropriate order automatically is left to future work.
- 3.
On \(\mathbb {N}^k\), sums and scalar products are defined component-wise as usual.
References
Aalbersberg, I., Ehrenfeucht, A., Rozenberg, G.: On the membership problem for regular DNLC grammars. Discrete Appl. Math. 13, 79–85 (1986)
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 Linguistics, Sofia, Bulgaria. Long Papers, vol. 1, pp. 924–932, August 2013
Costagliola, G., De Lucia, A., Orefice, S., Tortora, G.: A parsing methodology for the implementation of visual systems. IEEE Trans. Softw. Eng. 23(12), 777–799 (1997)
Drewes, F.: Recognising \(k\)-connected hypergraphs in cubic time. Theor. Comput. Sci. 109, 83–122 (1993)
Drewes, F., Hoffmann, B.: Contextual hyperedge replacement. Acta Informatica, 31 (2015, accepted for publication). doi:10.1007/s00236-015-0223-4
Franck, R.: A class of linearly parsable graph grammars. Acta Informatica 10(2), 175–201 (1978)
Fürst, L., Mernik, M., Mahnič, V.: Improving the graph grammar parser of Rekers and Schürr. IET Softw. 5(2), 246–261 (2011)
Habel, A. (ed.): Hyperedge Replacement: Grammars and Languages. LNCS, vol. 643. Springer, Heidelberg (1992)
Hoffmann, B., Minas, M.: Defining models - meta models versus graph grammars. In: Proceedings of the 6th Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2010), Electronic Communications of the EASST, 29, Paphos, Cyprus (2010)
Kaul, M.: Practical applications of precedence graph grammars. In: Ehrig, H., Nagl, M., Rozenberg, G., Rosenfeld, A. (eds.) Graph-Grammars and Their Application to Computer Science. LNCS, vol. 291, pp. 326–342. Springer, Heidelberg (1986)
Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Informatica 27, 399–421 (1990)
Lewis II, P.M., Stearns, R.E.: Syntax-directed transduction. JACM 15(3), 465–488 (1968)
Ludwigs, H.J.: A LR-like analyzer algorithm for graphs. In: Wilhelm, R. (ed.) GI - 10. Jahrestagung: Saarbrücken, 30. September - 2. Oktober 1980. Informatik-Fachberichte, vol. 33, pp. 321–335. Springer, Heidelberg (1980)
Minas, M.: Diagram editing with hypergraph parser support. In: Proceedings of 1997 IEEE Symposium on Visual Languages (VL 1997), Capri, Italy, pp. 226–233 (1997)
Parikh, R.J.: On context-free languages. JACM 13(4), 570–581 (1966)
Rekers, J., Schürr, A.: Defining and parsing visual languages with layered graph grammars. J. Vis. Lang. Comput. 8(1), 27–55 (1997)
Vogler, W.: Recognizing edge replacement graph languages in cubic time. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars and Their Application to Computer Science. LNCS, vol. 532, pp. 676–687. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Drewes, F., Hoffmann, B., Minas, M. (2015). Predictive Top-Down Parsing for Hyperedge Replacement Grammars. In: Parisi-Presicce, F., Westfechtel, B. (eds) Graph Transformation. ICGT 2015. Lecture Notes in Computer Science(), vol 9151. Springer, Cham. https://doi.org/10.1007/978-3-319-21145-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-21145-9_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21144-2
Online ISBN: 978-3-319-21145-9
eBook Packages: Computer ScienceComputer Science (R0)