The Syntax Definition Formalism (SDF for short) is a metasyntax

Metasyntax

A metasyntax describes the allowable structure and composition of phrases and sentences of a metalanguage, which is used to describe either a natural language or a computer programming language...

 used to define context-free grammar

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

s: that is, a formal way to describe formal languages. It can express the entire range of context-free grammar

Context-free grammar

In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....

s. Its current version is SDF2. A parser and parser generator for SDF specifications are provided as part of the free ASF+SDF Meta Environment

ASF+SDF Meta Environment

The ASF+SDF Meta-Environment is an IDE and toolset for interactive program analysis and transformation. It combines SDF , ASF and other technologies.Some of the features:...

. These operate using the SGLR (Scannerless GLR parser

GLR parser

A GLR parser is an extension of an LR parser algorithm to handle nondeterministic and ambiguous grammars. First described in a 1984 paper by Masaru Tomita, it has also been referred to as a "parallel parser"...

). An SDF parser outputs parse tree

Parse tree

A concrete syntax tree or parse tree or parsing treeis an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the...

s or, in the case of ambiguities, parse forests.

Overview

Features of SDF:

• Supports the entire range of context-free languages
• Allows modular syntax definitions (grammars can import subgrammars) which enables reuse
• Supports annotations

Examples

The following example defines a simple Boolean expression syntax:

module basic/Booleans

exports
sorts Boolean
context-free start-symbols Boolean

context-free syntax
"true" -> Boolean
"false" -> Boolean
lhs:Boolean "|" rhs:Boolean -> Boolean {left}
lhs:Boolean "&" rhs:Boolean -> Boolean {left}
"not" "(" Boolean ")" -> Boolean
"(" Boolean ")" -> Boolean

context-free priorities
Boolean "&" Boolean -> Boolean >
Boolean "|" Boolean -> Boolean

Program analysis and transformation systems using SDF

• ASF+SDF Meta Environment
  ASF+SDF Meta Environment
  The ASF+SDF Meta-Environment is an IDE and toolset for interactive program analysis and transformation. It combines SDF , ASF and other technologies.Some of the features:...
  
   provides SDF
• RascalMPL
  RascalMPL
  Rascal is an experimental Domain specific language for metaprogramming, such as Static code analysis, Program transformation and implementation of Domain specific languages. It includes primitives from relational calculus and term rewriting...
  
  
• Spoofax/IMP http://strategoxt.org/Spoofax
• Stratego/XT
  Stratego/XT
  Stratego/XT is a language and toolset for constructing stand-alone program transformation systems.It combines the Stratego transformation language with the XT toolset of transformation components, providing a framework for constructing stand-alone...
  
  
• Strafunski
  Strafunski
  Strafunski is a functional programming-based toolset for implementing program analysis and transformation components. It is implemented in Haskell, and provides an API for operating on parse trees such as those generated by SDF. Features:...
  
  

Further reading

• [ftp://ftp.stratego-language.org/pub/stratego/docs/sdfintro.pdf A Quick Introduction to SDF, Visser, J. & Scheerder, J. (2000) CWI]

External links

• Grammar Deployment Kit
• SdfMetz computes metrics for SDF grammars
• Download SDF from the ASF+SDF Meta Environment homepage