Parsing
Introduced
Vocabulary
| English | Meaning |
|---|---|
| context-free languages | Languages generated by context-free grammars; these include all regular languages and some nonregular languages. |
Table plus stack
- Context-free languages need a parser; LL(1) parsing: one symbol of lookahead, a table of (nonterminal, terminal) → production, a stack. FIRST/FOLLOW sets fill the table; conflicts reject the grammar.
{exercise:uni-cs1105-ll1}
Practice
The LL(1) table is filled from —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
FIRST chooses expansions; FOLLOW handles the empty production.
The trace, exactly
- Grammar $E \to T E'$, $E' \to {+} T E' \mid \varepsilon$, $T \to \mathbf{id}$; input
id + id: stack $E$; table $(E, \mathbf{id})$; match $\mathbf{id}$; table $(E', +)$; match $+$, match $\mathbf{id}$; table $(E', \$$) $\to \varepsilon$; accept — eight stack snapshots. - A leftmost derivation is exactly a stack discipline: push the production's right side, match consume terminals — the table's determinism comes from FIRST/FOLLOW disjointness.
{exercise:uni-cs1105-trace}
Practice
A FIRST/FOLLOW conflict means —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The grammar is not LL(1): table cell holds two productions.
Left recursion out
- $E \to E + T \mid T$ becomes $E \to T E'$, $E' \to {+} T E' \mid \varepsilon$ — the loop becomes a tail. Mechanical, but it trades left associativity in the tree: the compiler re-associates when building the AST.
- Parsing with a left-recursive grammar loops the stack forever; a FIRST/FOLLOW conflict means one symbol of lookahead cannot choose.
{exercise:uni-cs1105-recursion}
Practice
Left recursion is removed by —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The loop becomes a tail; associativity moves to the AST build.