编译原理课程重点.docx

《编译原理课程重点.docx》由会员分享，可在线阅读，更多相关《编译原理课程重点.docx（16页珍藏版）》请在三一办公上搜索。

1、编译原理课程重点编译原理课程测试试卷评分标准1 一、填空题参考答案 题号 1 2 上下文无关文法、VN、|=| 6 3 4 参考代码优化、前后端、答案 源语言与目标机器 题号 5 参考寄存器、计算机指令答案 系统、计算次序 题号 9 语法制导翻译、语AaB、AB、 义动作、属性文法 Z 7 8 FIRST()、=*、NFA、DFA、接受(识别) 线性、排序、散列 S=*A 10 参考顺序、最后一个语句、预测分析程序、答案 局部优化 SELECT(A)、没有值 说明：各个答案可有不同表达方式，只要意思相同即可。 二、简述题参考答案 1、简述将NFA转换为最小化DFA的步骤。 1、 第一步：将NF

2、A确定化。用造表法将NFA确定化过程如下： (0)表的第0行和第0列作标识行列的值。 (1) 将-closure(I)作为表中第1行第1列。 (2) 假定S=a1，a2，.an，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。 (3) 反复重复第(1) 步，直至无新状态出现为止。 (4) 重新命名新状态。 第二步：将DFA最小化。DFA最小化具体过程：用子集分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将

3、DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。 2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。 2、静态存储分配的特点：编译时刻确定存储位置；访问效率高。主要用途：子程序的目标代码段、全局数据目标。 栈式存储分配的特点：嵌套调用次序、先进后出、生存期限于本次调用、自动释放。用途：过程的局部环境、活动记录。 堆式存储分配的特点：将内存空间分为若干块，根据用户要求分配；无法满足时，调用无用单元收集程序将被释放的块收集起来重新分配。主要用途：用于动态数据结构：存储空间的动态分配和释放。 3、以表达式 a:=b*(-c)+b/(-d)为例，简述常用的三种

4、中间代码表示形式。 3、逆波兰式：abc-*bd-/+:= 。 三元式：(- , c , _ ) (* , b , ) (- , d , _ ) (/ , b , ) (+ , , ) (:= , ,a )。 四元式: (- , c , _ ,t1) (* , b ,t1 ,t2) (- , d , _ ,t3) (/ , b ,t3 ,t4) (+ ,t2 ,t4 ,t5) (:= ,t5 ,_ , a)。 4、简述判别文法是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的 4、判别步骤：先画出各非终结符能否推导出的情况表；然后，用定义法或关系图法计算FIRST、FOL

5、LOW集；再计算各规则的SELECT集；最后，根据同一个左部的规则其SELECT集是否相交来判断给定文法是否为LL(1) 文法。 将非LL(1) 文法转换成LL(1) 文法的两种主要方法：提取左公共因子、消除左递归。 三、应用题参考答案 1、证明(3分)：因为存在推导序列S=aAS=aSbAS=aabAS=aabbaS=aabbaa，即有S=*aabbaa成立，所以，是文法的一个句子。 语法树： 句型分析：将句型改写为a1a2b1b2a3a4，则：该句型相对于S的短语：a1a2b1b2a3a4和 a4；相对于A的短语： a2b1b2a3和b2a3；对于Sa的直接短语：a2，a4；相对于Aba的

6、直接短语：b2a3；句柄：a2。 2、(1)计算GE的FIRSTVT和LASTVT集如下：(5分) (2)构造GE的算符优先关系表如下：(4分) 由上表可知GE是算符优先文法(1分)。 (3)输入串w=i+i# 的算符优先分析过程如下：(5分) 3、基本块的DAG图如下：(3分) 根据DAG结点原来的构造顺序重写四元式如下：(2分) A：=5 T1=10 T3=10 B：=R+r T0：=A+B T2：=T0 X1：=T0+T1 X2：=T0*T1 假设基本块出口后只有X1，X2还被引用，则通过重新命名临时变量的基本块保结构变换，可将基本块的四元式代码进一步优化为：(3分) C：=R+r D：

7、=5+C X1：=D+10 X2：=D*10 4、0)SS 1)S A 2)S B 3)A aAe 4)A a 5)B bBd 6)B b (1)GS的LR(0)项目集规范族DFA如下：(4分) (2)由于，得GS的SLR(1)分析表如下：(3分) 由上左表可知GS是SLR(1)文法。 (3)用SLR方法分析输入串aae#过程如上右表所示：(4分) (4)由于GSLR(0)项目集规范族DFA中I4、T5中都包含有移进归约冲突，所以GS不是LR(0)文法，由于GS是SLR(1)文法故一定是LR(1)和LALR(1)文法。(3分) 编译原理课程测试试卷评分标准2 一、填空题参考答案 题号 1 2

8、3 4 参考中间代码生成、单词、句子、非终结符号集和答案 语义分析 终结符集、左部 题号 5 6 算符文法、多、算符优先文法 9 参考标识符、类型、作用答案 域和可视性、 题号 移进项目、不唯一、优先矩A.B、接受项目 阵、优先函数 7 8 目标代码、已定位、强连通、有且只有可重定位 一个入口结点 10 参考符号a、状态j、归约得到的非终结符A、gotoS,a全局变量、形参和实参 答案 的值j 说明：各个答案可有不同表达方式，只要意思相同即可。 二、简述题参考答案 1、简述运行目标程序时所需空间的种类。 1、 运行目标程序时所需空间分为两种容纳目标代码的空间和目标代码运行时的数据空间。 目标代

9、码运行时的数据空间中某些部分无法在编译时确定存储位置，它主要包括： 用户所定义的变量和常量所需空间、中间结果及参数传递所需的临时单元、调用过程时的连接单元、I/O操作所需缓冲区。 2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。 2、算符优先分析算法的步骤： 设单元a中存放当前输入符，S为一个符号栈，则： 1) 将当前输入符存放到a中，将#入符号栈。 2) 将栈顶第一个终结符b与a比较。如果ba ，而 b= #且栈中只剩一个非终结符时，则成功；否则a入栈；如果ba,则a入栈；如果ba,在栈顶寻找最左素短语，并将最左素短语归约为一个非终结符；如果文法中找不到相应规则，则出错； 3)

10、重复(2) 至成功或失败。 算符优先分析方法的优、缺点： 由于只考虑终结符之间的优先关系确定句柄，所以效率高；由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的，只适用于表达式的语法分析。 3、简述代码优化的概念和分类，并列举出四种以上常用的代码优化技术。 3、所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度或占用的存储空间加大。 代码优化按阶段分中间代码优化和目标代码优化，按程序范围分为局部基本块优化、循环优化、全局优化。 常用的优化技术有删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知变量与复写传播等。 4、简述判别

11、文法是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的 4、判别任意给定的一个上下文无关文法GS是否为LALR(1)文法的过程： 将GS加入一条规则：S S GS拓广为GS，然后构造GS的LR(0)项目集规范族DFA。检查DFA的项目集中有无移进归约冲突或归约归约冲突，若无，则GS是LR(0)文法，也是LALR(1)文法。 如果DFA的项目集中有无移进归约冲突或归约归约冲突，通过考虑归约项目左部非终结符的FOLLOW集能够解决这两类冲突，则GS是SLR(1)文法，也是LALR(1)文法。 如果通过考虑归约项目左部非终结符的FOLLOW集还有不能够解决的移进归约冲突，通过考

12、虑后跟符号来构造GS的LR(1)项目集规范族DFA。如果冲突可以解决，则GS是LR(1)文法。进一步合并LR(1)项目集规范族中同心集，如果依然不产生归约归约冲突，则GS是LALR(1)文法。 三、应用题参考答案 1、证明(3分)：因为存在推导序列：E=T+E=T+T+E=T+T*F+E=T+T*F+T =T+T*F+F=T+T*F+i，即有E=*T+T*F+i成立，所以，T+T*F+i是文法的一个句型。 语法树： 句型分析：该句型相对于E的短语：T+T*F+i、T*F+i和i ；相对于T的短语有：T*F和i，相对于F的短语有i。相对于TT*F的直接短语：T*F,相对于Fi的直接短语：i。句柄

13、：T*F。 (4) 该句型的所有素短语：T*F和 I；T*F为最左素短语。(3分) 2、if ab or cf then s1 else s2生成的三地址代码/四元式序列如下：(6分) (1) if a b goto (7) (2) goto (3) (3) if c f goto (7) (6) goto (p+1) (7) s1对应的四元式序列 (p) goto (q) (p+1) s2对应的四元式序列 (q) 3、(1)代入后有S的规则右部=a|b(aS|a)=ab|ba=,故对应的正规式R=(ab|ba)(ab|ba)* 。 (3分) (2)对应的NFA状态图如下左图所示： (3分)

14、(3)将所得NFA确定化为DFA状态图如上右图所示： (3分) (4)将所得DFA最小化：首先根据是否终态划分为非终态集P1=S,A,B和终态集P2=Z；然后对P1根据a弧划分为P11=S,P12=A，P13=B。可见原DFA已是最小化的DFA。 (3分) 4、 (1)计算GE的SELECT集如下：(2分) SELECT(E E T )=(，a SELECT(E T )=(，a SELECT(T T F)=(，a SELECT(T F)=(，a SELECT(F ( E )=( SELECT(F a)=a 由于SELECT(E E T ) SELECT(E T )=(，a； SELECT(T

15、T F) SELECT(T F)=(，a； SELECT (F ( E )SELECT (F a) = (a = 故 GE不是LL(1) 文法。(1分) 对GE的E E T和T T F两条规则消除左递归后变为：(2分) ET E E T E| T F T T F T F ( E )a 计算消除左递归后GE的SELECT集如下：(2分) SELECT(E T E)=(，a SELECT(E T E)= SELECT(E)=#，) SELECT(T F T)=(，a SELECT(T F T)= SELECT(T)= ，#，) SELECT(F( E )=( SELECT(Fa)=a 由于SELE

16、CT(E T E)SELECT (E) = SELECT (T F T) SELECT (T) = SELECT (F ( E )SELECT (F a) = = 故消除左递归后的GE是LL(1) 文法。(1分) 根据消除左递归后的GE的SELECT集构造预测分析表如下：(3分) 对输入串w=a-aa#的分析过程如下表所示：(5分) 编译原理课程测试试卷评分标准3 第一题：填空题 1、共有30个空，每空1分， 30130分。 2、参考答案： 题号 参考答案 题号 参考答案 题号 参考答案 题号 参考答案 题号 参考答案 1* 源语言、目标机 YACC、LEX 2 3 句型、句子 4 5 6 上

17、下文无关文法、有害规则、多余规则 状态转换函数、子集 一个非终结符 7 8 9* 预测分析方法、算提取左公共因子、消除待约项目、归约项目 符优先分析方法 左递归 10 11* 12 ai-1ai、ajaj+1 收集符号属性、目标代入口、出口 aiai+1aj-1aj 、 码生成阶段地址分配 13 14* 15 图中存在环/回路 传值、传地址 语法制导、属性文法 说明：各个答案可有不同表达方式，只要意思相同即可； 带*的题中的答案可交换次序。 第二题： 2、语法分析阶段的任务：根据语言的语法规则对单词符号串(符号序列)进行语法分析,识别出各类语法短语(可表示成语法树的语法单位),判断输入串在语法

18、上是否正确。 3、语义分析阶段的任务：按语义规则对语法分析器归约出的语法单位进行语义分析,审查有无语义错误,为代码生成阶段收集类型信息,并进行类型审查和违背语言规范的报错处理。 4、中间代码生成阶段的任务：将语义分析得到的源程序变成一种结构简单,含义明确,容易生成,容易译成目标代码的内在代码形式。 5、代码优化阶段的任务：对中间代码或目标代码进行等价的变换改造等优化处理,使生成的代码更高效。 6、目标代码生成阶段的任务：将中间代码生成特定机器上的绝对或可重定位的指令代码或汇编指令代码。 说明：结合具体高级语言的答案再加1分。 第三题： 1、正规文法GS： S0A|1B A1S|1 B0S|0

19、2、NFA ： 3、DFA ： 步骤如下表所示： 标记 T0 T1 T2 T3 新状态 S A B S,Z I0 A S,Z A I1 B S,Z B 将集合T0至T3各用一个状态表示，确定化后所得DFA M如下： 说明：此答案只供参考，可以是其他答案，只要功能等价即可。 第四题： 1、证明：因为存在推导序列E=E-T=E-T*F=E-F*F=E- F*(E) =E- F*(T)=E-F*(F)=E-F*(i)，即有EE-F*(i)成立，所以，E-F*(i)是文法的一个句型。 2、语法树： E 3、句型分析 句型E-F*(i)相对于E的短语有: E-F*(i), i。 句型E-F*(i)相对于

20、T的短语有: F*(i), F，i。 句型E-F*(i)相对于F的短语有: (i), i。 句型E-F*(i)相对于TF的直接短语有: F 。 句型E-F*(i)相对于Fi的直接短语有: i 。 句型E-F*(i)的句柄为: F。 说明：短语、直接短语的说明可不具体指明所相对的非终结符或规则。 短语每错两个扣1分。 第五题： (10分) 对任意给定的一个文法GS： 1、判断是否为LL(1)文法的步骤：(4分) 1）画出各非终结符能否推导出的情况表。 2）用定义法或关系图法计算FIRST、FOLLOW集。 3）计算各规则的SELECT集。 *E - T T * F F T F i 4） 检查所有

21、左部相同的规则的SELECT集是否相交，如果不相交，则GS为LL(1)文法。否则，说明GS不是LL(1)文法。 2、 构造GS预测分析表：(3分) 预测分析表为一个二维矩阵,其形式为MA,a,其中AVN ,aVT或#。对文法中的规则A,若有终结符aSELECT(A),则将A填入MA,a中。(书写时，通常省略规则左部，只填)。对所有没有值的MA,a标记为出错。 3、根据预测分析表M对给定的某个输入串进行预测分析的过程，可用下述算法表示：(3分) #,S进栈 ; /初始化工作，S为开始符 do X=当前栈顶符号;a=当前输入符号； if (XT#) if (X=a) if (X ! =#) 将X弹

22、出,且前移输入指针 else error else if (MX,a=Y1Y2Yk ) 将X弹出;依次YkY2Y1将压入栈; else error; while( X ! =#); 说明：此答案只供参考，可以是其他答案，只要意思相近即可。 第六题： (15分) 1、对文法进行拓广，加入规则E E 后得GE，其非终结符的FIRSTVT、LASTVT 集计算如下： 非终结符 E FIRSTVT集 # LASTVT集 # E ；,(,a ；,）,a D (,a ）,a H (,a ）,a T *，；,(,a *，；,）,a 由FIRSTVT、LASTVT 集构造和如下： VTVN符号对 #E ；D

23、E） T* 关系 LASTVT(E) # LASTVT(E) ； LASTVT(T) ） LASTVT(E) ） LASTVT(T) * 2、优先矩阵为： ；( ) a * # ； ( ) a * # 该文法是算符优先文法。 3、输入串# 的算符优先分析过程： 步骤 1 2 3 4 5 6 7 8 9 10 分析栈 # #( # (a # (H # (H * # (H * a # (H * H # (T # (T) # H 剩余输入串 关系 (a*a) # a*a) # *a) # *a) # a) # ) # ) # ) # # # 动作 入栈 入栈 归约 入栈 入栈 归约 归约 入栈 归约

24、 成功 优缺点： 由上述分析过程可知，用算符优先分析法分析在确定句柄时只考虑终结符之间的优先关系，而与非终结符无关，这使得算符优先分析法具有效率高的优点；但是，由于去掉了单非终结符之间的归约，有可能将错误的句子识别为正确的。上例中对输入串(a*a)#能分析成功，但(a*a)#并不是文法GE的句子。这就是算符优先分析法的缺点。 第七题： (18分) 1、GS的LR(0)项目集规范族DFA： 检查发现I2 =S L.=R, R L. 中存在移进归约冲突，所以，GS不是LR(0)文法。 在I2 =S L.=R, R L. 中，由于根据归约项目R L.所得的FOLLOW(R)=,# 中含有移进项目S

25、L.=R中的“=”，当面临输入符号为“ =” 时，出现了移进归约冲突： S L .=R I2 且 go(I2,=)=I6 action2,= = S6 R L . I2 且 “=” 在FOLLOW(R)=,# 中， action2,= = r5 说明GS不是 SLR文法。 2、GS的LR(1)项目集规范族DFA： 在上面LR(1)项目集规范族的I2中，当输入#号时才用项目RL.归约；当输入=号时用项目SL.=R作移进。所以， SLR(1)不能解决的移进-归约冲突可由LR(1)方法解决。故该文法是LR(1)文法。 进一步合并LR(1)项目集规范族中同心集I4和I11、I5和I12、I7和I13、

26、I8和I10 ，得合并结果为：I4、I5 、 I7 、和I8 。显然，它们依然不含归约-归约冲突。故该文法是LALR(1)文法。 3、LALR分析表： 状态 = 0 1 2 3 4 5 6 7 8 9 4、LR算法如下：(3分) S6 r4 r3 r5 ACTION * i S4 S4 S4 r2 S5 S5 S5 # acc r5 r2 r4 r3 r5 r1 S 1 GOTO L R 2 8 8 3 7 9 设s是栈顶状态，a是输入指针ip所指向的当前符号； 1）令ip指向输入串的第一个符号；将#压入符号栈，将开始状态0压入状态栈； 2）重复执行如下过程： if 把符号a入符号栈，把状态j入状态栈； 使 ip 指向下一个输入符号。 else if 从栈顶弹出第j条规则右部串长|个符号； 把归约得到的非终结符A压入符号栈； 将gotos,A的值j压入状态栈； 并输出规则 A。 else if return； /* 分析成功 */ else error；/* 报错 */ 说明：此答案只供参考，可以是其他答案，只要意思相近即可。