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.

 

Additional Resources

  1. The paper