《编译原理》考试试题及答案.pdf

《《编译原理》考试试题及答案.pdf》由会员分享，可在线阅读，更多相关《《编译原理》考试试题及答案.pdf（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 编锌原理 考锹被兼及答案(汇总)一、是非题(请在括号内，正确的划4错误的划X)(每个2分，共2 0分)1 .编译程序是对高级语言程序的解释执行。(X)2 .一个有限状态自动机中，有且仅有一个唯一的终态。(x)3.一 个算符优先文法可能不存在算符优先函数与之对应。(Y)4 .语法分析时必须先消除文法中的左递归。(x)5 .L R分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(力6 .逆波兰表示法表示表达式时无须使用括号。(Y)7 .静态数组的存储空间可以在编译时确定。(x)8 .进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(x)9 .两个正

2、规集相等的必要条件是他们对应的正规式等价。(x)1 0 .一个语义子程序描述了一个文法所对应的翻译工作。(x)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共4 0分)1 .词 法 分 析 器 的 输 出 结 果 是。A.()单词的种别编码 B.()单词在符号表中的位置C.()单词的种别编码和自身值 D.()单词自身值2 .正 规 式M 1和M2等价是指 oA.()M l和M2的状态数相等 B.()M l和M2的有向边条数相等C.()M 1和M 2所识别的语集和券 D.()M l和M 2状态数和有向边条数相等3 .文法G：S x S x|y所 识 别 的 语

3、 言 是。A.()x y x B.()(x y x)*C.()x n y x n(n 0)D.()x*y x*4 .如果文法G是无二义的，则它的任何句子a。A.()最左推导和最右推导对应的语法树必定相同B.()最左推导和最右推导对应的语法树可能不同1C.()最左推导和最右推导必定相同D.()可能存在两个不同的最左推导，但它们对应的语法树相同5.构 造 编 译 程 序 应 掌 握。A.()源程序 B.()目标语言C.()编译方法 D.()以上三项都是6.四元式之间的联系是通过 实现的。A.()指示器 B.()临时变量C.()符号表 D.()程序变量7.表达式(1 AVB)A(CVD)的 逆 波

4、兰 表 示 为。A.0-ABVACDV B.()A-|BVCDVAC.()ABV-|CDVA D.()Aq BVACDV8.优化可生成 的目标代码。A.()运行时间较短 B.()占用存储空间较小C.()运行时间短但占用内存空间大 D.()运行时间短且占用存储空间小9.下列 优化方法不是针对循环优化进行的。A.()强度削弱 B.()删除归纳变量C.()删除多余运算 D.()代码外提10.编译程序使用 区别标识符的作用域。A.()说明标识符的过程或函数名B.()说明标识符的过程或函数的静态层次C.()说明标识符的过程或函数的动态层次D.()标识符的行号三、填空题(每空1分，共10分)1.计算机执行

5、用高级语言编写的程序主要有两种途径：解释_ 和 _编译2.扫描器是一诃法分析落,它接受输入的源程方;对源程序进行一词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3.自上而下分析法采用 移进_、归约、错误处理、_ 接受等四种操作。4.一个LR分析器包括两部分：一个总控程序和_ 张分析及5.后缀式abc/所代表的表达式是_a/(b-c)_。6.局部优化是在基本块 范围内进行的一种优化。四、简 答 题(20分)1.简要说明语义分析的基本功能。答：语义分析的基本功能包括：确定类型、类型检查、语义处理和某些静态语义检查。2.考虑文法GS:S 一(T)|a+S|aT T,S|S消

6、除文法的左递归及提取公共左因子。解：消除文法GS的左递归：ST(T)I a+S I aTSTT f ST1 8提取公共左因子：S_(T)|aS，S一+S I T-srT f STI 3.试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。解：w ab+c d e l0-/+8+*+4.按照三种基本控制结构文法将下面的语句翻译成四元式序列：while(AC A Bl)C=C+l;else while(A D)A=A+2;解：该语句的四元式序列如下(其中E l、E2和 E3分别对应A C/B V D、A*和 AMD,并且关系运算符优先级高)：31 0 0 (j ,A,C,1

7、 0 2)1 0 1 (j,_,_,1 1 3)1 0 2 (j ,B,D,1 0 4)1 0 3 G，_,_,1 1 3)1 0 4 (j=,A,1,1 0 6)1 0 5 0,_,_,1 0 8)1 0 6 (+,C,1,C)1 0 7 U，_,_,1 1 2)1 0 8 U a A d|a A b|判断该文法是否是SL R(l)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有:S1-AA-aAd|aAb|e4下面构造它的L R(O)项目集规范族为:彳号abd#AIo：A-BaAdA-*aAbL：A-a*AdA f a AbA-*a

8、AdA-*aAbII：Ii：s/accIo：A 3 a AdA玲a AbA aA dA-*I：L：A-aA*dAaAbIs：A-aA*dA-aA*bI：A-aAbIs：A-aAd-I:A今aAbIs：AaAd*从上表可看出，状态1 0 和 1 2 存在移进-归约冲突，该文法不是L R(0)文法。对于1 0 来说有：F O L L O W(A)n a=b,d,#n a=0,所以在1 0 状态下面临输入符号为a 时移进，为 b,d,#时归约，为其他时报错。对于1 2 来说有也有与1 0 完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的,因此该文法是SL R(l)文法。其 SL R(l)分

9、析表为：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _状态ACTIONGOTOabd#A0S2Xir-r511acc2ScXir2r333SS54r2r:r：r25XiXiXiXi对输入串ab#给出分析过程为:5步骤状态栈符号栈输入串AC T I O NG O T O10#ab#S：20 2#ab#r5330 2 3#aAb#S40 2 3 4#aAb#150

10、1#A#acc一、是非题:1 .个上下文无关文法的开始符，可以是终结符或非终结符。2 .一个句型的直接短语是唯一的。3 .已经证明文法的二义性是可判定的。4 .每个基本块可用一个D AG 表示。5.每个过程的活动记录的体积在编译时可静态确定。6.2型文法一定是3型文法。7.一个句型一定句子。8.算符优先分析法每次都是对句柄进行归约。X9.采用三元式实现三地址代码时，不利于对中间代码进行优化。1 0 .编译过程中，语法分析器的任务是分析单词是怎样构成的。1 1 .一个优先表一定存在相应的优先函数。X1 2 .目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。1 3 .递归下降分析法是一种自

11、下而上分析法。1 4 .并不是每个文法都能改写成L L（D文法。1 5.每个基本块只有一个入口和一个出口。1 6.一个L L（1）文法一定是无二义的。1 7.逆波兰法表示的表达试亦称前缀式。1 8.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。1 9.正规文法产生的语言都可以用上下文无关文法来描述。2 0 .一个优先表一定存在相应的优先函数。2 1 .3型文法一定是2型文法。2 2 .如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。答案：1.X 2.X 3.X 4.V 5.V 6.X 7.X 8.X1 1.X 1 2.V 1 3.X 1 4.V()()()()()()

12、()()()()()()()()()()()()()()()()9.V 1 0.X1 5.V 1 6.V 1 7.X 1 8.V 1 9.V 2 0.X 2 1.V 2 2.V二、填空题：2 .编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。3 .如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。4 .从功能上说，程序语言的语句大体可分为（执行性）语 句 和（说明性）语句两大类。5 .语法分析器的输入是（单词符号），其输出是（语法单位）。6 .扫描器的任务是从（源程序中）中识别出一个个（单词符号）o7 .符号表中

13、的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。8 .一个过程相应的D I S P LA Y 表的内容为（现行活动记录地址和所有外层最新活动记录的地址）1 0 .常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。1 1 .一个名字的属性包括（类型）和（作用域）。1 2 .常用的参数传递方式有（传地址），（传值），（传名）613.根据优化所涉及的程序范围，可将优化分成为（局部优化），（循环优化），（全局优化）三个级另（I。14.语法分析的方法大致可分为两类，一 类 是（自上而下）分析法，另一 类 是（自下而上）分析法。15.预测分析程序是使用一张（分

14、析表）和 一 个（符 号 栈）进行联合控制的。17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。19.语法分析是依据语言的（语 法）规则进行。中间代码产生是依据语言的（语义）规则进行的。21.一个文法G,若它的预测分析表M不含多重定义，则该文法是（LL（1）文法）文法。22.对于数据空间的存贮分配，FORTRAN采用（静态策略，PASCAL采用（动态）策略。24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。26.对于文法G,仅含终结符号的句型称为（句 子）。27.所谓自上而下分析法是指（从开始符号出发，向下推导，推出句子）29.局限于

15、基本块范围的优化称（局 部 优 化）031.2 型文法又称为（上下文无关）文法；3 型文法又称为（正 则）文法。32.每条指令的执行代价定义为（指令访问主存次数加1）33.算符优先分析法每次都是对（最左素短语）进行归约。三、名词解释题：1.局部优化-局限于基本块范围的优化称。2.二义性文法-如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表一一过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。5.最左推导-任何一步a=B都是对a 中的最右非终结符替换。6.语法-组规则，用它可形成和产生一组合式的程序。7.文法-描述语言的语法结构的形

16、式规则。8.基本块-指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令 G是一个文法,S划文法的开始符号，假定a B 3 是文法G的一个句型,如果有a A 8 且P，则称B是句型a p 5 相对非终结符A的短语。11.待用信息-如果在个基本块中，四元式i 对 A定值，四元式j 要引用A值，而 从 i 到 j 之间没有A的其它定值，则称j 是四元式i 的变量A的待用信息。12.规范句型-由规范推导所得到的句型。13.扫描器

17、-执行词法分析的程序。14.超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄-个句型的最左直接短语。16.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。17.规范句型-由规范推导所得到的句型。18.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。_20.待用信息-如果在一个基本块中，四元式i 对 A定值，位元式j 要引用A值，而 从 i 到 j 之间没有A的其它定值，则称j 是四元式i 的变量A的待用信息。21.语义-定

18、义程序的意义的一组规则。四、简答题：71 .写一个文法G,使其语言为不以0开头的偶数集。2 .已知文法G(S)及相应翻译方案S a A b (p r i n t T”S *a p r i n t 2 A-A S p r i n t 3”A-*c p r i n t 4 输入a c a b,输出是什么？3 .已知文法G(S)S-*b A aA -(B|aB A a)写出句子b(a a)b 的规范归约过程。4 .考虑下面的程序：p r o c e d u r e p(x,y,z)；b eginy：=x+y;z:=z*z;en db eginA:=2;B:=A*2;P(A,A,B);P r in t

19、 A,Ben d.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出A,B 的值是什么？5 .文法G(S)S-dABA-*a A|aB-Bb|描述的语言是什么？6 .证 明 文 法 G(S)S-*S a S|是二义性的。7 .已知文法G(S)S-BAA-BS l dB-a A|b S|c的预测分析表如下abcd甘sS-BAS-BAS-BAAA-BSA-BSA-BSA-dBB-a AB-b SB-c给出句子a dc c d的分析过程。8 .写一个文法 G,使其语言为 L(G)=a,bmc,anbn|1=0,m=l,n=2 89.已知文法G 法):S-a:(T)T-T,S|S的优先关系表

20、如下:关系a()a-.(.请计算出该优先关系表所对应的优先函数表。1 0 .何谓优化？按所涉及的程序范围可分为哪几级优化？1 1 .目标代码有哪儿种形式？生成目标代码时通常应考虑哪几个问题？1 2 .一字母表X =a,b ,试写出上所有以a为首的字组成的正规集相对应的正规式。1 3 .基本的优化方法有哪几种？1 4 .写一个文法G,使其语言为L(G)=a bnc|n 0 1 5 .考虑下面的程序：p r o c edu r e p(x,y,z);b eginy：=y+z;z:=y*z+xen d;b egina:=2;b:=3;P (a+b,b,a);p r in t aen d.试问，若参数

21、传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么？1 6 .写出表达式a+b*(c-d)/e的逆波兰式和三元序列。1 7 .证明文法G(A)A-AA|(A)|e是二义性的。1 8 .令X =a,b ,则正规式a*b|b*a 表示的正规集是什么?1 9.何谓D I S P L AY 表？其作用是什么？2 0 .考虑下面的程序：p r o c edu r e p(x,y,z)；b eginy：=y+2;z:=z+x;en db egina:=5;b:=2;P (a+b,a-b,a);p r in t a9en d.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出a的值是什么

22、？2 1.写一个文法6,使其语言为1&)=1 1)%”|n 0 为奇数，m 0 为偶数2 2 .写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。2 3 .一个文法G 别是L L(1)文法的充要条件是什么？2 4 .已知文法G S S f S*a F|a F I*a FF-+a F|+a消除文法左递归和提公共左因子。2 5 .符号表的作用是什么？符号表查找和整理技术有哪几种？答案：1.所求文法是G S:S-AB|B AOA-AD|CB-*2|4|6|8C-l|3|5|7 9 BD-0|C2.输出是4 2 3 13.句子b(a a)b 的规范归约过程：步骤符号栈输入串动作0#b

23、(aa)b#预备1#b(aa)b#移进2#b(aa)b#移进3#b(aa)b#移进4#b(Aa)b#归约5#b(Ma)b#移进6#b(Ma)b#移进7#b(Bb#归约8#bAb#归约9#bAb#移进10#S#接受4.传地址 A=6,B=1 6传值 A=2,B=45.L(G)=da b n 0,m 2 0 6.证明：因为文法G S 存在句子a a 有两个不同的最左推导，所以文法G S 是是二义性的。S=S a S=S a S a S=a S a S=a a S=a aS=S a S=a S=a S a S=a a S=a a7.句 子 a dc c d的分析过程：10步骤符号栈输入串产生式0#s

24、a dc c d#1#ABa dc c d#S-*BA2#AAaa dc c d#B-a A3#AAdeed#4#Addeed#A f d5#Ac c d#6#S Bc c d#A-B S7#S cc c d#B f c8#Sc d#9#ABc d#Bc1 0#Acd#1 1#Ad#1 2#dd#A-d1 3U8.所求文法是G S:S-A BA-a Ac|DD-b D|bB-a Bb|a a b b函数a()f4244g55231 0.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化1 1 .目标代码通常采用三种形式：机器语言

25、，汇编语言，待装配机器语言模块。应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指令系统的特点。1 2 .正规式 a (a|b )*(A)A=()A=()A=A A=A=(A)=()111 8 .(a*b I b*a)=a,b,a b,b a,a a b,b b a.1 9 .D i s p l a y表：嵌套层次显示表由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，d i s p l a y表就是用于登记每个外层过程的最新活动记录起始地址。2 0 .传 地

26、址a=1 2传值 a=52 1 .所求文法是65 :S-A CA-a a A b b|a bC-c c C|c c2 2.逆波兰式 a b c+e*b c+f/+:=三元序列o pa r g la r g 2(1)十bc(2)*(1)e(3)4-bc(4)/(3)f(5)+(2)(4)(6):=a(5)2 3 .一个文法G别是LL(1)文法的充要条件是：(1)F I R S T(a)Cl F I R S T(B)=(2)如果 P=*e ,F I R S T(a )A F OLLOW (A)=2 4.消除左递归S-a F S，|*a F S S f*a F S|eF-+a F|+a提公共左因子，

27、文 法G (S)S f a F S|*a F S S -*a F S，|eF f+a F F -F I e2 5.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。五、计算题：1 .设文法G(S):S-|a|(T)T-T,S|S消除左递归；构造相应的FIR S T和FO L L O W集合；构造预测分析表2 .语句 if E then S(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。3.设文法G(S)：S-*(T)|aTf T+S|S(1)计算 FIR S T V T 和 L AS T V T；12(2)构造优先

28、关系表。4.设某语言的f o r语句的形式为f o r i:=E”to E d o S其语义解释为i:=E,L IM IT:=Ea g a in:if i=L IM IT thenB eg inS;i:=i+lg o to a g a inEnd;(1)写出适合语法制导翻译的产生式；(2)写出每个产生式对应的语义动作。5.把语句while a 0 then a:=a+lelse a:=a*3T;翻译成四元式序列。6 .设有基本块D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:二 A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有M还被引用，请写出优化

29、后的四元序列。7.已知文法G(S)S-a r|(T)T T,S|S(1)给出句子(a,(a,a)的最左推导；(2)给出句型(T,S),a)的短语，直接短语，句柄。8.对 于 C语言d o S while E 语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9.已知文法G(S)S-*a Ac B eA-Ab|bB d(1)给出句子a b b c d e的最左推导及画出语法树；(2)给出句型a Ab c d e的短语、素短语。1 0 .设文法G(S):13S-(T)I a S I aT T,S I S消除左递归和提公共左因子；构造相应的FIR S T和FO L L O

30、W集合；构造预测分析表。1 1.把语句if X 0 V Y 0 d o X:=A*3else Y:=B+3;翻译成四元式序列。1 2 .已知文法G(S)E-E+T|TT-T*F|FF-(E)|i(1)给 出 句 型(i+i)*i+i的最左推导及画出语法树；(2)给 出 句 型(E+T)*i+F的短语，素短语和最左素短语。1 3.设文法G(S)：S-T|S vTT-U|TAUU-i j-U(1)计算 FIR S T V T 和 L AS T V T；(2)构造优先关系表。答 案：(1)消除左递，文法变为G，S ：Si a|(T)T-S T,|S 一,S|g此文法无左公共左因子。(2)构造相应的F

31、IR S T和FO L L O W集合：FIR S T(S)=a,(,FO L L O W(S)=#,)FIR S T(T)=a,(,FO L L O W(T)=FIR S T(T*)=,e ,FO L L O W(F)=)构造预测 分析表：aA()/#sSasf八S-任)T-S T T f STT s rVTfT f s r2.(1)C-*if E thens-cs.+(.4.(1)Ff f o r i:=E”to E d oS-F S(1(2)Ff o r i:=E!to d o GEN(:=,E!l.p la c e,entry(i);F.p la c e:=entry(i);L IM

32、IT:=N ewtemp;GEN(:=,E.p la c e,L IM IT);Q:=N X Q;F.Q U AD:=q;GEN(j W,entry(i),L IM IT,q+2)F.c ha in:=N X Q;GEN(j,0)STS，B AC K P AT C H(S(1).c ha in,N X Q);GEN (+,F.p la c e,1,F.p la c e);GEN(j,F.Q U AD);S.c ha in:=F.c ha in5.(1)(j ,c,(4)(j,(5)(+)a,1 0 ,(3)(1 2)O ,(5)(8)T ,T l)(6)(:=,T l,a)(j,(D)(8)(

33、*,a,1 3 ,T 2)(9)(-,T 2,1 ,T 3)(1 0)(:=T 3,a)(1 1)(j,(D)6 .优化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+2 07.最左推导S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)短语(T,S),a)(T,S),a15(T,S)T,Sa直接短语T,Sa句柄T,S8.(1)S-*do M i Si while M 2 EM-(2)M M.quad=nestquad;S-*do M i Si while M 2 E backpatch(si.nextl

34、ist,M 2,quad)backpatch(E.tru elist,M i.quad);S.n ex tlist二E.fa le lis t;)9.(1)S=aAcBe=AAbcBe=abbcBe=abbcde(2)短语：a Ab c d e,Ab,d素短语：Ab,d1 0.(1)S -(L)I a S S，-S I Lf S L L fSU i (2)FIR S T (S)=a,(FIR S T(L)=a,(FO L L O W(S)=,),#FO L L O W(L)=)F I R S T S )=a,(,FIR S T (1 7)=,eFO L L O W(S?)=,),#FO L L

35、 O W(f )=)16(1 2)(:=,T2,Y)1 2.(1)E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(i+i)*i+F=(i+i)*i+i(2)短语 i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F素 短 语 i,E+T最左素短语E+T1 3.(1)FIR S T V T(S)=V,A,i,-FIR S T V T(T)=A,i,-)FIR S T V T(U)=i,-L AS T V T(S)=V,A,i,-L A

36、S T V T(T)=A,i,-L AS T V T(U)=i,-(2)iVA-S.V.A.-.bool,+的类型是int x int-int,=的类型是int x int-b o o l,:=要求id 和 E 的类型都是int或者都是bool为该文法写一个语法制导定义或翻译方案，它完成类型检查。S f id:=EE fE a n d E|E+E|E=E|id4、对于下面C 语言文件s.cfl(int x)(long x;x=1;)f2(int x)long x;x=1;)某编译器编译时报错如下：s.c:In function fl:s.c:3:warning:declaration of x

37、 shadows a parameter请回答，对函数f2 为什么没有类似的警告错误。175、下面C语言程序经非优化编译后，若运行时输入2,则结果是area=12.566360,addr=-1073743076经优化编译后，若运行时输入2,则结果是area=12.566360,addr=-1073743068请解释为什么输出结果有区别。main()(float s,pi,r;pi=3.14159;scanf(,%f,&r);printf(Harea=%f,addr=%dnH,s=pi*r*r,&r);)6、描述由正规式b*a(bb*a)*b*定义的语言，并画出接受该语言的最简DFA。7、下面的

38、文法产生代表正二进制数的0 和 1 的串集：B T B0|B1|1下面的翻译方案计算这种正二进制数的卜进制值：B -Bi 0 B.val:=Bi.ua/x 2|Bi 1 B.val:=Bi.va/x 2+1|1 B.val:=1请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。8、在 C语言中，如果变量i 和 j 都是long类型，请写出表达式&i和表达式&i-&j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main()long i,j;printf(%dn”,&i-&j);)9、一个C语言的函数如下：func(i)long i;l

39、ongj;j=i-l；func(j);)下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。fiinc:func:pushl%ebppushl%ebpmovl%esp,%ebpmovl%esp,%ebpsubl$4,%espsubl$8,%espmovl8(%ebp),%edxmovl8(%ebp),%eaxdeci%edxdeci%eaxmovl%edx,-4(%ebp)movl%eax,-4(%ebp)movl-4(%

40、ebp),%eaxmovl-4(%ebp),%eaxpushl%eaxmovl%eax,(%esp)callfiinccallfiincaddl$4,%espleaveleaveretret18编译原理试卷八答案1、由正规式b*(abb*)*(a|动定义的语言是字母表 a,b 上不含子串aa的所有串的集合。最 简 DFA如下:2、先给出接受该文法活前缀的DFA如下：/。和 b 都只有移进项目，肯定不会引起冲突；6和 都无移进项目并仅含一个归约项目，也肯定不会引不一样，因此A 也肯定不会引3、语法制导定义如下。S-id:=E S.type:=if(id.type=bool and E.type=

41、bool)or(id.type=int and E.type=int)then type_ok else type_errorE f Ei and E2 E.type:=if Ei.type=bool and E2.type=bool then bool else type_errorE f Ei+E2 E.type:=if Ei,type=int and E2.type=int then int else type_errorE f Ei=E2 E.type:=if Ei.type=int and E2.type=int then bool else type_errorE id E.typ

42、e:=/ookup(id.entry)4、对于函数f l,局部变量x 声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是个合法的C 语言函数，因此编译器给出警告错误。对于函数f 2,由于局部变量x 的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。5,使用非优化编译时、变量s,pi,r 在局部数据区都分配4 个字节的空间。使用优化编译时，由于复写传播,pi*r*r变成3.14159*r*r,pi=3.14159成为无用赋值而删去，函数中不再有p i的引用，因此不必为pi分配空间。类似地，s=3.14159*r*r也是-一 个无用赋值(表达式要计算，但赋值是无用

43、的)，也不必为s 分配空间。这样，和非优化情况相比，局部数据区少了 8 个字节，因此r 的地址向高地址方向移动了8 个字节。6、正规式b*a(bb*a)*b*体现的特点是，每个a 的左边都有若干b,除非a 是第一个字母。该正规式定义的语言是：至少含一个a,但不含子串aa的所有a 和 b 的串集。最 简 DFA如下：B f 1 B B f 0 B|1 B|相应的翻译方案如下：B f 1 Q.i:=1 BB.va/:=B.valB t 0 B,1./:=B.i x 2 Bj B.val:=B.valI 1 BiJ:=B.i x 2+1 Bi B.va/:=B.va/19 B.val:=B,./8、

44、表达式&i的类型表达式是pointer(long),表达式&i-&j的类型表达式是long。按照C语言的规定，指向同一个类型的两个指针可以相加减，它们值的差是它们之间的元素个数。9、左边的编译器版本：一般只为局部变量分配空间。调用函数前，用若干次pushl指令将参数压栈,返回后用addl$n,%esp 次将所有参数退栈(常数n根据调用前做了多少次pushl来决定)。右边的编译器版本：除了为局部变量分配空间外，同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。优点是每次函数调用结束后不需要执行addl$n

45、,%esp指令，另外增加优化的可能性。编译原理期末试题(三)1、从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？答：从优化的范围的角度，优化可以分为局部优化和全局优化两类;对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式：a b c*b d*+:=四元式序列：三元式序列：0 P17)/)z1234/(z(/(/(S=bMb n b(Lb=h(Ma)b(*,b,c,tl)(1)(*(*,b,d,t2)(2)(*(+,t l,t2,t3)(3)(+(:=,t 3,/,a)(4)(

46、：=3、对于文法G(S):S fb M bM f (L|aL-M a)A R G 1 A R G 2b,c )b,d )(1),(2)(3),a)2)短语：M a),(M a),b (M a)b直接短语：Ma)句柄：M a)三、设有字母表 a,b 上的正规式R=(a b|a)*。Ma20(4)令状态1 和 2 分别对应非终结符B和AG:A-*a B|a|e ；B-a B|b A|a|b|e ；可化简为:G:A a B|e ；B-*a B|b A|四、设将文法G 改写成等价的L L(1)文法，并构造预测分析表。G：S-*S*a T|a T|*a T；T +a T|+a解：消除左递归后的文法G，：

47、S a T S,|*a T SzS -*a T S|T+a T|+a提取左公因子得文法G，：S f a T S T a T S S -*a T S I T-+a T T，-T|S e l e c t (S a T Sz)=a 21S e l e c t (S*a T S，)=*S e l e c t (S a T S，)A S e l e c t (S-*a T S,)=C S e l e c t (Sz-*a T Sz)=*S e l e c t (S，/w)=F ol l ow(sz)=#S e l e c t (Sz*a T Sz)A S e l e c t (S,-E)=S e l e

48、 c t (T f+a T，)=+S e l e c t (T -T)=F i r s t (T)=+S e l e c t (T，f w)=F ol l ow (Tz)=*,#S e l e c t (Tz-T)A S e l e c t(Tz-E)=所以该文法是L L(1)文法。预测分析表：*+a#Sf*a T S f a T S S，f*a T S f wTf+a T T，EJ.T一6设文法G为:S-A；A-B A|；B-a B|b解：(1)拓广文法 G ：(0)S -S (1)S-A A-B A A e (4)B-a B B-*b ；F I R S T (A)=e,a,b ；F I R

49、 S T (B)=a,b 构造的D F A如下：项目集规范族看出，不存在冲突动作。，该文法是L R(1)文法。(2)L R(1)分析表如下：22状态ActionGotoaB#SAB0S4S5r31231acc2rl3S4S5r3631S4S575r5r5r56r27r4rdr4(3)输入串a b a b 的分析过程为:步骤状态极符号栈当前字符轲余字符串动作(1)0abab/移进(2)01b移送(3)0154 abab#归 约B-b(4)047=aBab*归 约B-aB(5)03邓ab#移进(6)034 Bab#移进(7)0345Bab归 约B B b(8)0347=BaBa出 约B-aB(9)

50、033即B=VI约 A今e(10)0336W B AsVI约 A TBA(11)036*BA5归 为A今BA(12)02is AS归 约S今A(13)01aS;acc简答题3、设有文法G S :S-S(S)S|e ,该文法是否为二义文法？说明理由。答:是二义的，因为对于()()可以构造两棵不同的语法树。五、给定文法G S ：S-a A|b Q；A a A|b B|b；B-b D|a Q ；Q a Q|b D|b；D b B|a A ；E 玲a B|b FF-b D|a E|b构造相应的最小的D F A o解：先构造其N F A：用子集法将N F A 确定化：23abSAQAABZQQDZBZQ