Sdf Language

Overview

The SDF syntax definition formalism allows a concise and natural expression of the syntax of a context-free language. SDF integrates lexical and context-free syntax in a single syntax formalism. The complete syntax of a language is thus defined in a single definition. SDF supports arbitrary context-free grammars. Therefore, SDF does not restrict the grammars to a subclass of the context-free grammars, such as LL or LALR. SDF syntax definitions can be modular. SDF modules can be reused in different syntax definitions. Disambiguation of grammars is not done by grammar hacking, but by applying special purpose disambiguation facilities in SDF, such as priorities, reject productions, and follow restrictions.

SDF is a declarative language. This means that a syntax definition can be used for different purposes then the usual application: the generation of a parser. Instead, SDF syntax definitions can be used to generate other tools from syntax definitions, e.g. pretty-printers and data type definitions.

Language Features

• Modules
• Integration of lexical and context-free syntax
• Character classes
• Regular expressions
• Disambiguation by relative priorities
• Disambiguation by associativity
• Disambiguation by preference
• Aliases
• Renaming and parameterization of modules
• Lookahead restrictions
• Reject productions
• Case-insensitive keywords

Design Features

Implementers of SDF2 will appreciate its orthogonality. Language features are defined, as much as possible, orthogonal with respect to each other. Despite providing a rich formalism at the level of the user language, the implementation only has to work on a small kernel formalism to which syntax definitions are transformed. Most features are expressed by a translation to the kernel formalism, which is performed by the SDF normalizer.

All symbols are first-class. For example, symbols can be used at the right-hande side of a production. This means that it is possible to define production rules that construct lists of symbols, optional symbols, and even literals.

Implementation Features

• Parser generation: SLR1 with special treatment of priorities
• Scannerless Generalized LR no separate scanner needed