The Syntax Definition Formalism (SDF) is a
metasyntax
In logic and computer science, 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.Sellink, Alex, and Ch ...
used to define
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
s: that is, a formal way to describe formal languages. It can express the entire range of
context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be ...
s. Its current version is SDF3.
sleconf.org
/ref> A parser
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
and parser generator for SDF specifications are provided as part of the free ASF+SDF Meta Environment. These operate using the SGLR ( Scannerless GLR parser). An SDF parser outputs parse tree
A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is used primarily in comp ...
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 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
lhs:Boolean "&" rhs:Boolean -> Boolean
"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 provides SDF
* RascalMPL
*Spoofax/IM
* Stratego/XT
* Strafunski
See also
*GNU bison
GNU Bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification in the BNF notation (a context-free language), warns about any parsing ambiguities, and generates a parser that reads sequen ...
*ANTLR
In computer-based language recognition, ANTLR (pronounced ''antler''), or ANother Tool for Language Recognition, is a parser generator that uses LL(*) for parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set (PCCTS), fir ...
References
Further reading
A Quick Introduction to SDF, Visser, J. & Scheerder, J. (2000) CWIThe Syntax Definition Formalism SDF, Mark van den Brand, Paul Klint, Jurgen Vinju (2007) CWI
External links
Grammar Deployment KitSdfMetz
computes metrics for SDF grammars
*Download SDF from th
ASF+SDF Meta Environment homepage
Parser generators
Extensible syntax programming languages
Programming language implementation
{{comp-sci-stub