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

1装订线华南农业大学期末考试试卷2参考答案考试科目：编译原理考试时间：120分钟学号姓名年级专业题号一二三四五总分得分评阅人一、本题共6小题，每小题5分，共30分。1、写出下面右线性正规文法所对应的正规式。2、给出下面语言集合的上下文无关文法。L1={anbm|n≥m≥1}3、按照编译过程的5个阶段得到编译程序的逻辑结构框图如下：得分S→aDD→bD|aA|bA→aD文法所对应的正规式为：a(b|aa)*b文法：S→aS|DD→aDb|ab24、判断下图FA是NFA还是DFA，并用正规式来描述它所识别的语言。5、空心圆柱体的表面积计算公式如S=2*3.1416*(R+r)*(R-r)+2*3.1416*(R+r)*h采用LR语法制导翻译技术生成相应的三地址代码，然后运用DAG对其进行局部优化，试写出能生成最优目标代码的优化后的三地址代码序列。6、有文法及其语义子程序如下：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)时，画出其语法树（可以带注释、也可以不带注释），并求输出的结果。1AB001是DFA(1分)，对应的正规式为：1*01*(01*01*)*(4分)可以采用合并已知量、删除公共子表达式、删除无用赋值、交换语句位置等优化方法，得到三地址代码序列如下：(1)T1=R+r(2)T2=6.2832*T1(3)T3=T2*h(4)T4=R-r(5)T5=T2*T4(6)S=T5+T3输出的结果是：5语法树：STT*EE(T)a(T)T*EaEEa（3分）（2分）3装订线二、构造识别下列语言的最小DFA（共20分）：00100102、以101结尾的二进制串；（8分）得分1、正规式1（0|1）*0|0；（7分）3、不以101结尾的二进制串。（5分）A1BD100C101ABCD01101ABCD0111求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。求出NFA得4分，确定化了得6分，最小DFA的状态错漏一个扣1分，弧错漏一条扣0.5分。4三．有定义算术表达式的文法如下：E→E+T|E-T|TT→T*F|T/F|FF→PF|PP→(E)|i构造句型Pi*(E+F-T)的语法树；并指出该句型所有的短语、直接短语、素短语以及句柄。（10分）得分短语：(2分)Pi*(E+F-T)、Pi、i、(E+F-T)、E+F-T、E+F、F直接短语：i、F(1分)素短语：i、E+F(1分)句柄：i(1分)语法树：（5分）ETT*FFPPF(E)E-TE+TF5装订线四、有文法如下：（共20分）S→aBB→aDd|dD→Ab|εA→aD|e(1)计算文法的每个非终结符的FIRST集合和FOLLOW集合；(5分)(2)计算文法的每个候选产生式的SELECT集合；(5分)(3)说明文法是LL（1）文法的理由，并给出其预测分析表；(6分)(4)给出符号串aaebd的预测分析过程（即最左推导过程）。(4分)abde#SS→aBBB→aDdB→dDD→AbD→εD→εD→AbAA→aDA→e(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}SELECT(A→aD)={a}SELECT(A→e)={e}(3).（6分）如上所求结果，定义非终结符B(或D或A)的两个规则的SELECT集合无交集，所以文法是LL(1)文法，其预测分析表如下：(3).（4分）符号串aaebd的预测分析过程：符号串aaebd的最左推导过程：SaBaaDdaaAbdaaebd分析栈输入串所用规则#Saaebd##Baaaebd#S→aB#Baebd##dDaaebd#B→aDd#dDebd##dbAebd#D→Ab#dbeebd#A→e#dbbd##dd###结束6五、有定义二进制串的文法如下：(共20分)S→LL→0L1L→01ACTIONGOTO01#L0S211acc2S2S433S54r2r25r1r1符号栈状态栈输入串动作#00011#S2#002011#S2#0002211#S4#00102241#r2#0L0231#S5#0L10235#r1#L01#acc得分(1).给产生式编号(1分)：S→L①L→0L1②L→01文法的识别规范句型活前缀的DFA：I0:S→.LL→.0L1L→.01I1:S→L.LI2:L→0.L1L→0.1L→.0L1L→.011L1I4:L→01.0I3:L→0L.1I5:L→0L1.0(2).上一步DFA各状态所识别的活前缀（4分）分别是：I0:ε；I1:L；I2:00*；I3:0*0L；I4:0*01；I5:0*0L1；(3).因为上面DFA各状态都不含冲突，所以文法是LR(0)文法，也是SLR(1)文法。（1分）FOLLOW(L)={1,#}，SLR(1)分析表如下：LR（0）分析表如下（5分）：(4)符号串aaee的LR分析过程（4分）：(4)符号串0011的LR分析过程：