编译原理复习重点：短语、句柄与文法类型解析

"编译原理习题" 在编程领域，编译原理是一门核心课程，它研究如何将高级语言转换为机器可理解的目标代码。这里我们将深入探讨几个关键概念。 1. 短语：在编译原理中，短语是一个重要的概念。如果文法G的开始符号S可以扩展为αAδ，而αβδ是一个句型，并且存在AB，那么β被称为αβ相对非终结符A的短语。简单来说，短语是文法中符合特定规则的子串。 2. 句柄：句柄是指在文法中，一个句型的最左简单短语，即最左边的、不能被进一步分解的短语。在句型xuy中，如果满足Z[pic]xUy和U[pic]u，那么u就是句柄，它是直接短语，不包含其他非终结符。 3. 上下文无关文法：上下文无关文法（Context-Free Grammar, CFG）是一种形式文法，用于描述语言的结构。在这些文法中，产生式的左侧是一个非终结符，右侧是零个或多个终结符与非终结符的序列。 4. LL(1)文法：LL(1)文法是一种特殊的上下文无关文法，允许从左到右扫描输入，采用最左推导，并且在每一步分析时最多向前看一个输入符号来决定解析动作。LL(1)文法不含有左递归，且所有产生式的First集合和Follow集合无交集，保证了解析的唯一性。 5. LR(1)文法：LR(1)文法是另一种上下文无关文法的类型，适用于自底向上的语法分析。它同样从左到右扫描输入，但使用一个看起来一步的预测信息（Lookahead symbol）来决定分析动作。LR(1)文法能够处理更广泛的语言，但构造解析表可能更复杂。 6. 语法分析：这是编译过程的一部分，它确定输入的符号序列是否符合文法，进而构建抽象语法树（AST）。 7. 无环路有向图（DAG）：在编译器设计中，DAG常用于表示优化后的中间代码，因为它们可以有效地表示数据依赖关系，且便于发现和利用重复计算。 8. 后缀式：后缀式或逆波兰表示法是一种运算符在操作数之后的表达式表示法，常用于实现表达式求值。 9. 语法制导翻译：这是一种基于语法规则的翻译方法，当遇到特定的产生式时，会执行相应的语义动作，帮助生成目标代码。 10. 遍：编译过程中的遍通常指的是对源代码或中间代码进行一次完整扫描，以完成特定的处理，如词法分析、语法分析或优化。 11. 局部优化：局部优化是在编译过程中针对代码的特定区域进行的等价变换，目的是提高目标代码的效率。 12. 词法分析：词法分析器（也叫分词器或扫描器）读取源代码，将其分解为一系列有意义的标记（tokens），供语法分析使用。 13. 语义分析：语义分析检查源代码的逻辑含义，确保其符合目标语言的语义规则，并生成中间表示或目标代码。 14. 源语言：源语言是程序员使用的高级编程语言，如C++、Java等。 15. 源程序：源程序是由源语言编写的、待编译的程序。 16. 目标语言：目标语言是机器可直接执行的语言，通常为机器码或汇编语言。 17. 中间语言（中间表示）：编译器可能在源代码和目标代码之间创建一种抽象表示，简化后续处理，如三地址码、四元式等。 简答题： 1) 编译程序与高级语言的区别：编译程序是一种软件工具，它将高级语言程序转化为机器语言，使得计算机能理解和执行。而高级语言是人易于理解的编程语言，提供了丰富的结构和抽象，使程序员能更高效地编写代码，而无需关注底层硬件细节。