哈工大计算机科学复习笔记：编译原理重点解析

"哈工大计算机科学与技术学院2012年的研究生复试复习总结，涵盖了4门课程，包括编译原理。" 这篇复习总结主要聚焦于编译原理这一核心主题，编译原理是计算机科学中的重要分支，涉及将高级编程语言转换为机器可执行的指令的过程。以下是对编译原理相关知识点的详细解释： 1. **短语**：在编译原理中，短语是一个重要的概念，指的是在语法分析过程中，由非终结符扩展得到的、包含终结符的子句型。例如，如果S可以推导出αAw，而Aw可以推导出αβw，那么β就被认为是相对于A的、句型αβw的短语。 2. **源程序与目标程序**：源程序是程序员用高级语言编写的代码，而目标程序是经过编译后的、以二进制形式存在的、可被机器直接执行的程序。翻译程序，包括编译程序和解释程序，负责将源程序转换为目标程序。编译程序一次性将整个源程序翻译为目标代码，而解释程序则是逐行解释并执行。 3. **直接短语**：直接短语是短语的一种特例，当S可以推导出αAw， Aw可以推导出αβw，且A可以推导出β时，β被称为相对于A的直接短语。 4. **句柄**：句柄是指一个最左直接短语，它在语法分析中扮演关键角色，常用于确定最左推导和最右推导。 5. **素短语**：素短语是构成短语的基本单元，它必须包含至少一个终结符，并且自身不能再分解为其他素短语。 6. **最左素短语**（LPP）：最左素短语是最左的并且不能再分解为其他素短语的子串。 7. **语法树**：语法树是编译原理中表示程序结构的图形化工具，它反映了语法规则如何应用于源代码，每个节点代表一个非终结符或终结符，根节点对应起始符号S，树枝表示产生式的应用。 8. **编译程序**：编译器是实现编译过程的软件，它将源代码转换为目标代码，使得计算机能够理解和执行。 9. **规约**：规约是编译过程中的逆操作，即将语法树中的某一部分替换为产生式右侧的串，相当于逆向推导。 10. **推导**：推导是根据上下文无关文法的产生式，将非终结符替换为其产生式右侧的过程，用符号“=>”表示。 11. **最左推导**：最左推导是推导的一种策略，每次替换都是从当前句型中最左边的非终结符开始，确保了推导的可预测性。 12. **最右推导/规范推导**：最右推导与最左推导相反，每次替换都是从句型最右边的非终结符开始，这也是编译器常用的推导方式。 13. **Chomsky文法分类**：Chomsky提出了文法的四类划分，从1型文法到4型文法，分别对应不同的形式和限制，如1型文法（正规文法）不允许空字符串作为产生式右部，而4型文法（上下文相关文法）允许更复杂的结构。 这些知识点是学习编译原理的基础，理解和掌握它们对于理解编译器的工作原理以及编写和优化编译器至关重要。在哈工大的研究生考试中，这些概念可能是考察的重点，因此复习时需要深入理解并能灵活运用。