GrappaGrappa-Logo

Predictive Top-down and Shift-reduce Graph Parsing

Graph languages defined by hyperedge replacement grammars can be NP-complete. We study more efficient parsing for subclasses of hyperedge replacement grammars. We generalize the concepts of SLL(1) and SLR(1) parsing for string grammars, defining predictive top-down (PTD) hypergraph parsing and predictive shift-reduce (PSR) hypergraph parsing. PTD parsers run in linear space and quadratic time, PSR parsers in linear space and time.

PTD parsing can not only be applied to hyperedge replacement grammars, but also to the the more general contextual hyperedge replacement grammars. We are working to make this possible for PSR parsing, too.

The Grappa generator of PTD and PSR parsers has been implemented in Java and Scala; it is available for download (see below).

References

[1]
B. Hoffmann and M. Minas. Generating efficient predictive shift-reduce parsers for hyperedge replacement grammars. In M. Seidl and S. Zschaler, editors, Software Technologies: Applications and Foundations, pages 76--91, Cham, 2018. Springer International Publishing. [ DOI | http ]
[2]
F. Drewes, B. Hoffmann, and M. Minas. Predictive shift-reduce parsing for hyperedge replacement grammars. In J. de Lara and D. Plump, editors, Graph Transformation: 10th International Conference, ICGT 2017, Held as Part of STAF 2017, Marburg, Germany, July 18-19, 2017, Proceedings, volume 10373 of Lecture Notes in Computer Science, pages 106--122, Cham, 2017. Springer International Publishing. [ DOI | http ]
[3]
F. Drewes, B. Hoffmann, and M. Minas. Approximating Parikh images for generating deterministic graph parsers. In P. Milazzo, D. Varró, and M. Wimmer, editors, Software Technologies: Applications and Foundations -- STAF 2016 Collocated Workshops: DataMod, GCM, HOFM, MELO, SEMS, VeryComp, Vienna Austria, July 4-8, 2016, Revised Selected Papers, volume 9946 of Lecture Notes in Computer Science, pages 112--128. Springer International Publishing, 2016. [ DOI | http ]
[4]
F. Drewes, B. Hoffmann, and M. Minas. Predictive top-down parsing for hyperedge replacement grammars. In F. Parisi-Presicce and B. Westfechtel, editors, Graph Transformation, 8th International Conference, ICGT 2015, L'Aquila, Italy, volume 9151 of Lecture Notes in Computer Science, pages 19--34. Springer International Publishing, 2015. This paper received the EATCS Best Paper Award at ICGT 2015. [ DOI | http ]

Parser Performance

The results of some experiments with PSR and PTD parsers are summarized in the following preliminary report: [pdf]

PSR Examples

The following pdf files show characteristic finite automata (CFA) for some example grammars as described in the ICGT'17 paper

  • Trees [pdf]
  • Nassi-Shneiderman diagrams [pdf]
  • {anbbcn | n > 0} language [pdf]
  • Simple arithemtic expressions [pdf]
  • Palindromes [pdf]
  • Palindromes (of even length) [pdf]
  • Profile demonstration [pdf]
  • Structured flowcharts [pdf]
    Note that the CFA has conflicts
  • Serial-parallel graphs [pdf]
    Note that the CFA has conflicts

Download

grappa-2.2.zip:
Grappa source files (version 2.2, September 13, 2017, 1699413 bytes)
(changelog.txt)
grappa-2.1.zip:
Grappa source files (version 2.1, June 10, 2017, 524336 bytes)
grappa-2.0.zip:
Grappa source files (version 2.0, April 23, 2017, 524303 bytes)

Contact

Mark Minas