Context Free Grammar

• $(V,\Sigma ,R,S)$
  • V is the set of variables, or nonterminals.
    • Typically in upper case
  • Σ is the set of terminal symbols.
    • Typically in lower case
  • R is the set of production rules.
    • X → Y1..Yn
    • X is non terminal
    • Y can be NT, T, epsilon
  • S is the start symbol.
  • Example:
    • S → (S)
    • S → epsilon
• S → aSa | bSb | a | b | ε
• N → ε

Palindrome	Derivation
abba	S ⇒ NT ⇒ aT ⇒ ab ⇒ abba
aba	S ⇒ NT ⇒ aT ⇒ ab ⇒ aba
b	S ⇒ NT ⇒ b ⇒ b
aa	S ⇒ NT ⇒ aa

• Derive
• Yields

Links

• First and Follows Sets
• Parsing