编译原理之自底向上分析学习笔记

系哈工大陈鄞慕课笔记。

“句柄”的另一个定义？

在“移入-归约”分析中，每次归约的符号串称为“句柄”。

又：句柄是句型的最左直接短语。

按：这个和句柄的最初的定义是一致且吻合的。

一个移入-归约分析的例子。

在移入-归约分析（可以参见上图）中，对 栈内符号串 + 剩余输入 = “规范句型” 的理解？

可以结合下面的定义来理解：

在形式语言中，最右推导常被称为规范推导。
由规范推导所得的句型称为右句型或规范句型。

按：本来这个移入-归约分析采用的就是最左归约方式（反向构造最右推导），所以，从例子的最后一行往上看，那么，显然它就是最右推导嘛，那么，结果就很显然了。

移入-归约分析器可采取的 4 中动作？

移入：将下一个输入符号移到栈的顶端
归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
接收：宣布语法分析过程成功完成
报错：发现一个语法错误，并调用错误恢复子例程

按：这个错误恢复子例程的规则应是由写程序的人来定。

移入-归约分析中存在的问题？

在归约的过程中，应该被归约的字符串的左端可能不会被正确识别到，即错误地识别了句柄。

$LR$ 分析的含义？

$LR$ 文法是最大的、可以构造出相应移入-归约语法分析器的文法类
- L：对输入进行从左到右的扫描
- R：反向构造出一个最右推导序列
按：这和前面那张移入-归约分析图的过程很像啊。
$LR(k)$ 分析
- 需要向前查看 k 个输入符号的 LR 分析
  按：这里的向前在输入符号串中表现为向右。

如何用“状态”表示句柄识别的进展程度？

\[ \begin{split} S &\rightarrow \cdot bBB \quad &移进状态\\ S &\rightarrow b \cdot BB \quad &待约状态\\ S &\rightarrow bB \cdot B \quad &待约状态 \\ S &\rightarrow bBB \cdot \quad &归约状态 \\ \end{split} \]

$LR$ 分析表的结构？

注意这里的 $sn$ 和 $rn$ 的含义：

$sn$：将符号 $a$、状态 $n$ 压入栈
$rn$：用第 $n$ 个产生式进行归约

一个 $LR$ 分析的例子？

文法：

\[ \begin{split} ① \; &S \rightarrow BB \\ ② \; &B \rightarrow aB \\ ③ \; &B \rightarrow b \end{split} \]

状态表

初始情况：

输入：$b \; a \; b$

\[ \begin{split} &栈 \qquad &剩余输入 \\ &0 \qquad &　\\ &\$ \qquad &bab\$ \end{split} \]

然后分析过程如下：

初始状态是 0，遇到输入的符号 b，其操作是 $s4$，即将 $b$、状态 $4$ 压入栈，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &04 \qquad &　\\ &\$b \qquad &ab\$ \end{split} \]

然后是状态 4 遇到输入 a，查表，得 $r3$，即用文法中的第 3 个式子进行归约，状态 4 和符号 $b$ 出栈，$B$ 入栈，然后此时状态栈的 0 遇到了刚入栈的 $B$，就会 "GOTO" 到状态 2，这个可以通过查表得到，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &02 \qquad &　\\ &\$B \qquad &ab\$ \end{split} \]

然后，状态 2 遇到 a，采取 $s3$ 操作，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &023 \qquad &　\\ &\$Ba \qquad &b\$ \end{split} \]

然后，3 遇到 b，$s4$，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &0234 \qquad &　\\ &\$Bab \qquad &\$ \end{split} \]

然后，4 遇到 $\$$，$r3$，将状态 4 和栈顶符号 $b$ 一起出栈，然后将刚刚的 $b$ 归约成 $B$ 并将其入栈，然后现在的状态栈栈顶的 3 遇到刚刚入栈的 B，就会 "GOTO" 到状态 6，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &0236 \qquad &　\\ &\$BaB \qquad &\$ \end{split} \]

然后，6 遇到 $\$$，$r2$，将状态 $3$、$6$ 和符号 $a$、$B$ 一起出栈，然后将归约成的 $B$ 入栈，然后现在状态栈栈顶的 2 遇到刚刚入栈的 $B$，会 "GOTO" 到状态 5，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &025 \qquad &　\\ &\$BB \qquad &\$ \end{split} \]

然后，5 遇到 $\$$，$r1$，

\[ \begin{split} &栈 \qquad &剩余输入 \\ &01 \qquad &　\\ &\$S \qquad &\$ \end{split} \]

然后，1 遇到 $\$$，到达状态 "acc"，分析成功，分析到此结束。

何为 $LR(0)$ 项目？

右部某位置标有圆点的产生式称为相应文法的一个 $LR(0)$ 项目（简称为项目）。

\[ A \rightarrow \alpha_{1} \cdot \alpha_{2} \]

何为增广文法？

如果 $G$ 是一个以 $S$ 为开始符号的文法，则 $G$ 的增广文法 $G^{'}$ 就是在 $G$ 中加上新开始符号 $S^{'}$ 和产生式 $S^{'} \rightarrow S$ 而得到的文法。

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

何为后继项目（Successive Item）？

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目；
$A \rightarrow \alpha \cdot X \beta$ 的后继项目是 $A \rightarrow \alpha X \cdot \beta$。

如何理解某些项目是等价的？

以上面的文法举例。

项目 (0) 和项目 (2) 是等价的，理由是：对于项目 (0)，我们在等待 $S$ 的时候，根据产生式②，就相当于我们在等待 $v$，所以 (0) 和 (2) 是等价的。

同理，其它的等价的项目归类如下：

\[ \begin{split} &(3) \; (7) \; (11) \\ &(5) \; (13) \end{split} \]

按：当圆点后面是非终结符时，就存在等价项目。

何为项目集闭包？

可以把等价的项目组成一个项目集($I$)，称为项目集闭包（Closure of Item Sets），每个项目集闭包对应着自动机的一个状态。

如何计算给定项目集 $I$ 的闭包？

\[ \text{CLOSURE}(I) = I \cup \{B \rightarrow \cdot \gamma | A \rightarrow \alpha \cdot B \beta \in \text{CLOSURE}(I), \; B \rightarrow \gamma \in P\} \]

根据这个公式计算即可。

按：可以从第一个项目依次往下计算，在计算的过程中，如果有已经被加入相应项目集闭包的项目，就跳过。

如何理解和计算 $\text{GOTO()}$ 函数？

此函数返回项目集 $I$ 对应于文法符号 $X$ 的后继项目集闭包

\[ \text{GOTO}(I, X) = \text{CLOSURE}(\{A \rightarrow \alpha X \cdot \beta | A \rightarrow \alpha \cdot X \beta \in I\}) \]

按：一个 $I$ 就相当于一个状态，然后，对于 $\text{GOTO}$，简单理解，就是状态 $I$ 接受了一个符号 $X$ 之后就“GOTO”到了另外一个状态。

如何构造 $LR(0)$ 自动机的状态机？

规范 $LR(0)$ 项集族（Canonical $LR(0) Collection$）

\[ C = \{I_0\} \cup \{I | \exists J \in C, X \in V_N \cup V_T, I = GOTO(J, X)\} \]

按：简单来讲，就是从初始项目集一步一步往下构造。

$LR(0)$ 分析表的构造算法？

$LR(0)$ 自动机的形式化定义？

$I_0$ 代表初始状态集合；
$F$ 代表终止状态集合。

何为移进/归约冲突？

简单来讲，就是某个状态遇到某一个输入符号时，不知道该进行移进动作还是归约动作。

按：这里的状态 2 在遇到 * 时，不知道是该将 $E \rightarrow T \cdot$ 归约成 $E$，还是针对 $T \rightarrow T \cdot * F$ 将 * 给移进。状态 9 也是同样的问题。但是，就状态 2 而言，如果采取归约动作的话，即，将 $T \cdot$ 归约成 $E$，那么，由于 $E$ 的 $FOLLOW$ 集中没有 $*$，显然，这是不合理的。