BNF AND EBNF

Question 1

What is BNF

Answer 1

• It stands for Backus-Naur Form
• It is a formal, mathematical way to specify
  context-free grammars
• It is precise and unambiguous
• Before BNF, people specified
  programming languages ambiguously, i.e.,
  with English

Question 2

How did BNF come about?

Answer 2

• John Backus presented a new notation
  containing most of the elements of BNF at
  a UNESCO conference
• His presentation was about Algol 58
• Peter Naur read this report and found that
  he and Backus interpreted Algol differently
• He wanted even more precision
• So he created what we now know as BNF
  for Algol 60
• Thus BNF was first published in Algol 60
  Report

Question 3

What does BNF look like

Answer 3

• Like this:

<number> ::= <digit> | <number> <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
* “::=” means “is defined as” (some variants use
“:=” instead)
* “|” means “or”
* Angle brackets mean a nonterminal
* Symbols without angle brackets are terminals
</digit></digit></number></digit></number>

Question 4

Origin of EBNF

Answer 4

• Stands for “Extended Backus-Naur Form”
• After BNF appeared with Algol 60, lots of
  people added their own extensions
• Niklaus Wirth wanted to see one form, so
  he published “What Can We Do About the
  Unnecessary Diversity of Notation for
  Syntactic Definitions” in Communications
  of the ACM in 1977
• He suggested the use of “[ .. ]” for optional
  symbols (0 or 1 occurrences), “{ .. }” for 0
  or more occurrences.
• Did not mention “EBNF” or Kleene cross

Question 5

What is EBNF

Answer 5

• EBNF is a few simple extensions to BNF
  which make expressing grammars more
  convenient; adds “syntactic sugar”
• Thus it is more concise than BNF
• EBNF is widely used as the de facto
  standard to define programming languages

Question 6

What are the EBNF extensions

Answer 6

• They vary, but often are derived from
  regular expression syntax
• “
  *” (The Kleene Star): means 0 or more
  occurrences
• “
  +” (The Kleene Cross): means 1 or more
  occurrences
• “
  ?”: means 0 or 1 occurrences (sometimes
  “[ … ]” used instead)
• Use of parentheses for grouping