BNF and Context-Free Grammars

Context-Free Grammars

• Developed by Noam Chomsky, who classified four classes of generative devices or grammars that define four classes of languages
• Context-free grammars are one of the two classes (along with regular grammars) that are useful for describing the syntax of programming languages

Backus-Naur Form (BNF)

• Invented by John Backus to describe the syntax of ALGOL 58
• A natural notation for describing syntax, equivalent to context-free grammars

BNF Fundamentals

• A BNF grammar consists of:
  • A start symbol
  • A finite set of production rules
  • A finite set of terminal symbols
  • A finite set of nonterminal symbols

Production Rules

• A production rule has:
  • A left-hand side (LHS), which is a single nonterminal
  • A right-hand side (RHS), which is a string of terminals and/or nonterminals

Nonterminal Symbols

• Nonterminal symbols are abstractions used to represent classes of syntactic structures
• Also called simply nonterminals
• Nonterminals are often enclosed in angle brackets

Terminal Symbols

• Terminal symbols are lexemes or tokens

Derivation

• A derivation is the repeated application of rules, starting with the start symbol and ending with a sentence (a string of only terminal symbols)
• A sentential form is every string of (nonterminal or terminal) symbols in a derivation
• A sentence is a sentential form that has only terminal symbols
• Leftmost derivation: the leftmost nonterminal in each sentential form is the one that is expanded next

BNF Rules

• An abstraction (or nonterminal symbol) can have more than one RHS, chained using the | symbol

Describing Lists

• Syntactic lists are described using recursion
• Example: a list of identifiers can be described using a recursive rule, where the list can be either an identifier or an identifier followed by a comma and another list