Parsing
도입됨
어휘
| English | 의미 |
|---|---|
| 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}
연습
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.