课程资料编译原理复习题及答案.doc

### 编译原理知识点解析 #### 一、LL(1)文法的性质与证明 **知识点1：LL(1)文法与无二义性的关系** - **定义**: LL(1)是一种自顶向下、左到右扫描的文法分析方法。 - **证明**: 任何LL(1)文法都是无二义性的。 - **证明思路**: - 假设存在一个句子α，它可以有两种不同的最左推导。 - 在LL(1)分析的过程中，对于每一个推导步骤，都只能有一个明确的动作。 - 如果存在两个不同的推导路径，则意味着在某个分析步骤中存在两种不同的选择，这与LL(1)文法的性质相矛盾。 - 因此，任何LL(1)文法必然是无二义性的。 **知识点2：LL(1)文法的要求** - **要求**: - 对于文法G中的每个非终结符A，其所有候选式的FIRST集互不相交。 - 如果候选式中存在ε，则其他候选式的FIRST集与FOLLOW(A)互不相交。 #### 二、上下文无关文法的分析 **知识点3：句子的推导** - 给定文法生成句子`abbaa`的推导树。 - **最左推导**: \[ S \Rightarrow ABS \Rightarrow aBS \Rightarrow aSBBS \Rightarrow a\epsilon BBS \Rightarrow a\epsilon bBS \Rightarrow a\epsilon bbS \Rightarrow a\epsilon bbaA \Rightarrow a\epsilon bbaa \] - **最右推导**: \[ S \Rightarrow ABS \Rightarrow ABAa \Rightarrow ABaa \Rightarrow ASBBaa \Rightarrow ASBbaa \Rightarrow ASbbaa \Rightarrow A\epsilon bbaa \Rightarrow a\epsilon bbaa \] - **可能的产生式集合P**: - \(S \rightarrow ABS | Aa | \epsilon\) - \(A \rightarrow a\) - \(B \rightarrow SBB | b\) - **短语、直接短语、句柄**: - **短语**: \(a_1b_1b_2a_2a_3, a_1, b_1, b_2, b_1b_2, a_2a_3, a_2\) - **直接短语**: \(a_1, b_1, b_2, a_2\) - **句柄**: \(a_1\) #### 三、存储空间的分配策略 **知识点4：存储分配策略** - **静态分配**: - 适合于数组上下界固定、不支持递归调用、不允许动态建立数据实体的语言。 - **栈式分配**: - 适合于支持递归调用的程序设计语言。 - **堆式分配**: - 适合于运行时需要动态申请和释放存储空间的语言。 #### 四、循环优化技术 **知识点5：循环优化技术** - **不变运算外提**: 将循环体内的不变运算移动到循环外部。 - **运算强度削弱**: 降低循环内部的计算复杂度。 - **消除归纳变量**: 减少循环计数器的使用。 - **下标变量地址计算优化**: 改进数组访问效率。 #### 五、活动记录与优化 **知识点6：活动记录** - **活动记录**: 用于管理过程执行时所需信息的数据结构。 - **主要内容**: - **临时变量域** - **局部数据域** - **机器状态域** - **存取链** - **控制链** - **实参** - **返回值** #### 六、自动机构造 **知识点7：自动机构造** - **构造DFA和NFA**: - 接受以01结尾的所有串的DFA。 - 接受不包含01子串的所有串的DFA。 - 接受正规式x(x|y)*x的NFA。 - 接受正规式(ab|a)*b+的NFA，并将其转换为等价的DFA及最小状态DFA。 #### 七、LR(1)分析表构造 **知识点8：LR(1)分析表** - **给定文法**: - \(S \rightarrow Aa | dAb | Bb | dBa\) - \(A \rightarrow c\) - \(B \rightarrow c\) - **构造LR(1)分析表**: 需要通过计算项目集族、闭包、goto函数等来完成LR(1)分析表的构建。 #### 八、文法转换 **知识点9：文法转换** - **给定文法**: - \(S \rightarrow SaB | SbB | A | a\) - \(A \rightarrow S | a\) - \(B \rightarrow Ac\) - **求出FIRST集和FOLLOW集**: - 计算每个非终结符的FIRST集和FOLLOW集。 - **改写为LL(1)文法**: - 通过消除左递归、公共前缀因子化等手段将原文法转换为LL(1)文法。 #### 九、编译程序总体结构 **知识点10：编译程序总体结构** - **总体结构图**: 包括词法分析器、语法分析器、语义分析及中间代码产生器、优化器和目标代码生成器。 - **主要功能**: - **词法分析器**: 识别源程序中的单词符号。 - **语法分析器**: 判断输入串是否构成语法上正确的“程序”。 - **语义分析及中间代码产生器**: 按照语义规则对语法分析的结果进行进一步处理。