BNF (Backus-Naur Form)

• basic notation form

• 4 constants

  • meta-linguistic variables (non-terminals)
    • written between < >
  • language primitives (terminals)
    • no special limiters
    • e.g. any letter
  • ::= a.k.a is defined as
  • | a.k.a alternatives

• e.g.

  <construct> ::= expr 1 | expr 2 | … | expr n
  

Exercises

• Write a BNF form for non-empty strings of letters

  <letter> ::= a | b | … | z | A | B | .. | Z
  
  <letters_string> ::= <letter> <letters_string> | <letter>
  

  • use recursion for writing BNF forms

• Write a BNF form for (un)signed integers

  • 0 doesn’t have a sign
  • no. of at least 2 digits should not start with 0

  <integers> ::= 0 | <unsigned_int> | <signed_int>
  
  <sign> ::= + | - 
  <non_zero_digit> ::= 1 | ... | 9
  
  <unsigned_int> ::= <non_zero_digit> | <non_zero_digit> <non_zero_number>
  <non_zero_number> = ::= <non_zero_digit> | <non_zero_digit> <non_zero_number>
  
  <signed_int> ::= <sign> <unsigned_int>
  

EBNF (extended BNF)

Wirth’s dialect

• nonterminals loose < > (no delimiters)
• terminals are written between “”
• ::= → :=
• | → the same
• { } → repetition 0 or more
• [ ] → 0 or 1
• ( ) → grouping
• (* *) → comments
• rules end with .

Exercises