Context-Free Grammars

Definition

Derivations

• Leftmost: the leftmost nonterminal is always chosen for expansion at each step of derivation.
• Rightmost: the rightmost nonterminal is always chosen for expansion at each step of derivation.
• Unambiguous grammars have unique leftmost and rightmost derivations.

Parse Trees

• Shows a graphical depiction of a derivation.

Ambiguity

• Ambiguous grammars have more than parse tree for some input.

CFGs vs. REs

• CFGs can describe matched, nested structures in high-level programming languages.
• The language $a^n b^n$, n>0 can't be described by RE.
• Proof by contradiction that no DFA can accept $a^n b^n$, n>0.

Limitations to CFGs

Chomsky Hierarchy