东北农业大学网络教育题库建设管理办法.docVIP

东北农业大学网络教育学院 编译原理网上作业题 第一章 编译概述 一、多项选择题： 1.编译程序各阶段的工作都涉及到（）。 A.语法分析 B.表格管理 C.出错处理D.语义分析E.词法分析 2.编译程序工作时，通常有（）阶段。? A.词法分析 B.语法分析 C.中间代码生成 D.语义检查 E.目标代码生成 1．解释程序和编译程序的区别在于。2．编译过程通常可分为5个阶段，分别是、、和生成。 3．编译程序工作过程中，第一段输入是，最后阶段的输出为程序。 4．编译程序是指将程序翻译成程序的程序。1.画出编译程序的总体结构图，简述各部分的主要功能。1.下面哪些说法是错误的（）。 A.有向图是一个状态转换图?B.状态转换图是一个有向图? C.有向图是一个DFA?D.DFA可以用状态转换图表示? 2.对无二义性文法来说，一棵语法树往往代表了（）。 A.多种推导过程?B.多种最左推导过程?C.一种最左推导过程D.仅一种推导过程?E.一种最左推导过程? 3.如果文法G存在一个句子，满足下列条件（）之一时，则称该文法是二义文法? A.该句子的最左推导与最右推导相同??B.该句子有两个不同的最左推导?? C.该句子有两棵不同的最右推导?D.该句子有两棵不同的语法树??E.该句子的语法树只有一个?4.有一文法G：S→AB 　　　　　　 A→aAb|ε 　　　　　　 B→cBd|ε 　它不产生下面（）集合? A.{anbmcsupndm|n,m≥0}??B.{anbncsupmdm|n,m0}?? C.{anbmcsupmdn|n,m≥0}??D.{anbncsupmdm|n,m≥0}?E.{anbncsupndm|n,n≥0}? 5.自下而上的语法分析中，应从（）开始分析。?? A.句型B.句子C.以单词为单位的程序D.文法的开始符E.句柄? 6.对正规文法描述的语言，以下（）有能力描述它。?? A.0型文法B.1型文法C.上下文无关文法D.右线性文法E.左线性文法? 1．文法 S→aS|bR|ε 　R→cS。描述的语言是(a|bc)* 2．在自下而上的语法分析中，语法树与分析树一定相同。　　　　　 3．二义文法不是上下文无关文法。　　　　 4．语法分析时必须先消除文法中的左递归。　　　　　　 5．规范归约和规范推导是互逆的两个过程。　　　　　　　　 6．一个文法所有句型的集合形成该文法所能接受的语言。　　　　．有穷自动机接受的语言是正则语言。．若r1和r2是Σ上的正规式，则r1|r2也是。．令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。简答题 句柄： 2．素短语： 3．语法树： 4．归约： 5．推导：问答题 1．给出上下文无关文法的定义。 2.文法G[S]： 　　　　　　　S→aSPQ|abQ 　　　　　　　QP→PQ 　　　　　　　bP→bb 　　　　　　　bQ→bc 　　　　　　　cQ→cc 　　　（1）它是Chomsky哪一型文法？ 　　　（2）它生成的语言是什么？ 3．按指定类型，给出语言的文法。 　　 　L={aibj|j＞i≥1}的上下文无关文法。 4．有文法G：S→aAcB|Bd 　　　　　　　　A→AaB|c 　　　　　　　　B→bScA|b 　　　（1）试求句型aAaBcbbdcc和aAcbBdcc的句柄； 　　　（2）写出句子acabcbbdcc的最左推导过程。 5．对于文法G[S]： 　　　　　S→（L）|aS|a L→L, S|S 　　　（1）画出句型（S,（a））的语法树。 　　　（2）写出上述句型的所有短语、直接短语、句柄和素短语。 S→(L)|a L→L，S|S ．考虑文法G[T]： 　　　　T→T*F|F 　　　　F→F↑P|P 　　　　P→（T）|i 　　　证明T*P↑（T*F）是该文法的一个句型，并指出直接短语和句柄。．试描述下列文法产生的语言L（G[S]） 　　　　S→10S0|aA 　　　　A→bA|a ．已知语言L(G)={abnc　|n≥1} 试对该语言构造相应文法。证明下列文法的二义性　　　　1．G[Z] 　　　　　　2．G[S] 　　　　　 Z→aZbZ|aZ|a　　　　S→AB 　　　　　　　　　　　　　　　 A→bB|bC|ba 　　　　　　　　　　　　　　　 B→Sb|ba|a 　　　　　　　　　　　　　　　 C→Bb|b有文法G[S]：S→iSeS|iS|i 　　 该文法是否是二义的。试证明之。文法G[T]：T→aR，R→Tb|d生成的语言是什么？G[T]是否为3型文法010(010 试构造生成语言的上下文无关文法。（﹡﹡﹡） (1) { anbnci | n≥1,i≥0 }