The Syntax Definition Formalism SDF

The Syntax Definition Formalism SDF is intended for the high-level description of grammars for programming languages, application languages, domain-specific languages, data formats and other computer-based formal languages. The primary goal of any SDF definition is the description of syntax. The secondary goal is to generate a working parser from this definition. A parser is a tool that takes a string that represents a program as input and outputs a tree that represents the same program in a more structured form. SDF is based mainly on context-free grammars, like EBNF is. It has a number of additions that make it more apt to describe the syntax of really complex programming languages. Especially the languages that were not originally designed to be formally defined, or to have parsers generated for, are the ones that SDF is meant to be applicable to.

These are the unique selling points of SDF, from the language definition point of view:

The implementation of SDF is the combination of an SLR(1) parse table generator and a scannerless generalized LR parser.The goal of this implementation is to fully implement all expressiveness that is available in SDF, and avoiding any hidden implementation details.

These are the unique selling points of the implementation of SDF, from the parser generation point of view:

Note that the language definition point of view, and the parser generation point of view are closely related. Because of SDF's focus on the definition of languages and explicitly declaring disambiguations it is particulary well suited for situations that have "language multiplicity":

The basic assumption of SDF is that all derivations of an input string will be produced. This guarantees that no implicit disambiguation will take place. To disambiguate, the user has to give explicit (declarative) disambiguation rules. Examples of disambiguation rules are longest-match and priorities. By making all these language design choices explicit in a concise manner, SDF allows you to deal with language multiplicity in a more visible (controlled) fashion. In that way high level syntax definition in SDF is like high level programming.

On the one hand, SDF can be used to simply define a language, in order to communicate it as documentation. There are tools that support this use case; checking the definition for inconsistencies and other basic editing support. On the other hand, SDF is often used to obtain a parser for the defined language. Sometimes, SDF is used for other kinds of processing.

The following references on SDF may be interesting for you:

In this document we describe the syntax of SDF and its basic semantics. It is a basic but complete reference manual for SDF based on small examples. This document is loosely structured according to the syntactic structure of SDF: modules, grammars and symbols. After we have described all of it, we continue with a set of examples. The document ends with special sections on well-formedness, disambiguation and the history of SDF. This document does not detail the usage of the implementations of SDF (sdf2table and sglr).

Figure 1.1. The hierarchical structure of the SDF syntax, extracted from the SDF definition of SDF

As an index to this document, the following example exhibits almost all features of SDF with references to the appropriate sections. SDF keywords are highlighted in boldface.

module languages/mylanguage/MyFunnyExample[Param1 Param2]           
  imports basic/Whitespace                                           
  imports utilities/Parsing[Expr]                                     
  imports languages/mylanguage/MyExpressions[Expression => Expr]   
exports                                                               
 sorts Identifier Expr List Stat                                      
 lexical syntax                                                       
   [A-Z][a-z]+ -> Identifier                                           
 lexical restrictions                                                 
   Identifier -/- [a-z]                                              
 context-free syntax                                                  
   Identifier                          -> Expr {cons("name")}                               
   Expr*                               -> List[[Param1]]                                              
   "if" Expr "then" {Param2 ";"}+ 
             "else" {Param2 ";"}+ "fi" -> Param2           
   "if" Expr "then" {Param2 ";"}+ "fi" -> Param2 {prefer}   
 context-free syntax      
   "if" | "then" | "fi"                -> Identifier {reject}                                 
 context-free priorities                                                        
   Expr "&" Expr -> Expr {left}  >                                              
   Expr "|" Expr -> Expr {right}                                                 
hiddens                                                               
 variables                                                            
   "Id"[0-9\']* -> Identifier                                     
 lexical variables                                                    
   "Head" -> [A-Z]
   "Tail" -> [a-z]+

An SDF specification consists of a number of module declarations. The sdf2table commandline tool takes a file with all modules concatenated and the word "definition" in front of them as input. The ASF+SDF Meta-Environment accepts the modules in separate files, each with the extension ".sdf". In that case, an SDF module must be in a file named exactly as the name of the module.

Each module may define lexical syntax, context-free syntax and disambiguations. Modules may import other modules for reuse or separation of concerns. A module may extend the definition of a non-terminal in another module. A module may compose the definition of a language by importing the parts of the language.

The basic structure of a module is this. The module keyword is followed by the module name, then a series of imports can be made, followed by the actual definition of the syntax:

module <ModuleName>
  <ImportSection>*
  <ExportOrHiddenSection>*

A <ModuleName> is either a simple <ModuleId> or a <ModuleId> followed by zero or more parameter symbols, e.g., <Module>[<Symbol>*], the symbols will be explained later. The <ModuleId> may be a compound module name (i.e. <ModuleId> separated by forward slashes), the ModuleId reflects the directory structure. For example basic/Booleans means that the module Booleans is found in the subdirectory basic.

An <ExportOrHiddenSection> is either an export section or a hidden section. The former starts with the keyword exports and makes all entities in the section visible to other modules. The latter starts with the keyword hiddens and makes all entities in the section local to the module. So, hidden means that when another module imports that module, none of the hiddens sections will be present in the composition. The effect for parser generation is that only the hiddens sections of top module of an SDF specification contribute to the parser generation.

An <ExportOrHiddenSection> has thus one of the two forms:

exports 
  <Grammar>+

or

hiddens
  <Grammar>+

A <Grammar> can be a definition of one of the following:

Each of these entities is described and illustrated in Grammars. Most grammars have Symbols as their basic building blocks. Symbols are the SDF term for terminals and non-terminals. Note that it is possible to have hidden imports as well, this means that the full definition of the import definition is copied in the hiddens section of the importing module.

Modules may have formal symbol parameters, which can be bound by actual symbols using imports. The syntax of module parameters is:

module <ModuleName> [ <Symbol>+ ]

When the module is imported, all occurences of the formal parameters will be substituted by the actual parameters.

SDF modules may be collected in a single definition file, for input to the sdf2table tool. The structure of the definition file is as follows:

definition
  <Module>+

A literal symbol defines a fixed length word. This usually corresponds to a terminal symbol in ordinary BNF grammars, e.g., "true" or "&". Literals must always be quoted, also the literals consisting of letters only. SDF generates automatically one production for each literal in order to define it in terms of terminal symbols.

lexical syntax
  "definition" -> Definition

will generate:

[d][e][f][i][n][i][t][i][o][n] -> "definition"

The above obviously generates a case-sensitive implementation of the defined literal. There are also case-insensitive literals. They are defined using single quotes as in 'true' and 'def-word'. SDF generates a different production to implement case insensitivity:

[dD][eE][fF][\-][wW][oO][rR][dD] -> 'def-word'

In literals, the following characters are special and should be escaped:

A sort corresponds to a non-terminal, e.g., Bool. Sort names always start with a capital letter and may be followed by letters and/or digits. Hyphens (-) may be embedded in a sort name. Sort names should be declared in a sorts section to allow some static consistency checking.

Sort names can have parameters. Parameterized sorts can be used to implement grammar polymorphism, and to facilitate grammar reuse without clashing sort names. It provides a way of distinguishing a List of integers from a List of booleans, e.g. List[[Int]], versus List[[Bool]]. The sort parameters are usually instantiated via the parameters of a module or via renaming. A parameterized sort may have several parameters, like List[[X,Y]]. See parameters for more details. Parameterized sorts have the following form:

 <Sort>[[<Symbol1>, <Symbol2>, ... ]]

Enumerations of characters occur frequently mostly in lexical definitions. They can be abbreviated by using character classes enclosed by [ and ]. A character class contains a list of zero or more characters (which stand for themselves) or character ranges such as, for instance, [0-9] as an abbreviation for the characters 0, 1, ..., 9. In a character range of the form c₁-c₂ one of the following restrictions should apply:

Escape Conventions Characters with a special meaning in SDF may cause problems when they are needed as ordinary characters in the lexical syntax. The backslash character (\) is used as escape character for the quoting of special characters. You should use \c whenever you need special character c as ordinary character in a definition. All individual characters in character classes, except digits and letters, are always escaped with a backslash.

You may use the following abbreviations in literals and in character classes:

Character Class Operators The following operators are available for character classes:

The first operator is a unary operator, whereas the other three are left-associative binary operators. Note that the character class operators are not applicable to symbols in general.

The postfix option operator ? describes an optional part in a syntax rule. For instance, ElsePart? defines zero or exactly one occurrence of ElsePart. SDF generates the following syntax:

          -> ElsePart?
 ElsePart -> ElsePart?

The sequence operator (...) describes the grouping of two or more symbols, e.g., (Bool "&"). Sequences are mostly used to group symbols together to form a more complex symbol using one of the available operators, e.g., (Bool "&")*. It has no effect to construct a sequence consisting of a single symbol, because then the (...) brackets are simply brackets. The empty sequence is a special symbol. SDF generates the following syntax for the (Bool "&") symbol:

Bool "&" -> (Bool "&")

For () it simply generates:

 -> ()

Repetition operators express that a symbol should occur several times. In this way it is possible to construct flat lists and therefore we usually refer to repetitions as \emph{lists}. Repetition operators come in two flavors, with and without separators. Furthermore, it is possible to express the minimal number of repetitions of the symbol: at least zero times (*) or at least one time (+). Examples are:

Note that the separator may be an arbitrary symbol, but that some back-ends do not support parse trees that contain them. The sdf-checker of the ASF+SDF Meta-Environment will warn you if you use anything but a literal as a separator.

Again, to implement lists SDF simply generates a few production for you, i.e.:

             -> Bool*
 Bool+       -> Bool*
 Bool        -> Bool+
 Bool+ Bool+ -> Bool+ {left}

                             -> {Bool ","}*
 {Bool ","}+                 -> {Bool ","}+
 Bool                        -> {Bool ","}+
 {Bool ","}+ "," {Bool ","}+ -> {Bool ","}+ {left}

Note that there are some more productions generated, but they are not shown here. SDF generates more productions to allow arbitrary compositions of * and + lists, and also adds disambiguation filters to deal with the ambiguity this introduces.

The alternative operator | expresses the choice between two symbols, e.g., "true" | "false" represents that either a "true" symbol or a "false" symbol may occur here. The alternative operator is right associative and binds stronger than any other operator on symbols. This is important because Bool "," | Bool ";" expresses Bool ("," | Bool) ";" instead of (Bool ",") | (Bool ";"). So, in case of doubt use the sequence operator in combination with the alternative operator.

For "," | ";" SDF generates:

"," -> "," | ";"
";" -> "," | ";"

It is possible to decorate the symbols with labels. The labels have no semantics in SDF, and will be removed before parse table generation. Other tools that take SDF definitions as input, such as API generators make use of the labels.

So, labels are removed by replacing the labelled symbol with the symbol, as in:

mylist:{elem:Stat sep:";"}+
is replaced by
{Stat ";"}+

The tuple operator describes the grouping of a sequence of symbols of a fixed length into a tuple. The notation for tuples is < , , >, i.e., a comma-separated list of elements enclosed in angle brackets. For example, <Bool, Int, Id> describes a tuple with three elements consisting of a Bool, an Int and an Id (in that order). For instance, <true, 3, x> is a valid example of such a tuple.

Tuple is one of the few symbols that actually introduce a fixed syntax, i.e. the angular brackets. You may consider them as an arbitrary shorthand. To define your own short hand, consider the use of parameterized sorts and module parameters.

For <A,B> SDF generates:

"<" A "," B ">" -> <A,B>

The function operator (...=>...) allows the definition of function types. Left of => zero or more symbols may occur, right of => exactly one symbol may occur. For example, (Bool Int) => Int represents a function with two argument (of types Bool and Int, respectively) and a result type Int. The function symbol may be used to mimick a higher order type system. The function symbol also introduces some arbitrary syntax (the ( ) brackets).

SDF generates the following syntax for (A B => C):

(A B => C) "(" A B ")" -> C

Read this as "something of type (A B => C) may be applied to A and B to become a C". Note that this is the only symbol that is not defined by generating productions with the defined symbol on the right-hand side. The user must still define the syntax for (A B => C) manually like:

"myfunction" -> (A B => C)

The lifting operator `...` translates the name of an arbitrary complex symbol to a literal syntax definition of that name. It makes a symbol a part of the defined syntax. An example: `X?` defines the syntax ("X" "?"). The lifting operator is typically used in combination with parameterized modules, and specifically for applications of SDF that implement concrete syntax. The lifting symbol is a reflexive operator, it generates different syntax for different operators.

Note that the lifting operator is not implemented by defining it using production symbols. This operator is implemented by replacing it with another symbol. Examples:

`"foo"` is replaced by "\"foo\""
`A ?"` is replaced by ("A" "?")
`{A ","}+` is replaced by ("{" "A" "\",\"" "}" "+") 

The LAYOUT symbol is a reserved sort name. SDF does not generate any productions for it. Instead for all context-free syntax grammars it will distribute LAYOUT? between all members of the left-hand sides of all productions. Note that the "?" in LAYOUT? will take care of some production generation. The user must define all alternatives for LAYOUT herself. Example:

[\ \t\n] -> LAYOUT

Note that LAYOUT may only be defined in lexical syntax grammars. The LAYOUT non-terminal is used by back-ends (independent of SDF) to find out what is irrelevant about a parse tree and what is relevant. Still, SDF does not attribute any additional semantics to it. It is just a non-terminal that is distributed over context-free productions.

Aliases are similar to productions but not quite. An alias is used to define a short hand for a complex or otherwise cumbersome symbol.

aliases
  <Sort1> -> <Sort2>

where the alias Sort₂ is given to Sort₁. An example is ("{" | "<:") from the C programming language. Instead of having to repeat that everywhere you may write:

aliases
  ("{" | "<:") -> BracketOpen

Aliases are tricky. There are a number of rules you should adhere to:

Sorts are declared by listing their name in a sorts section of the form:

sorts
  <Symbol>*

Only plain Sorts and parameterized Sorts should declared in the sorts section. The sdf-checker will generate a warnings. The checker requires that all sorts that occur in some symbol in the specification are declared. Note however that the sorts declaration does not carry any semantics other than simply declaring a name. The checker uses this to warn the SDF user for possible typos.

Lexical syntax describes the low-level structure of text while context-free syntax describes the higher-level structure. In SDF, these two aspects of syntax are defined in a very uniform manner. In fact, production rules are used to describe both lexical and concrete syntax.

The only difference between the two is that context-free productions are pre-processed somewhat extensively by SDF before parser generation, while lexical productions are not. And, it is important to note that symbols defined in lexical syntax and symbols defined in context-free syntax are in separate name-spaces. Example:

lexical syntax
  "a" -> A
context-free syntax
  "b" -> A

Here we are defining two different A's: one lexical and one context-free. The two definitions are automatically linked by SDF by the following transformation:

 "a"     -> <A-LEX>
 <A-LEX> -> <A-CF>
 "b"     -> <A-CF>

lexical syntax
  <Production>*

context-free syntax
   <Production>*

context-free syntax
  "{" Stat* "}" -> Block

is pre-processed to:

"{" LAYOUT? Stat* LAYOUT? "}" -> Block

which will be then wrapped as in:

"{" <LAYOUT?-CF> <Stat*-CF> <LAYOUT?-CF> "}" -> <Block-CF>

<Symbol>* -> <Symbol>

 P ::= 'b' D S 'e'

  "b" D S "e" -> P

A ::= C | D | E

C -> A
D -> A
E -> A

C | D | E -> A
will generate the following grammar:
C | D | E -> A
C         -> C | D | E
D         -> C | D | E
E         -> C | D | E

<Symbol>* -> <Symbol> { <Attribute1>, <Attribute2>, ...}

"if" E "then" S -> S {cons("if")}
"if" E "then" S -> S {prefer}
will be merged to:
"if" E "then" S -> S {cons("if"), prefer}

f(X,Y) -> Z {cons("f")} 
is replaced by
"f" "(" X "," Y ")" -> Z {cons("f")}

Via the lexical or context-free start symbols section the symbols are explicitly defined which will serve as start symbols when parsing terms. If no start symbols are defined it is not possible to recognize terms. This has the effect that input sentences corresponding to these symbols can be parsed. So, if we want to recognize booleans terms we have to define explicitly the sort Boolean as a start symbol in the module Booleans. Any symbol, also lists, tuples, etc., can serve as a start-symbol. A definition of lexical start symbols looks like

lexical start-symbols
  <Symbol>*

while context-free start symbols are defined as

context-free start-symbols
  <Symbol>*

Start symbols are short-hand notation, for which SDF generates productions as in:

lexical start-symbols
   Identifier
generates
   <Identifier-LEX> -> <START>
and
context-free start-symbols
   Program
generates
   <LAYOUT?-CF> <Program-CF> <LAYOUT?-CF> -> <START>

Priorities are one of SDF's most often used disambiguation constructs. A priority 'grammar' defines the relative priorities between productions. There is a lot of short-hand notation for doing this concisely. Priorities are a powerful disambiguation construct. The basic priority looks like this:

context-free priorities
<Production>   >   <Production>

Context-free priorities work on context-free productions, while lexical priorities work on lexical productions. The idea behind the semantics of priorities is that productions with a higher priority "bind stronger" than productions with a lower priority. However, strictly speaking the semantics of SDF's priorities are that they give rise to parse forest filters that remove certain trees. If A > B, then all trees are removed that have a B node as a direct child of an A node.

Several priorities in a priority grammar are separated by comma's. Productions may be grouped between curly braces on each side of the > sign. Groups may have relative associativity labels. Examples:

context-free priorities
  { left: E "*" E -> E {left}
          E "/" E -> E {right}
  } >
  { right: E "+" E -> E {left}
           E "-" E -> E {left}
  ,
  "-" E -> E > E "+" E -> E {left}
 

Please note the following details on priorities:

There are two recent additions to priorities which make them more flexible. Firstly, priorities can now be targeted at specific members of the first production: "priorities in specific arguments". Example:

context-free priorities
  E "[" E "]" -> E
  <0> > 
  E "+" E -> E {left}

Between the angular brackets a comma separated list of argument indexes indicates to which arguments the disambiguation should be applied (and implicitly in which not). In fact, in this example applying the filter to all arguments would result in parse errors for terms such as "1 [ 2 + 3 ]". The semantics of priorities in specific arguments is thus to remove all derivations that have the second production as a child of the first production at the specified positions.

The second addition is non-transitive priorities. In rare cases the automatic transitive closure may be incorrect. Note however that by not transitively closing the priority relation you may have to write down a high amount of priorities. Example:

context-free priorities
  "-" E -> E >.
  E "+" E -> E

The ".", or full stop, makes sure that this relation does not contribute to any transitive closure.

Variables are declared in the variables section of a module. Like all other entities in a module, except equations, variables may be exported (see section Modules). A variables section consists of a list of variable names followed by a symbol. In fact, a variable declaration can define an infinite collection of variables by using a naming scheme instead of a simple variable name. A naming scheme is a regular expression like the ones allowed in the lexical syntax except that sorts are not allowed. A variable may represent any symbol. In the specification below, Id, Type3, and Id-list are examples of variables declared by the naming schemes in the variables section. Strings that occur in the left-hand side of variable declarations should always be quoted.

module VarDecls

imports basic/Whitespace

exports
  context-free start-symbols Decl
  sorts Id Decl Type 

  lexical syntax
    [a-z]+ -> Id
 
  context-free syntax
    "decl" {Id ","}+ ":" Type -> Decl 
    "integer"                 -> Type 
    "real"                    -> Type 

hiddens
  variables
    "Id"           -> Id 
    "Type"[0-9]*   -> Type 
    "Id-list"[\']* -> {Id ","}* 
    "Id-ne-list"   -> {Id ","}+

Lexical variables are similar to variables. The difference is that they range over non-terminals defined in lexical syntax sections, and may range over character classes and symbol operators applied to character classes.

The notion of restrictions enables the formulation of lexical disambiguation strategies that occur in the design of programming languages. Examples are "shift before reduce" and "longest match". A restriction filters applications of productions for certain non-terminals if the following character (lookahead) is in a certain class. The result is that specific symbols may not be followed by a character from a given character class. A lookahead may consist of more than one character class (multiple lookahead). Restrictions come in two flavors:

The general form of a restriction is:

<Symbol>+ -/- <Lookaheads>

In case of lexical restrictions <Symbol> may be either a literal or sort. In case of context-free restrictions only a sort or symbol is allowed. The restriction operator -/- should be read as may not be followed by. Before the restriction operator -/- a list of symbols is given for which the restriction holds.

Lookaheads are lists of character classes separated by ".". Note that single character restrictions are implemented faster then multiple character restrictions. Example:

Identifier -/- [i].[f]
Identifier -/- [e].[l].[s].[e]

The semantics of a restriction <Symbol> -/- <Lookahead> are thus to remove all derivations that produce a certain <Symbol>. The condition for this removal is that the derivation tree for that symbol is followed immediately by something that matches the lookahead declaration. Note that to be able to check this condition, one must look past derivations that produce the empty language, until the characters to the right of the filtered symbol are found. Also, for finding multiple lookahead matches, one must ignore nullable sub-trees that may occur in the middle of the matched lookahead.

As mentioned before SDF is based on two notions. The first is context-free grammars, and the second is disambiguation filters. The disambiguation constructs of SDF are:

Each disambiguation construct gives rise to a specific derivation filter. So, the semantics of SDF can be seen as two-staged. First, the grammar generates all possible derivations. Second, the disambiguation constructs remove a number of derivations. This section mainly serves as an index to the disambiguation constructs found in the the section called “Grammars”, and it provides additional information where needed.

An extensive "How To" on disambiguation can be found in the SDF Disambiguation Med kit for Programming Languages. In the current document there is only limited "howto" information on this subject.

Priorities are described in the section called “Lexical and context-free priorities”. Note that there is a link between associativity and priorities: priority declarations can contain relative associativities. The {bracket} attribute also plays a role in priorities. The essence of the priority disambiguation construct is that certain vertical (father/child) relations in derivations are removed.

Associativity declarations occur in two places in SDF. The first is as production attributes. The second is as associativity declarations in priority groups. Like with priorities, the essence of the associativity attribute is that certain vertical (father/child) relations in derivations are removed:

Note that in general associatity attributes are thus intended to work on production rules with the following pattern: X ... X -> X.

In priority groups, the associativity attribute can also be found. It has the same semantics as the associativity attributes, except that the filter refers to two nested productions instead of a recursive nesting of one production. The group associativity attribute works pairwise and commutative on all combinations of productions in the group. If there is only one element in the group the attribute is reflexive, otherwise it is not reflexive.

Note that associativity does not work transitively. Another way of defining associativity is to translate associativity attributes to non-transitive priorities in specific arguments.

It is not used by SDF, but some back-ends use it. For example, the restore-brackets tool uses the bracket attribute to find productions to add to a parse tree before pretty printing (when the tree violates priority constraints). Note that most of these tools demand the production with a {bracket} attribute to have the shape: "(" X ")" -> X {bracket} with any kind of bracket syntax but the X being the same symbol on the left-hand side and the right-hand side.

The connection with priorities and associativity is that when a non-terminal is disambiguated using either of them, a production rule with the {bracket} attribute is probably also needed.

The reject disambiguation construct also filters derivations. For a production <Symbol>+ -> Symbol {reject} the semantics is that the set of all derivations for <Symbol> are filtered. Namely, all derivations that derive a string that can also be derived from <Symbol>+ are removed. Another way of saying this is that the language (set of strings) defined by <Symbol> has become smaller, namely the set of strings defined by <Symbol+> is subtracted from it.

The reject mechanism effectively defines the difference operator between two context-free languages. As such it can be used to define non context-free languages such as aⁿbⁿcⁿ. This is not it's intended use.

The preferences mechanism is another disambiguation filter that provides a filter semantics to a production attribute. The attributes {prefer} and {avoid} are the only disambiguation constructs that compare alternative derivations. They are sometimes referred to as horizontal disambiguation filters.

The following definition assumes that derivations are represented using parse forests with "packaged ambiguity nodes". This means that whenever in a derivation there is a choice for several sub-derivations, at that point a special choice node (ambiguity constructor) is placed with all alternatives as children. We assume here that the ambiguity constructor is always placed at the location where a choice is needed, and not higher (i.e. a minimal parse forest representation). The preference mechanism compares the top nodes of each alternative:

Restrictions, or follow restrictions, are intended for filtering ambiguity that occurs on a lexical level. They are described in restrictions.

Below we give an example of a simple lexical function definition for defining the first three words that Dutch children learn to read. The three sorts Aap, Noot and Mies, each recognize, respectively, the strings aap, noot and mies. The sort LeesPlank (a reading-desk used in primary education) recognizes the single string aapnootmies.

module LeesPlank

imports basic/Whitespace

exports
  context-free start-symbols LeesPlank
  sorts Aap Noot Mies LeesPlank
  lexical syntax
    "aap"         -> Aap
    "noot"        -> Noot
    "mies"        -> Mies
    Aap Noot Mies -> LeesPlank

Definitions for lower-case letter (LCLetter), upper-case letters (UCLetter), lower-case and upper-case letters (Letter) and digits (Digit) are shown in the first example below}.

module LettersDigits1

imports basic/Whitespace

exports
  context-free start-symbols Letter Digit
  sorts LCLetter UCLetter Letter Digit
  lexical syntax
    [a-z]    -> LCLetter
    [A-Z]    -> UCLetter
    [a-zA-Z] -> Letter
    [0-9]    -> Digit

The next example gives a definition of the sort LetterOrDigit that recognizes a single letter (upper-case or lower-case) or digit.

module LettersDigits2
imports basic/Whitespace

exports
  context-free start-symbols LetterOrDigit
  sorts LetterOrDigit
  lexical syntax
    [a-z]    -> LetterOrDigit
    [A-Z]    -> LetterOrDigit
    [0-9]    -> LetterOrDigit

The example below gives the definition of a single letter or digit using the alternative operator \/. This definition is equivalent to the one given above.

module LettersDigits3
exports
  context-free start-symbols LetterOrDigit
  sorts LetterOrDigit
  lexical syntax
    [a-z] \/ [A-Z] \/ [0-9]   -> LetterOrDigit

Another example is shown below. This definition of characters contains all possible characters, either by means of the ordinary representation or via their decimal representation.

module Characters

imports basic/Whitespace

exports
  context-free start-symbols L-Char
  sorts AlphaNumericalEscChar DecimalEscChar EscChar L-Char
  lexical syntax
    "\\" ~[]                 -> AlphaNumericalEscChar

    "\\" [01] [0-9] [0-9]    -> DecimalEscChar
    "\\" "2" [0-4] [0-9]     -> DecimalEscChar
    "\\" "2" "5" [0-5]       -> DecimalEscChar

    AlphaNumericalEscChar    -> EscChar
    DecimalEscChar           -> EscChar

    ~[\0-\31\"\\] \/ [\t\n]  -> L-Char
    EscChar                  -> L-Char

Consider the language of coordinates and drawing commands presented below.

module DrawingCommands

imports basic/Whitespace

exports
  context-free start-symbols CMND 
  sorts NAT COORD CMND 

  lexical syntax
    [0-9]+ -> NAT 

  context-free syntax
    "(" NAT "," NAT ")" -> COORD
    "line" "to" COORD   -> CMND 
    "move" "to" COORD   -> CMND

An equivalent conventional BNF grammar (and not considering lexical syntax) of the above grammar is as follows:

<COORD> ::= "(" <NAT> "," <NAT> ")" 
<CMND>  ::= "line" "to" <COORD> | "move" "to" <COORD>

Lexical tokens are often described by patterns that exhibit a certain repetition. The list symbols described in List Symbols can be used to express repetitions. The example below demonstrates the use of the repetition symbol * for defining identifiers consisting of a letter followed by zero or more letters or digits.

module Identifiers-repetition

imports basic/Whitespace

exports
  context-free start-symbols Id
  sorts Letter DigitLetter Id
  lexical syntax
    [a-z]       -> Letter
    [a-z0-9]    -> DigitLetter

    Letter DigitLetter* -> Id

If zero or exactly one occurrence of a lexical token is desired the option operator described in Optional symbols can be used. The use of the option operator is illustrated below. Identifiers are defined consisting of one letter followed by one, optional, digit. This definition accepts a and z8, but rejects ab or z789.

module Identifiers-optional

imports basic/Whitespace

exports
  context-free start-symbols Id
  sorts Letter Digit Id
  lexical syntax
    [a-z]  -> Letter
    [0-9]  -> Digit

    Letter Digit? -> Id 

Productions with the same result sort together define the lexical syntax of tokens for that sort. The left-hand sides of these function definitions form the alternatives for this function. Sometimes, it is more convenient to list these alternatives explicitly in a single left-hand side or to list alternative parts inside a left-hand side. This is precisely the role of the alternative operator. The example below shows how this operator can be used. It describes identifiers starting with an upper-case letter followed by one of the following:

According to this definition, Aap, NOOT, and B49 are acceptable, but MiES, B49a and 007 are not.

module Identifiers-alternative1

imports basic/Whitespace

exports
  context-free start-symbols Id
  sorts LCLetter UCLetter Digit Id
  lexical syntax
    [A-Z]   -> UCLetter
    [a-z]   -> LCLetter
    [0-9]   -> Digit

  UCLetter LCLetter* | UCLetter* | Digit* -> Id

Note that the relation between juxtaposition and alternative operator is best understood by looking at the line defining Id. A parenthesized version of this same line would read as follows:

 UCLetter (LCLetter* | UCLetter* | Digit*) -> Id

As an aside, note that moving the * outside the parentheses as in

 UCLetter (LCLetter | UCLetter | Digit)* -> Id

yields a completely different definition: it describes identifiers starting with an uppercase letter followed by zero or more lower-case letters, uppercase letters or digits. According to this definition MiES, B49a and Bond007 would, for instance, be acceptable. A slightly more readable definition that is equivalent to the previous one is shown below. In any case, we recommend to use parentheses to make the scope of alternatives explicit.

module Identifiers-alternative2

imports basic/Whitespace

exports
  context-free start-symbols Id
  sorts UCLetter LCLetter Digit Id
  lexical syntax
    [A-Z]                     -> UCLetter
    [a-z]                     -> LCLetter
    [0-9]                     -> Digit

    (UCLetter LCLetter*) | 
    (UCLetter UCLetter*) | 
    (UCLetter Digit*)          -> Id

Definitions of integers and real numbers are shown below. Note the use of the alternative operator in the definitions of UnsignedInt and Number. Also note the use of the option operator in the definitions of SignedInt and UnsignedReal.

module Numbers

imports basic/Whitespace

exports
  context-free start-symbols Number
  sorts UnsignedInt SignedInt UnsignedReal Number 

  lexical syntax
    [0] | ([1-9][0-9]*)                           -> UnsignedInt

    [\+\-]? UnsignedInt                           -> SignedInt

    UnsignedInt "." UnsignedInt ([eE] SignedInt)? -> UnsignedReal 
    UnsignedInt [eE] SignedInt                    -> UnsignedReal

    UnsignedInt | UnsignedReal                    -> Number  

The specification below, gives the lexical definition of strings which may contain escaped double quote characters. It defines a StringChar as either

A string consists of zero or more StringChars surrounded by double quotes.

module Strings

imports basic/Whitespace

exports
  context-free start-symbols String
  sorts String StringChar

  lexical syntax
    ~[\"\n]               -> StringChar
    [\\][\"]              -> StringChar
    "\"" StringChar* "\"" -> String

Context-free syntax often requires the description of the repetition of a syntactic notion or of list structures (with or without separators) containing a syntactic notion. The list symbols can be used for this purpose. Lists may be used in both the left-hand side and right-hand side of a context-free function as well as in the right-hand side of a variable declaration.

Here is an example of how lists can be used to define the syntax of a list of identifiers (occurring in a declaration in a Pascal-like language).

module Decls

imports basic/Whitespace

exports
  context-free start-symbols Decl
  sorts Id Decl Type 

  lexical syntax
    [a-z]+ -> Id 

  context-free syntax
    "decl" {Id ","}+ ":" Type -> Decl
    "integer"                 -> Type 
    "real"                    -> Type

A context-free syntax may contain productions that do not add syntax, but serve the sole purpose of including a smaller syntactic notion into a larger one. This notion is also known as injections. Injections are productions without a name and with one argument sort like Id -> Data. A typical example is the inclusion of identifiers in expressions or of natural numbers in reals. Such a chain function has one of the following forms:

It is a common misconception that chain rules will not be represented in the parse tree that sglr outputs. An injection production is a production like any other, and will lead to a node in the parse tree. However, some back-ends are known to interpret chain rules as sub-sort relations. In the example below the symbols Nat and Var are injected in Exp.

module Exp

imports basic/Whitespace

exports
  context-free start-symbols Exp
  sorts Nat Var Exp

  lexical syntax
    [0-9]+   -> Nat
    [XYZ]    -> Var

  context-free syntax
    Nat                 -> Exp
    Var                 -> Exp
    Exp "+" Exp         -> Exp

See below for an example of an SDF specification containing labels. Remember that labels do not have semantics in SDF.

module Booleans

imports basic/Whitespace

exports
  context-free start-symbols Boolean
  sorts Boolean

  context-free syntax
    lhs:Boolean "|" rhs:Boolean -> Boolean
    lhs:Boolean "&" rhs:Boolean -> Boolean

Groups of associative productions define how to accept or reject trees containing related occurrences of different productions with the same priority. They are defined by prefixing a list of context-free productions in a priority declaration with one of the following attributes:

where F and G are productions appearing in the list. Below is an example of the use of grouped associativity.

module ComplexExpr

imports basic/Whitespace
imports basic/NatCon

exports
  context-free start-symbols E 

  sorts E 

  context-free syntax
    NatCon    -> E
    E "+" E   -> E {left}
    E "-" E   -> E {non-assoc}
    E "*" E   -> E {left}
    E "/" E   -> E {non-assoc}
    E "^" E   -> E {right}
    "(" E ")" -> E {bracket}

  context-free priorities
    E "^" E -> E > 
    {non-assoc: E "*" E -> E
                E "/" E -> E} >
    {left: E "+" E -> E
           E "-" E -> E} 

Associativity attributes can be attached to binary productions of the form S op S -> S, where op is a symbol or empty. Without associativity attributes, nested occurrences of such productions immediately lead to ambiguities, as is shown by the sentence S-string op S-string op S-string where S-string is a string produced by symbol S. The particular associativity associated with op determines the intended interpretation of such sentences. We call two occurrences of productions F and G related, when the node corresponding to F has a node corresponding to G as first or last child. The associativity attributes define how to accept or reject trees containing related occurrences of the same function, F:

Currently, there is no syntactic or semantic difference between left and assoc, but  we may change the semantics of the assoc attribute in the future. Is this really true?

Below we give an example of a definition of simple arithmetic expressions with the usual priorities and associativities.

module SimpleExpr

imports basic/Whitespace
imports basic/NatCon

exports
  context-free start-symbols E 
  sorts E 

  context-free syntax
    NatCon    -> E
    E "+" E   -> E {left}
    E "*" E   -> E {left}
    "(" E ")" -> E {bracket}

  context-free priorities
    E "*" E -> E > 
    E "+" E -> E

Module parameterization allows the definition of generic modules for lists, pairs, sets, etc. The operations defined in these modules are independent of a specific type. When importing a parameterized module and instantiating the formal by actual parameters the operations become sort specific. Modules can have formal parameters when defining them. The module name is then followed by a list of symbols, representing the formal parameters of this module. The specification below shows an example of a parameterized module. In this example the formal parameters are used in the parameterized sorts as well, in order to increase readability and to avoid name clashes between different instances of the same module.

module Pair[X Y]

imports basic/Whitespace
imports basic/Booleans

hiddens
  sorts X Y

exports
  context-free start-symbols Pair[[X,Y]]
  sorts Pair[[X,Y]]

  context-free syntax
    "[" X "," Y "]"      -> Pair[[X,Y]]

    make-pair(X, Y)      -> Pair[[X,Y]]
    first(Pair[[X,Y]])   -> X
    second(Pair[[X,Y]])  -> Y
    is-pair(Pair[[X,Y]]) -> Boolean

When importing a parameterized module the formal parameters have to be replaced by actual parameters. The specification below shows an example of a rather complicated import of a parameterized module. The symbols Pair[[Boolean,Boolean]] and Pair[[Integer,Integer]] are the actual parameters of the module Pair[X Y] in the last import.

module TestPair

imports basic/Booleans 
imports basic/Integers 
imports Pair[Boolean Boolean]
imports Pair[Integer Integer]
imports Pair[Pair[[Boolean,Boolean]] Pair[[Integer,Integer]]]

The specification below shows an example of the Pair module without parameters. The idea is to achieve the same effect as parameterization by explicitly renaming X and Y to the desired names when Pair is imported.

module Pair

imports basic/Whitespace
imports basic/Booleans

hiddens
  sorts X Y

exports
  context-free start-symbols Pair[[X,Y]]
  sorts Pair[[X,Y]]

  context-free syntax
    "[" X "," Y "]"      -> Pair[[X,Y]]

    make-pair(X, Y)      -> Pair[[X,Y]]
    first(Pair[[X,Y]])   -> X
    second(Pair[[X,Y]])  -> Y
    is-pair(Pair[[X,Y]]) -> Boolean

During import such module symbols can be renamed via symbol renaming. The specification below shows an example of a rather complicated import of the module Pair using renamings. Renaming X to Boolean is, for instance, written as X => Boolean.

module TestPair

imports basic/Booleans 
imports basic/Integers 
imports Pair[X => Boolean Y => Boolean]
imports Pair[X => Integer  Y => Integer]
imports Pair[X => Pair[[Boolean,Boolean]] Y => Pair[[Integer,Integer]]]

In the example below both let and in may not be followed by a letter. This example shows how lexical restrictions can be used to prevent the recognition of erroneous expressions in a small functional language. The lexical restriction deals with the possible confusion between the reserved words let and in and variables (of sort Var). It forbids the recognition of, for instance, let as part of letter. Without this restriction letter would be recognized as the keyword let followed by the variable ter. The context-free restriction forbids that a variable is directly followed by a letter. It does not forbid layout characters between the letters, e.g. a b is a legal recognizable string.

module Functional

imports basic/Whitespace

exports
  context-free start-symbols Term 
  sorts Var Term
  lexical syntax
    [a-z]+ -> Var
  context-free syntax
    Var                          -> Term
    Term Term                    -> Term {left}
    "let" Var "=" Term "in" Term -> Term

  lexical restrictions
    "let" "in" -/- [a-z]

  context-free restrictions
    Var -/- [a-z]  

The next example illustrates the use of restrictions to define a safe way of layout. Recall that optional layout, represented by the symbol LAYOUT?, may be recognized between the members of the left-hand side of a context-free syntax rule. However, if a such a member recognizes the empty string, this gives rise to a an ambiguity. This problem is avoided by the definition given below: it simply forbids that optional layout is followed by layout characters.

module basic/Whitespace

exports
  lexical syntax
    [\ \t\n] -> LAYOUT

  context-free restrictions
    LAYOUT? -/- [\ \t\n]

The example shown below illustrates the use of restrictions to extend the previous layout definition with C-style comments. For readability we give here two restrictions whereas the first one is already imported from module basic/Whitespace. The repetition of this first restriction is redundant and could be eliminated.

module Comment

imports basic/Whitespace

exports
  sorts ComWord Comment
  lexical syntax
    ~[\ \n\t\/]+ -> ComWord

  context-free syntax
    "/*" ComWord* "*/" -> Comment
    Comment            -> LAYOUT

  context-free restrictions
    LAYOUT? -/- [\ \t\n]
    LAYOUT? -/- [\/].[\*]

A frequently asked question is when to use lexical restrictions and when to use context-free restrictions. In one of the previous examples the lexical restrictions on let and in cannot be defined using context-free restrictions because these keywords do not "live" at the context-free level. Is it possible to put a lexical restriction on Var? Yes, but it will have no effect, because internally the lexical Var is injected in the context-free Var. The general rule is to define the restrictions always on the context-free level and not on the lexical level unless a situation as will be discussed in the next paragraph occurs. The specification below is an example of an erroneous use of context-free expressions, because it prevents the recognition of (abc)def. If we want to enforce the correct restriction, it is necessary to transform this context-free restriction into a lexical restriction.

module RestrictedExpressions

imports basic/Whitespace

exports
  context-free start-symbols Expr
  sorts Expr

  lexical syntax
    [a-z]+ -> Expr

  context-free syntax
    Expr Expr    -> Expr {left}
    "(" Expr ")" -> Expr {bracket}

  context-free restrictions
    Expr -/- [a-z]

In Symbols a number of sophisticated operators, like alternative, option, function, sequence, and tuple are discussed. These operators allow a concise manner of defining grammars. There are, however, a number of issues to be taken into consideration when using this operators.

module Lists

imports basic/Whitespace

exports
  context-free start-symbols List1 List2
  sorts Nat List1 List2

  lexical syntax
    [0-9]+   -> Nat

  context-free syntax
    {Nat ","}+ -> List1
    (Nat ",")+ -> List2

module Bool

imports basic/Whitespace

exports
  context-free start-symbols Bool1 Bool2
  sorts Bool1 Bool2

  context-free syntax
    "true"                  -> Bool1
    "false"                 -> Bool1
    Bool1 "|" Bool1         -> Bool1 {left}
    Bool1 "&" Bool1         -> Bool1 {left}

    "true" | "false"        -> Bool2
    Bool2 ("|" | "&") Bool2 -> Bool2 {left}

module Cycle

imports basic/Whitespace

exports
  context-free start-symbols T
  sorts A P T

  context-free syntax
    "a"        -> A
    A?         -> P
    "[" P+ "]" -> T

There are three different types of parse errors:

Warnings do not break the specification, but it is advisable to fix them anyway. Often they point out some not well-formed part in the specification.