计算机编译原理期末考试试卷及评分标准

1、系别_ 专业_年级_姓名_学号 密封线 计科专业编译原理 课题 号一二三四五总 分总分人复核人分 数一、分数评卷人选择题：（每小题2分，共20分，请将答案写在下面的答题栏中，否则答案无效）123456789101. 一个文法所描述的语言是 ；描述一个语言的文法是 。A 唯一的；唯一的 B 唯一的；不唯一的C 不唯一的；不唯一的 D 不唯一的；唯一的2. 若文法 G 定义的语言是无限集，则文法必然是 。A 递归的 B上下文无关的C二义性的 D无二义性的3. 文法 G 产生的 的全体是该文法描述的语言。A 句型 B 终结符号集 C 非终结符号集 D 句子4 下面状态转换图接受的字集为 。 A.以0

2、开头的二进制数组成的集合 B.以0结尾的二进制数组成的集合C. 含奇数个0的二进制数组成的集合 D.含偶数个0的二进制数组成的集合5 在下述的编译方法中，简单优先分析 算符优先分析 递归下降分析 预测分析技术 LR(k)分析 SLR分析 LL(k)分析 LALR(k)分析自底向上的方法有 。A B C D 6自顶向下的分析方法有 。A B C D 7 Chomsky 定义的四种形式语言文法中，0 型文法又称为 文法；A 短语文法 B上下文无关文法 C上下文有关文法 D正规文法8 1 型文法又称为 文法；A 短语文法 B上下文无关文法 C上下文有关文法 D正规文法9 3型文法可以由 准确的识别A

3、图灵机 B下推自动机 C有限自动机 D以上皆不对10词法分析器的输出结果是 。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值二、分数评卷人简答题：（每题10分，共20分）1简述编译过程的五个阶段及各个阶段的任务。2简述自下而上语法分析方法基本思想及其中心问题是什么？三、分数评卷人推导计算题：（共60分）1(10分)给出下面语言的相应文法L(G)=anbnci| n1，i0。2(10分)构造正规式(a|b) * (aa|bb)(a|b)*的DFA （写出步骤）。3 (20分)对文法G(S)：S a | | (T)T T，S | S(1) 构造各非终结符的FIR

4、STVT和LASTVT集合；(2) 构造算符优先表，该文法是算符优先文法吗?(3) 给出输入串（a，（a，a）的算法分析过程?（注：答案格式为：步骤 栈 关系 输入符 剩余输入符 动作）4(20分)考虑文法 EaAbB AcAd BcBd (1) 列出这个文法的所有LR(0)项目。(2) 构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。(3) 这个文法是SLR文法吗？给出原因。第 5 页 共 页计科专业编译原理 课参考答案及评分标准一、选择题（每小题2分，共20分） 1-5 BADDC 6-10 AABCD 二、简答题（每题10分，共20分）1（1）词法分析，任务: 输入源程序，对构

5、成源程序的字符串进行扫描和分解，识别出一个个单词符号。（2）语法分析，任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。（3）中间代码生成，任务:对各类不同语法范畴按语言的语义进行初步翻译。（4）优化，任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。（5）目标代码生成，任务: 把中间代码变换成特定机器上的目标代码。评分标准：每条2分。2基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。（4分）中心问题：怎样判断栈顶符号串的可归约性，以及如何归约。即识别可归约串。（6分）三、推导计算题：（共60分）1. SAC （2分） AaAbab （4分） CcCb （4分）2XY(a|b)*(aa|bb)(a|b)*XYe514236abeeeababab3. (1) (5分) (2) (5分)a(),a(=,是算符优先文法，因为任何两个终结符之间至多只有一种优先关系