BNF

tags : Context Free Grammar (CFG)

What? §

• Backus-Naur-Form
• Format/Notation for Context Free Grammar (CFG)

Format §

• variables : Words in <..>. Eg. <statement>
• terminals: Multi-character strings, boldface/underline. Eg. while or WHILE. Eg ; in Programming Languages.
• ::= : Used in place of -> when defining production
• | : or. Shorthand for a list of productions with the same left side.
  • Eg. S -> 0S1 and S -> 01 can be written as S -> 0S1 | 01
• ... : “one or more”
• [] : Make things optional
• {} : Make a group of sequences

Alternative forms §

CNF (Chomsky Normal Form) §

See Chomsky Hierarchy