About Stratego/XT

Stratego -- Strategies for Program Transformation
Stratego/XT is the combination of the Stratego language for strategic programming with the XT bundle of transformation tools.


XT is a bundle of transformation tools that combines Stratego, a language for transformation of abstract syntax trees, with tools for other aspects of program transformation. Stratego only deals with transformation of programs represented by means of terms. Parsing and pretty-printing is provided by the XT bundle of transformation tools, which combines Stratego with the Syntax Definition Formalism SDF and the Generic Pretty-Printing Package GPP.

ATerm Exchange Format

The foundation of XT is the ATerm format for exchange of structured data such as abstract syntax trees. The format essentially consists of first-order prefix terms. The format is supported by libraries for C, Java, and Haskell, which support reading and writing of ATerms.


The Syntax Definition Formalism SDF supports high-level, declarative, and modular definition of the syntax of programming languages and data formats. The formalism integrates the definition of lexical and context-free syntax. The modularity of the formalism implies that it is possible to easily combine two languages or to embed one language into another.

Grammar Base

The SDF Grammar Base is a collection of syntax definitions for various languages, including Java, C, SQL, COBOL, BibTex, Stratego, and SDF. The Grammar Base will be distributed separately.

Parser Generation

The parser generator PGEN Generates parse tables from SDF definitions.

Scannerless Generalized-LR Parser

The scannerless generalized-LR parser SGLR interprets parse tables generated from SDF definitions. The parser does not use a separate scanner; lexical analysis is included in the parsing process. The parser can deal with arbitrary context-free grammars. Disambiguation is based on filters in different stages of the parsing process.

Parse Tree Manipulation

XT provides several generic tools for parse tree manipulation such as implosion of parse trees to abstract syntax trees.

Grammar Engineering

XT provides several tools for derivation of SDF syntax definitions from YACC-like formalisms, which allows reusing existing grammars to a large extent, and tools for improving syntax definitions.

Generic Pretty-Printing Package

Generic pretty-printing package (GPP) is based on the device-independent Box format and allows pretty-printing to different targets; now supported are text, html and latex. Pretty-printers are driven by pretty-print tables, which can be generated automatically from syntax definitions.

Application Areas

XT is applicable in a many instances of program transformation including

  • Meta-programming
  • Generative programming
  • Compilation
  • Implementation of domain-specific languages
  • Language extensions
  • Documentation generation
  • Software visualization


This two page brochure

summarizes the main features of Stratego and XT. Useful for distribution at conferences and such.

-- EelcoVisser - 17 Nov 2002
-- EelcoVisser - 04 Jun 2002