# 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$;<br>$Y_1Y_2Y_3\dots$ | - Each grammar describes/generates/produces a [[language]]. - _Rule_ ($\rightarrow$) versus _derivation_ ($\Rightarrow$) - Top-down versus bottom-up derivation ## Ambiguity > [!tip] 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 [[dangling-else|the dangling else problem]] ## Categories - [[ll1|LL(1) Grammar]] - [[lr1|LR(1) Grammar]]