编译原理复习：选择填空与文法分析

"该资源包含了编译原理的复习例题，包括选择题、填空题，涉及了编译过程的各个阶段、文法类型、语法分析、代码优化、逆波兰表示、有穷自动机和正规式等多个核心概念。" 本文主要讨论了编译原理的相关知识点，以下是详细的解释： 1. **文法类型**： - 正规文法（也称为0型文法）是上下文无关文法的一种特例，它可以由正规式表示，例如题目中提到的正规文法与0型文法的关联。 2. **LL(1)文法**： - LL(1)文法是一种自左至右的最左推导，同时每次预测一步的分析方法。题目指出某些文法不是LL(1)的，如递归文法、右递归文法或含有公共左因子的文法。 3. **语法分析树**： - 语法分析树是表示程序结构的树形结构，对于文法E→E+E|E*E|i，不同解析可能产生不同的树形结构，题目中询问了总共有多少种不同的树。 4. **四元式**： - 四元式是编译器中间表示的一种形式，它们之间的联系通常通过临时变量来实现，以便进行计算和存储。 5. **同心集合并**： - 在LR分析中，同心集合并可能导致新的冲突，如移进/移进冲突、移进/归约冲突和归约/归约冲突。题目中提到了归约/归约冲突。 6. **代码优化**： - 代码优化基于等价变换规则，旨在提高程序的执行效率或减少代码大小。 7. **逆波兰表示**： - 逆波兰表示是一种无括号的数学表达式表示法，表达式a-(-b)*c的逆波兰表示为ab@c-*，其中@表示单目减运算符。 8. **DISPLAY表**： - 过程的DISPLAY表记录了过程的嵌套层次，用于处理递归调用时的局部变量管理。 9. **最左素短语与句柄**： - 句柄是推导过程中能被替换的最长非终结符串，而最左素短语是句柄且不含左公因子的部分。 10. **规范规约与最右推导**： - 最右推导的逆过程是规范规约，也称为规约过程。 11. **逆波兰式与属性文法**： - 属性文法中，文法符号的属性分为继承属性和综合属性。 12. **符号表**： - 符号表是编译器中存储标识符信息的数据结构，包含名字栏和定义栏，是目标代码生成的依据。 13. **有穷自动机与正规式**： - 题目要求构造最小的确定有限自动机（DFA）以接受特定的语言，并给出了一个正规式的等价转换问题。 14. **算符优先文法与LL(1)文法**： - 文法的算符优先关系表可以帮助判断是否为算符优先文法，而消除左递归和提取左公因子后，如果不存在第一类冲突，那么文法可能是LL(1)的。 以上内容涵盖了编译原理中的关键概念，包括文法类型、分析方法、优化技术、逆波兰表达式、属性文法以及有穷自动机与正规式等，这些是理解和设计编译器的基础。