电子科技大学《程序设计语言与编译》自测题答案.doc

程序设计语言与编译一一、 单项选择题（每题1分，共10分）1.一个程序单元可有（ D ）实例。A. 0个，B.1个， C.2个，D.多个2.编译程序是将（ C ）程序改造成目标语言程序的翻译程序。A. 机器语言，B.汇编语言，C.高级语言，D.低级语言3.规范规约每次都是对（ A ）进行规约。A. 句柄， B.短语， C.最左素短语，D.句型4LR分析法的核心部分是（ B ）。A. 总控程序，B.分析表，C.分析栈，D.可规约串5现今多数语言的描述工具是上下文无关文法，它对应于（ D ）。A. 图灵机，B.线性有界自动机，C.有限自动机，D.非确定的下推自动机6将一台实际的机器装上Pascal编译程序，它就成为Pascal( D )。A. 抽象机，B.识别机，C.翻译机，D.虚拟机7词法分析器的输入是（ A ）。A. 字符串，B.二元式，C.三元式，D.四元式8在一棵语法树中，子树叶结点的自左至右排列称为（ A ）。A 短语，B.句型，C.句柄，D.素短语9运行时进行的检查称为（ B ）。A 错误检查，B.动态检查，C.静态检查，D.随机检查10一个对象与其某种属性建立某种联系的过程，称为（ D ）。A 赋值，B.存储，C.定义，D.绑定二、 多项选择题（每小题2分，共10分）1类型转换的方法（ B E ）A. 动态转换，B.拓展，C.静态转换，D.收缩，E.显式转换2语句级控制结构有（ BCE ）A.递归，B.顺序，C.选择，D.过程调用，E.重复3Chomsky 将文法分成（ ACDE ）A 短语文法，B.LL(1)文法，C.上下文无关文法，D.上下文有关文法，E.正规文法4数据聚合的方式有（ ABDE ）A. 笛卡儿积，B.有限映像，C.指针，D.递归，E.判定或5强制性语言中，变量具有属性（ ABDE ）A. 作用域，B.生存期，C.强制性，D.值，E.类型三、 简答题（每小题5分，共20分）1、 分程序与复合语句的区别是什么？分程序中可说明局部于该程序的变量，复合语句是可执行语句的序列，其中没有说明语句2、 循环优化有哪几种方法？代码外提，强度削弱，删除归纳变量3、 怎样判断一个文法具有二义性？文法G如果产生的某个句子对应两棵不同的语法数，则有二义性4、 什么叫语法制导翻译？每个产生式配一个子程序，在语法分析的过程中，每当用一个产生式进行匹配或归约时，就调用相应的语义子程序四、 推导题（共15分）1、已知文法G(S):Sab(A)ASdAS1. 证明（bdS）是G（S）的句型；（5分）S=（A）= (SdA)=(bdA)=(bdS)所以是句型2. 画出（bdS）的推导树；（5分） S （ A ） S d A b S 3. 求句型（bdS）的短语，直接短语，素短语，句柄。（5分）短语b、S、bdS、（bdS）直接短语 b、S素短语 b句柄 b五、 算符优先分析法（共15分）设有文法G：PP(F)| PFabFda | a(1)求每个非终结符的FIRSTVT集和LASTVT集（8分）FIRSTVT(P)=a,cLASTVT(P)=a,) FIRSTVT(F)=aLASTVT(F)=a（2）试构造文法G的优先关系表（7分）优先关系表：六、 LR分析法（共20分）已知文法G（S）：ScAAAdBBBab1 构造G（S）的LR（0）项目集规范族；（8分）拓广文法：(0) SS (1) ScA (2) AAdB (3) AB(4) Ba(5)BbI0:SSI3:ScA AA.dBI7:AAbB ScAI4:AB BaI1:SSI5:Ba BbI2:ScA I8:AAdB AaI6:Bb AAdB B.a B.b2 构造SLR分析表；（8分）actiongotoabcd$SAB0S211acc2S5S6343S7R14R3R35R4R46R5R57S5S688R2R23 该文法是SLR（1）文法吗？理由是什么？（4分）是，不存在多重入口七、 语义分析题（10分）将下面语句翻译成四元式序列：WHILE a0 THEN y:=0 ELSE y:=y+1;(100)(j,-,-,109)(107)(:=,t1,-,y)(102) (j,a,0,104)(108) (j,-,-,100)(103)(j,-,-,106)(109)(104)(:=,0,-,y) (105)(j,-,-,100)程序设计语言与编译二一、选择题（每题1分，共10分）1编译时能进行的检查类型检查为（ C ）A. 错误检查，B.动态检查，C.静态检查，D.随机检查2一个程序单元可有（ D ）实例A. 0个，B.1个， C.2个，D.多个3把一个高级语言程序翻译成机器可执行的目标程序的工作由下列程序之一完成（ C ）A. 汇编程序，B.解释程序，C.编译程序，D.预处理程序4. LR分析法的核心部分是（ B ）。B. 总控程序，B.分析表，C.分析栈，D.可规约串5.词法分析时，单词的识别依据（ C ）实现A. 下推自动机，B.图灵机，C.状态转换图，D.抽象机6.句型是由（ D. ）推导出的符号串。A. 非终结符，B.终结符，C.任何符号，D.开始符号7.一棵语法树中，子树叶结点的自左至右排列称为（ A ）。B 短语，B.句型，C.句柄，D.素短语8.一个对象与其某种属性建立某种联系的过程，称为（ D. ）。B 赋值，B.存储，C.定义，D.绑定9（ A ）是指可访问该变量的程序范围。a) 变量的作用域，B.变量的生存期，C.变量的值，D.变量的类型10（ B. ）不属于单元级控制结构。A 过程调用，B.循环，C.异常处理，D.并发单元二、 填空题（每空1分，共25分）1 变量用名字来标识，此外还有4个属性：_作用域_、_生存期_、_值_、_类型_。2 程序语言的生成机制是_文法_,它的识别机制是_语法图_。3 类型聚合的方式有_笛卡儿集_、_有限映象_、_序列_、_递归_、_判定或_、_幂集_。4 传统语言三种语句级控制结构是_顺序_、_选择_、_重复_。5 按Chomsky观点，文法可分为_0型文法_、_1型文法_、_2型文法_、_3型文法_。6 静态存储分配时，不允许_递归调用_,不允许_动态数组_。8引用调用的参数传递方式，被调用程序单元对形参的引用，理解为对形参单元中实参地址的_间接访问_;在传值方式中，形参只起_局部变量_作用。9. 机器语言和汇编语言都是与机器无关的语言，统称_低级语言_，与机器无关的程序设计语言称为_高级语言_。三、 简答题（每小题5分，共20分）1 用户定义类型满足哪两个特性时，才能称为抽象数据类型？在允许实现这个新类型的程序单元中，建立与表示有关的具体操作对使用这个新类型的程序单元来说，新类型的表示是隐蔽的2 一个典型的编译程序有哪几部分？词法分析器、语法分析器、语义分析器、中间代码生成器、优化器、代码生成器3 循环优化有哪些措施？代码外提 强度削弱 删除归纳变量4 参数传递有哪几种方式？5种：传值 传地址 得结果 传值得结果四、 推导题（共10分）已知文法G(S):Sab(A)ABBSdBS1. 给出（b）da）的最左推导过程及相应的推导树；（5分） S=(A)=(B)=(SdB)=(A)dB)=(B)dB)= (S)dB) = (b)dB)= (b)dS) = (B)da)2. 求（b）da）的短语、直接短语和句柄。（5分） 短语：b,(b),(b)da,（b）da）,a直接短语：b ,a句柄：b五、 算符优先分析法（共10分）已知文法G（P）：PP（F）| FFabFdaa1 求每个非终结符的FIRSTVT集;(3分)FIRSTVT(P)=a,bFIRSTVT(F)=a2 求每个非终结符的LASTVT集;(3分)LASTVT(P)=a,) LASTVT(F)=a3 构造此文法的优先关系表；（4分） a b d ( ) a = （）六、LR分析法（共15分）已知文法G（S）：SAABBb4 构造G（S）的LR（0）项目集规范族；（分）（） （） （） （） （） ：5 构造SLR分析表；（分）6 该文法是SLR（1）文法吗？理由是什么？（分）不是，SLR分析表中存在多重入口i. 分析题（10分）将下面语句翻译成中间代码：I:=1;While I=N dobegin AI:=I+10; I:=I+1;end;（）（：，）（）（，）（）（，）（）（，）（）（，）（）（，）（）（：，）（）（，）（） 程序设计语言与编译三一、单项选择题（每小题1分，共10分）1. 词法分析器的输出是（ ）。 字符串 二元式 三元式 四元式2. 下述方法中，（ ）不是自下而上的分析方法。 规范归约 算符优先分析法 递归下降分析法 LR分析法3. =A, B, 0, 1上的正规式（A | B）（A | B | 0 | 1）*表示（ ）。 字符串 整数 数字串 标识符4. 句型是由（ ）推导出的符号串。 非终结符 终结符 任何符号 开始符号5. 项目Aaab称为（ ），其中aVT。 移进项 归约项 待约项 接受项6. LR分析法的核心部分是（ ）。 总控程序 分析表 分析栈 可归约串7. 把一个高级语言程序翻译成机器可执行的目标程序的工作由（ ）完成。 汇编器 解释器 编译器 预处理器8. 编译时能进行的类型检查称为（ ）。 错误检查 动态检查 静态检查 随机检查9. 若过程P调用过程Q，其参数传递方式是传名，同以（ ）来实现。 传地址 传值 调用过程P 参数子程序10. 在一棵语法树中，仅有两层的子树叶结点的自左至右排列称为（ ） 短语 直接短语 句柄 素短语二、多项选择题（每小题2分，共10分）1. 按Chomsky的观点，将文法分成（ ）等几类。 短语文法 算符优先文法 上下文有关文法 上下文无关文法2. 编译的各个阶段都要涉及表格管理，表格管理的工作有（ ）。 符号表的建立 生成四元式 报告错误 符号表的查找 符号表的更新3. 基本块的入口语句可能是（ ）。 程序的第一条语句 能由转移语句转移到的语句 紧跟在条件转移语句后面的语句 说明语句 循环语句4. 词法分析时，通常将单词分成（ ）等几类。 保留字 标识符 常数 算符 界符5. 设文法G有形如Aa | b的产生式，G为LL（1）文法的充要条件是（ ）。 FIRST(a)FIRST(b)=f FOLLOW(a)FOLLOW(b)=f ae,则FOLLOW(A)FIRST(b)=f be，则FOLLOW(A)FIRST(a)=f FIRST(a)FOLLOW(b)=f三、简答题（每小题5分，共25分）1. 给出=0, 1, 2, 3, 4, 5, 6, 7, 8, 9上正整数的正规式。(1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)*2. 下述四元式可进行哪种优化？写出优化后的四元式序列。 J:=5 A:=3 A:=8+C B:=A+C删除无用赋值： J:=5 A:=8+C B:=A+C3. 什么叫算符优先文法？如果文法G中不存在形如PRQ或Pe的产生式，且任何两个终结符之间至多存在、=、三种关系之一，则称G是算符优先文法。4. 数组的内情向量应包括哪些内容？包括各维上下界、维数、首地址、类型。5. 说明参数传递的方式在C语言和Pascal语言中的体现。C语言中仅有传值的参数传递方式，可通过传递指针实现传地址；四、推导题（共15分）已知文法G(S)： SSbF | F FFaP | P Pc1. 证明FaPbc是G(S)的一个句型；（5分）2. 画出FaPbc的语法树；（5分）3. 求FaPbc的短语、直接短语和句柄。（5分）1. SSbFSbPSbcFbcFaPbc FaPbc是G(S)的一个句型2. 语法树3. 短语:FaP,c,FaPbc 直接短语：FaP,c 句柄：FaP五、预测分析法（共15分）已知文法G(S)： SA | SiA AB | A+B BbS*|a1. 消除G(S)的左递归得G(S)；(4分)2. 求G(S)各非终结符的FIRST和FOLLOW集；(5分)3. 构造G(S)的预测分析表。(6分)1. G(S):SAS（4分） SiAS | e ABA A+BA | e BbS* | a2.（5分）FIRSTFOLLOWSb, a#, *Si, e#, *Ab, a#, *, iA+, e#, *, iBb, a#, *, i, +3.（6分）ai+b*#SSASSASSSiASSeSeAABAABAAAeA+BAAeAeBBaBbS*六、LR分析法（共15分）已知文法G(S)： SaAb Aa | bSA1. 构造G(S)的LR（0）项目集规范族；（9分）2. 构造SLR分析表。（6分）1. 构造LR（0）项目集规范族（9分）拓广文法：(0) SS (1) SaAb (2) Aa (3) AbS