编译原理期末考试试卷及答案.pdf

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

1、n|p：诚信应考,考试作弊将带来严重后果！:华南理工大学期末考试i 编译原理试 卷A：注意事项：L 考前请将密封线内各项信息填写清楚；：2.所有答案请直接答在试卷上；色 3.考试形式：闭卷；：4.本试卷共 八 大 题，满 分 1 0 0 分，考试时间1 2 0 分钟。题 号一二三四五六七A总分得 分评卷人n|p浒二 填空(20分，每题2分)1.设G是一个文法，S是它的开始符号，如 果S二a,则称a是一个句型。仅由终结符号组成的句型是一个句子。2.在编译器的设计中，通常采用EBNF 作为描述程序设计语言语法的工具,从语法上描述程序设计语言。3.词法分析器分析的单词通常可以分为：关键词、标识符、运

2、 算 符、常数和界符几种。4.在编译器设计中，在生成源代码之前，通常在内部采用一种不依赖目标机的结构的代码表示原代码，这 种 代 码 被 称 为 中 间 代 码。5.表达式a*b+(c+d/(e+f)的逆波兰式(后缀式)为ab*cdef+/+。6.对中间代码优化按涉及的范围分为局部优化，过程间优化和全局优化。7.Z=a,b上的正规式alb的正规集是(a,b;。(应该是正则表达式所表示的串的集合吧)8.为了将非LL(1)变换为与之等价的LL(1)文法，通常采用消除左递归和提取左公共因子对文法进行等价变换。9.局部优化主要包括合并已知量、利用公共子表达式和 删除无用赋值等内容。10.运行编译程序的

3、计算机称为宿主机，运行编译程序所产生的目标代码的计算机称为目标机。言二、编 译 过 程 通 常 分 为 哪 几 个 主 要 阶 段？每 个 阶 段 的 主 要 功 能？（10分）词法分析，语 法 分 析，语义分析,中间代码生成，代 码 优 化，目标代码生成.三、设 有 文 法G S 为：(2 5分)Snumber I ListList (Seq)Seq Seq,S I Snumber 4|5其 中number是 终 结 符 表 示 数 字，其它字符均为非终结符1.试 给 出 句 型(4,(5)的 短 语，直接(简单)短语,句柄。(5分)短 语：直 接 短 语：句 柄：4S-list-(Seq)

4、-(Seq,S)-(Seq,list)-(Seq,(Seq)-(Seq,(S)-(Seq,(number)-(Seq,(5)-(S,(5)-(number,(5)-(4,(5)2.请通过消除左递归将该文法变换为等价的LL(1)文法G l。(10分)S-number I ListList (Seq)Seq Seq,S I Snumber 4|5Seq-SSeq9Seq、,SSeq1 空3.针对变换后的文法G l,构造其相应的LL(1)分析表。(10分)S number I ListList(Seq)Seq-SSeq9Seq、,SSeq1 空number 4|5对应每一条产生式，先求出其FOLLO

5、W集之间的关系1,FOLLOW(L is t)包含 FOLLOW2,FOLLOW(Seq)包含)3,FOLLOW(Scq)包含 FOLLOW(Seq),FOLLOW(S)包含 FIRST(Seq)去掉空的部分。而因为空在FIRST(Seq)中，所以 FOLLOW包含 FOLLOW(Seq)所以 FOLLOW(S)=$,)FOLLOW(LIST)=),$,)FOLLOW(Seq)=)FOLLOW(Scq,)=D)4.针对变换后的文法G 1,构造其相应的LL（。分析表。（10分）（另）三、设有文法G S 为：（25分）S-（SEQ）SEQ-SEQ,Letter LetterLetter-ab其中a

6、,b是终结符，其它字符均为非终结符。1.给出句型（b,a）的最左推导。（5分）S-（SEQ）-（SEQ,LETTER）-（LETTER,LETTER）-（b,a）2.试给出句型（b,a）的短语，直接（简单）短语,句柄。（5分）短语：直接短语：句柄：b3.请通过消除左递归将该文法变换为等价的LL(1)文法G1。(5分)S-(SEQ)SEQ-SEQ,Letter LetterLetter-abS-(SEQ)SEQ-LETTER SEQ9SEQ-,SEQ|空LETTER-a|b4.针对变换后的文法G l,构造其相应的LL（。分析表。（10分）1,FOLLOW(SEQ)包含)2,FOLLOW(SEQ)

7、包含 FOLLOW(SEQ)3,FOLLOW(SEQ)包含 FOLLOW(SEQ)FOLLOW(S)=($)FOLLOW(SEQ)=FOLLOW(SEQ,)=(),J五、文 法GS:ST(N)|4 N-N,S|S其中，(”、，)，、“”和，,，是终结符。(25分)1.构建该文法的LR(O)有穷确定自动机。10分2.构建该文法的SLR(l)分析表.15分3.请给出对输入串(a,a)#的分析过程1 0分五、把下面的语句翻译成四元式序列。(1 0分)(只给出最后结果，设ne x ts ta t当前值为1 0 0)while BD do if B=1 then D:=D+1 else B:=B*2LA

8、BEL L0T0=BDIF TO GOTO LIIF_FALSE TO GOTO L3LABEL LIT1=B=1IF_FALSE T1 GOTO L2T2=D+1D=T2LABEL L2T3=B*2B=T3T0=BDIF TO GOTOLOLABEL L3HALT(lab,L 0,_,)(GTR,B,D,T0)(IF,TO,LI,_)(IF_FALSE,T0,L3,_)(LAB,L1,_,)(EQU,B,1,T1)(IF_FALSE,TI,L2,_)(SUM,D,1,T2)(ASN,T2,D,_)(LAB,L2,_,_)(MUL,B,2,T3)(GTR,B,D,TO)(IF,TO,LO,_)(LAB,L3,_,_)(HALT,六、N F A 如下图所示（1 0 分）1 .请给出与该N F A 等价的正则表达式（3 分）(a*ba*b*)*ba*2 .请将该N F A 确定化为D F A （7 分）Ilalb0,1(2,623223,4,5,6,1234,5,6,1,23,456,1,24,5,1,6,2)124,5,62,5,6/123,4,5,6,7123,4,5,6,78,1,2,3,456,9123,4,5,6,7,8,9()