Extended Backus-Naur Form (EBNF)-Descriptions

EBNF Rules

An EBNF rule is of the form

$$\text{LHS}⟸\text{RHS}$$

where LHS stands for left-hand side and RHS for right-hand side. Usually the LHS is denoted in lowercase, cursive font. Since cursive can be hard to differentiate in handwriting, names appearing on the RHS can also be wrapped in < and > to denote a reference to another EBNF rule. The LHS is the name of an EBNF rule, whereas the RHS describes it. The RHS can contain names of other EBNF rules, characters, or combinations of the four control forms. EBNF descriptions only allow for statements about the syntax of the symbols of a language, not however about the semantics, i.e., the meaning of those symbols.

Control Forms

• Sequence
  • order is relevant, example: $\text{myrule}⟸\text{form\_1}\text{form\_2}\text{form\_3}$ , where $\text{form\_1}$, $\text{form\_2}$, $\text{form\_3}$ are other EBNF rules defined previously in the description
• Decision

  • a set of alternatives, order irrelevant. Denoted by a vertical bar. Example: $\text{room}⟸\text{room\_1}|\text{room\_2}|\text{room\_3}$. Sequence preceeds decision, however in order to prevent misunderstandings use parentheses when using

  • Option: elements wrapped in square brackets, can be chosen, can also be omitted. Example: $\text{initials}⟸T[R]G$. If the option is omitted it is denoted $ϵ$, which represents the empty character
• Repetition
  • denoted by curly braces, signifying its contents can be repeated $0,1,\dots$ times, where 0 times represents a choice of $ϵ$. Example:

  $$\begin{array}{rl}\text{digit}& ⟸1|2|3|4|5|6|7|8|9|0\\ \text{sequence}& ⟸\text{digit}\{\text{digit}\}\\ \text{integer}& ⟸[+|-]\text{digit}\{\text{digit}\}\end{array}$$

• Recursion

  • an EBNF rule that is defined in term of itself, i.e., the name of the rule appears on the RHS of the rule (directly or indirectly, where indirectly means first having to substitute the definition(s) of other EBNF rules to see that the name of the rule appears on the RHS). For such a rule to be legal according to the rules for EBNF rules there must exist a way to remove the name of the rule from the RHS of the rule, i.e., by substituting appropriately. For example, there are no legal symbols for the rule $\text{pos\_integer}⟸\text{digit}\{\text{pos\_integer}\}$}, as whenever we substitute $\text{pos\_integer}$ on the RHS we still have $\text{pos \_integer}$ on the RHS:

    $$\begin{array}{rl}& \text{pos\_integer}\\ & \text{digit}\{\text{pos\_integer}\}\\ & \text{digit}\text{digit}\{\text{pos\_integer}\}\\ & \text{digit}\text{digit}\text{digit}\{\text{pos\_integer}\}\\ & \dots \end{array}$$

    The following rule however does allow for legal symbols: $\text{pos\_integer}⟸\text{digit}\{\text{pos\_integer}\}|\text{digit}$

    $$\begin{array}{rl}& \text{pos\_integer}\\ & \text{digit}\{\text{pos\_integer}\}\\ & \text{digit}\text{digit}\{\text{pos\_integer}\}\\ & \text{digit}\text{digit}\text{digit}\end{array}$$

Formal Proof of Validity of a Symbol according to a given EBNF Description/Rule

Build a step-by-step derivation table or a derivation tree. Example for the above EBNF description of an integer:

$$\begin{array}{rlrlr}& \text{integer}& & & \\ & [+|-]& \text{digit}& \{\text{digit}\}& \\ & [+]& \text{digit}& \{\text{digit}\}& \\ & +& \text{digit}& \{\text{digit}\}& \\ & & 1& \{\text{digit}\}& \\ & & & \text{digit}& \{\text{digit}\}\\ & & & 2& \{\text{digit}\}\\ & & & & \text{digit}\\ & & & & 8\end{array}$$

An EBNF description can also be depicted as a graph, and a symbol is valid if there exists a path from start to finish through that graph:

Equivalence of EBNF Descriptions

Two EBNF descriptions are equivalent if they recognize the same set of symbols as legal.