(erweiterte) Backus-Naur-Form

• Noam Chomsky: Struktur natürlicher Sprachen (1956)
• John Backus, Peter Naur: Definition der Syntax von Algol (1958)

Backus-Naur-Form (BNF) $\approx$ kontextfreie Grammatik

<assignment> -> <variable> = <expression>
<number> -> <digit> <number> | <digit>

Erweiterte BNF

• Wiederholungen (Stern, Plus) <digit>^+
• Auslassungen

  if <expr> then <stmt> [ else <stmt> ]
  

kann in BNF übersetzt werden