Grappa & Grappa REGrappa-Logo

Grappa is a graph parsing tool that comes with a graph parser generator (the distiller) and employs so-called PTD and PSR parsing for HR and CHR grammars (see below). The distiller has been implemented in Java and Scala, and it generates parsers in Java. Generated parsers can thus be used in any program using the JVM. This is demonstrated with the help of the graph processor, which is also part of Grappa. The graph processor can read graphs from files in textual notation and run generated parsers on them. The graphs and the parses can be exported in several ways.

Grappa RE is a tool for efficient graph recognition based on finite automata and regular expressions described in [GCM'23] and [GCM'24].

The source code of Grappa is available as a public Git-repository. Precompiled versions for Windows, Linux, and MacOS can be used instead; they are available for download below. A mini-tutorial that guides you through the installation process and the first steps with Grappa is available in the Document section

The source code of Grappa RE is available as a public Git-repository. Precompiled versions for Windows, Linux, and MacOS can be used instead; they are available for download below.

Predictive Top-down and Shift-reduce Graph Parsing for HR and CHR Grammars

Graph languages defined by hyperedge replacement (HR) grammars can be NP-complete, which makes parsing hard even for fixed HR languages. We study more efficient parsing for subclasses of hyperedge replacement grammars. In particular, we have generalized the concepts of SLL(1) and SLR(1) parsing for string grammars, defining predictive top-down (PTD) hypergraph parsing [ICGT'15] and predictive shift-reduce (PSR) hypergraph parsing [ICGT'17]. PTD parsers run in linear space and quadratic time, PSR parsers in linear space and time. The correctness of these parsers has been proven in [ICGT'20] and [JLAMP], respectively.

PTD and PSR parsing can not only be applied to hyperedge replacement grammars, but also to the more general contextual hyperedge replacement grammars. PSR parsing for CHR grammars has been described in [ICGT'19]. [ICGT'21] formalizes PTD parsing for CHR grammars and shows its correctness.

PTD and PSR parsers cannot exist for all HR and CHR languages because these parsers run in linear or quadratic time, but HR-parsing is NP-complete in general. We have generalized Tomita's idea of generalized LR parsing to PSR parsers and have defined generalized PSR (GPSR) parsers [LATA'19]. GPSR parsers exist for every HR grammar, but they may run in exponential time. Memoization techniques may be used to make them more efficient [GCM'19].

References

[GCM'24]
Mattia De Rosa and Mark Minas. Grappa RE - a tool for efficient graph recognition based on finite automata and regular expressions. Accepted for presentation at 15th International Workshop on Graph Computation Models (GCM’24), Enschede, NL, 9th July 2024.
[GCM'23]
Frank Drewes, Berthold Hoffmann, and Mark Minas. Finite automata for efficient graph recognition. To appear in Proceedings 14th International Workshop on Graph Computation Models, Leicester, UK, 18th July 2023, 2024. Available at arXiv:2404.15052 [cs.FL].
[ICGT'22]
Frank Drewes, Berthold Hoffmann, and Mark Minas. Acyclic contextual hyperedge replacement: Decidability of acyclicity and generative power. In Nicolas Behr and Daniel Struüber, editors, Graph Transformation - 15th International Conference, ICGT 2022, Held as Part of STAF 2022, Nantes, France, July 7-8, 2022, Proceedings, volume 13349 of Lecture Notes in Computer Science, pages 3–19. Springer, 2022. [DOI]
[ICGT'21]
F. Drewes, B. Hoffmann, and M. Minas. Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars. In F. Gadducci and T. Kehrer, editors, Graph Transformation 14th International Conference, ICGT 2021. Held as Part of STAF 2021. Virtual Event, June 24–25, 2021. Proceedings, volume 12741 of Lecture Notes in Computer Science, pages 164--184, Cham, 2021. Springer International Publishing. This paper received the EASST Award as Best Software Science paper at ICGT 2021. [ DOI ]
[ICGT'20]
F. Drewes, B. Hoffmann, and M. Minas. Graph parsing as graph transformation - correctness of predictive top-down parsers. In F. Gadducci and T. Kehrer, editors, Graph Transformation - 13th International Conference, ICGT 2020, Held as Part of STAF 2020, Bergen, Norway, June 25-26, 2020, Proceedings, volume 12150 of Lecture Notes in Computer Science, pages 221--238. Springer, 2020. [ DOI | http ]
[JLAMP]
F. Drewes, B. Hoffmann, and M. Minas. Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement. Journal of Logical and Algebraic Methods in Programming, 104:303--341, April 2019. Preprint available also at arXiv:1812.11927 [cs.FL]. [ DOI | http ]
[LATA'19]
B. Hoffmann and M. Minas. Generalized predictive shift-reduce parsing for hyperedge replacement graph grammars. In C. Martín-Vide, A. Okhotin, and D. Shapira, editors, Language and Automata Theory and Applications, 13th International Conference, LATA 2019, St. Petersburg, Russia, March 26-29, 2019, Proceedings, volume 11417 of LNCS, pages 233--245, Cham, 2019. Springer International Publishing. [ DOI ]
[ICGT'19]
F. Drewes, B. Hoffmann, and M. Minas. Extending predictive shift-reduce parsing to contextual hyperedge replacement grammars. In E. Guerra and F. Orejas, editors, Graph Transformation: 12th International Conference, ICGT 2019, Held as Part of STAF 2019, Eindhoven, The Netherlands, July 15--16, 2019, Proceedings, volume 11629 of Lecture Notes in Computer Science, pages 55--72, Cham, 2019. Springer International Publishing. [ DOI | http ]
[GCM'19]
M. Minas. Speeding up Generalized PSR parsers by memoization techniques. In R. Echahed and D. Plump, editors, Proceedings Tenth International Workshop on Graph Computation Models, Eindhoven, The Netherlands, 17th July 2019, volume 309 of Electronic Proceedings in Theoretical Computer Science, pages 71--86. Open Publishing Association, 2019. [ DOI ]
[GCM'17]
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 ]
[ICGT'17]
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 ]
[GCM'16]
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 ]
[ICGT'15]
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 ]

Documents

  • A Mini-Tutorial [pdf] describes how to install Grappa using one of the installers available below and how to use Grappa with its GUI. It describes how to generate different parsers for some HR grammars and how generated parsers can be used for parsing input graphs. These grammars and input graphs are available as a zip-file here.
  • PTD Parsers in AGG describes how the rule-based top-down parser for linked trees defined in [ICGT'21] is realized - as proof-of-concept of the constructions in [ICGT'21] - in the algebraic graph transformation system AGG.
  • A preliminary performance report [pdf] shows the results of some experiments with PSR and PTD parsers.
  • 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

Installer files for pre-compiled versions of Grappa

Select and download the installer depending on the OS of your computer. Installation of Grappa works as usual on your computer (In general: Just double click the downloaded installer file.) The Grappa installation can then be used immediately; no further software packages are required because each installer also contains JDK 14 and the required Scala runtime components.

Grappa-2.4.exe:
Grappa installer for Windows (version 2.4, Nov. 3, 2021, 54897152 bytes)
grappa_2.4-1_amd64.deb:
Grappa installer for Linux (version 2.4, Nov. 3, 2021, 39722260 bytes)
Grappa-2.4.dmg:
Grappa installer for MacOS with Intel processor (version 2.4, Nov. 3, 2021, 59669126 bytes)

Older versions can be found here.

Installer files for pre-compiled versions of Grappa RE

Select and download the installer depending on the OS of your computer. Installation of Grappa RE works as usual on your computer (In general: Just double click the downloaded installer file.) The Grappa RE installation can then be used immediately; no further software packages are required because each installer also contains JDK runtime components.

Note: The installer also installs an examples directory with sample input files for Grappa RE. The location of this directory depends on your machine. On MacOs, e.g., it is contained in the directory /Applications/GrappaRE.app/Contents.

GrappaRE-1.0.1.exe:
Grappa RE installer for Windows (version 1.0.1, July 4, 2024, 35293696 bytes)
GrappaRE-intel-1.0.1.dmg:
Grappa RE installer for MacOS with Intel processor (version 1.0.1, July 4, 2024, 36495203 bytes)
GrappaRE-aarch-1.0.1.dmg:
Grappa RE installer for MacOS with Apple processor (version 1.0.1, July 4, 2024, 33982570 bytes)
grappare_1.0.1_amd64.deb:
Grappa RE installer for Linux (version 1.0.1, July 4, 2024, 30605928 bytes)

Older versions can be found here.

Contact

Mark Minas