Bidirectional Grammar Transformation
Assigned to Simon Wegendt.
These are grammar transformations useful in compiler construction (Compilerbau): conversion to Chomsky normal form, left factoring, left recursion elimination. Standard textbooks describe how these transformations work on the production rules of grammars. However, a real compiler works on syntax trees. For each of these transformations between grammars, there exist forward and backward transformations between syntax trees of the grammars. To use grammar transformations in practice, we need the syntax tree transformations.
In this project, the student should design a domain-specific language for grammar transformations, and implement a program to generate syntax tree transformations from grammar transformations. The program should turn the textbook descriptions of grammar transformations into practical libraries.
Simon Wegendt. 2015. Bidirectional Grammar Transformations. Bachelor’s thesis, University of Tübingen.