Entry
Compiler: Syntax: Parser: Extended Backus-Naur form: EBNF: What is EBNF?
May 24th, 2008 08:02
Knud van Eeden, Sammy Mitchell
----------------------------------------------------------------------
--- Knud van Eeden --- 23 October 2003 - 01:35 am --------------------
Compiler: Syntax: Parser: Extended Backus-Naur form: EBNF: What is
EBNF?
===
EBNF = 'E'xtended 'B'ackus-'N'aur 'F'orm
===
EBNF is a combination of Backus Naur Forms (=BNF) and regular
expressions.
===
To do so, Extended Backus Naur Form (EBNF) adds metasymbols to Backus
Naur Form (BNF).
===
This Extended Backus Naur Form, or EBNF, was first used by Niklaus
Wirth.
He used it to describe his computer language Algol-W, and later Pascal.
===
The used (meta) symbols are:
1. -Concatenation
Serial:
If there are two symbols in the pattern successive, the
corresponding characters in the text will also have to be
successive
1. -E.g.
abcDEF
1234_57ABC
2. -Terminals (like a digit, character, ...) are put in
1. -single quotes
''
or
2. -double quotes
""
3. -E.g.
'0'
'1'
'2
'3'
'A'
'B'
'C'
2. -Closure
Repetition:
A string of equal symbols with variable length or an optional
symbol.
1. -Closure: 0 or 1 occurrence of a symbol (or the symbol is thus
optional)
[]
which means 0 or 1 times, or thus an optional (if) structure
this can also be written as:
( ... )?
to remain more consistent with standard regular expression
notation.
1. -E.g.
[A]BC
2. -Closure: 0 or more occurrences of a symbol
{}
which means 0 or more times,
or thus a 'while-endwhile' structure
===
this can also be written as:
( ... )*
to remain more consistent with standard regular expression
notation.
1. -E.g.
{A}BC
is matched by BC
3. -Closure: 1 or more occurrences of a symbol
( ... )+
which means one or more times,
or thus a 'repeat-until' structure
Note: this was not part of the official EBNF, but was added
for e.g. compiler compiler convenience.
1. -E.g.
(A)+BC
is matched by e.g. AAAAAABC
3. -Alternation
Parallel:
One of the alternative symbols must occur in the text in which the
pattern is searched
1. -Alternation or
|
which means 'or', or thus a case structure
1. -E.g.
A|BC
is matched by AC and BC
E.g.
AB|C
4. -Grouping
()
the parentheses are used for grouping of symbols
1. -E.g.
(AB)|C
===
Example: EBNF:
Give the EBNF of a number
Number = Digit { Digit }
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Thus e.g.
12341245
is a number according to this description,
but
-12341245
should not be valid here (because of the '-' which is not part of the
EBNF that was chosen in this specific example here)
===
Example: EBNF:
Give the EBNF of an example sentence
Sentence = ("John" | "Vanessa") ("runs" | "stops").
Thus e.g.
John runs
John stops
Vanessa runs
Vanessa stops
is a sentence according to this description,
but
Bella runs
should not be valid here (because of the 'Bella' which is not part of
the
EBNF that was chosen)
===
So, the often-used +,* calculator example is:
===
in BNF:
exp = term | exp '+' term
term = factor | term '*' factor
factor = var | '(' exp ')'
===
in EBNF:
exp = term { '+' term }
term = factor { '*' factor }
factor = var | '(' exp ')'
---
As you can see, the major difference is that BNF uses recursion to
express the relationships, whereas EBNF uses iteration.
---
Any EBNF production can be translated into an equivalent set of BNF
productions.
---
In order to convert between BNF and EBNF, you can so in some cases (as
seen in the example below) just remove or insert the left hand term,
thus removing or inserting the recursive part.
===
For example:
===
in BNF
exp = term | exp '+' term
becomes in EBNF
exp = term { '+' term }
---
Niklaus Wirth claims that EBNF is more readable, and for the most this
is true, as iteration is much easier to comprehend by most humans, than
recursion.
---
So you can easily follow an EBNF grammar, but usually you might have
difficulties when dealing with BNF grammars for a while.
---
So it might be an idea to first write your language in EBNF, and
then if necessary convert this to BNF.
===
Book: see also:
---
[book: Wirth, Niklaus - algorithms + data structures = programs - p.
287 'Sentence analysis', p. 299-300 - 'A translator from BNF into
parser-driving data structures' - Constructing a syntax graph', p.
291 - 'Constructing a parser for a given syntax', p. 292 - 'Rules of
graph to program translation', p. 295 - 'Constructing a table driven
parsing program' - http://www.amazon.com/exec/obidos/tg/detail/-
/0130224189/qid=1066523226/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]
---
[book: Wirth, Niklaus - compiler construction - p. 8-19 -
http://www.amazon.com/exec/obidos/tg/detail/-
/0201403536/qid=1066525626/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]
---
[book: source: Tucker, Allen B. - computer science and engineering
handbook - p. 2144 - 'Defining terms' -
http://www.amazon.com/exec/obidos/tg/detail/-
/0849329094/qid=1066801548/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]
===
Internet: see also:
---
Extended Backus-Naur form
http://en.wikipedia.org/wiki/Extended_Backus-Naur_form
---
Backus-Naur form
http://en.wikipedia.org/wiki/Backus-Naur_form
---
BNF and EBNF: What are they and how do they work?
http://www.garshol.priv.no/download/text/bnf.html
---
How to create (ASCII text) diagram representation of regular
expression or Extended Backus Naur form? [Grammar / Parser / Syntax
diagram / Railroad diagram / BNF / EBNF]
http://www.knudvaneeden.com/tinyurl.php?urlKey=url000135
----------------------------------------------------------------------
