Back to University of Twente portal
| author: | Peter van Dijk |
| title: | Parsing and Code Generation using Graph-Based Rules |
| keywords: | |
| topics: | Algorithms and Data Structures , Graphs |
| committee: | Arend Rensink |
| end: | June 2014 |
Description
Parser generators such as Antlr are based on the specification of parsing rules and tree walkers in a domain-specific, textual language. These rules essentially specify the construction and transformation of abstract syntax trees (ASTs) from strings, and (in the code generation phase) the construction of strings from ASTs.
On the other hand, GROOVE (an FMT-based open source tool) is a genral-purpose graph transformer able to visually specify and explore rules specifying changes to arbitrary graphs. Since ASTs form a dedicated class of graphs, it is certainly possible to use GROOVE to transform them.
This assignment involves the design of suitable mechanisms to specify graph input structure and code templates for GROOVE to enable its use as a parser generator. This use should then be demonstrated on a non-trivial example of a textual language.
A good understanding of the concepts of Compiler Construction (Vertalerbouw) is a prerequisite for this assignment.