中科大编译原理期末考试：DFA设计与文法分析

"这是一份来自中国科学技术大学(USTC)大三上学期的编译原理期末考试试卷，包含了多项关于编译原理的核心知识点，如有限自动机(DFA)、文法分析(FIRST/FOLLOW集合，LR(1)文法)、语法优化(左因子提取，左递归删除)、递归下降解析、C语言数组理解和下标计算、函数调用的内存布局以及X86汇编代码编写和布尔表达式的短路计算。" 详细知识点解释： 1. **有限状态自动机(DFA)**：问题要求设计一个DFA来识别能被4整除的非空二进制串。这需要理解DFA的工作原理，以及如何根据整数的二进制表示来判断其是否能被4整除。DFA的状态通常与二进制串的位数对应，转移条件基于当前位和前一位的组合。 2. **文法分析**：题目中的文法G0是一个上下文无关文法，要求计算FIRST和FOLLOW集合，并构造LR(1)项目集簇。理解这些概念需要掌握文法规则，以及如何通过这些规则推导出文法的解析策略。LR(1)文法是一种自底向上的分析方法，要求没有移进-归约冲突和归约-归约冲突。 3. **语法优化**：对于文法G1，需要进行左因子提取和左递归删除，这是编译器优化的常见步骤，旨在简化文法结构，使其更适合分析。同时，要设计递归下降语法分析程序，这需要理解递归函数如何与文法结构对应。 4. **C语言数组理解**：题目要求根据C语言数组声明`int g[][2][2]={{0},{1},2,3,{4,5},{6},{7},8,{9}};`找出特定元素的下标。这涉及到理解多维数组的存储方式和下标计算规则。 5. **函数调用的内存布局与汇编代码**：给定的C/C++程序段展示了函数`punc`的活动记录内容安排，需要绘制并理解栈帧的构造。同时，需要填充汇编代码中的空白部分，这涉及到X86架构下的函数调用约定和内存操作。 6. **布尔表达式短路计算**：在`shiftdown`函数的三地址代码生成中，需要考虑布尔表达式的短路计算特性。三地址代码是一种中间代码表示，用于编译过程中的代码优化和生成。短路计算是指在逻辑运算中，如果能够提前确定结果，就不再计算后续部分。 以上就是试卷中涉及的主要知识点，涵盖了编译原理的多个核心概念，包括理论、分析、优化和实现等多个层面。