福州大学2007-2008学年编译原理A卷考试试题

"福州大学2007～2008学年第一学期《编译原理》A卷考试试题，包含单项选择题和填空分析题，主要考察词法分析、正则表达式、无二义性文法、文法与句子的关系、有限自动机、规范归约、短语与句型、LR(0)分析法和同心集合并等相关概念。" 这篇资料主要涉及编译原理的基础知识，包括以下几个核心概念： 1. **词法分析器**：词法分析器（也称词法器或扫描器）的任务是将源代码分解成一系列的单词（token），其输出通常是单词的种类编码和自身值，选项C正确。 2. **正则表达式**：正则表达式等价指的是它们识别的语言集相同，即能够匹配的字符串集合一致，选项C正确。 3. **无二义性文法**：如果一个文法G是无二义的，那么对于任意句子α，其最左推导和最右推导对应的语法树必定相同，选项A正确。 4. **文法与句子**： - 句型：由文法的开始符号经0步或多步推导产生的文法符号序列，选项C正确。 - 句子：文法中的句型中不包含非终结符的子串。 5. **有限自动机**：一个确定的有限自动机通常只有一个初始状态（初态），但可以有多个终态，选项D错误。 6. **规范归约**：在规范归约过程中，句柄用来刻画可归约串，它是产生式的最左边的非终结符，对应于当前栈顶的最左素短语，选项B正确。 7. **文法规则与短语**：对于文法G，句型P+T+i的短语包括P、P+T、i，选项B正确。 8. **LR分析法**： - A→α·aβ项目表示当前读入符号为a，当前项目处于α之后，β之前，这对应于移进操作，选项B正确。 - “·”表示句柄的位置。 9. **LR(0) ACTION子表**：如果某一行存在标记为“ri”的栏，表示该行是归约操作，选项A错误，应该是归约操作。 10. **同心集合并**：同心集合并可能导致新的归约—归约冲突，因为不同归约路径可能在同一点产生冲突，选项D正确。 此外，还涉及到的概念有活前缀（在推导过程中某个中间串的前缀，且不含产生式右部的后继符号）以及LR(1)分析法中的“L”代表自左至右扫描输入。 这份试题全面地测试了学生对编译原理基本理论和方法的理解，涵盖了编译器设计的关键步骤，如词法分析、语法分析和语义分析等方面的知识。