编译原理期末考试重点：LR分析、二义性文法与DFA构造

"该资源是一份关于编译原理的期末考试习题及答案，涵盖了填空题、解析题等多种题型，旨在测试学生对编译器设计基础理论的理解和应用能力，包括文法类型、语法分析、属性文法、运行时存储管理、最右推导、语法树构建、二义性文法判断、正规文法与DFA构造等内容。" 1. **文法类型**：乔姆斯基定义的3型文法，也称为线性文法，其产生式形式为A → Ba | a 或 A → aB | a，其中A和B属于非终结符集Vn，a和b属于终结符集Vt。这种文法产生的语言是由单个终结符串构成或由一个非终结符后面跟着一个终结符串构成的语言。 2. **语法分析**：语法分析程序的输入是单词符号序列，输出是这些符号的语法结构，即语法单位，如句柄、短语、直接短语等。 3. **LR(0)分析**：在LR(0)分析中，形如B . aB的项目被称为移进项目，因为它指示解析器应该读取下一个输入符号a并移进；而形如Ba . B的项目被称为待约项目，因为它表明当前输入串可以被规约。 4. **属性文法**：在属性文法中，文法符号有两种属性——继承属性和综合属性。继承属性是从父节点传递到子节点的属性，而综合属性是在分析过程中计算得出的，通常基于子节点的属性值。 5. **运行时存储管理**：运行时存储管理包括静态存储分配（预先分配所有内存）、动态存储分配（在运行时根据需要分配内存）以及堆式存储分配（用于动态数据结构，如链表和树）。 6. **最右推导和语法树**：最右推导是自右向左地构造一个句子的过程，例如，对于文法G(S)，句型(T*F+i)的最右推导为E→T→F→(E)→(E+T)→(E+F)→(E+i)→(T+i)→(T*F+i)。对应的语法树可以帮助可视化这个推导过程。 7. **短语、直接短语和句柄**：短语是符合文法的子串，直接短语是文法中的基本构造块，句柄是能够通过左递归规则进行规约的非终结符的最长直接短语。 8. **二义文法**：如果一个文法可以生成的句子有多种不同的语法分析树，则称该文法为二义文法。例如，文法G(S)：S → SaS | ε，句子aaa可以生成两棵树，表明文法是二义的。 9. **正规文法与DFA构造**：给定正规文法G(S)，可以通过构造NFA然后确定化得到等价的DFA，用于识别特定的正规语言，如题目中给出的正规文法G(S)：S → Sa | Ab | b 和正规语言 b*a(bb*a)*b*。 10. **消除文法的左递归**：左递归可能导致无限循环，需要消除以确保文法的有效解析。通过替换规则，可以将左递归转化为右递归或直接递归，使得文法更易于分析。 11. **first和follow集合**：在LL(1)或LR(1)分析中，first集合包含一个非终结符可能开始的所有终结符，而follow集合包含在解析过程中一个非终结符可能接收到的所有后续终结符。 这份习题集全面覆盖了编译原理的关键概念，包括文法理论、解析技术、语言识别和存储管理，是学习和复习编译原理的重要参考资料。