资源描述：
《编译原理复习题目集答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章词法分析重点内容：正规式转化为DFAa、正规式->NFAb、NFA->DFA（子集法）c、DFA化简（分割法）题目1：课件例题：a、为R=(a
2、b)*(aa
3、bb)(a
4、b)*构造NFAb、从NFA构造DFA的算法c、化简12题目2：4.7例1：构造正规式相应的DFA：1(0
5、1)*101按照以下三步：（1）由正规表达式构造转换系统（NFA）（2）由转换系统（NFA）构造确定的有穷自动机DFA（3）DFA的最小化答：（1）构造与1(0
6、1)*101等价的NFA(0
7、1)*111(0
8、1)*101XYXABCDY10
9、XABCY11010,1（2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合：01XAAAABABACABACAABYABYACAB除X，A外，重新命名其他状态：01XAAAB12BCBCADDCB1、将M的状态分成非终态和终态集{X,A,B,C}和{D}。2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。最后生成DFA：XABCD110100101题目3：自习、书本练习4.7，参考答案见《z4书本练习4.7.doc》已知文法G[S
10、]：S→aA
11、bQA→aA
12、bB
13、bB→bD
14、aQQ→aQ
15、bD
16、bE→aB
17、bFF→bD
18、aE
19、b1、构由于不可到达，去除E、F相关的多余产生式2、由新的G[S]构造NFA如下123、NFA的转换表：abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD4、子集法重命名状态：（上标0：初态，*：终态）ab00131122*343354165*14634125、使用分割法化简以上DFAG：5.1令G={(0,1,3,4,6),(2,5)}//分别为非终态和终态集5.2由{0,1,3,4,6}a={1,3}，{0,
20、1,3,4,6}b={3,2,5,6,4}将{0,1,3,4,6}划分为{0,4,6}{1,3}，得G={(0,4,6),(1,3),(2,5)}5.3由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={(0),(4,6),(1,3),(2,5)}5.4观察后，G中状态不可再分，为最小化DFA。6、分别用0，4，1，2代表各状态，DFA状态转换图如下：造相应的最小的DFA第5章自顶向下的语法分析重点内容：LL（1）文法a、去除左递归b、LL（1）文法的判定（first、follow、select集）
21、c、预测分析表d、使用栈和预测分析表对输入串的分析题目1：课件例题：消除左递归+判定+分析算术表达式文法G E→E+T│TT→T*F│FF→(E)│Id、分析输入串i+i*i#12（1）消除G的左递归得到文法G‘E→TE'E'→+TE'│εT→FT'T'→*FT'│εF→(E)│i（2）求出每个产生式的select集,G’是LL(1)文法SELECT(E→TE')={(,i}SELECT(E'→+TE')={+}SELECT(E'→ε)={),#}SELECT(T→FT')={(,i}SELECT(T'→*FT')={*
22、}SELECT(T'→ε)={+,),#}SELECT(F→(E))={(}SELECT(F→i)={i}（3）依照选择集合把产生式填入分析表注：表中空白处为出错题目2：作业、习题5.1：消除左递归+判定+分析G[S]:S->a
23、^
24、(T)T->T,S
25、Sd、分析输入串（a,a）#文法G[S]:S->a
26、^
27、(T)，T->T,S
28、S(1)给出对(a,(a,a))的最左推导(2)改写文法，去除左递归(3)判断新文法是否LL1文法，如是，给出其预测分析表(4)给出输入串（a,a）#的分析过程，判断其是否文法G的句子。答：（1
29、）对(a,(a,a))的最左推导为：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))（2）改写文法为：120)S→a1)S→ʌ2)S→(T)3)T→SN4)N→,SN5)N→ε非终结符FIRST集FOLLOW集S{a,ʌ,(}{#,,,)}T{a,ʌ,(}{)}N{,,ε}{)}对左部为N的产生式可知：FIRST(→,SN)={,}FIRST(→ε)={ε}FOLLOW(N)={)}由于SELECT(N→,SN
30、)∩SELECT(N→ε)={,}∩{)}=ᴓ所以文法是LL(1)的。（3）预测分析表：aʌ(),#S→a→ʌ→(T)T→SN→SN→SNN→ε→,SN可由预测分析表中，无多重入口判定文法是LL（1）的。（4）对输入串（a,a）#的分析过程为：栈当前输入符剩余输入符所用产生式#S#)T(#)T#)NS#)Na#)N#
