Title: Declarative Syntax Tree Engineering*
Or, One Grammar to Rule Them All


(NYU-CS-TR905)

Authors: Robert Grimm 

Abstract:
Grammars for many parser generators not only specify a language's
syntax but also the corresponding syntax tree.  Unfortunately, most
parser generators pick a somewhat arbitrary combination of features
from the design space for syntax trees and thus lock in specific
trade-offs between expressivity, safety, and performance.  This paper
discusses the three major axes of the design space---specification
within or outside a grammar, concrete or abstract syntax trees, and
dynamically or statically typed trees---and their impact.  It then
presents algorithms for automatically realizing all major choices from
the same, unmodified grammar with inline syntax tree declarations.  In
particular, this paper shows how to automatically (1) extract a
separate syntax tree specification, (2) embed an abstract syntax tree
within a concrete one, and (3) infer a strongly typed view on a
dynamically typed tree.  All techniques are implemented in the
Rats! parser generator and have been applied to real-world C and Java
grammars and their syntax trees.