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 Chr ...

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 empt ...

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

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 In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine. The most common type of compiler- ...

for SDF specifications are provided as part of the free

ASF+SDF Meta Environment ASF may refer to: Arts and entertainment * Alabama Shakespeare Festival, a drama festival * ''Asimov's Science Fiction'', a U.S.-based English-language science fiction magazine containing SF stories Science and technology Biological * A ...

. These operate using the SGLR ( Scannerless

GLR parser A GLR parser (GLR standing for "Generalized LR", where L stands for "left-to-right" and R stands for "rightmost (derivation)") is an extension of an LR parser algorithm to handle non-deterministic and ambiguous grammars. The theoretical foundatio ...

). 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 co ...

s or, in the case of

ambiguities Ambiguity is the type of meaning in which a phrase, statement or resolution is not explicitly defined, making several interpretations plausible. A common aspect of ambiguity is uncertainty. It is thus an attribute of any idea or statement ...

, 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

provides SDF *

RascalMPL Rascal is an experimental domain specific language for metaprogramming, such as static code analysis, program transformation, program generation and implementation of domain specific languages. It is a general meta language in the sense that it doe ...

*Spoofax/IM

* Stratego/XT * Strafunski

References

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

Overview

Examples

Program analysis and transformation systems using SDF

See also

References

Further reading

External links