# Syntax Definition Formalism

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Syntax_Definition_Formalism
> Markdown URL: https://mediated.wiki/source/Syntax_Definition_Formalism.md
> Source: https://en.wikipedia.org/wiki/Syntax_Definition_Formalism
> Source revision: 1323318451
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

The **Syntax Definition Formalism** (**SDF**) is a [metasyntax](/source/Metasyntax) used to define [context-free grammars](/source/Context-free_grammar): that is, a formal way to describe formal languages. It can express the entire range of [context-free grammars](/source/Context-free_grammar). Its current version is SDF3.[1] A [parser](/source/Parser) and [parser generator](/source/Parser_generator) for SDF specifications are provided as part of the free [ASF+SDF Meta Environment](/source/ASF%2BSDF_Meta_Environment). These operate using the SGLR ([Scannerless](/source/Scannerless_parsing) [GLR parser](/source/GLR_parser)). An SDF parser outputs [parse trees](/source/Parse_tree) or, in the case of [ambiguities](/source/Ambiguous_grammar), 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 in SDF2:

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](/source/ASF%2BSDF_Meta_Environment) provides SDF
- [RascalMPL](/source/RascalMPL)
- Spoofax/IMP [\[1\]](http://strategoxt.org/Spoofax)
- [Stratego/XT](/source/Stratego/XT)
- [Strafunski](/source/Strafunski)

## See also

- [GNU bison](/source/GNU_bison)
- [ANTLR](/source/ANTLR)

## References

1. [sleconf.org](http://www.sleconf.org/2014/parsing-slides/2-sdf3-slides.pdf)

## Further reading

- [A Quick Introduction to SDF, Visser, J. & Scheerder, J. (2000) CWI](http://ftp.strategoxt.org/pub/stratego/docs/sdfintro.pdf)
- [The Syntax Definition Formalism SDF, Mark van den Brand, Paul Klint, Jurgen Vinju (2007) CWI](http://homepages.cwi.nl/~daybuild/daily-books/learning-about/sdf/sdf.pdf)

## External links

- [Grammar Deployment Kit](https://gdk.sourceforge.net/)
- [SdfMetz](http://wiki.di.uminho.pt/twiki/bin/view/Research/PURe/SdfMetz) computes metrics for SDF grammars
- Download SDF from the [ASF+SDF Meta Environment homepage](http://www.meta-environment.org/)

---
Adapted from the Wikipedia article [Syntax Definition Formalism](https://en.wikipedia.org/wiki/Syntax_Definition_Formalism) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Syntax_Definition_Formalism?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.