Meeting Register Page

Meeting banner
GReTA seminar #34: "Contextual Hyperedge Replacement Grammars: Languages – Parsing – Grappa" (by F. Drewes, B. Hoffmann and M. Minas)
Please note:* as the seminar will be live-streamed to YouTube, we kindly ask participants to join the meeting ideally already during the 15min prior to the start of the talk at 15:00 (albeit the link will remain active throughout the duration of the event). After the talk, there will be a possibility to interact with the speaker and other participants during a 30min discussion session (not streamed to YouTube) starting from 16:00.


Graph transformation allows to extend formal language theory to the generation of graph languages. This has applications in areas such as model-driven software engineering, natural language processing, and shape analysis of programs.

We start from the well-established theory of context-free grammars based on hyperedge replacement (HR) and introduces a modest extension, contextual hyperedge replacement (CHR), in order to extend their generative power. We discuss the generative power and other properties of CHR, and relate them to HR.

Then we consider parsing for CHR grammars. As for HR, parsing is NP-complete in general, so that efficient parsing algorithms can only be achieved for subclasses. We have devised two algorithms, called predictive top-down (PTD) and predictive shift-reduce (PSR), which are inspired by the well-known LL(k) and LR(k) parsing for strings, and are usually linear, at most quadratic. We illustrate the ideas of these algorithms by graph transformation rules.

Finally we demonstrate Mark Minas' graph parser generator Grappa, which implements not only PTD and PSR parsing, including the needed analysis tools, but also generalized PSR, where parallel parsing allows to cope with ambiguous grammars. Measurements of generated parsers validate our theoretical findings regarding complexity.

Jun 3, 2022 02:45 AM in Paris

* Required information