资源描述：
《【8A版】编译原理复习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、【MeiWei81-优质实用版文档】二、概念题1、设有文法：P→P+Q
2、QQ→QGR
3、RR→(P)
4、i（1）证明QGR+Q+Q是它的一个句型。（3分)（2）给出QGR+Q+Q的所有短语，直接短语和句柄。(4分)（3）给出句子ｉ+ｉGｉ的最右推导。(4分)（4）给出句子ｉ+ｉGｉ的最左推导。(4分)2、设有文法：E→E+T
5、TT→TGF
6、FF→(E)
7、i（1）证明E+TGF是它的一个句型。（3分)答案：（2）给出E+TGF的所有短语，直接短语和句柄。(4分)短语:E+TGF,TGF,直接短语:TGF句柄:TGF（3）给出句子ｉ+ｉGｉ的最右推导。(4分)3、写出表达式a+b
8、G(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-G+)三元式序列:OPARG1ARG2(1)-cd(2)Gb(1)(3)+a(2)三、词法分析题给出下面语言的相应文法L1={anbnambm
9、n,m≥0}【MeiWei81-优质实用版文档】【MeiWei81-优质实用版文档】答案：S→AB
10、A
11、B
12、∑A→aAb
13、abB→aBb
14、ab给出下面语言的相应文法L2={anbnci
15、n≥1,i≥0}答案：S→AB
16、BA→a
17、aAB→bBc
18、bc给出下面语言的相应文法L3={anbncm
19、m,n≥1，n为奇数，m为偶数}。答案：文法G(S):S→ACA→aaAb
20、b/abC→ccCcc/cc四、词法分析题1、构造下面正规式相应的DFA((0
21、1)G
22、(11)G)G（要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA1(0
23、1)G101答案：II0I1{G}Ф{A,B,C}{A,B,C}{B,C}{B,C,D}{B,C}{B,C}{B,C,D}【MeiWei81-优质实用版文档】【MeiWei81-优质实用版文档】{B,C,D}{B,C,E}{B,C,D}{B,C,E}{B,C}{B,C,D,y}{B,C,D,y}{B,C,E}{B,C,D}3、构造一个DFA，它接受S={a，b}上所有包含ab的
24、字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a
25、b)Gab(a
26、b)G(二)①与此正规式对应的NFA为②状态转换矩阵为：③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}baa01b3ba④所以此等价的DFA为：开始状态为0，终态集为{3}，状态集为{0,1,3}，输入字母表是{a,b}状态转换图如上。4、构造与正规式b(a
27、b)Gba等价的DFA五、语法分析题1、对下面的文法G:【MeiWei81-优质实用版文档】【MeiWei81-优质实用版文档】EGpr→-EGprEGpr→(EGpr)
28、VarEG
29、prTailEGprTail→-EGpr
30、εVar→idVarTailVarTail→(EGpr)
31、ε（1）构造LL(1)分析表。（12分）答案：（1）FIRST(EGpr)={_,(,id}FIRST(EGprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(,ε}FOLLOW(EGpr)={#,)}FOLLOW(EGprTail)={#,)}FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}（2）给出对句子id—id((id))的分析过程。（8分）步骤符号栈输入串所用产生式0＃EGprid__id(
32、(id))＃1#EGprTailVarid__id((id))＃EGpr→VarEGprTail2#EGprTailVarTailidid__id((id))＃Var→idVarTail3#EGprTailVarTail__id((id))＃4#EGprTail__id((id))＃VarTail→ε5#EGpr___id((id))＃EGprTail→_EGpr6#EGpr_id((id))＃7#EGpr__id((id))＃EGpr→_EGpr8#EGprid((id))＃9#EGprTailVarid((id))＃EGpr→VarEGprTail10#EGprTai
33、lVarTailidid((id))＃Var→idVarTail11#EGprTailVarTail((id))＃【MeiWei81-优质实用版文档】【MeiWei81-优质实用版文档】12#EGprTail)EGpr(((id))＃VarTail→(EGpr)13#EGprTail)EGpr(id))＃14#EGprTail))EGpr((id))＃EGpr→(EGpr)15#EGprTail))EGprid))＃16#EGprTail))EGprTailVarid))＃EGp→VarEGprTail17#EGprTail)
