Diary Log 2

2026-04-22

日程

  • 学习编译原理知识（以备考试，无甚大用）：

① 分析过程的“死循环”和“回溯”问题

② 语法分析都是通过判断终结符号串 $\omega$ 是否属于一个句子。

③ “死循环”出现的原因：$P \rightarrow P\alpha$ 这种左递归。

“回溯”的成因是扩展非终结符时存在多个候选式。

④ “死循环”问题可以通过消除文法左递归来解决：

1) 消除文法左递归：

  • 直接左递归： **$P \rightarrow P\alpha\ \ \beta$** （其中 $P$ 不是 $\beta$ 的前缀）
  • 间接左递归： **$A \rightarrow N\beta\ \ \gamma$** ；$N \rightarrow A\alpha$

2)

i) 消除直接左递归： $P \rightarrow \beta P’$ ； **$P’ \rightarrow \alpha P’\ \ \epsilon$**
之所以等价，是由于 **$P \rightarrow P\alpha\ \ \beta$，必有 **$P \Rightarrow \beta\alpha\dots\alpha$ 形式（$\beta\alpha\dots\alpha$ 的形式），且第一个必为 $\beta$。改写为 $P \rightarrow \beta P’$，再 **$P’ \rightarrow \alpha P’\ \ \epsilon$**

ii) 消除间接左递归：

$N \rightarrow A\alpha$

**$A \rightarrow N\beta\ \ \gamma$**

（将 $A$ 代入 $N$） $\Rightarrow$

**$N \rightarrow \gamma\alpha\ \ N\beta\alpha$** （转化为直接左递归）
**$A \rightarrow N\beta\ \ \gamma$**

⑤ $\overline{r}$ 修剪，即为消除左递归的修剪，首先消去 $\epsilon$ 产生式，然后消去单位产生式，在执行我们上面提到的方法，即可消除左递归，结果文法中可能会有 $\epsilon$ 产生式！！！（输入文法不能包括单位产生式和 $\epsilon$ 产生式）

⑥ 如何消除回溯？

i) 当多个候选式有公共前缀：

\[N \rightarrow \text{if then}\] \[N \rightarrow \text{if then else}\]

提取：

\[N \rightarrow \text{if then } N'\] \[N' \rightarrow \text{else} \mid \varepsilon\]

ii) 候选式推导出的串有公共终结符前缀

iii) 含有 $\varepsilon$ 产生式时的选择问题

  • FIRST / FIRST 冲突： 任意两个候选式的首终结符集合不相交。
  • FIRST / FOLLOW 冲突： 如果某个非终结符 $A$ 的 FIRST 集合含 $\varepsilon$，那么：它的 FOLLOW 和候选式的 FIRST 也不能相交

如何计算 FOLLOW？（以符号 $X$ 为例）

① 起始符号必定有 #

② 看产生式右部，如果出现 $X$，例如 $A \rightarrow \alpha X \beta$ ：

  • 则 $\text{FOLLOW}(X)$ 中包含 $\text{FIRST}(\beta)$ 的所有元素（除 $\varepsilon$ 之外）。
  • 如果 $\beta$ 可以推导出 $\varepsilon$ ，那么 $\text{FOLLOW}(X)$ 中还要加入 $\text{FOLLOW}(A)$ 的内容（除 $\varepsilon$）。

  • 如果 $X$ 位于结尾，那么 $\text{FOLLOW}(X)$ 添加入 $\text{FOLLOW}(A)$ 的内容（除 $\varepsilon$）。

  • 简单看了十分钟 Rust 课程项目；
  • 将之前的五子棋 AI 的架构由 ResNet 转换为 Transformer，通过实践汲取知识

总结

惰性依然牵绊着我，但我依然度过了充实的一天，既有任务的完成（人永远无法每时每刻都做有趣的事，生活使我们必然要做一些相对来说无趣乃至无用的事，我想我们要学会适应这种无趣的生活），也有一些探索，关于 Transformer 在五子棋 AI 上的使用，半年前我便尝试过，效果并不好，此次我想通过 Debug 以及观察数据的变化，深入剖析原理，建立直觉。