Thumbnail Image

Automatic derivation of compact abstract syntax data types from concrete syntax descriptions

Lorenzen, Florian

Forschungsberichte der Fakultät IV - Elektrotechnik und Informatik / Technische Universität Berlin

We describe an algorithm (written in Haskell) to automatically derive compact abstract syntax data types from concrete grammar descriptions. The input for the algorithm is almost the grammar language of the parser generator PaGe which not only constructs a parser but also the data types necessary to represent an abstract syntax tree. The algorithm of this report is suitable to minimize the data type used to represent the parsing result to both improve the handling of abstract syntax trees and their space requirements.