编译原理复习题目集答案

1、第4章 词法分析重点内容：正规式转化为DFAa、 正规式-NFAb、 NFA - DFA（子集法）c、 DFA化简（分割法）题目1：课件例题：a、 为 R=(a|b)*(aa|bb)(a|b)*构造 NFA b、 从NFA构造DFA的算法c、 化简题目2：4.7 例1：构造正规式相应的DFA：1(0|1)*101按照以下三步：（1）由正规表达式构造转换系统（NFA）（2）由转换系统（NFA）构造确定的有穷自动机DFA（3）DFA的最小化答：（1）构造与1(0|1)*101等价的 NFA(0|1)*111(0|1)*101XYXABCDY10XABCY11010,1（2）将NFA转换成DFA：采

2、用子集法，即DFA的每个状态对应NFA的一个状态集合：01XAAAABABACABACAABYABYACAB除X，A外，重新命名其他状态：01XAAABBCBCADDCB1、将M的状态分成非终态和终态集X,A,B,C和D。2、寻找子集中不等价状态X,A,B,C=X，A,BC=XABC，无需合并。最后生成DFA：XABCD110100101题目3：自习、书本练习4.7，参考答案见z4 书本练习4.7.doc 已知文法GS：SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b EaB|bF FbD|aE|b1、 构由于不可到达，去除E、F相关的多余产生式2、 由新的GS构造NFA如下3、

3、 NFA的转换表：abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD4、子集法重命名状态：（上标0：初态，*：终态）ab00131122*343354165*146345、使用分割法化简以上DFA G：5.1 令G=(0,1,3,4,6),(2,5)/ 分别为非终态和终态集5.2 由0,1,3,4,6a=1,3，0,1,3,4,6b=3,2,5,6,4 将0,1,3,4,6划分为 0,4,61,3，得G=(0,4,6),(1,3),(2,5)5.3 由0,4,6b=3,6,4，将之划分为0,4,6，得G=(0),(4,6),(1,3),(2,5) 5.4 观察后，G中状态不可再分，

4、为最小化DFA。6、分别用 0，4，1，2代表各状态，DFA状态转换图如下：造相应的最小的DFA第5章 自顶向下的语法分析重点内容：LL（1）文法a、 去除左递归b、 LL（1）文法的判定（first、follow、select集）c、 预测分析表d、 使用栈和预测分析表对输入串的分析题目1：课件例题：消除左递归+判定+分析算术表达式文法GEE+TTTT*FFF(E)Id、分析输入串i+i*i#（1）消除G的左递归得到文法 GETE E+TE TFT T*FTF(E)i（2）求出每个产生式的select集,G是LL(1)文法 SELECT(ETE ) = (,i SELECT(E+TE ) =

5、 + SELECT(E ) = ),# SELECT(TFT ) = (,i SELECT(T*FT ) = * SELECT(T ) = +,),# SELECT(F(E) ) = ( SELECT(F i ) = i （3）依照选择集合把产生式填入分析表注：表中空白处为出错题目2：作业、习题5.1：消除左递归+判定+分析GS:S-a|(T) T-T,S|S d、分析输入串（a,a）#文法GS:S-a|(T)，T-T,S|S (1) 给出对(a,(a,a)的最左推导(2) 改写文法，去除左递归(3) 判断新文法是否LL1文法，如是，给出其预测分析表 (4) 给出输入串（a,a）#的分析过程，

6、判断其是否文法G的句子 。答：（1）对(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） 改写文法为： 0)Sa 1) S 2) S(T) 3) TSN 4) N,SN 5) N非终结符FIRST集FOLLOW集Sa,(#,)Ta,()N,)对左部为N的产生式可知：FIRST (,S N) = , FIRST () =FOLLOW (N) =)由于SELECT(N,S N)SELECT(N)=, )=所以文法是LL(1)的。（3）预测分析表：a(),#Sa(T)TSNSNSN

7、N,SN可由预测分析表中，无多重入口判定文法是LL（1）的。（4）对输入串（a,a）#的分析过程为：栈当前输入符剩余输入符所用产生式#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#(aaa,aa)#a,a)#a,a)#,a)#,a)#,a)#a)#a)#)#)#S(T)TSNSaN,SNSaN可见输入串（a,a）#是文法的句子。题目3：复习、书本5.6例1：判定+分析GS：SaH，HaMd|d，MAb|，AaM|ed、分析输入串aaabd#（1）判断GS是否为LL（1）文法；若是，构造其预测分析表；Select(HaMd)=a , Select(Hd)= d ；S

8、elect(MAb)= a,e, Select(M)= d,b；Select(AaM)= a , Select(Ae)= e相同左部产生式的select集的交集均为空，所以GS是LL（1）文法。预测分析表：（2）分析aaabd#是否GS的句子。 使用栈和预测分析表对输入串的分析：第6章 自底向上的语法分析重点内容：算符优先文法a、 非终结符的firstvt集和lastvt集的计算b、 算符优先关系表c、 使用栈和算符优先关系表对输入串的归约题目1：课件例题：文法：EE+T|TTTF|FF(E)|Ic、算符优先归约输入串i+i#（1）求各非终结符的FIRSTVT集与LASTVT集（2）计算算符优

9、先关系表并说明此文法是否算符优先文法（3）给出输入串i+i#的算符优先分析过程 （1）FIRSTVT-LASTVT表：非终结符FIRSTVTLASTVTE+ i (+ ) iTx i ( ) i Fi () i（2）算符优先关系表：+x()i#+x(=i#a|(T) T-T,S|S c、算符优先归约输入串（a,a）#文法GS:S-a|(T)，T-T,S|S (1) 计算GS的FIRSTVT、LASTVT(2) 改造算符优先关系表并说明GS是否算符优先文法 (3) 给出输入串（a,a）#的算符优先分析过程，判断其是否文法G的句子 。答：文法展开为：SaSS(T)TT,STS（1）FIRSTVT-LASTVT表：非终结符FIRSTVTLASTVTSa (a )T, a (, a )（2）算符优先关系表：a(),#a(=,# ; ( )由G(T)( = )由TT+SLASTVT（T） + FIRSTVT（S）由H(S)( )( = )由S- #S# # = #;()a+#;(a+#由优先关系表中所有符号对的关系唯一，可判定文法GS是算符优先文法。 (2) 分析a;(aa) / SS;G |G GG(T) |H Ha |(S) TT+S |S分析