编译原理习题答案.docx

《编译原理习题答案.docx》由会员分享，可在线阅读，更多相关《编译原理习题答案.docx（28页珍藏版）》请在三一办公上搜索。

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、编译过程中，语法分析器的任务是。 分析单词是怎样构成的 分析单词串是如何构成语句和说明的 分析语句和说明是如何构成程序的 分析程序的结构 A、 B、 C、 D、 6、文法G：EE+T|T TT*

2、P|P P (E)| i 则句型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、

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

4、文法 D、正规文法 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

5、)(3) (6) 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、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 BB 。A.正确 B.不正确 23、有限自动机能识别 C A上下文无关文法 B上下文有关文法 C正规文法 D短

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

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

8、确 34、算符优先分析法每次都是对 C 进行归约。 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

9、 | nm1 的文法为 D 。 A、ZAbb C、ZAb D、ZaAb 41、间接三元式表示法的优点为 A A、采用间接码表，便于优化处理 B、节省存储空间，不便于表的修改 C、便于优化处理，节省存储空间 D、节省存储空间，不便于优化处理 AaA | a AaAb | a AAb | aAb | BbB | b B、ZAB | b AAa | a BaBb | b 42、编译时能进行的类型检查称为 C A错误检查 B动态检查 C静态检查 D随机检查 43、文法 GS：S xSx | y所识别的语言是 A 。 A、xnyxn(n0) B、(xyx)* C、xyx D、x*yx* 44、项目A称为

10、 B ，其中AVN，A不是开始符。 A、移进项目 B、归约项目 C、出错项目 D、接受项目 45、设有文法GS: S- S*S | S+S | (S) | a, 该文法_A_二义性文法。 A、 是 46、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。 A、自左至右 B、自顶向下 C、自底向上 D、自右至左。 47、有文法G：EE*T|T TTi|i 句子25*33按该文法G归约，其值为 B A 23 B 42 C 30 D 17 48、高级语言编译程序常用的语法分析方法中，LL分析法属于 B 分析方法。 A 自左至右 B 自顶向下 C 自底向上 D自右至左。 49、形如A

11、B的项目为 A 项目。 A、待约 B、移进 C、接受 D、规约 50、活动记录的连接数据不包括 A 。 A、形参单元 B、动态链 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、

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

13、数的关系的描述中正确的是。 A、一个算符优先文法一定存在优先函数与之对应 B、一个算符优先文法可能存在多个优先函数与之对应 C、一个算符优先文法一定存在多个优先函数与之对应 D、一个算符优先文法一定存在有限对优先函数与之对应 59、一个句型中称为句柄的是该句型的最左 D 。 A 非终结符 B 短语 C 句子 D 直接短语 60、描述一个语言的文法是 A、唯一的 B、不唯一的 C、可能唯一，也可能不唯一 61、下列 C 优化方法不是针对循环优化进行的。 A、强度削弱 B、删除归纳变量 C、删除多余运算 D、代码外提 62、更动一张 A 表很困难。 A 三元式 B 间接三元式 C 四元式 D 三元

14、式和四元式 63、栈式存储分配申请和释放存储空间遵守 BC 原则。 A、先申请先释放 B、先申请后释放 C、后申请先释放 D、任意 64、所谓自上而下分析法是指 。 65、所谓语法制导翻译方法是 。 66、确定的有穷自动机是一个 五元组 ，通常表示为 M=(S , ,f,s0,Z ) 。 67、规范归约中的可归约串是指 句柄 ；算符优先分析中的可归约串是指最最左左素素短短语语 。 68、编译程序在逻辑上由 词法分析 、 语语法法分分析析 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。 69、 D 不可能是目标程序。 A、汇编语言模块 B、可重定位目标模块 C、可执行目标模块 D、

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

16、E + T | T TT * F | F F| id 该文法终结符集合VT= ， 文法非终结符集合VN= ，该文法在乔姆斯基文法分类属于 2 文法。 78、编译程序的各个阶段的工作都涉及到 和 。 79、假设G是一个文法，S是文法开始符号，如果S*x，则称x是该文法的一 。 80、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。 81、优化时，节省一条指令MOV Ri，M，节省的指令代价为 C A、0 B、1 C、2 D、3 82、采用 LL(1) 语法分析时，必须消除文法的左递归。 83、在状态转换图中，结点代表 状态 ，用圆圈表示。 84、若源程序是高级语言编写的，目标程序

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

18、个L表示 产生最左推导 ，K表示 在决定语法分析器每步动作时向前看K个输入符 。 93、一个上下文无关文法所含四个组成部分是 文法终结符集合 文法非终结符集合 开始符号 产生式有限集合 。 94、对于文法G，仅含终结符号的句型称为 句子 。 95、设有文法GE： EE + T | E T | T TT * F | T/F | F F| i 该文法句型E + T * F 的句柄是 T * F 。 96、后缀式 ab+c+d*e- 所表达的式子为 。 97、文法符号的属性有两种，一种称为 继承 属性，另一种称为 综合 属性，S属性定义是指仅使用 综合 属性的语法制导定义。 98、LR(0)项目和L

19、R(1)项目的区别在于 是否有搜索符 。 99、紧跟在条件转移语句后面的语句是基本块的 入口 语句。 100、若二个正规式所表示的 DFA 相同，则认为二者是等价的。 101、仅含终结符的句型称为 。 ( F ) 103、规范归约和规范推导是互逆的两个过程。 ( T ) 104、一个上下文无关文法的开始符号可以是终结符或非终结符。 ( F ) 102、编译方式与解析程序的根本区别在于是否生成目标代码。 105、逆波兰表示法表示表达式时无需使用括号。 ( T ) 106、符号表由词法分析程序建立，由语法分析程序使用。 ( F ) 107、逆波兰法表示的表达式亦称前缀式。 ( F ) 108、代码

20、生成器的输入包括中间代码和符号表中的信息。 ( T ) 109、孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。 ( T ) 110、目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( T ) 111、无左递归的文法是LL(1)文法。 ( F ) 112、一个句型的直接短语语是唯一的。 ( F ) 113、正规文法产生的语言都可以用上下文无关文法来描述。 (F ) 114、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 ( F ) 115、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( F ) 116、一个上下文无关文法的开始符号可以是终结

21、符或非终结符。 ( F ) 117、一个文法所有句子的集合构成该文法定义的语言。 ( T ) 118、优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。 ( T ) 119、算符优先分析法是一种规范归约分析法。 ( F ) 120、非终结符可以有综合属性，但不能有继承属性。 ( F ) 121、所有LR分析器的总控程序都是一样的，只是分析表各有不同。 ( T ) 122、因名字都是用标识符表示的，故名字与标识符没有区别 (F ) 123、空符号串的集合=。 ( F ) 124、非终结符可以有综合属性，但不能有继承属性。 ( F ) 125、终结符可以有综合属性，也可以有继承属

22、性。 ( F ) 126、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( ) 127、若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。 ( F ) 129、DAG是一个可带环路的有向图。 ( F ) 130、设有符号串x和y，把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。 ( T ) 131、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 ( F ) 132、对任何正规表达式e，都存在一个DFA M，满足L(M)L(e)。 ( T) 133、 运行时的DISPLAY表的内容是什么？它的作用是什么？ 答：内容：1、过程R的

23、现行活动记录的地址2、R的外层Q的最新活动记录的地址3、Q的外层即主程序P的活动记录的地址 作用：跟踪每个外层的最新活动记录的位置 134、何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？ 答：局部优化：在基本快内的优化。循环优化：对循环中的代码进行优化。全局优化：整个程序范围内的优化。 在 中间代码优化阶段。 135、常见的存储分配策略有几种？它们都适合于什么性质的语言？ 答：1、静态分配策略 适用于无动态申请内存、无可变体积数组、无递归调用的程序语言 2、动态分配策略 2.1栈式动态分配 2.1.1简单栈式分配 适用于没有分程序结构、不允许程序嵌套定义但允许过程递归调用、允

24、许过程含可变数组的语言 2.1.2嵌套过程语言的栈式分配 适用于没有分程序结构、允许程序嵌套定义和过程递归调用、允许过程含可变数组的语言 2.2堆式动态分配 适用于允许程序为变量在运行时动态申请和释放存储空间的语言 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 i 138、把算术表达式(a+b

25、)*(b+c)翻译成： (a) 后缀表示 ab+bc+* (b) 语法树 图略 (c) 有向无环图 图略 (d) 四元式三地址代码 四地址代码： 139、DFA与NFA的区别？ 答：1、DFA弧上不允许有出现，NFA允许 2、DFA中每个状态S和输入符号a最多有一条边离开S，NFA有多条 3、NFA可以有多个初态，DFA只有一个 140、设已构造出文法G(S)： SS(S) Se 的LR分析表如下 状态 0 1 2 3 4 5 6 7 ACTION ( r2 S2 r2 S4 r2 r1 S4 r1 ) r2 S5 r2 S7 r1 # r2 Acc r1 GOTO S 1 3 6 假定输入串

26、为( )( )，请给出LR分析过程(即状态，符号，输入串的变化过程)。 步骤 状态 符号 输入串 步骤 1 2 3 4 5 6 7 8 9 10 141、对符号表的基本操作有几种，分别是什么？ 答：5类。1、填写名称2、查找名字3、访问信息4、填写修改信息5、删除 142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值 procedure P(w,x,y,z); begin y := y*w; z := z+x; end begin a := 5; b := 3; P(a+b,a-b,a,a); write(a); end 状态 0 01 012 0123 01235 01 01

27、2 0123 01235 01 符号 S S( S( S S S( S(S S(S) S 输入串 $ $ ）$ )$ $ $ ）$ ）$ $ $ 传值: 5 传地址: 42 得结果: 7 传名: 77 143、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ 答：1、汇编语言2、机器语言 又可分为a可立即执行的机器语言b可重定位的机器语言 需要考虑：1.、如何使生成的目标代码最短2、如何分配寄存器的使用 144、下面的推导S rm rm g A b w rm g l b b w中，最后一步用的是A lb，分别指出LL方法和LR方法在扫描到此句型的什么位置决定用此产生式？(5分) P7

28、9 答： LL(1)扫描到l的时候决定用此产生式；LR(1)扫描到b的时候决定使用次产生式 145、构造一个最简DFA，它接受正规式ab (a|b)*。 给出文法GS：SSaA|A AAbB|B BcSd|e (1)证实AacAbcBaAdbed是文法GS的一个句型； (2)请写出该句型的所有短语、素短语以及句柄。 答：1）这里用最右推导表示，省略树SSaASaBSacSdSacAdSacAbBdSacAbedSacAbBbedSacAbcSdbed SacAbcSaAdbedSacAbcAaAdbedSacAbcBaAdbed AacAbcBaAdbed 2）短语：AacAbcBaAdbed

29、 cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短语：BaA e 句柄：A 146、写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽象语法树。 147、什么是活动记录？它主要由哪些内容构成？ 148、对下列四元式序列生成目标代码 (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 ，E SUB R1 ，F DIV R1 ，R0 MUL

30、R1 ，S 149、设有如下的三地址码(四元式)序列： 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：Print NO Return 、对题中代码划分基本块，并给每个基本块一个序号 、画出基本块集合的控制流图，每个基本块就用小题中的序号表示。 、若有循环的话，列出构成每个循环的结点。 150、已知文法G(V)： V N | N E E V | V+E Ni (1)给出与G(V)等价的LL(1)文法G(V)； V NV V

31、 E| E VE E +E| Ni (2)求文法G(V)的每个非终结符的FIRST集合和FOLLOW集合； First(V)=i First(V)= , First(E)=i First(E)= + , First(N)=i Follow(V)=$,+, Follow(V)=$,+, Follow(E)= Follow(E)= Follow(N)= , $ , + (3)构造文法G(V)的LL(1)分析表。 V V + V V E V i V NV $ V E E N E +E E E VE Ni 151、考虑下面的三地址语句序列： b := 1 b := 2 if w = x goto L2

32、 e := b goto L2 L1: goto L3 L2: c := 3 b := 4 c := 6 L3: if y 则First()Follow(A)=空集 154、写出语句a:=b*(-c)+b*(-c)的后缀式、抽象语法树、DAG图、四元式三地址代码和三元式三地址代码。 155、设有文法GA： A iB*e B SB | S eC | . i C eC | 判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。 (20分) First(A)=i First(B)= , , . First(S)= , . First(C)=e, Follow(A)=$ Fol

33、low(B)=* Follow(S)=* Follow(C)= 对产生式B SB | First(SB)=First(S)= , . First()= 所以First(SB)First()=空集 First(SB)Follow(B)=空集 对产生式S eC | . i First(eC)= First(. i)= . i 所以First(eC)First(. i)=空集 对产生式C eC | First(eC) e First()= 所以First(eC)First()=空集 First(eC)Follow(C)=空集 所以此文法是LL(1)文法 A B S C . S . i * i e C

34、 eC $ A iB*e B SB B B SB S eC C | 156、构造一个DFA，它接受=0，1上能被5整除的二进制数。 157、正规式 (0 | 1)* 和 ( (e | 0) 1* )*是否等价，说明理由。 158、写出字母表S = a, b上语言L = w | w的最后两个字母是aa或bb的正规式，并画出接受该语言的最简DFA。 (a|b)*aa|bb 159、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。 (1) S DbB (4) B a (2) D d (3) D (6) B (5) B Bba LR分析表 0 1 2 3 4 5 6 7 8 ACTION b r3 s4 r2 r6 r4 s7 r5 d s3 a S5 S8 $ acc r6 r4 r1 r5 GOTO S 1 B 6 D 2 (注：答案格式为 步骤 栈 步骤 1