编译原理期末考试试题（卷）(C卷)

./编译原理期末考试试卷〔C卷一、单项选择题〔每小题2分,共30分1、编译程序是对______程序进行翻译。A.自然语言B.汇编语言C.高级语言D.机器语言B.S→ABA→aB→bS→ABAB.S→ABA→aB→bS→ABA→Aa|aB→Bb|bD.S→D.S→aSb|εC.S→aSb|ab3、设有文法G=<{b},{S,B},S,{S→bB,B→bS|ε}>,下列哪个符号串不是该文法的句子。A.bB.bbC.bbbD.bbbbb4、下图DFA所识别的语言为_______。00BA00BA11111100D00DCA.含有偶数个0偶数个1的二进制串B.含有偶数个0奇数个1的二进制串C.含有奇数个0偶数个1的二进制串D.含有奇数个0奇数个1的二进制串5、下述正规式等价的是。A.<a|b>*与<a*b*>*B.<ab>*与a*b*C.<a|b>*与<ab>*D.<a|b>*与a*|b*6、设有一个LR<1>项目集I={X→.bB,aB→.,a}则该项目集__________。A.不含冲突项目B.含有移进-归约冲突C.含有归约-归约冲突D.含有移进-待约冲突7、LR语法分析栈中存放的状态是识别文法规范句型__________的DFA状态。A.句柄B.前缀C.活前缀D.项目8、有文法如S→rDD→D,i|i则FIRSTVT<D>=_________。A.{i}B.{i,}C.{ir}D.{ir,}9、有文法如S→rDD→D,i|i则i和,的优先关系是_________。A.没有优先关系B.等于C.低于D.高于10、算符优先分析法从左到右扫描输入串,采用移进-归约的方式,当栈顶出现___________时进行归约。A.素短语B.最左素短语C.句柄D.直接短语11、局部优化是局限于一个_________范围内的一种优化。A.程序B.函数C.基本块D.循环12、在编译中,动态存储分配的含义是_________。A.在运行阶段对源程序中的量进行存储分配B.在编译阶段对源程序中的量进行存储分配C.在说明阶段对源程序中的量进行存储分配D.以上都不正确13、以下说法正确的是_________。A.对任何一个编译程序来说,产生中间代码不是不可缺少的一部分。B.在属性文法中,文法的终结符只有综合属性,不存在继承属性。C.自下而上语法制导翻译中语法分析栈与语义分析栈必需同步操作。D.以上都正确14、后缀式abcd+*的中缀表达式是_________。A.ab*<c+d>B.a<b*c+d>C.a<b*<c+d>>D.a*<b+c>d15、有翻译模式如下：D→intL{print<L.s>;}L→id{L.s=1;}L→L1,id{L.s=L1.s+1;}采用移进归约的分析方法,当分析器的输入为inta,b,c时,输出的结果是。A.4B.3C.2D.1三、应用题〔1、4、5每题10分,2、3每题15分,共60分2、有文法如下：S→TLT→int|floatL→idRR→,idR|ε<1>.计算文法的每个非终结符的FIRST和FOLLOW集合；<1>〔8分FIRST<S>={int,float}FOLLOW<S>={#}FIRST<T>={int,float}FOLLOW<T>={id}FIRST<L>={id}FOLLOW<L>={#}FIRST<R>={,ε}FOLLOW<R>={#}4、有定义算术表达式的文法如下：E→E+T|E-T|TT→T*F|T/F|FF→PF|PP→<E>|i构造句型E-T*PF+i的语法树；并指出该句型的所有短语、直接短语、素短语、句柄。4、句型E-T*PF+i的语法树：〔5分短语：E-T*PF+i、E-T*PF、T*PF、PF、i直接短语：PF、i素短语：PF、i句柄：PF123456789101112131415CABDAACBDBCADCB.编译原理期末考试试卷〔B卷一、简述编译程序的工作过程。〔10编译程序的工作过程,是指从输入源程序开始到输出目标程序为止的整个过程,是非常复杂的,就其过程而言,一般可以划分为五个工作阶段：①词法分析,对构成源程序的字符串进行扫描和分解,识别出一个个的单词；②语法分析,根据语言的语法规则,把单词符号串分解成各类语法单位；③语义分析与中间代码产生,即对各类语法单位,分析其汉一并进行初步翻译；④代码优化,以期产生更高效的代码；⑤目标代码生成,把中间代码变换成特定机器上的低级语言指令形式。二、给出下面的正规表达式〔15以01结尾的二进制数串；能被5整除的十进制整数；包含偶数个1或偶数个0的二进制数串。〔1〔0|1*01〔2digit=0|1|2|3|4|5|6|7|8|9digit*〔0|5〔3〔〔0*10*1*0*|〔〔1*01*0*1*三、对下面的文法G：S→a|b|〔TT→T,S|S<1>消去文法的左递归,得到等价的文法G2；<2>判断文法G2是否LL〔1文法,如果是,给出其预测分析表。〔15G2：S→a|b|〔TT→ST’T’→,ST’|εG2是LL〔1文法。ab〔,#SS→aS→bS→〔TTT→ST’T→ST’T→ST’T’T’→εT’→,ST’四、对下面的文法G：S→ABA→A00|0B→B11|1<1>消去文法的左递归,得到等价的文法G2；<2>判断文法G2是否LL〔1文法,如果是,给出其预测分析表。〔15G’：S→ABA→0A’A’→00A’|εB→1B’B’→11B’|ε文法G’[S]是LL<1>文法。预测分析表：01#SS→ABAA→0A’A’A’→00A’A’→εBB→1B’B’B’→11B’B’→ε五、设有文法G[A]：A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|c计算该文法的每一个非终结符的FIRST集和FOLLOW集；试判断该文法是否为LL〔1文法。〔15FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL〔1文法。编译原理期末考试试卷〔D卷三、应用题〔1、4、5每题10分,2、3每题15分,共60分1、为正规式<a|b>*a<a|b>构造等价且状态最少的确定有限自动机。〔要求给出主要步骤2、有文法如下：S→BAA→BS|dB→aA|bS|c<1>.计算文法的每个非终结符的FIRST和FOLLOW集合；<2>.判断文法是否LL〔1文法,如果是,给出其预测分析表,否则说明理由。4、有文法如下：T→T*F|FF→PF|PP→<T>|i证明T*iP是该文法的一个句型,但不是规范句型；指出T*iP的所有短语、直接短语、素短语、句柄。三、应用题〔1、4、5每题10分,2、3每题15分,共60分abAaaabAaaBCbNFA如图〔5分：NFA如图〔5分：〔也可是其它等价的FAIIaIb1{A}{A,B}{A}2{A,B}{A,B,C}{A,C}3{A,B,C}{A,B,C}{A,C}4{A,C}{A,B}{A}用子集法得到的状态转换矩阵：用子集法得到的状态转换矩阵：确定化〔3分后的DFA如图,已是状态最少的。如不说明是最简的扣1分。确定化〔3分后的DFA如图,已是状态最少的。如不说明是最简的扣1分。化简〔2分11babaa234bab注：初态或终态错扣1分注：初态或终态错扣1分2、<1>〔6分FIRST<S>={a,b,c}FOLLOW<S>={#,a,b,c,d}FIRST<A>={a,b,c,d}FOLLOW<A>={#,a,b,c,d}FIRST<B>={a,b,c}FOLLOW<B>={a,b,c,d}<2>因为文法不含左递归,关于A的两个规则的SELECT集不相交,关于B的3个规则的SELECT集两两不相交,所以文法是LL〔1文法〔2分。预测分析表〔7分如下：abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→c4、对于符号串T*iP存在如下推导：〔或画一颗语法树证明是句型TT*FT*PFT*PPT*iP所以T*iP是该文法的一个句型,但不存在一个规范推导能推导出该句型,所以不是规范句型。〔5分短语：T*iP、iP、i、p直接短语：i、p素短语：i句柄：i2.考虑文法G[S]:S→<T>|a+S|aT→T,S|S消除文法的左递归及提取公共左因子。解：消除文法G[S]的左递归：

S→<T>|a+S|a

T→ST′

T′→,ST′|ε

提取公共左因子：

S→<T>|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε24.已知文法G[S]S→S*aF|aF|*aFF→+aF|+a消除文法左递归和提公共左因子。答：消除左递归S→aFS’|*aFS’S’→*aFS’|εF→+aF|+a提公共左因子,文法G’<S>S→aFS’|*aFS’S’→*aFS’|εF→+aF’F’→F|ε1、设文法G<S>:S→^|a|<T>T→T,S|S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表<1>消除左递,文法变为G’[S]：S→^|a|<T>'T→ST’|ST’→,ST’|ε此文法无左公共左因子。10.设文法G<S>:S→<T>|aS|aT→T,S|S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。.<1>S→<L>|aS’S’→S|εL→SL’L’→,SL’|ε<2>FIRST<S>={a,<}FIRST<S’>={a,<,ε}FIRST<L>={a,<}FIRST<L’>={,,ε}FOLLOW<S>={,,>,#}FOLLOW<S’>={,,>,#}FOLLOW<L>={>}FOLLOW<L’>={>}<3><>a,#SS→<L>S→aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’L’L’→ε已知文法G<S>：S—>a|<T>T—>T,S|S①给出句子<<a,a>,a>的最左推导并画出语法树；②给出句型<T,a,<T>>所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：〔1最左推导：S<T><T,S><S,S><a,S><a,<T>><a,<T,S>><a,<S,S>><a,<a,S>><a,<a,a>>语法树：如图A-16所示。图A-16<a,<a,a>>的语法树〔2句型<T,a,<T>>的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树〔图A-17。短语：a||T,a||<T>||T,a,<T>||<T,a,<T>>直接短语：a||<T>素短语：a||<T>最左素短语：a句柄：a活前缀：||<||<T||<T,||<T,a图A-17<T,a,<T>>的语法树二、构造下列正则表达式的确定性的有限状态自动机。〔12%aba<a|b>*a答：二、设={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA。<8分>答：构造相应的正规式：<0|1>*1<0|1><3分>NFA:<2分>111043211043200确定化：<3分>I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1