Parsing
Introduit
Vocabulaire
| English | Sens |
|---|---|
| context-free languages | Languages generated by context-free grammars; these include all regular languages and some nonregular languages. |
English
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}
Pratique
The LL(1) table is filled from —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
FIRST chooses expansions; FOLLOW handles the empty production.
English
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}
Pratique
A FIRST/FOLLOW conflict means —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The grammar is not LL(1): table cell holds two productions.
English
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}
Pratique
Left recursion is removed by —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The loop becomes a tail; associativity moves to the AST build.