上下文无关语言与语法分析理论
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| derivation | 推导 | tuī dǎo |
| parse tree | 语法分析树 | yǔ fǎ fēn xī shù |
| ambiguity/ˌæmbɪˈɡjuːɪti/ | 歧义 | qí yì |
会嵌套的文法
- 上下文无关文法重写非终结符：$E \to E + T \mid T$、$T \to T \times F \mid F$、$F \to (E) \mid \mathbf{id}$。推导 derivation 逐步展开；语法分析树 parse tree 记录展开。
{exercise:uni-cs1102-cfg}
练习
分层文法下 id + id * id 有——棵分析树。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
分层强制优先级：× 挂 T 下、比 + 深。
歧义与优先级
- 分层文法下
id + id * id只有棵分析树：× 挂在 T 下、比 + 深。不分层的 $E \to E + E \mid E \times E \mid \mathbf{id}$ 给出两棵树——歧义 ambiguity 靠文法设计治愈。 id + id * id的最左推导六步，套件逐步核对。
{exercise:uni-cs1102-ambiguity}
练习
id + id * id 的最左推导用——步。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
E、E+T、T+T、id+T、id+TF、id+idF、id+id*id——六步。
下一层天花板
- $\{a^n b^n c^n\}$ 要两个独立计数：CFG 只泵得动一个，需要上下文有关机器——乔姆斯基层次的下一层，也是类型检查器住在语法分析之上的原因。
- 把推导次序（最左/最右）当成树形是经典陷阱：字符串本身必须选定那棵树。
{exercise:uni-cs1102-ceiling}
练习
语言 a^n b^n c^n 需要——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
两个独立计数：CFG 只泵得动一个。