程序设计语言与编译一一、单项选择题（每题1分，共10分）1.一个程序单元可有（ D ）实例。
A.0个，B.1个，C.2个，D.多个2.编译程序是将（ C ）程序改造成目标语言程序的翻译程序。
A.机器语言，B.汇编语言，C.高级语言，D.低级语言3.规范规约每次都是对（A ）进行规约。
A.句柄，B.短语，C.最左素短语，D.句型4．LR分析法的核心部分是（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.重复3．Chomsky 将文法分成（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):S→a∣b∣(A)A→SdA∣S1.证明（bdS）是G（S）的句型；（5分）S=>（A）=> (SdA)=>(bdA)=>(bdS)所以是句型2.画出（bdS）的推导树；（5分）S（ A ）S d Ab S3.求句型（bdS）的短语，直接短语，素短语，句柄。
（5分）短语b、S、bdS、（bdS）直接短语b、S素短语b句柄 b五、算符优先分析法（共15分）设有文法G：P→P(F)| PF→abFda | a(1)求每个非终结符的FIRSTVT集和LASTVT集（8分）FIRSTVT(P)={a,c} LASTVT(P)={a,)}FIRSTVT(F)={a} LASTVT(F)={a}（2）试构造文法G的优先关系表（7分）优先关系表：六、LR分析法（共20分）已知文法G（S）：S→cAA→AdB∣BB→a∣b1．构造G（S）的LR（0）项目集规范族；（8分）拓广文法：(0) S'→S(1) S→cA(2) A→AdB(3) A→B(4) B→a(5)B→bI0:S'→·S I3:S→cA·A→A.dB I7:A→Ab·B S→·cA I4:A→B·B→·aI1:S'→S·I5:B→a·B→·bI2:S→c·A I8:A→AdB·A→·a I6:B→b·A→·AdBB→.aB→.b3．该文法是SLR（1）文法吗？理由是什么？（4分）是，不存在多重入口七、语义分析题（10分）将下面语句翻译成四元式序列：WHILE a<b DOIF a>0 THEN y:=0ELSE y:=y+1;(100)(j<,a,b,102) (106)(+,y,’1’,t1)(101) (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):S→a∣b∣(A)A→BB→SdB∣S1.给出（（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）：P→P（F）| FF→abFda∣a1．求每个非终结符的FIRSTVT集;(3分)FIRSTVT(P)={a,b}FIRSTVT(F)={a}2．求每个非终结符的LASTVT集;(3分)LASTVT(P)={a,) }LASTVT(F)={a}3．构造此文法的优先关系表；（4分）a b d ( )a = > >＞ｂ＜＝ｄ＝（＜＝）＞六、LR分析法（共15分）已知文法G（S）：S→AＢA→ａB∣ａB→b4．构造G（S）的LR（0）项目集规范族；（５分）（０）Ｓ＇→Ｓ（１）Ｓ→ＡＢ（２）Ａ→ａＢ（３）Ａ→ａ（４）Ｂ→ｂＩ０：Ｓ＇→．ＳＳ→．ＡＢＡ→．ａＢＡ→．ａＩ１：Ｓ＇→Ｓ．Ｉ２：Ｓ＇→Ａ．ＢＢ→．ｂＩ３：Ａ→ａ．ＢＡ→．ａＢ→．ｂＩ４：Ｓ→ＡＢ．Ｉ５：Ｂ→ｂ．Ｉ６：Ａ→ａＢ．i.分析题（10分）将下面语句翻译成中间代码：I:=1;While I<=N dobeginA[I]:=I+10;I:=I+1;end;（１００）（：＝，１，，Ｉ）（１０４）（ｊ＜＝，Ｉ，Ｎ，１１２）（１０８）（ｊ，，，１３２）（１１２）（＋，Ｉ，１０，ｔ１）（１１６）（［］＝，ｔ１，，ａ０［Ｉ］）（１２０）（＋，Ｉ，Ｉ，ｔ２）（１２４）（：＝，ｔ２，，Ｉ）（１２８）（ｊ，，，１０４）（１３２）程序设计语言与编译三一、单项选择题（每小题1分，共10分）1. 词法分析器的输出是（②）。
①字符串②二元式③三元式④四元式2. 下述方法中，（③）不是自下而上的分析方法。
①规范归约②算符优先分析法③递归下降分析法④LR分析法3. Σ={A, B, 0, 1}上的正规式（A | B）（A | B | 0 | 1）*表示（④）。
①字符串②整数③数字串④标识符4. 句型是由（④）推导出的符号串。
①非终结符②终结符③任何符号④开始符号5. 项目A→α·aβ称为（①），其中a∈V T。
①移进项②归约项③待约项④接受项6. LR分析法的核心部分是（②）。
①总控程序②分析表③分析栈④可归约串7. 把一个高级语言程序翻译成机器可执行的目标程序的工作由（③）完成。
①汇编器②解释器③编译器④预处理器8. 编译时能进行的类型检查称为（③）。
①错误检查②动态检查③静态检查④随机检查9. 若过程P调用过程Q，其参数传递方式是传名，同以（④）来实现。
①传地址②传值③调用过程P ④参数子程序10. 在一棵语法树中，仅有两层的子树叶结点的自左至右排列称为（②）①短语②直接短语③句柄④素短语二、多项选择题（每小题2分，共10分）1. 按Chomsky的观点，将文法分成（①③④⑤）等几类。