编译原理试卷2

北京工业大学2088-2089学年第一学期试卷考试课程：编译原理考试日期：年月日学院：专业：学号：姓名：成绩：题号一二三四总分成绩阅卷教师一、选择题（16分）1、描述高级语言词法的最简单模型是(D)。A、上下文无关文法B、图灵机C、下推自动机D、有穷状态自动机2、自顶向下的语法分析在于寻找输入串的(A)。A、推导（派生）B、归约C、回溯D、推导（派生）或者归约3、通常编译程序是把高级语言书写的源程序翻译为(D)程序。A、BASIC语言B、中间语言C、另一种高级语言D、等价的机器/汇编语言4、代码优化的目的是加快(B)的执行速度。A、编译程序B、目标程序C、源程序D、编译程序和目标程序5、符号表存取方法影响(A)的效率。A、编译程序B、目标程序C、解释程序D、编译程序和目标程序6、设有文法G[E]：EE+E|E*E|（E）|i。在下述文法类中，文法G[E]属于(A)、(B)和(D)。A、算符文法B、上下文无关文法C、正规文法D、二义文法二、简答题（18分）1、简要解释编译程序中的遍（趟）的含义。2、何为“标识符”？何为“名字”？两者的区别是什么？在程序设计语言中，标识符是一个最基本的概念，其定义为：凡以字母开头的字母数字序列(有限个字符)都是标识符。当给予某标识符以确切的含义时，这个标识符就叫做名字。程序语言中各种名字都是用标识符表示的，只是标识符是一个没有意义的字符序列，而名字却有着确切的意义和属性。3、简述为什么自顶向下的语法分析技术不能处理具有左递归的文法？这是由于在自顶向下的语法分析技术中，要解决的问题是根据当前输入符号判断将栈顶（最左）的非终结符号替换成哪条规则的右部，若文法具有左递归，则在分析过程中，无法判断出替换的规则，造成无穷递归求解的过程。三、文法设计（22分）1、已知语言L={anbm|m≥n≥0}对应的上下文无关文法为S→aSb|Sb|ε（1）试说明该文法是二义文法；（本小题4分）（2）试给出该语言一个等价的无二义性的上下文无关文法。（本小题6分）S->aSb|bS’|εS’->bS’|ε2、设计上下文无关文法G，使得abcdba∈L(G),且G中至少含有三个语法变量（非终结符）。（本小题12分）（1）给出设计的文法；（2）画出该句子的语法分析树；（3）写出该句子的最右推导中的任意一个句型，并指出该句型中的句柄。四、语法分析（44分）1、考虑文法G[S]：S→(T)|a+S|aT→T,S|S试消去该文法的左递归并提取左因子；（本题8分）2、写出下面文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法；（本题16分）S→aA|BAA→cB|B→bB|解：各候选式的FIRST集FIRST（aA）={a}FIRST（BA）={b，c，}FIRST（cB）={c}FIRST（）={}FIRST（bB）={b}FIRST（）={}各非终结符的FOLLOW集FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(B)={c，#}LL（1）分析表abc#SS→aAS→BAS→BAS→BAAA→cBA→BB→bBB→B→说明它是否为LL（1）文法(2分)判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。3、考虑文法G