编译考前复习题(第二次整理)_

编译考前复习题整理2012-4-14仲丛旭第1页共7页一、单项选择题1．词法分析的任务是（A）[参照P2页：词法分析：……从而识别出一个个单词]A、识别单词B、分析句子的含义C、识别句子D、生成目标代码2．语言是（A）[参照P36页倒数第五行黑体字]A、句子的集合B、产生的集合C、符号的串的集合D、句型的集合3．对应Chomsky四种文法的四种语言之间的关系是（B）[参照P39页：4个文法类的字义是逐渐……]A、0型文法⊂1型文法⊂2型文法⊂3型文法B、3型文法⊂2型文法⊂1型文法⊂0型文法C、3型文法＝2型文法⊂1型文法⊂0型文法D、0型文法⊂1型文法⊂2型文法＝3型文法4．一个句型中称为句柄的是该句型的最左（D）[参照P44面黑体字]A、非终结符号B、短语C、句子D、直接短语5．自顶向下的推导自动机识别的语言是（C）[参照P76页：定义5.1：上下文无关文法也称2型文法]A、0型语言B、1型语言C、2型语言D、3型语言6．常用的中间代码形式不含（D）[参照P177页：中间代码的形式：常见的有……树形（不是语法树）]A、三元式B、四元式C、逆波兰式D、语法树7．代码优化的目的是（C）[参照P249页：第一段第一行：所谓优化……]A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换8．所谓基本块，是指程序中一个顺序执行的语句序列，其中（D）[参照P251页：局部优化：所谓基本块……]A、只有一个入口语句B、只有一个出口语句C、只有一个入口语句或一个出口语句D、只有一个入口语句和一个出口语句二、填空题1．编译八大模块包括（词法分析程序）、（语法分析程序）、（语义分析程序）、（中间代码生成程序）、（代码优化程序）、（目标代码生成程序）、（表格管理程序）和（出错处理程序）。[参照P7页：图1.10]2．乔姆斯基把文法分成四种类型，即（0型文法）、（1型文法）、（2型文法）和（3型文法）。其中（2型文法）又称为上下文无关文法，（3型文法）又称为正规文法。[参照P38—P39页]3．描述上下文无关文法的句型推导的直观工具是（语法树）。[参照P40页黑体字]4．一个句型的最左直接短语称为该句型的（句柄）。[参照P44黑体字]5．常用的语法分析方法有（自底向上）和（自顶向下）两种。其中LL（1）属于（自顶向下）的语法分析，LR（0）是（自底向上）的语法分析。[参照P75页第二句]6．优先分析法可分为（简单优先分析法）和（算符优先分析法）。[参照P103页：自底向上优先分析概述]7．LR（0）项目集中把项目分为（移进项目）、（待约项目）、（归约项目）和（接受项目）四种。[参照P131页]8．常用的中间代码形式包括（逆波兰式）、（三元式）、（四元式）和（树形）表示。[参照P177页：中间代码的形式]9．符号表有哪些内容（符号名）、（符号的类型）、（符号的存储类别）、（符号的作用域及可视性）、（符号变量的存储分配信息）和（符号的其他属性）。[参照P205页：符号的主要属性及作用]10．符号表项的排列的组织方案有（线性组织）、（排序组织及二分法）和（散列组织）。[参照P213页：符号表项……]11．数据空间管理方法分为（静态存储分配）和（动态存储分配）。其中动态存储分配又分为（栈式动态存储分配）和（堆式动态存储分配）。[参照P231页：倒数第二行]12．参数传递包括（传值）和（传地址）。[参照P244页：参数传递]编译考前复习题整理2012-4-14仲丛旭第2页共7页三、判断题1．在编译程序六个阶段中，中间代码生成是必不可少的步骤。（×）[参照老师语录]2．LL（1）方法是自顶向下的分析方法。（√）[参照笔记]3．素短语和句柄没有任何关系。（√）[参照老师语录]4．简单优先文法中任意两个符号之间可以有多种优先关系成立。（×）[参照P105页：简单优先文法的定义]5．句子也是句型。（√）[参照老师语录]四、简答题1．句型、句子、语言之间的区别[参照笔记]句型：设S是文法G的开始符，项S*，∈（VN∪VT）则称为G的句型。[注：“*”号位于键号的上面]句子：仅含终极符的句型。即S+，∈VT*称为句子。[注：“+”号位于键号的上面]语言：全体句子的集合，构成语言。2．短语、直接短语、句柄、素短语、最左素短语。[参照笔记]短语：设μ是文法G[S]的一个句型，如果满足（1）S*A（2）A+μ则称μ为该句型的一个短语。[注：“*”、“+”号位于键号的上面]直接短语：以短语为前提，若满足（1）S*A（2）Aμ则称μ为该句型的一个直接短语。[注：“*”号位于键号的上面]句柄：最左边直接短语称为句柄。素短语：设有文法G[S]，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他素短语，最左边的素短语称最左素短语。[参照P115定义6.4]3．符号表的作用和地位？[参照P204页]地位：在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。作用：（1）收集符号属性（2）上下文语义的合法性检查的依据（3）作为目标代码生成阶段地址分配的依据4．简述什么是代码优化及代码优化结果有哪些。[参照P249页]所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储存储空间减少，或两者都有。六种优化结果：（1）删除多余运算（2）代码外提（3）强度削弱（4）变换循环控制条件（5）合并已知量与复写传播（6）删除无用赋值5．什么是编译程序？[参照笔记]编译程序：将高级语言源程序转换为低级目标程序，这个翻译程序叫编译程序。五、综合应用题[题型1：给语言构造文法][网上查的，有问题请指正]试分别构造产生下列语言的文法：（1）{abna|n=0，1，2，3……}（2）{aban|n≥1}编译考前复习题整理2012-4-14仲丛旭第3页共7页（3）{anbmcp|n，m，p≥0}解：（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P={S→aAaA→bA|ε}S=S（2）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，P={S→abA[或A→aA|a]}S=S（3）G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，P={S→ABCA→aA|εB→bB|εC→cC|ε}S=S[题型2：给文法给句子，求最左推导和最右推导，并画语法树][自己做的，有问题请指正]注：〖最右推导〗也叫〖规范推导〗已知文法G：SaSbS|aS|d，求句子aadbd的最左推导和最右推导解：aadbd的最左推导S=aSbS=aaSbS=aadbS=aadbdaadbd的最右推导S=aSbS=aSbd=aaSbd=aadbd语法树如图：语法树[题型3：已知语法树求短语、直接短语、句柄、素短语与最左素短语][参照P122页第4小题的第2小问]已知语法树如右图，求短语、句柄、素短语和最左素短语：短语：aT+Sa(T+S)Ha(T+S);H(S)dSSabSSad编译考前复习题整理2012-4-14仲丛旭第4页共7页a(T+S);H;(S)直接短语：aT+SH(S)句柄：a素短语：aT+S(S)最左素短语a[题型4：构造正规式的NFA和DFA][参照P68页：4.7典型例题及解答：第1题]构造正规式((a|b)*|aa)*b相应的DFA。步骤1：画出NFA图步骤2：构造状态表abT0=[X124][1234]T1[124Y]T2T1=[1234][1234]T1[124Y]T2T2=[124Y][1234]T1[124Y]T2步骤3：画出DFAT0T1T2ababab编译考前复习题整理2012-4-14仲丛旭第5页共7页[题型5：求LL（1）文法（1）。给文法求FIRST集和FOLLOW集。（2）。证明该文法是LL（1）文法（求SELECT集）。（3）。构造文法分析表][参照P100页第2题，自己做的，如有错误请指正]对下面的文法G[E]E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（2）证明这个文法是LL（1）文法。（3）构造它的LL（1）分析表。解：（1）FIRST集与FOLLOW集为：FIRST(E)={(,a,b,∧}FIRST(E’)={+}FIRST(T)={(,a,b,∧}FIRST(T’)={(,a,b,∧}FIRST(F)={(,a,b,∧}FIRST(F’)={*}FIRST(P)={(,a,b,∧}FOLLOE(E)={#,)}FOLLOE(E’)={#,)}FOLLOE(T)={#,+,)}FOLLOE(T’)={#,+,)}FOLLOE(F)={#,(,a,b,∧,+,)}FOLLOE(F’)={#,(,a,b,∧,+,)}FOLLOE(P)={#,*,(,a,b,∧,+,)}（2）证明文法是LL（1）文法。证明：对于规则E’→+E|ε，T’→T|ε，F’→*F’|ε（仅有一边能推出空串）各产生式的SELECT集合为如下：SELECT（E’→+E）=FIRST(E’)={+}SELECT（E’→ε）=FOLLOE(E’)={#,)}SELECT（T’→T）=FIRST(T’)={(,a,b,∧}SELECT（T’→ε）=FOLLOE(T’)={#,+,)}SELECT（F’→*F’）=FIRST(F’)={*}SELECT（F’→ε）={#,(,a,b,∧,+,)}则有：SELECT（E’→+E）∩SELECT（E’→ε）=øSELECT（T’→T）∩SELECT（T’→ε）=øSELECT（F’→*F’）∩SELECT（F’→ε）=ø所以该文法是LL（1）文法。（3）构造文法分析表编译考前复习题整理2012-4-14仲丛旭第6页共7页ab+*()∧#EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’T’T’→TT’→TT’→εT’→TT’→εT’→TT’→εFF→PF’F→PF’F→PF’F→PF’F’F’→εF’→εF’→εF’→*F’F’→εF’→εF’→εF’→εPP→aP→bP→(E)P→∧[题型6：构造算符优先关系表，并判断是否为算符优先文法。（OPG是算符优先文法）][参照P122页第4题（1）]试为下列各文法建立算符优先关系表E→EandT|TT→TorF|FF→notF|NN→(E)|true|false步骤1：求firstvt与lastvtFIRSTVT(E)={and,or,not,(,true,false}FIRSTVT(T)={or,not,(,true,false}FIRSTVT(F)={not,(,true,false}FIRSTVT(N)={(,true,false}LASTVT(E)={and,or,not,),true,false}LASTVT(T)={or,not,),true,false}LASTVT(F)={not,),true,false}LASTVT(N)={),true,false}步骤2：求三种关系：＜··＞=·（1）形如：aAandT则and＜·FIRSTVT(T)orF则or＜·FIRSTVT(F)notF则not＜·FIRSTVT(F)（E则(＜·FIRSTVT(E)（2）形如：AaEand则LASTVT(E)·＞andTor则LASTVT(T)·＞orE)则LASTVT(E)·＞)（3）形如：aAa(F)则(=·)步骤3：构造算符优先关系矩阵truefalsenotandor()#true·＞·＞·＞·＞false·＞·＞·＞·＞not＜·＜·＜··＞·＞＜··＞·＞and＜·＜·＜··＞＜·＜··＞·＞or＜·＜·＜··＞·＞＜··＞·＞(＜·＜·＜·＜·＜·＜·=·)·＞·＞·＞·＞#＜·＜·＜·＜·＜·＜·=