cfg

Context Free Grammar

Definition

Component	Definition	Notation
Terminal	aka. Token	$a$, $b$, $c$, …
Non-Terminal	A non-literal structure	$A$, $B$, $C$, …
Sentence	A valid sequence of terminals
Sentential Form	A valid sequence of (non-)terminals	$\alpha$, $\beta$, $\gamma$; $Y_1{Y}_2{Y}_3\dots$

• Each grammar describes/generates/produces a language.
• Rule ($\to$) versus derivation ($\Rightarrow$)
• Top-down versus bottom-up derivation

Ambiguity

Ambiguity comes from symmetry! Eliminate ambiguity by breaking

symmetry.

• Ambiguity = more than one way to parse a sentence
• In binary operator:
  • E -> E + T is left-associative
  • E -> T + E is right-associative
• See the dangling else problem

Categories

• LL(1) Grammar
• LR(1) Grammar