BNF and EBNF
BNF began as an abbreviation of Backus Normal Form and later became popularly known as the Backus-Naur Form. It is a formal notation that describes a language's syntax. BNF was developed primarily by John Backus and modified by Peter Naur to formalize the grammar of the Algol 60 programming language. It is now standard practice to use formal grammars to specify languages.A BNF grammar consists of a number of production rules. The rules are principally written as:
<S> ::= A1 | A2 | A3 ... ANwhere A1..AN are alternatives separated by the |. The symbol S on the left-hand side of ::= must be replaced by one of the alternatives on the right-hand side. Alternatives consist of terminals and non-terminals. A terminal is an atomic string that cannot be broken down. They terminate the production process. On the other hand, a non-terminal recursively refers to a rule. Here's a trivial example BNF grammar that specifies an integer number:
<integer> ::= <digit> | <integer> <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9In plain English, this example can be read as: "An integer is a single digit, or, an integer followed by a single digit. A digit is one of 0 or 1 or 2 or 3 ... 9." Symbols in angle brackets, <digit> and <integer>, are non-terminals while 0..9 are terminals.
Repetition is very common in grammars. With BNF, as in the example above, you have to use recursion to do repetition. This is rather awkward. Extended BNF (EBNF) adds several additional facilities to BNF to express repetition. There are quite a few EBNF dialects and even an ISO standard: ISO/IEC 14977. For simplicity and familiarity, below is an EBNF dialect that borrows the ubiquitous regular expression operators.
X* The Kleene star. X can appear zero or more times. X+ X can appear one or more times. X? Make X optional, X can appear zero or one time.To simplify the integer rule, it can be written in EBNF like so:
integer ::= digit+
digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' |
'8' | '9'
This example is read in English as: "An integer is comprised of one or more
digits." Notice that the angle brackets are removed from non-terminal symbols
and quotes are introduced to indicate terminal strings.
