Syntax Notation

The syntax is described by means of an extended Backus-Naur form (EBNF).

Syntactic entities (non-terminals) are denoted by English words expressing their intuitive meaning. Terminal symbols of the language are written between acute accents ' or double quotes " in order to be distinguished from non-terminals.

A syntax definition is a collection of productions. Each production has the form

    S = E.

where S is a non-terminal and E a syntax expression denoting the set of constructs for which S stands. An expression E has the form

    T₁ | T₂ | ... | T_n       (n>0)

where the T_i's are the terms of E. Each T_i stands for a set of constructs, and E denotes their union. Each term T has the form

    F₁ F₂ ... F_n             (n>0)

where the F_i's are the factors of T. Each F_i stands for a set of constructs, and T denotes their product, i.e. the set of constructs of the form X₁ X₂ ... X_n, where each X_i belongs to the set denoted by F_i.

Each factor F has either the form

"x"

(x is a terminal symbol, and "x" denotes the singleton set consisting of this single symbol), or

    ( E )

(denoting the expression E), or

    [ E ]

(denoting the union of the set denoted by E and the empty construct), or

    { E }

(denoting the set consisting of the union of the empty construct and the sets E, E E, E E E, etc.).

Here are a few examples of syntactic EBNF-expressions along with the sets of constructs described by the expressions.

    (A|B)(C|D)     A C, A D, B C, B D
    A[B]C          A B C, A C
    A {B A}        A, A B A, A B A B A, A B A B A B A, ...
    {A|B} C        C, A C, B C, A A C, A B C, B B C, B A C, ...

Since an EBNF-description may be regarded as a text in a language, the syntax of EBNF-descriptions may also be defined in terms of EBNF in the following way:

Syntax         = { SyntFormula }.
SyntFormula    = Identifier "=" SyntExpression ".".
SyntExpression = SyntTerm { "|" SyntTerm }.
SyntTerm       = SyntFactor { SyntFactor }.
SyntFactor     = Identifier | '"' TerminalSymbol '"' |
     "(" SyntExpression ")" | "[" SyntExpression "]" |
     "{" SyntExpression "}".