Parsing
Đã giới thiệu
Từ vựng
| English | Ý nghĩa |
|---|---|
| context-free languages | context-free 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}
Luyện tập
The LL(1) table is filled from —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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}
Luyện tập
A FIRST/FOLLOW conflict means —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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}
Luyện tập
Left recursion is removed by —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
The loop becomes a tail; associativity moves to the AST build.