2014编译原理试卷1(参考答案)

《2014编译原理试卷1(参考答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、装订线华南农业大学期末考试试卷2参考答案考试科目：　编译原理　　考试时间：　120　分钟学号姓名年级专业题号一二三四五总分得分评阅人得分一、本题共6小题，每小题5分，共30分。1、写出下面右线性正规文法所对应的正规式。文法所对应的正规式为：a(b

2、aa)*bS→aDD→bD

3、aA

4、bA→aD2、给出下面语言集合的上下文无关文法。文法：S→aS

5、DD→aDb

6、abL1={anbm

7、n≥m≥1}3、按照编译过程的5个阶段得到编译程序的逻辑结构框图如下：5装订线4、判断下图FA是NFA还是DFA，并用正规式来描

8、述它所识别的语言。是DFA(1分)，对应的正规式为：1*01*(01*01*)*(4分)1AB0015、空心圆柱体的表面积计算公式如S=2*3.1416*(R+r)*(R-r)+2*3.1416*(R+r)*h采用LR语法制导翻译技术生成相应的三地址代码，然后运用DAG对其进行局部优化，试写出能生成最优目标代码的优化后的三地址代码序列。可以采用合并已知量、删除公共子表达式、删除无用赋值、交换语句位置等优化方法，得到三地址代码序列如下：(1)T1=R+r(2)T2=6.2832*T1(3)T3=T2*h(4

9、)T4=R-r(5)T5=T2*T4(6)S=T5+T36、有文法及其语义子程序如下：S→T{print(T.h)}T→T1*E{T.h=T1.h+E.h+1}T→E{T.h=E.h}E→（T）{E.h=T.h}E→a{E.h=1}采用移进归约的分析方法，当分析器的输入为(a)*(a*a)时，画出其语法树（可以带注释、也可以不带注释），并求输出的结果。（2分）（3分）STT*EE(T)a(T)T*EaEEa语法树：输出的结果是：55装订线得分二、构造识别下列语言的最小DFA（共20分）：1、正规式1（0

10、

11、1）*0

12、0；（7分）111DBA0010C求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。2、以101结尾的二进制串；（8分）00BAD0C11110求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。3、不以101结尾的二进制串。（5分）00CBA111100D5装订线得分三．有定义算术表达式的文法如下：E→E+T

13、E-T

14、TT→T*F

15、T/F

16、FF→PF

17、PP→(E)

18、i构造句型Pi*(E+F-T)的语法树；并指出该句型所有

19、的短语、直接短语、素短语以及句柄。（10分）（5分）短语：(2分)Pi*(E+F-T)、Pi、i、(E+F-T)、E+F-T、E+F、F直接短语：i、F(1分)素短语：i、E+F(1分)句柄：i(1分)语法树：ET*FTPFFET+T-E(E)PF5装订线四、有文法如下：（共20分）S→aBB→aDd

20、dD→Ab

21、εA→aD

22、e(1)计算文法的每个非终结符的FIRST集合和FOLLOW集合；(5分)(2)计算文法的每个候选产生式的SELECT集合；(5分)(3)说明文法是LL（1）文法的理由，并给出其预测

23、分析表；(6分)(4)给出符号串aaebd的预测分析过程（即最左推导过程）。(4分)(1).（5分）FIRST(S)={a}FOLLOW(S)={#}FIRST(B)={a,d}FOLLOW(B)={#}FIRST(D)={a,e,ε}FOLLOW(D)={b,d}FIRST(A)={a,e}FOLLOW(A)={b}(2).（5分）SELECT(S→aB)={a}SELECT(B→aDd)={a}SELECT(B→d)={d}SELECT(D→Ab)={a,e}SELECT(D→ε)={b,d}SELE

24、CT(A→aD)={a}SELECT(A→e)={e}abde#SS→aBBB→aDdB→dDD→AbD→εD→εD→AbAA→aDA→e##结束#dd##dbbd##dbeebd#A→e#dbAebd#D→Ab#dDebd##dDaaebd#B→aDd#Baebd##Baaaebd#S→aB#Saaebd#分析栈输入串所用规则符号串aaebd的最左推导过程：SÞaBÞaaDdÞaaAbdÞaaebd(3).（4分）符号串aaebd的预测分析过程：(3).（6分）如上所求结果，定义非终结符B(或D或A)的

25、两个规则的SELECT集合无交集，所以文法是LL(1)文法，其预测分析表如下：5装订线得分五、有定义二进制串的文法如下：(共20分)S→LL→0L1L→01(1).给产生式编号(1分)：S→L①L→0L1②L→01文法的识别规范句型活前缀的DFA：I5:L→0L1.I1:S→L.LI0:S→.LL→.0L1L→.0110LI2:L→0.L1L→0.1L→.0L1L→.01ACTIONGOTO01#L0S211acc2S2S4