编译原理期末考试题目解析：存储空间划分与文法分析

在南航编译原理期末考试例题11中，涉及了多方面的概念，主要集中在编译理论的基础知识上。以下是各部分知识点的详细解析： 1. 编译程序结构与中间语言 - 编译程序通常包含词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等模块。其中，中间语言是编译过程中的一种抽象表示形式，常见的有后缀式（如操作数紧跟操作符的形式）、三地址代码（例如三元式、四元式和间接三元式）、以及DAG（有向无环图）等，这些语言有助于简化后续处理步骤。 2. 文法分析与FIRST/LAST集合 - 文法G中的非终结符集合及其FIRST和LAST集合用于描述符号在句子开始和结束位置可能出现的符号序列。例如，对于S、T和R，它们的第一步可能包括'a'、'b'和'/'，而最后可能只看到'a'和'c'，这是用于语法分析的重要工具。 3. 运行时存储空间划分 - 运行时存储空间通常分为几个关键区域：目标代码区，存放机器指令；静态数据区，存储程序初始化后的常量和全局变量；栈区，用于函数调用时的局部变量和返回地址；堆区，动态分配的内存，主要用于对象实例和函数的局部大对象。 4. 文法构造与语言生成 - 两组文法展示了如何构造语言，第一组要求m为奇数，n为偶数且n>0的字符串，第二组则涉及句型的最左推导和分解。理解文法构造规则并能绘制语法分析树是核心技能。 5. 短语、直接短语、句柄与素短语 - 在文法分析中，短语是指由文法规则生成的符号串；直接短语不包含其他短语作为子串；句柄是直接短语中最左的元素；素短语是最小的短语，不能进一步分解。例题中的"a-a"、"-aT"等都是这些概念的应用实例。 6. 正规式和有限状态自动机 - 提供了一个正规式表达式，要求转化为等价的最小确定有限状态自动机（DFA）。理解和转换正规式到自动机模型是理论计算机科学中的基础内容。 7. LL(1)文法转换 - 通过消除左递归（将左递归转换为右递归）和提取左公因子，使文法变得易于解析。LL(1)文法意味着在每一步的分析中，只有一个候选解析动作是明确的，这对于编译器实现高效解析至关重要。 8. FIRST/FOLLOW集合 - 非终结符的FIRST集合描述了该符号在文法的开始位置可能接收到的第一个符号，而Follow集合则指出了一个符号在某个位置之后可以跟的符号集。在LL(1)文法设计中，这两个集合的计算和分析是关键步骤。 这份试题涵盖了编译原理的多个重要知识点，旨在考察学生对词法分析、语法分析、文法转换、存储管理以及自动机理论的理解和应用能力。理解和掌握这些内容对于深入学习和实践编译技术至关重要。