编译原理习题答案

1、1、正规文法又称 DA、0 型文法 B、1 型文法 C、2 型文法 D、3 型文法2、对于无二义性的文法，规范归约是 BA.最左推导 B.最右推导的逆过程 C 最左归约的逆过程 D.最右归约的逆过程。3、扫描器的任务是从源程序中识别出一个个单词符号。4、程序所需的数据空间在程序运行前就可确定，称为 A 管理技术。A 静态存储 B 动态存储 C 栈式存储 D 堆式存储5、编译过程中，语法分析器的任务是(B)。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、日CD、6、文法 G:E-E+T|TT-T*P|PP 一(E)|i则句型 P+T+i 的句

2、柄和最左素短语分别为 B。A、P+T 和 iB、P 和 P+TC、i 和 P+T+iD、P 和 P7、四元式之间的联系是通过 B 实现的A.指示器 B.临时变量 C.符号表 D.程序变量8、程序语言的单词符号一般可以分为保留字、标识符、常数、运算符、界符9、下列 B 优化方法是针对循环优化进行的。A.删除多余运算 B.删除归纳变量 C.合并已知量 D.复写传播10、若文法 G 定义的语言是无限集，则文法必然是 AA、递归的日前后文无关的 C、二义性白 DD、无二义性的11、文法 G 产牛的 D 的全体是该文法描述的语言。A、句型 B、终结符集 C 非终结符集 D、句子12、Chomsky 定义

3、的四种形式语言文法中，0 型文法又称为 A 文法:1 型文法又称为 C 文法。A.短语文法 B.上下文无关文法 C.上下文有关文法 D.正规文法A.短语文法 B.上下文无关文法 C.上下文有关文法 D.正规文法13、语法分析最常用的两类方法是自顶向下和自底向,上分析法。14、一个确定的有穷自动机 DFA 是一个 A。A 五元组(K,汇，f,S,Z)B 四元组(VN,VT,P,S)C 四元组(K,汇,f,S)D 三元组(VN,VT,P)A、语法 B、语义 C、代码 D、运行15、B 不属于乔姆斯基观点分类的文法。A、上下文无关文法 B、算符优先文法 C、上下文有关文法 D、正规文法16、一个文法

4、所描述的语言是_A_；描述一个语言的文法是 B。A.唯一的 B.不唯一的 C.可能唯一，可能不唯一A.唯一的 B.不唯一的 C.可能唯一，可能不唯一17、语法分析是依据语言的语法=规则进行的,中间代码产生是依据语言的等价变换规则进行的。18、B 不属于乔姆斯基观点分类的文法。A 上下文无关文法 B 算符优先文法 C 上下文有关文法 D 正规文法19、过程调用时参数传递方式有 A(1)传地址(2)传值(3)传标识符(4)得结果(5)传名(6)返回值可选项有：A、(1)(2)(4)(5)B、(1)(2)(5)(6)C(2)(3)(6)D、(2)(3)(4)(6)20、过程调用时参数传递方式有(1)

5、传地址(2)传值(3)传标识符(4)得结果(5)传名(6)返回值可选项有：A、(1)(2)(4)(5)B、(1)(2)(5)(6)C(2)(3)(6)D、(2)(3)(4)(6)21、下列代码中 D 不可能是目标代码。A、汇编指令代码已可重定位指令代码 C、绝对指令代码 D、中间代码22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。母_。A.正确 B.不正确23、有限自动机能识别 CA.上下文无关文法 B.上下文有关文法C.正规文法 D.短语文法。_24、汇编程序是将 B 程序改造成目标语言程序的翻译程序。A 机器语言 B 汇编语言 C 高级语言 D 低级语言25、L

6、R(k 戌法B 二义性的。A、都是 B、都不是 C、不一定都是26、乔姆斯基方法的 2 型语言是这样一种语言，其产生式限制为 AA、A 一 B、A-a,AfaBC 一面|)D、一27、局部优化是局限于一个 C 范围内的一种优化。A.循环 B.函数 C 基本块 D.整个程序28、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。A。A.正确 B.不正确29、乔姆斯基方法的 3 型语言是这样一种语言，其产生式限制为 BAA-BAaAaBC 一用|)D 一30、运算符与运算对象类型不符属于 AQA、语法错误 B、语义错误 C、语用错误 D、规则集合31、词法分析器的输入是 B。A、词法记号 B

7、、源程序 C、语法单位 D、目标程序32、在下述的编译方法中，自底向上的方法有 F,自顶向下的分析方法有 A。简单优先分析算符优先分析递归下降分析预测分析技术LR(K)分析SLR(k)分析LL(k)分析LALR(K)分析A.B.CD.EF.A.B.CD.EF.33、对于数据空间的存贮分配，FORTRAN用动态贮存分配策略。B。A.正确 B.不正确34、算符优先分析法每次都是对 C 进行归约。A 句柄 B 短语 C 最左素短语 D 素短语35、编译时能进行的类型检查称为 CQA、错误检查 B、动态检查C 静态检查 D、随机检查36、规范推导的每一步总是用产生式右边符号串替换句型中 B_位置的非终

8、结符号A、最左 B、最右 C、最中 D、任意37、语法分析器的输入是单词符号流.其输出是分析树的某种表示38、每个文法都能改写为 LL(1)文法。BA.正确 B.不正确39、对于无二义性的文法，规范推导是 CA 最左推导 B 最右推导的逆过程 C 最左归约的逆过程 D 最右归约的逆过程。40、描述语言 L=ambn|nm1 的文法为 D。A、Z-AbbA-aA|aB-bB|bB、ZfAB|bA 一 Aa|aB-aBb|bCZ-AbA-aAb|aD、Z-aAbA-Ab|aAb|41、间接三元式表示法的优点为一 AA、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改C 便于优化处理，节

9、省存储空间 D、节省存储空间，不便于优化处理42、编译时能进行的类型检查称为 CA 错误检查 B 动态检查 C 静态检查 D 随机检查43、文法 GS:S-xSx|y 所识别的语言是 A。A、xnyxn(n0)B、(xyx)*C、xyxD、x*yx*44、项目 Aa,称为 B,其中 ACVN,A 不是开始符。A、移进项目已归约项目 C、出错项目 D、接受项目45、设有文法 GS:S-S*S|S+S|(S)|a,该文法 A 二义性文法。A、是 B、不是 C、不一定46、高级语言编译程序常用的语法分析方法中，LL 分析法属于_B 分析方法。A、自左至右 Ek 自顶向下 C 自底向上 D、自右至左。

10、47、有文法 G:E-E*T|TT-T+i|i 句子 2+5*3+3 按该文法 G 归约，其值为 BA23B42C30D1748、高级语言编译程序常用的语法分析方法中，LL 分析法属于_B 分析方法。A 自左至右 B 自顶向下 C 自底向上 D 自右至左。49、形如 A-a的甑目为 A 项目。A、待约 B、移进 C、接受 D、规约50、活动记录的连接数据不包括 AQA、形参单元 B、动态链(老 SP)C、返回地址 D、全局 Display 地址51、高级语言编译程序常用的语法分析方法中，IALR 分析法属于_C 分析方法。A、自左至右 B、自上而下 C、自下而上 D、自右至左52、设 a、b、

11、c 是文法的终结符，且满足优先关系 a=b 和 b=c,则 D。A.必有 a=cB.必有 c=aC 必有 b=aD 答案 AC 都不一定成立53、词法分析器的输出是二。A、词法记号流 B、源程序 C、语法单位 D、目标程序54、对一个基本块来说，A 基 M 确的。A、只有一个入口语句和一个出口语句 B、有一个入口语句和多个出口语句C 有多个入口语句和一个出口语句 D、有多个入口语句和多个出口语句55、词法分析所依据的是 B。A 语义规则 B 构词规则 C 语法规则 D 等价变换规则56、句型是由 D 推导出的符号串。A、非终结符 B、终结符 C、任何符号 D、开始符号57、如果文法 G 是无二

12、义的，则它的任何句子 aA。A、最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C 最左推导和最右推导必定相同D、可能存在两个不同的最左推导，但它们对应的语法树相同58、算符优先文法与算符优先函数的关系的描述中正确的是（B）。A、一个算符优先文法一定存在优先函数与之对应B、一个算符优先文法可能存在多个优先函数与之对应C 一个算符优先文法一定存在多个优先函数与之对应D、一个算符优先文法一定存在有限对优先函数与之对应59、一个句型中称为句柄的是该句型的最左 DQA 非终结符 B 短语 C 句子 D 直接短语60、描述一个语言的文法是（B）A、唯一的 B、不唯一的 C、

13、可能唯一，也可能不唯一61、下列 C 优化方法不是针对循环优化进行的。A、强度削弱 B、删除归纳变量 C、删除多余运算 D、代码外提62、更动一张 A 表很困难。A 三兀式 B 间接三兀式 C 四兀式 D 三兀式和四兀式63、栈式存储分配申请和释放存储空间遵守 BC 原则。A、先申请先释放 B、先申请后释放 C、后申请先释放 D、任意64、所谓自上而下分析法是指=。65、所谓语法制导翻译方法是。66、确定的有穷自动机是一个五元组，通常表示为 M=（S,2,f,s0,Z）。67、规范归约中的可归约串是指包翅;算符优先分析中的可归约串是指疆羞羞赞。68、编译程序在逻辑上由词法分析、哧绘擀、语义分析

14、、中间代69、D 不可能是目标程序。A、汇编语言模块 B、可重定位目标模块 C、可执行目标模块 D、中间代码70、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义W。71、一个名字的属性包括继承属性和综合属性。72、正规式的“*读作星闭包。73、编译程序在逻辑上由、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。74、编译程序的各个阶段的工作都涉及到符号表管理和错误处理75、文法用来描述语言的语法结构，它由如下 4 个部分组成：文法终结符集合、文法非终结符集合、D 和文法开始符号。A 单词集合日字母数字串C 文法句子集合 D、文法产生式的集合76、确定的有穷自动机是一

15、个元组，通常表示为。77、已知文法GE:E-E+T|TTT*F|FFf（E）|id该文法终结符集合Vk,文法非终 25 符集合VN=，该文法在乔姆斯基（Chomsky）文法分类属于2文法。78、编译程序的各个阶段的工作都涉及到和。79、假设 G 是一个文法，S 是文法开始符号，如果 S*x,则称 x 是该文法的一。80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。81、优化时，节省一条指令 MOVR,M,节省的指令代价为 CA、0B、1C、2D、382、采用 31_语法分析时，必须消除文法的左递归。83、在状态转换图中，结点代表状态,用圆圈表示。84、若源程序是高级语言编写的

16、，目标程序是机器语言或汇编一语言的程序，则相应的翻译程序称为编译程序。85、常用的两种动态存贮分配办法是栈式分配和堆式分配。86、翻译方案和语法制导定义不同的是它的语义动作（而不叫语义规则）放在括号内，并且可以插在产生式右部的任何地方87、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。88、所谓最左推导是指：。89、上下文无关文法的可以用四元组表示,其形式为 G=(V,VT,S,P)。90、后缀式 ab+c+d*e-所表达的式子为(a+b+c)*d-e。91、常用的两种动态存贮分配办法是分配和分配。92、LL(K良法中，第一个L表示从左到右扫描输入串，第二个L表示产生最左推导,

17、K表示在决定语法分析器每步动作时向前看K个输入。93、一个上下文无关文法所含四个组成部分是文法终结符集合文法非终结符集合开始符号产生式有限集合。94、对于文法 G,仅含终结符号的句型称为句子。95、设有文法GE:E-E+T|ET|FT-T*F|T/F|FF-(E)|i该文法句型E+T*F的句柄是T*F。96、后缀式 ab+c+d*e-所表达的式子为。97、文法符号的属性有两种，一种称为继承属性，另一种称为综合属性，S属性定义是指仅使用综合属性的语法制导定义。98、LR(0 预目和 LR(1 预目的区别在于是否有搜索符。99、紧跟在条件转移语句后面的语句是基本块的入口语句。100、若二个正规式所

18、表示的 DFA(或止.视集)相同，则认为二者是等价的。101、仅含终结符的句型称为。102、编译方式与解析程序的根本区别在于是否生成目标代码。(F)103、规范归约和规范推导是互逆的两个过程。(T)104、一个上下文无关文法的开始符号可以是终结符或非终结符。(F)105、逆波兰表示法表示表达式时无需使用括号。(T)106、符号表由词法分析程序建立，由语法分析程序使用。（F）107 逆波兰法表布的表达式亦称前缀式。（F）108、代码生成器的输入包括中间代码和符号表中的信息。（T）109、孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。（T）110、目标代码生成时，应考虑如何充分利用计算机

19、的寄存器的问题。（T）111无左递归的文法是LL（1）文法。（F）112 一个句型的直接短语语是唯一的。（F）113、正规文法产生的语言都可以用上下文无关文法来描述。（F）114、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。（F）115、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（F）116、一个上下文无关文法的开始符号可以是终结符或非终结符。（F）117、一个文法所有句子的集合构成该文法定义的语言。（T）118、优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。（T）119、算符优先分析法是一种规范归约分析法。（F）120、非终结符可

20、以有综合属性，但不能有继承属性。（F）121、所有 LR 分析器的总控程序都是一样的，只是分析表各有不同。（T）122、因名字都是用标识符表示的，故名字与标识符没有区别（F）123、空符号串的集合=（F）124、非终结符可以有综合属性，但不能有继承属性。（F）125、终结符可以有综合属性，也可以有继承属性。（F）126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。（F）129、DAG 是一个可带环路的有向图。（F）130、设有符号串x和y,把y的符号写在x的符号之后所得的符号串，叫做x与y的连

21、接，记为xy。（T）131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。（F）132、对任何正规表达式 e,都存在一个 DFAM,满足 L（M）=L（e）。（T）133、运行时的DISPLAY6的内容是什么它的作用是什么答：内容：1、过程 R 的现行活动记录的地址(sp 的现值)2、R 的外层 Q 的最新活动记录的地址 3、Q 的外层即主程序 P 的活动记录的地址作用：跟踪每个外层的最新活动记录的位置134、何谓局部优化、循环优化和全局优化优化工作在编译的哪个阶段进行答：局部优化：在基本快内的优化。循环优化：对循环中的代码进行优化。全局优化：整个程序范围内的优化。在中间代码优化阶段

22、。135、常见的存储分配策略有几种它们都适合于什么性质的语言答：1、静态分配策略适用于无动态申请内存、无可变体积数组、无递归调用的程序语言(如 Fortran)2、动态分配策略栈式动态分配 2.1.1 简单栈式分配适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允许过程含可变数组的语言嵌套过程语言的栈式分配适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言堆式动态分配适用于允许程序为变量在运行时动态申请和释放存储空间的语言136、下面文法是否是二义文法试说明理由。GS:SSaS答：二义137、已知文法 G(E)EfT|E+TT-F|T*FF-(E)|i(

23、1)给出句型(T*F+i)的最右推导及画出语法树；(2)给出句型(T*F+i)的短语、素短语。1)E-E+T-E+-T+i-T*F+I 树略2)短语：T*F+iT*Fi素短语：T*Fi138、把算术表达式(a+b)*(b+c)翻译成：(a)后缀表示ab+bc+*(b)语法树图略(c)有向无环图图略(d)四元式三地址代码四地址代码：(+,a,b,t1)(+,b,c,t2)(*,t1,t2,t3)(,t3,-,t4)139、DFA 与 NFA 的区另 1J答：1、DFA 弧上不允许有出现，NFA 允许2、DFA 中每个状态 S 和输入符号 a 最多有一条边离开 S,NFA 有多条3、NFA 可以有

24、多个初态，DFA 只有一个140、设已构造出文法 G(S):SS(S)S的 LR 分析表如下状态ACTIONGOTO()#S0r2r211S2Acc2r2r233S4S54r2r265r1r16S4S77r1r1假定输入串为()()，请给出 LR 分析过程(即状态，符号，输入串的变化过程)。步骤状态符号输入串步骤状态符号输入串10()()$201S()()$3012S()()$40123S()()$501235S()()$601S()$7012S()$80123S(S)$901235S(S)$1001S$141、对符号表的基本操作有几种，分别是什么答：5 类。1、填写名称 2、查找名字 3、访

25、问信息 4、填写修改信息 5、删除(或者：4 类。建立、插入、查找、删除)142、给定代码段如下，求出按四种不同方式进行参数传递后，变量 a 的值procedureP(w,x,y,z);beginy:=y*w;z:=z+x;endbegina:=5;b:=3;P(a+b,a-b,a,a);write(a);end传值：5传地址：42得结果：7传名：77143、目标代码有哪几种形式生成目标代码时通常应考虑哪几个问题答：1、汇编语言 2、机器语言又可分为 a 可立即执行的机器语言 b 可重定位的机器语言需要考虑：1.、如何使生成的目标代码最短 2、如何分配寄存器的使用144、下面的推导 Srmrm

26、AbWrmlbW 中，最后一步用的是 Al,分别指出 LL(1)方法和 LR(1)方法在扫描到此句型的什么位置决定用此产生式(5 分)P79答：LL(1)扫描到l的时候决定用此产生式；LR(1)a描到b的时候决定使用次产生式145、构造一个最简DFA,它接受正规式ab(a|b)*。给出文法GS:SSaA|AAfAbB|BBfcSd|e(1)证实 AacAbcBaAdbed 是文法 GS的一个句型；(2)请写出该句型的所有短语、素短语以及句柄。答：1)这里用最右推导表示，省略树SSaSaBSacScRSacAcRSacAbBcRSacAbeCSacAbBbecHSacAbcSdbedfSacAb

27、cSaAdbecRSacAbcAaAdbecHSacAbcBaAdbedfAacAbcBaAdbed2)短语：AacAbcBaAdbedcAbcBaAdbedAbcBaAdbeAbcBaAdcBaAdBaAeA 素短语：BaAe 句柄：A146、写出表达式 a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。147、什么是活动记录它主要由哪些内容构成148、对下列四元式序列生成目标代码(10 分)T=A-BS=C+DW=E-FU=W/TV=U*S其中，V 是基本块出口的活跃变量，R0 和 R1 是可用寄存器。答 MOVR0,ASUB R0,BMOVR1,AADD R1， DM

28、OVS， R1MOvR1， ESUB R1， FDIVR1， R0MULR1， S149、设有如下的三地址码(四元式)序列:ReadNI:=NJ：=2L1：ifIJgotoL2ifI=0gotoL4J：=J+1I:=NgotoL1L3:PrintYESReturnL4：PrintNOReturn(1)、对题中代码划分基本块，并给每个基本块一个序号(2)、画出基本块集合的控制流图，每个基本块就用(1)小题中的序号表示。(3)、若有循环的话，列出构成每个循环的结点。150、已知文法G(V):VN|N旧EV|V+ENT(1)给出与G(V痔价的LL(1)文法G(V);VNVV-E|EVEEf+E|eN

29、i(2)求文法G(V)的每个非终结符的FIRST集合和FOLLOW集合；First(V)=iFirst(V)=,First(E)=iFirst(E)=+,First(N)=iFollow(V)=$,+,Follow(V)=$,+,Follow(E)=Follow(E户Follow(N)=,$,+)(3)构造文法G(V)的LL(1汾析表。+i$VV一NVV，V一eVfEV一eV一eEEVEE，E-+EE，一eNNT151、考虑下面的三地址语句序列:b:=1b:=2ifw=xgotoL2e:=bgotoL2L1:gotoL3L2:c:=3b:=4c:=6L3:ifye 则 First(a)FFol

30、low(A)=空集154、写出语句 a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG 图、四元式三地址代码和三元式三地址代码。155、设有文法 GA：A-iB*eB 一 SB|sS 一eC|.iC 一 eC|判定该文法是否为 LL(1)文法若是则给出它的 LL(1 汾析表，否则说明理由。(20 分)First(A)=iFirst(B)=,.First(S)=,.First(C)=e,Follow(A)=$Follow(B)=*Follow(S)=*Follow(C)=对产生式 BSB|First(SB)=First(S)=,.First(=所以 First(SB)nFirst(9=

31、空集First(SB)AFollow(B 尸空集对产生式 S 一eC|.iFirst(eC)=First(.i)=.i所以 First(eC)nFirst(.i 尸空集对产生式 CeC|First(eC)eFirst(s)=所以 First(eC)nFirst(。=空集First(eC)nFollow(C 尸空集所以此文法是 LL(1)文法.*ie$AA-iB*eBB 一 SBB 一B 一 SBSS 一.iSeCCC 一|&C 一 eC156、构造一个 DFA,它接受汇=0,1上能被 5 整除的二进制数。157、正规式(0|1)*和(|0)1*)*是否等价，说明理由。158、写出字母表

32、=a,b上语言 L=w|w 的最后两个字母是 aa 或 bb的正规式，并画出接受该语言的最简 DFA（a|b）*aa|bb159、文法 G(S 汲其 LR 分析表如下，请给出串 baba$的分析过程。(1)SDbB(2)Dd(3)D 一 e(4)Ba(5)BBba(6)B 一LR 分析表ACTIONGOTObda$SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5（注：答案格式为步骤馍输入串动作）步骤愎输入串动作）10baba$按 Be 规约20D2baba$移进30D2b4aba$移进40D2b4a5ba$按 B 一 a 规约50D2b4B6ba$移

33、进60D2b4B6b7a$移进70D2b4B6b7a8$按 BBba 规约80D2b4B6$按 SDbB 规约90S1$接受160、已知文法G(A):A-aABl|aB-Bb|d(1)消除文法中的左递归，提取公共左因子，给出与G(A将价的LL(1)t?feG(A);(2)求文法G(A)的每个非终结符的FIRS球合和FOLLOW集合；(3)构造文法G(A)的LL(1汾析表。答：1)A-aAAABl|eB-dBB-bB|e2)First(A尸aFirst(B尸dFirst(A尸a,First(B)=b,Follow(A)=$,dFollow(B)=lFollow(A)=$,dFollow(B)=l3)abld$AA-aAAA-ABlAeAeBB-bBB，B一e161、设文法G(S):SS+aF|aF|+aFF-*aF|*a(1)消除左递归和回溯；(2)计算每个非终结符的FIRSTS口FOLLOW(3)构造预测分析表。答1、Sr+aFS|aFSS一+aFS|F7*aFF一F|&2、Fist(S)=