编译原理习题答案.

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

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

3、msky 定义的四种形式语言文法中， 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

4、、正规文法16、一个文法所描述的语言是 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、(1)(2)(3) (6)

5、D、(2)(3)(4)(6)20、过程调用时参数传递方式有 (1)传地址 (2)传值 (3)传标识符 (4)得结果 (5)传名 (6) 返回值 可选项有：A、(1)(2)(4)(5) B、(1)(2)(5)(6) C、(1)(2)(3) (6) D、(2)(3)(4)(6)21、下列代码中 D 不可能是目标代码。 A、汇编指令代码 B、可重定位指令代码 C、绝对指令代码 D、中间代码22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 B 。A.正确 B.不正确23、有限自动机能识别 C A上下文无关文法 B上下文有关文法C正规文法 D短语文法。 24、汇编程序是将 B

6、 程序改造成目标语言程序的翻译程序。A机器语言 B汇编语言 C高级语言 D低级语言25、LR(k)文法_B_二义性的。A、都是B、都不是C、不一定都是26、乔姆斯基方法的2型语言是这样一种语言，其产生式限制为 A A、Aa B、Aa，AaB C、a (| a | | b |) D、a b27、局部优化是局限于一个 C 范围内的一种优化。A.循环 B.函数 C.基本块 D.整个程序28、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 A 。A.正确 B.不正确29、乔姆斯基方法的3型语言是这样一种语言，其产生式限制为 B A Aa B Aa或AaB C a(| a | | b |) D

7、 a b30、运算符与运算对象类型不符属于 A 。A、语法错误 B、语义错误 C、语用错误 D、规则集合31、词法分析器的输入是 B 。A、词法记号 B、源程序 C、语法单位 D、目标程序32、在下述的编译方法中，自底向上的方法有 F ，自顶向下的分析方法有 A 。简单优先分析 算符优先分析 递归下降分析 预测分析技术 LR（K）分析 SLR（k）分析 LL（k）分析 LALR（K）分析 A. B. C. D. E. F. A. B. C. D. E. F. 33、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 B 。 A.正确 B.不正确34、算符优先分析法每次都是对 C 进行

8、归约。A 句柄 B短语 C最左素短语 D素短语35、编译时能进行的类型检查称为 C 。A、错误检查 B、动态检查C、静态检查 D、随机检查36、规范推导的每一步总是用产生式右边符号串替换句型中 B 位置的非终结符号A、最左 B、最右 C、最中 D、任意37、语法分析器的输入是 单词符号流 ，其输出是 分析树的某种表示 38、每个文法都能改写为LL(1)文法。 B A.正确 B.不正确39、对于无二义性的文法，规范推导是 C A 最左推导 B 最右推导的逆过程 C 最左归约的逆过程 D 最右归约的逆过程。40、描述语言 L= ambn | nm1 的文法为 D 。A、ZAbb AaA | a B

9、bB | bB、ZAB | b AAa | aBaBb | bC、ZAb AaAb | aD、ZaAbAAb | aAb | 41、间接三元式表示法的优点为 A A、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改C、便于优化处理，节省存储空间 D、节省存储空间，不便于优化处理42、编译时能进行的类型检查称为 C A错误检查 B动态检查 C静态检查 D随机检查43、文法 GS：S xSx | y所识别的语言是 A 。 A、xnyxn(n0) B、(xyx)* C、xyx D、x*yx*44、项目A称为 B ，其中AVN，A不是开始符。A、移进项目 B、归约项目 C、出错项目 D、接

10、受项目45、设有文法GS: S- S*S | S+S | (S) | a, 该文法_A_二义性文法。A、 是 B、不是 C、不一定46、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。A、自左至右 B、自顶向下 C、自底向上 D、自右至左。47、有文法G：EE*T|TTTi|i句子25*33按该文法G归约，其值为 B A 23 B42 C 30 D 1748、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。A 自左至右 B 自顶向下 C 自底向上 D自右至左。49、形如AB的项目为 A 项目。 A、待约 B、移进 C、接受 D、规约50、活动记录的连接数

11、据不包括 A 。A、形参单元 B、动态链（老SP） C、返回地址 D、全局Display地址51、高级语言编译程序常用的语法分析方法中，lALR分析法属于 C 分析方法。A、 自左至右 B、 自上而下 C、 自下而上 D、自右至左52、设a、b、c是文法的终结符，且满足优先关系a=b和b=c，则 D 。A.必有a=c B.必有c=a C 必有b=a D 答案AC都不一定成立53、词法分析器的输出是 A 。A、词法记号流 B、源程序 C、语法单位 D、目标程序54、对一个基本块来说， A 是正确的。 A、只有一个入口语句和一个出口语句 B、有一个入口语句和多个出口语句C、有多个入口语句和一个出口

12、语句 D、有多个入口语句和多个出口语句55、词法分析所依据的是 B 。A 语义规则 B 构词规则 C 语法规则 D 等价变换规则56、句型是由 D 推导出的符号串。A、非终结符 B、终结符 C、任何符号 D、开始符号57、如果文法G是无二义的，则它的任何句子 A 。 A、最左推导和最右推导对应的语法树必定相同 B、最左推导和最右推导对应的语法树可能不同 C、最左推导和最右推导必定相同 D、可能存在两个不同的最左推导，但它们对应的语法树相同58、算符优先文法与算符优先函数的关系的描述中正确的是（B）。A、一个算符优先文法一定存在优先函数与之对应B、一个算符优先文法可能存在多个优先函数与之对应C、

13、一个算符优先文法一定存在多个优先函数与之对应D、一个算符优先文法一定存在有限对优先函数与之对应59、一个句型中称为句柄的是该句型的最左 D 。 A 非终结符 B 短语 C 句子 D 直接短语60、描述一个语言的文法是（B ）A、唯一的 B、不唯一的 C、可能唯一，也可能不唯一61、下列 C 优化方法不是针对循环优化进行的。 A、强度削弱 B、删除归纳变量 C、删除多余运算 D、代码外提62、更动一张 A 表很困难。 A 三元式 B 间接三元式 C 四元式 D 三元式和四元式63、栈式存储分配申请和释放存储空间遵守 BC 原则。A、先申请先释放 B、先申请后释放 C、后申请先释放 D、任意64、

14、所谓自上而下分析法是指 。65、所谓语法制导翻译方法是 。66、确定的有穷自动机是一个 五元组 ，通常表示为 M=(S , ,f,s0,Z ) 。67、规范归约中的可归约串是指 句柄 ；算符优先分析中的可归约串是指最左素短语 。68、编译程序在逻辑上由 词法分析 、 语法分析 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。69、 D 不可能是目标程序。 A、汇编语言模块 B、可重定位目标模块 C、可执行目标模块 D、中间代码70、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义的 。71、一个名字的属性包括 继承属性 和 综合属性 。72、正规式的“*”读作 星

15、闭包 。73、编译程序在逻辑上由 、 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。74、编译程序的各个阶段的工作都涉及到 符号表管理 和 错误处理 75、文法用来描述语言的语法结构，它由如下4个部分组成：文法终结符集合、文法非终结符集合、 D 和文法开始符号。A、单词集合 B、字母数字串C、文法句子集合 D、文法产生式的集合 76、确定的有穷自动机是一个 元组，通常表示为 。 77、已知文法GE： EE + T | T TT * F | F F（E）| id 该文法终结符集合VT= ， 文法非终结符集合VN= ，该文法在乔姆斯基（Chomsky）文法分类属于 2 文法。78、编

16、译程序的各个阶段的工作都涉及到 和 。79、假设G是一个文法，S是文法开始符号，如果S*x，则称x是该文法的一 。80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。81、优化时，节省一条指令MOV Ri，M，节省的指令代价为 C A、0 B、1 C、2 D、382、采用 LL(1) 语法分析时，必须消除文法的左递归。83、在状态转换图中，结点代表 状态 ，用圆圈表示。84、若源程序是高级语言编写的，目标程序是 机器语言或汇编 语言的程序，则相应的翻译程序称为编译程序。85、常用的两种动态存贮分配办法是 栈式 分配和 堆式 分配。86、翻译方案和语法制导定义不同的是它的 语义

17、动作 （而不叫语义规则）放在括号 内，并且可以插在产生式 右部 的任何地方87、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。88、所谓最左推导是指： 。89、上下文无关文法的可以用 四元组 表示，其形式为 G=(VN,VT,S,P) 。90、后缀式 ab+c+d*e- 所表达的式子为 （a+b+c）*d-e 。91、常用的两种动态存贮分配办法是 分配和 分配。92、LL(K)文法中，第一个L表示 从左到右扫描输入串 ，第二个L表示 产生最左推导 ，K表示 在决定语法分析器每步动作时向前看K个输入符 。93、一个上下文无关文法所含四个组成部分是 文法终结符集合 文法非终结符集

18、合 开始符号 产生式有限集合 。94、对于文法G，仅含终结符号的句型称为 句子 。95、设有文法GE： EE + T | E T | T TT * F | T/F | F F（E）| i 该文法句型E + T * F 的句柄是 T * F 。96、后缀式 ab+c+d*e- 所表达的式子为 。97、文法符号的属性有两种，一种称为 继承 属性，另一种称为 综合 属性，S属性定义是指仅使用 综合 属性的语法制导定义。98、LR(0)项目和LR(1)项目的区别在于 是否有搜索符 。99、紧跟在条件转移语句后面的语句是基本块的 入口 语句。100、若二个正规式所表示的 DFA（或正规集） 相同，则认为

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

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

21、119、算符优先分析法是一种规范归约分析法。 ( F )120、非终结符可以有综合属性，但不能有继承属性。 ( F )121、所有LR分析器的总控程序都是一样的，只是分析表各有不同。 ( T )122、因名字都是用标识符表示的，故名字与标识符没有区别 (F )123、空符号串的集合=。 ( F )124、非终结符可以有综合属性，但不能有继承属性。 ( F )125、终结符可以有综合属性，也可以有继承属性。 ( F )126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( )127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。 ( F )129、DA

22、G是一个可带环路的有向图。 ( F )130、设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。 ( T )131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 ( F )132、对任何正规表达式e，都存在一个DFAM，满足L(M)L(e)。 ( T)133、 运行时的DISPLAY表的内容是什么？它的作用是什么？答：内容：1、过程R的现行活动记录的地址（sp的现值）2、R的外层Q的最新活动记录的地址3、Q的外层即主程序P的活动记录的地址作用：跟踪每个外层的最新活动记录的位置134、何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？

23、答：局部优化：在基本快内的优化。循环优化：对循环中的代码进行优化。全局优化：整个程序范围内的优化。 在 中间代码优化阶段。135、常见的存储分配策略有几种？它们都适合于什么性质的语言？答：1、静态分配策略 适用于无动态申请内存、无可变体积数组、无递归调用的程序语言（ 如 Fortran）2、动态分配策略2.1栈式动态分配 2.1.1简单栈式分配 适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允许过程含可变数组的语言 2.1.2嵌套过程语言的栈式分配 适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言2.2堆式动态分配 适用于允许程序为变量在运行时动态申

24、请和释放存储空间的语言136、下面文法是否是二义文法？试说明理由。 GS： S SaS | e 答：二义137、已知文法G(E) ET|ET TF|T * F F(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树； (2) 给出句型(T * Fi)的短语、素短语。1）EETE+iT+iT*F+I 树略2）短语：T*F+i T*F i素短语：T*F i138、把算术表达式(a+b)*(b+c)翻译成： (a) 后缀表示 ab+bc+*(b) 语法树 图略(c) 有向无环图 图略(d) 四元式三地址代码四地址代码：（+, a ，b，t1）（+，b，c，t2）（*，t1，t2，t3）

25、（，t3，-，t4）139、DFA与NFA的区别？答：1、DFA弧上不允许有出现，NFA允许2、DFA中每个状态S和输入符号a最多有一条边离开S，NFA有多条3、NFA可以有多个初态，DFA只有一个140、设已构造出文法G(S)：SS(S)Se的LR分析表如下状态ACTIONGOTO()#S0r2r211S2Acc2r2r233S4S54r2r265r1r16S4S77r1r1假定输入串为( )( )，请给出LR分析过程(即状态，符号，输入串的变化过程)。步骤 状态 符号 输入串步骤状态符号输入串10（）（）$201S（）（）$3012S(）（）$40123S()（）$501235S()（）$

26、601S（）$7012S(）$80123S(S）$901235S(S)$1001S$141、对符号表的基本操作有几种，分别是什么？ 答：5类。1、填写名称2、查找名字3、访问信息4、填写修改信息5、删除（或者：4类。建立、插入、查找、删除）142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+b,a-b,a,a); write(a);end传值:5传地址: 42得结果: 7传名: 77143、目标代码有哪几种形式？生成目标代码时通常

27、应考虑哪几个问题？答：1、汇编语言2、机器语言 又可分为a可立即执行的机器语言b可重定位的机器语言需要考虑：1.、如何使生成的目标代码最短2、如何分配寄存器的使用144、下面的推导S rm rm g A b w rm g l b b w中，最后一步用的是A lb，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？(5分) P79答： LL(1)扫描到l的时候决定用此产生式；LR(1)扫描到b的时候决定使用次产生式145、构造一个最简DFA，它接受正规式ab (a|b)*。给出文法GS：SSaA|A AAbB|B BcSd|e (1)证实AacAbcBaAdbed是文

28、法GS的一个句型；(2)请写出该句型的所有短语、素短语以及句柄。 答：1）这里用最右推导表示，省略树SSaASaBSacSdSacAdSacAbBdSacAbedSacAbBbedSacAbcSdbedSacAbcSaAdbedSacAbcAaAdbedSacAbcBaAdbed AacAbcBaAdbed2）短语：AacAbcBaAdbed cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短语：BaA e 句柄：A146、写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。147、什么是活动记录？它主要由哪些内容构成？14

29、8、对下列四元式序列生成目标代码 (10分) T=A-B S=C+D W=E-F U=W/T V=U*S其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。答 MOV R0 ，A SUB R0 ，B MOV R1 ，A ADD R1 ，D MOV S ，R1 MOv R1 ，ESUB R1 ，FDIV R1 ，R0MUL R1 ，S149、设有如下的三地址码(四元式)序列：Read N I=N J=2 L1：if IJ goto L3 L2：I=I-J if IJ goto L2 if I=0 goto L4 J=J+1 I=N goto L1 L3：Print YES Return L4

30、：Print NO Return （1）、对题中代码划分基本块，并给每个基本块一个序号（2）、画出基本块集合的控制流图，每个基本块就用（1）小题中的序号表示。（3）、若有循环的话，列出构成每个循环的结点。 150、已知文法G(V)： V N | N EE V | V+E Ni(1)给出与G(V)等价的LL(1)文法G(V)；V NV V E| E VE E +E| Ni(2)求文法G(V)的每个非终结符的FIRST集合和FOLLOW集合；First(V)=i First(V)= , First(E)=i First(E)= + , First(N)=iFollow(V)=$,+, Follow

31、(V)=$,+, Follow(E)= Follow(E)= Follow(N)= , $ , + (3)构造文法G(V)的LL(1)分析表。+i$VV NVVV V EV V EE VEEE +EE NNi151、考虑下面的三地址语句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y 则First()Follow(A)=空集154、写出语句a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG图、四元式三地址代码和三元式三地址代码。155、设有文法GA： A iB*e B

32、SB | S eC | . i C eC | 判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 (20分)First(A)=i First(B)= , , . First(S)= , . First(C)=e, Follow(A)=$ Follow(B)=* Follow(S)=* Follow(C)=对产生式B SB | First(SB)=First(S)= , . First()= 所以First(SB)First()=空集First(SB)Follow(B)=空集对产生式S eC | . iFirst(eC)= First(. i)= . i 所以Firs

33、t(eC)First(. i)=空集对产生式C eC | First(eC) e First()= 所以First(eC)First()=空集First(eC)Follow(C)=空集所以此文法是LL(1)文法.*ie$AA iB*eBB SBB B SBSS . iS eCCC | C eC156、构造一个DFA，它接受=0，1上能被5整除的二进制数。157、正规式 (0 | 1)* 和 ( (e | 0) 1* )*是否等价，说明理由。 158、写出字母表S = a, b上语言L = w | w的最后两个字母是aa或bb的正规式，并画出接受该语言的最简DFA。(a|b)*aa|bb159、

34、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObda$SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5(注：答案格式为 步骤 栈 输入串 动作) 步骤栈输入串动作)10baba$按B 规约20D2baba$移进30D2b4aba$移进40D2b4a5ba$按B a规约50D2b4B6ba$移进60D2b4B6b7a$移进70D2b4B6b7a8$按B Bba规约80D2b4B6$按S DbB规约90S1$接受160、已

35、知文法G(A)： A aABl | aB Bb | d(1)消除文法中的左递归，提取公共左因子，给出与G(A)等价的LL(1)文法G(A)；(2)求文法G(A)的每个非终结符的FIRST集合和FOLLOW集合；(3)构造文法G(A)的LL(1)分析表。答：1）A aA AABl| B dB B bB |2) First(A)=a First(B)=d First(A)=a, First(B)=b, Follow(A)=$,d Follow(B)=l Follow(A)=$,d Follow(B)=l3) abld$AA aAAAABlAABB bBBB 161、设文法G(S)： SS+aF | aF | +aF F*aF | *a(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。答1、S+aFS | aFS S+aFS |F*aFF F|2、Fist(S)=a,+ Fist(S)=+, Fist(F)=* Fist(F)=*, Follow(S)=$ Follow(S)=$ Follow(F)=$,+ Follow(F)=$,+3、+a*$SS+aFSSaFSSS+aFSSFF*aFFF F FF 162、构造下面文