编译原理考试复习

考完按：考完了，希望老师能给 60 分。最后一题考了代码优化的问题，什么划分代码块啦，什么找出循环啦，没复习到。就这样。

何为 $L(G)$？

文法 $G$ 所产生的语言定义为集合

\[ \{ x| S \mathop{\Rightarrow}\limits^* x, 其中 S 为文法识别符号，且 x \in V^*_T\} \]

可用 $L(G)$ 表示该集合。

何为最左推导、最右推导、规范推导、右句型、规范句型？

如果在推导的任何一步 $\alpha \Rightarrow \beta$，其中，$\alpha$、$\beta$ 是句型，都是对 $\alpha$ 中的最左非终结符进行替换，则称这种推导为最左推导。

如果在推导的任何一步 $\alpha \Rightarrow \beta$，其中，$\alpha$、$\beta$ 是句型，都是对 $\alpha$ 中的最右非终结符进行替换，则称这种推导为最右推导。

在形式语言中，最右推导常被称为规范推导。

由规范推导所得的句型称为右句型或规范句型。

何为短语、直接短语、和句柄？

令 $G$ 是一个文法，$S$ 是文法的开始符号，$\alpha \beta \delta$ 是文法 $G$ 的一个句型。如果有 $S \mathop{\Rightarrow}\limits^* \alpha A \delta$ 且 $A \mathop{\Rightarrow}\limits^+ \beta$，则称 $\beta$ 是句型 $\alpha \beta \delta$ 相对于非终结符 $A$ 的短语。

特别地，如果有 $A \Rightarrow \beta$，则称 $\beta$ 是句型 $\alpha \beta \delta$ 相对于规则 $A \rightarrow \beta$ 的直接短语（也称简单短语）。

一个右句型的直接短语称为该句型的句柄。句柄的概念只适用于右句型。

关于句柄的其他理解？

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

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

何为 3 型文法？

设 $G = (V_N, V_T, P, S)$，若 $P$ 中的每一个产生式的形式都是 $A \rightarrow aB$ 或 $A \rightarrow a$，其中 $A$ 和 $B$ 都是非终结符，$a \in V_T^*$，则 $G$ 是 3 型文法 或 正规文法。

如何消除文法的直接左递归？

将

\[ A \rightarrow A \alpha | \beta \; (\alpha \neq \varepsilon, \beta \;不以 A 开头) \]

转换成

\[ \begin{split} A \rightarrow \beta A^{'} \\ A^{'} \rightarrow \alpha A^{'} | \varepsilon \end{split} \]

如何消除文法的间接子递归？

消除左递归的算法？

何为上下文无关文法？

设 $G = (V_N, V_T, P, S)$。若 $P$ 中的每一个产生式 $\alpha \rightarrow \beta$ 满足：$\alpha$ 是一个非终结符，$\beta \in (V_N \cup V_T)^*$，则此文法称为 2 型的 或 上下文无关的（context-free）

上下文无关文法 即 CFG(Context-Free Grammer))。

对 $\text{FIRST}$ 的理解？

对 $\text{FOLLOW}$ 的理解？

如何理解 $\text{SELECT()}$？

给定上下文无关文法的产生式 $A \rightarrow \alpha$ $, $ $A \in V_N, \alpha \in V^*$，

若 $\alpha \stackrel{*}{\nRightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $\text{FIRST}(\alpha)$。
若 $\alpha \stackrel{*}{\Rightarrow} \varepsilon$，则 $\text{SELECT}(A \rightarrow \alpha)$ $=$ $(\text{FIRST}(\alpha) - \{\varepsilon\})$ $\cup$ $\text{FOLLOW}(A)$。

一个 $\text{SELECT}$ 的例子。

一张预测分析表。

按：这张图中上面的那张表中差了一个表达式：$T^{'} \rightarrow \varepsilon$。

何为 $LL(1)$ 文法？

一个上下文无关文法是 $\text{LL}(1)$ 的充分必要条件是,

对每个非终结符 $A$ 的两个不同产生式，$A \rightarrow \alpha$ $,$ $A \rightarrow \beta$，满足

\[ \text{SELECT}(A \rightarrow \alpha) \cap \text{SELECT}(A \rightarrow \beta) = \varnothing \]

其中 $\alpha、\beta$ 不同时能 $\stackrel{*}{\Rightarrow} \epsilon$。

$\text{LL}(1)$ 的含义是：第 1 个 $\text{L}$ 表明自顶向下分析是从左向右扫描输入串，第 2 个 $\text{L}$ 表明分析过程中将用最左推导，1 表明只需要向右看一个符号便可决定如何推导，即选择哪个产生式（规则）进行推导。

如何判别某文法是否是 $\text{LL}(1)$ 文法？

首先计算 $\text{FIRST}$、$\text{FOLLOW}$、$\text{SELECT}$ 集合，然后根据定义判别文法是否是 $\text{LL}(1)$ 文法。

在基本块范围内进行的优化？

局部优化指的是在一个基本块范围内进行的优化。常见的局部优化有：

常量传播
常量合并
删除公共子表达式
复写传播
删除无用代码
代数化简

循环优化的常见方法？

代码外提
归纳变量的删除

文法描述的语言是由文法开始符推导的终结符号串的集合。

何为可归前缀和活前缀？

设文法 $G[S]$，如果 $S \stackrel{*}{\Rightarrow} \alpha A \omega$ $\Rightarrow \alpha \beta \omega$ 是句型 $\alpha \beta \omega$ 的规范推导，则 $\alpha \beta$ 称为可归前缀，$\alpha \beta$ 的前缀称为活前缀。

活前缀就是可归前缀的前缀。

例如文法 $G[S]$，

\[ \begin{split} S &\rightarrow aAcBe \\ A &\rightarrow b \\ A &\rightarrow Ab \\ B &\rightarrow d \end{split} \]

句型 $aAbcde$ 的句柄为 $Ab$，活前缀有：$\varepsilon$、$a$、$aA$ 和 $aAb$，其中，$aAb$ 为可归前缀。