BNF

  • BNF (Backus Naur Form) is a notation system for defining the syntax of programming languages.

Basic Form

  • < > = syntactic element
  • ::= = definition
  • | = or

Examples:

<num> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<alpha> ::= a | b | c | d | ... | x | y | z
<identifier> ::= <alpha> <identifier> <alpha> | <identifier> <num>
  • This means identifiers should start with an alphabet and then be followed by either numbers or alphabets.
  • Note that <identifier> is recursive.

BNF Tree Example (Korean Sentence)

Production rules:

<sent.> ::= <subj.> <pred.>               # Rule 1
<subj.> ::= <noun> <part.>                # Rule 2
<pred.> ::= <verb>                        # Rule 3
<noun> ::= 나 | 너 | 철수                  # Rule 4
<part.> ::= 은 | 는 | 이 | 가             # Rule 5
<verb> ::= 간다 | 공부한다 | 먹는다      # Rule 6

Tree expansion:

<sent.>
  -> <subj.> <pred.>                        (Rule 1)
  -> <noun> <part.> <pred.>                 (Rule 2)
  -> <noun> <part.> <verb>                  (Rule 3)
  -> 나 <part.> <verb>                      (Rule 4)
  -> 나는 <verb>                            (Rule 5)
  -> 나는 공부한다                          (Rule 6)

Extended Backus Naur Form (EBNF)

  • EBNF is an extended version of BNF with 4 additional meta-symbols:
  1. [ ] → can skip (optional)
  2. { } → repeat more than 0 times
  3. ( ) → grouping
  4. ::= → meta-symbol as non-terminal

Example:

<identifier> ::= <alpha> { <alpha> | <num> }
  • This means an identifier starts with an alphabet and can be followed by multiple alphabets or numbers.

Special Symbols:

  • ε = empty
  • {α} = repeat more than 0 times
  • Recursive definitions are allowed, e.g.:
A ::= {B}
A ::= ε | AB

Updated: