资源描述：
《编译原理05联办试卷1答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、大庆师范学院2008——2009学年第一学期《编译原理》期末考试试卷答案与评分标准大庆师范学院2005级计算机科学与技术专业（联办）《编译原理》期末考试试卷1答案与评分标准一．单项选择题(每题1分，共15分)1．B2．D3．D4．C5．B6．A7．C8．B9．A10．B11．C12．D13．D14．B15．B二、填空题（每空1分，共20分）1．是否生成目标程序（是否有目标代码生成）2．构词语义3．静态、栈式动态、堆式动态4保留字（或关键字）常数运算符(图1)（5分）5．自上而下、自下而上、递归下降分析法、LL（1）分析法、算符优先分析方法、LR分析方法6．2（上
2、下文无关），3（正规），上下文无关，正规，有限三、判断题（每题2分，共20分）1．错误2．正确3．错误4．正确5．错误6．错误7．正确8．正确9．正确10．错误四、应用题(1题10分，2题15分，3、4题各10分，共45分)1.解:DFAMn的状态转换图见图1，状态转换矩阵见下表。（5分）状态字符abs0s1s2s1s1s2S2S2s1评分标准：本题满分10分。有符号错误，出现2处扣1分。2．解：(1)将G[A]改造为LL(1)文法:G′[A]:A→aA′A′→ABl
3、εB→dB′B′→bB′
4、ε（4分，错1个扣1分）求得:FIRST(A)={a},FIRST(
5、A′)={a,ε}FIRST(B)={d},FIRST(B′)={b,ε}（4分，错1个扣1分）对文法开始符号A,有FOLLOW(A)={#}.由A′→ABl得FIRST(B){ε}FOLLOW(A),即FOLLOW(A)={#,d};由A′→ABl得FIRST('l')FOLLOW(B),即FOLLOW(B)={l};由A→aA′得FOLLOW(A)FOLLOW(A′),即FOLLOW(A)={#,d};由B→dB′得FOLLOW(B)FOLLOW(B′),即FOLLOW(B′)={l}.（4分，错1个扣1分）对A′→ABl来说,FIRST(A)∩FOLLO
6、W(A′)={a}∩{#,d}=,所以文法G[A′]为所求等价的LL(1)文法.第2页（共2页）大庆师范学院2008——2009学年第一学期《编译原理》期末考试试卷答案与评分标准(2)构造预测分析表如下:（3分，错2个扣1分）abld#AA→aA′A′A′→ABlA′→εA′→εBB→dB′B′B′→bB′B′→ε3．解：语句i+i*i的LR分析过程如下：步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION[0,i]=s5，即状态5入栈205#i+i*i#r6:用F→i归约且GOTO(0,F)=3入栈303#F+i*i#r4:用T→F归约且GOTO(0,
7、T)=2入栈402#T+i*i#r2:用E→T归约且GOTO(0,E)=1入栈501#E+i*i#ACTION[1,+]=s6，即状态6入栈6016#E+i*i#ACTION[6,i]=s5，即状态5入栈70165#E+i*i#r6:用F→i归约且GOTO(6,F)=3入栈80163#E+F*i#r4:用T→F归约且GOTO(6,T)=9入栈90169#E+T*i#ACTION[9,*]=s7，即状态7入栈1001697#E+T*i#ACTION[7,i]=s5，即状态5入栈11016975#E+T*i#r6:用F→i归约且GOTO(7,F)=10入栈12016
8、9710#E+T*F#r3:用T→T*F归约且GOTO(6,T)=9入栈130169#E+T#r1:用E→E+T归约且GOTO(0,E)=1入栈1401#E#Acc:分析成功评分标准：本题满分10分。本题15行，前5行每行1分，后续10行每2行1分，完全正确得10分；个别符号错误，出现2处扣1分。4．解：100(=，0，_，X)（1分）101(j<，X，10，103)（1分）102(j，_，_，106)（1分）103(+，X，1，T)（1分）104(=，T，_，X)（1分）105(j，_，_，101)（4分）106（1分）第2页（共2页）
