Parsing
導入済み
語彙
| English | 意味 |
|---|---|
| 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}
実践
The LL(1) table is filled from —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
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}
実践
A FIRST/FOLLOW conflict means —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
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}
実践
Left recursion is removed by —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
The loop becomes a tail; associativity moves to the AST build.