编译原理复习题目集答案

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）将NF

2、A转换成DFA：采用子集法，即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相关的多余产生式

3、2、 由新的GS构造NFA如下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)

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

5、生式的select集,G是LL(1)文法 SELECT(ETE' ) = (,i SELECT(E'+TE' ) = + 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）#文法

6、GS:S->a|(T)，T->T,S|S (1) 给出对(a,(a,a)的最左推导(2) 改写文法，去除左递归(3) 判断新文法是否LL1文法，如是，给出其预测分析表 (4) 给出输入串（a,a）#的分析过程，判断其是否文法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非终结符

7、FIRST集FOLLOW集Sa,(#,)Ta,()N,)对左部为N的产生式可知：FIRST (,S N) = , FIRST () =FOLLOW (N) =)由于SELECT(N,S N)SELECT(N)=, )=所以文法是LL(1)的。（3）预测分析表：a(),#Sa(T)TSNSNSNN,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)TSN

8、SaN,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 ；Select(MAb)= a,e, Select(M)= d,b；Select(AaM)= a , Select(Ae)= e相同左部产生式的select集的交集均为空，所以GS是LL（1）文法。预测分析表：（2）分析aaabd#是否GS的句子。 使用栈和预测分析表对输入串的分析：第6章 自底向上的语法分析

9、重点内容：算符优先文法a、 非终结符的firstvt集和lastvt集的计算b、 算符优先关系表c、 使用栈和算符优先关系表对输入串的归约题目1：课件例题：文法：EE+T|TTT×F|FF(E)|Ic、算符优先归约输入串i+i#（1）求各非终结符的FIRSTVT集与LASTVT集（2）计算算符优先关系表并说明此文法是否算符优先文法（3）给出输入串i+i#的算符优先分析过程 （1）FIRSTVT-LASTVT表：非终结符FIRSTVTLASTVTE+ × i (+ × ) iTx i (× ) i Fi () i（2）算符优先关系表：+x()i#+>

10、<<><>x>><><>(<<<=<)>>>>i>>>>#<<<<=优先关系表中无多重定义，此文法是算符优先文法（3）对输入串i+i#的算符优先分析过程为：题目2：作业、习题6.1、复习：文法GS:S->a|(T) T->T,S|S c、算符优先归约输入串（a,a）#文法GS:S->a|(T)，T->T,S|S (1) 计算GS的FIRSTVT、LASTVT(2) 改造算符优先关系表并说明GS是否算符优先文法

11、(3) 给出输入串（a,a）#的算符优先分析过程，判断其是否文法G的句子 。答：文法展开为：SaSS(T)TT,STS（1）FIRSTVT-LASTVT表：非终结符FIRSTVTLASTVTSa (a )T, a (, a )（2）算符优先关系表：a(),#a>>>>>>(<<<=<)>>>,<<<>>#<<<=表中无多重入口，所以是算符优先（OPG）文法。（3）对输入串（a,a）#的算符优先分析过程为：栈当前输入字符剩余输入串动作#(#(a#(N#(N,#(N,a#(

12、N,N#(N#(N)#N(a,a)#a,a)#,a)#a) #a) #)#Move inMove inReduce:SaMove inMove inReduce:SaReduce:TT,SMove inReduce:S(T)可见输入串（a,a）#是文法的句子。题目3：自习、书本练习6.4，参考答案见z6 书本练习6.4.doc 已知文法GS：SàS;G SàG GàG(T) GàH Hàa Hà(S) TàT+S TàSc、算符优先归约输入串a;(a+a)#（1）构造算符优先关系表FIRSTVT(S)=;FIRST

13、VT(G) = ; , a , ( FIRSTVT(G)= ( FIRSTVT(H) = a , ( FIRSTCT(H)=a , ( FIRSTVT(T) = + FIRSTVT(S) = + , ; , a , ( LASTVT(S) = ; LASTVT(G) = ; , a , )LASTVT(G) = ) LASTVT(H) = a , )LASTVT(H) = a, LASTVT(T) = + LASTVT(S) = + , ; , a , 即：FIRSTVTLASTVTS; , a , (; , a , )Ga , (a , )Ha , (a , )T+ , ; , a , (+

14、 , ; , a ,)由SàS;GLASTVT（S） > ; < FIRSTVT（G）由GàG(TLASTVT（G） > ( < FIRSTVT（T）由GàT)LASTVT（T） > )由Gà(T)( = )由TàT+SLASTVT（T） > + < FIRSTVT（S）由Hà(S)( < FIRSTVT（S）LASTVT（S） > )( = )由S-> #S#< FIRSTVT（S）LASTVT（S） > # = #;()a+#;><><>>(<<<<)>>>>>a>>>>>+<<><>#<<<由优先关系表中所有符号对的关系唯一，可判定文法GS是算符优先文法。 (2) 分析a;(aa) / SàS;G |G GàG(T) |H Hàa |(S) TàT+S |S分析栈优先关系当前字符剩余输入串动作1#<a;(aa)#移进2#a>(a