编译原理重点解析：选择与填空题集锦

"编译原理精华" 这篇摘要涵盖了编译原理中的核心概念，包括编译器的不同阶段、文法类型、解析技术、自动机理论以及代码优化策略。以下是对这些知识点的详细说明： 1. **编译器阶段**：编译器通常分为词法分析、语法分析、语义分析和代码生成四个主要阶段。词法分析处理源代码中的字符流，将其分解成有意义的符号或 token；语法分析根据文法规则将 token 组合成抽象语法树；语义分析检查程序的逻辑正确性，并生成中间代码；代码生成阶段将中间代码转换为目标机器语言。 2. **文法类型**：文法按照 Chomsky 分类，可以分为 0 型、1 型（上下文有关文法）、2 型（上下文无关文法）和 3 型（正则文法）。题目中的第 2 题提到的型文法指的是 3 型文法，即正则文法。 3. **LL(1) 文法**：LL(1) 文法是一种左到右的解析策略，其中 L 表示从左到右扫描输入，L 也代表 Leftmost derivation，1 指使用一个输入符号的预测分析表。第 3 题提到的不是 LL(1) 的文法可能是因为它包含递归、右递归、2 型文法特征或公共左因子。 4. **语法树**：语法树是表示程序结构的树形表示，每个内部节点对应文法中的非终结符，叶子节点对应终结符。第 4 题中的文法 E→E+E|E*E|i 可以生成不同数量的语法树，具体取决于如何组合 E 和 E。 5. **自动机**：自动机理论在编译原理中用于识别语言。第 11 题中的自动机 M 能识别特定的字符串模式。例如，M 不能识别字符串 "bbaa"。 6. **语法分析方法**：第 12 题涉及不同的 LR 分析方法，如 LR(0)、LALR、SLR(1) 和 LR(1)，它们都是为了处理不同的归约决策问题。LR(1) 分析法在 LR(0) 的基础上加入了查看一个输入符号的信息来决定归约动作。 7. **语法制导翻译**：语法制导翻译是一种自顶向下的翻译方法，其中每个产生式都有一个相应的代码段。第 13 题展示了如何根据输入序列生成输出序列。 8. **代码优化**：第 14 题提到的局部优化是在基本块级别进行的，优化目标通常是减少计算次数或提高代码效率。第 15 题的削减运算强度是循环优化的一种形式，旨在减少重复计算。 9. **填空题**：词法分析阶段的任务是从左到右扫描源代码，识别出一个个的单词（tokens）；文法 G[E]：E→T|E+TT→F|T... 是一个简单的算术表达式文法，描述了如何构建表达式。 这些知识点构成了编译原理的基础，对于理解编译器的工作原理和设计至关重要。