哈工大 复习总结

### 哈工大计算机科学与技术学院复试总结知识点详解 #### 编译原理核心概念解析 ##### 1. 短语与直接短语 - **短语**：如果存在一个推导过程 \( S \Rightarrow^* \alpha A w \Rightarrow \alpha \beta w \)，则称 \(\beta\) 为相对于非终结符 \(A\) 的句型 \(\alpha \beta w\) 的短语。简单来说，短语是通过某个非终结符经过一系列推导得到的字符串。 - **直接短语**：如果存在一个推导步骤 \( S \Rightarrow^* \alpha A w \Rightarrow \alpha \beta w \)，并且 \(A \rightarrow \beta\) 是一个产生式，则称 \(\beta\) 为相对于非终结符 \(A\) 的句型 \(\alpha \beta w\) 的直接短语。直接短语是短语的一种特殊形式，它是由非终结符直接产生的字符串。 ##### 2. 源程序与目标程序 - **源程序**：指用特定编程语言编写的人可读的程序代码。 - **目标程序**：是编译器或解释器处理源程序后的输出，通常为机器语言或另一种编程语言的程序。 - **翻译程序**：将一种语言转换为另一种语言的程序。包括编译程序和解释程序。 - **解释程序**：逐行读取源代码并立即执行，不生成中间目标代码。 - **编译程序**：将源代码完全转换为目标代码后再执行。 ##### 3. 句柄与素短语 - **句柄**：最左直接短语被称为句柄，是语法分析过程中重要的概念。 - **素短语**：满足以下条件的短语被称为素短语：本身是一个短语，至少包含一个终结符，并且除了自身之外不再包含其他的素短语。 ##### 4. 语法树 - **定义**：对于一个上下文无关文法 \( G = (V_N, V_T, P, S) \)，如果一棵树满足以下条件，则这棵树称为文法 \( G \) 的语法树： - 树的每个节点都有一个标记，该标记属于 \( V_N \)。 - 根节点的标记是 \( S \)。 - 如果一个节点 \( n \) 至少有一个子孙节点，并且标记为 \( A \)，那么 \( A \in V_N \)。 - 如果节点 \( n \) 的标记为 \( A \)，其直接子孙节点从左到右的标记为 \( A_1, A_2, ..., A_k \)，那么 \( A \rightarrow A_1A_2...A_k \) 必须是产生式集合 \( P \) 中的一个产生式。 ##### 5. 编译程序 - **定义**：编译器是一种特殊的翻译程序，用于将源程序转换成目标程序。 ##### 6. 推导与规约 - **推导**：从文法的开始符号出发，按照文法的规则逐步推导出一个终结符串的过程。 - **规约**：推导的逆过程，即从终结符串出发，反向应用文法规则回到文法的开始符号。 ##### 7. 最左/最右推导 - **最左推导**：每次替换句型中最左边的非终结符。 - **最右推导**：每次替换句型中最右边的非终结符，也称为规范推导。 ##### 8. Chomsky 文法类型 - **0型文法**：无限制文法。 - **1型文法**：线性文法，允许产生式 \(\alpha \rightarrow \beta\)，满足 \(|\beta| \geq |\alpha|\)，除了 \(S \rightarrow \epsilon\)。 - **2型文法**：上下文无关文法，所有产生式的形式为 \(A \rightarrow \beta\)，其中 \(A \in V_N\)，\(\beta \in (V_N \cup V_T)^*\)。 - **3型文法**：正则文法，所有产生式的形式为 \(A \rightarrow aB\) 或 \(A \rightarrow a\)，其中 \(A, B \in V_N\)，\(a \in V_T\)。 ##### 9. 自动机 - **确定的有穷自动机 (DFA)**：由状态集 \(Q\)、输入字母表 \(\Sigma\)、转移函数 \(\delta\)、初始状态 \(q_0\) 和接受状态集合 \(Z\) 组成。 - **下推自动机 (PDA)**：由状态集 \(Q\)、输入字母表 \(\Sigma\)、下推字母表 \(\Gamma\)、转移函数 \(\delta\)、初始状态 \(q_0\)、栈底符号 \(Z_0\) 和接受状态集合 \(F\) 组成。 ##### 10. LL(1) 文法 - **定义**：上下文无关文法如果满足以下条件，则称为 LL(1) 文法： - 文法不含左递归。 - 文法中每个非终结符的各个产生式的首终结符集两两不相交。 - 对于含有 \(\epsilon\) 的非终结符，其首字符集与跟随符集不相交。 - **特点**：从左到右扫描输入串，采用最左推导，每次向前查看一个符号。 ##### 11. 算符文法 - **定义**：如果一个文法的任意产生式的右部都不含两个相邻的非终结符，则该文法是算符文法。 ##### 12. LR(k) 文法 - **定义**：根据栈中的符号串和向右顺序查看输入串中的 \(k\) 个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。 - **特点**：L 表示从左至右扫描输入符号串，R 表示构造一个最右推导的逆过程，K 表示为了作出分析决定而向前看的输入符号的个数。 ##### 13. 活前缀 - **定义**：在语法分析过程中，识别了句柄的一部分，这部分被识别的符号称为活前缀。 ##### 14. 语法制导翻译 - **定义**：在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序进行翻译的方法。 ##### 15. 翻译文法 - **定义**：翻译文法是一种特殊的属性文法，它包含一个上下文无关文法 \(G\)、一个属性的有限集 \(V\) 和一系列语义规则。这种文法主要用于指导翻译过程，实现源代码到目标代码的有效转换。 这些概念构成了编译原理中的基础知识体系，对于理解编译器的工作原理及其内部机制具有重要意义。掌握这些核心概念不仅有助于深入学习编译原理，还能为后续的软件开发和技术研究打下坚实的基础。