语法分析

词汇

English	释义	拼音
context-free languages	上下文无关语言	shàng xià wén wú guān yǔ yán

表加栈

上下文无关语言 context-free languages 需要语法分析器；LL(1)：一个前瞻符号、一张（非终结符，终结符）→ 产生式的表、一个栈。FIRST/FOLLOW 集填表；冲突即拒绝该文法。

{exercise:uni-cs1105-ll1}

练习

LL(1) 表由——填充。

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

文法 $E \to T E'$、$E' \to {+} T E' \mid \varepsilon$、$T \to \mathbf{id}$；输入 id + id：栈 $E$；查 $(E, \mathbf{id})$；匹配；查 $(E', +)$；匹配 $+$ 与 $\mathbf{id}$；查 $(E', \$$) 取空；接受——八个栈快照。
最左推导恰是栈纪律：压产生式右部、匹配消费终结符——表的确定性来自 FIRST/FOLLOW 不相交。

{exercise:uni-cs1105-trace}

练习

FIRST/FOLLOW 冲突意味着——

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励

$E \to E + T \mid T$ 改写为 $E \to T E'$、$E' \to {+} T E' \mid \varepsilon$——循环变尾巴。机械，但把左结合性从树里换走：编译器建 AST 时要重新结合。
左递归文法让栈死循环；FIRST/FOLLOW 冲突意味着一个前瞻符号选不出来。

{exercise:uni-cs1105-recursion}

练习

左递归靠——消除。

难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励