资源描述：
《编译原理复习参考题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。并画出串135的分析树。参考答案：S→AD
2、DA→AB
3、CB→0
4、CC→1
5、2
6、3
7、4
8、5
9、6
10、7
11、8
12、9D→1
13、3
14、5
15、7
16、9分析：其正则表达式为[1-9][0-9]*(13579)
17、(13579)。可将前一部分用左递归文法表示。4.有文法G如下：S→S(S)
18、ε试写出一个语法制导语义的属性文法，它输出配对的括号个数。参考答案：属性文法如下：S1→S2(S3)S1.num=S2.num+S3.num+1S→εS.num=0分析：前一个产生式将增加一个括号，并可能在S2或S3中重复匹配产生括号a
19、.LL(1)文法一定无二义性。因为对任何LL(1)文法G，在其LL(1)分析表中没有产生冲突的产生式。故对文法G的语言L(G)中的每个句子(即记号串)w，其最左推导过程中的每一个推导步骤(均由LL(1)分析算法给出！)都是唯一确定的，因而该句子的分析树也是唯一确定的。根据定义，文法G无二义性。b.二义性文法不会是LL(1)文法。因为对任何二义性文法G，必定存在某一个句子w，它有两个不同的分析树。因而，句子w有两个不同的最左推导。因而，它至少存在一个不同的推导步骤，可以选择两个不同的产生式进行最左推导。因此，在该文法的LL(1)分析表中，至少有一个
20、单元格中存在两个可选的产生式。因此，该文法G不会是LL(1)文法。c.非二义性文法不一定是LL(1)文法。因为包含左递归和左因子的无二义性文法显然不是LL(1)文法。生成语言L(G)={albmclanbn,l>=0,m>=1,n>=2}的文法G是什么？它是chomsky那一型的文法？参考答案：S→ABA→aAc
21、DD→bD
22、b(也可用左递归！)B→aBb
23、aabb它是属于chomsky的第2型文法，即：上下文无关文法。分析：要掌握左、中、右递归文法的语言特征；注意怎样组合它们；注意最少的重复次数，它往往变成非终结符的基本情况的定义。3.请写出在
24、∑＝{a,b}上，不是a开头的，以aa结尾的字符串集合的正则表达式，并构造与之等价的DFA图。参考答案：正则表达式=b(a
25、b)*aa。12bb3ab4ab等价的DFA图如下：a.b.3.一个人带着狼、山羊和白菜来到一条河边，想要到河对岸去。岸边有一条小船，小船只能装下这个人以及狼、山羊和白菜中之一。如果没有人照看，狼会吃掉山羊，山羊会吃掉白菜。试问它们能不能安全地渡河？如果可能，请用有穷自动机写出渡河的方法。参考答案：能安全地渡河。先定义：人=M，狼=W，山羊=G，白菜=C。字符集为每次渡河的成员，故∑={M，MW，MG，MC}。状态集为河边和
26、对岸的情况，用双竖线表示河。因此，开始状态为：MWGC
27、
28、φ，接受状态为：φ
29、
30、MWGC。DFA图如下：MWGC
31、
32、φWC
33、
34、MGMGMWC
35、
36、GMW
37、
38、MGCMCC
39、
40、MWGMWMWG
41、
42、CMGMGC
43、
44、WMGMWG
45、
46、MWCMCMG
47、
48、WCMφ
49、
50、MWGCMG3.已知文法G为：A→aABc
51、aB→Bb
52、d1)试给出与G等价的LL(1)文法G';2)构造G'的LL(1)分析表;3)给出输入串aadc的分析过程。参考答案：1)对文法G提取左因子、消除左递归后，可得文法G’如下：A→aA’A’→ABc
53、εB→dB’B’→bB’
54、ε2)对文法G’求F
55、irst集合和Follow集合，得：First(A)={a};First(A’)={a,ε};First(B)={d};First(B’)={b,ε};Follow(A)={d,$};Follow(A’)={d,$};Follow(B)={c};Follow(B’)={c};因而可得文法G’的LL(1)分析表为：$dcbaM[N,T]A→aA’AA’→εA’→εA’→ABcA’B→dB’BB’→εB’→bB’B’从上表可知，文法G’是LL(1)文法。3)串aadc的分析过程用最左推导简单表示如下：(详细说明要基于LL(1)分析栈进行)AÞaA’Þ
56、aABcÞaaA’BcÞaaBcÞaadB’cÞaadc。4.已知文法G为：S→dABA→aA
57、aB→Bb
58、ε1)试问G是否为正规文法，为什么？2)G产生的语言是什么？3)G能否改写为等价的正规文法？如能，请写出等价的正则表达式。参考答案：1)文法G不是正规文法。因为它既不是左线性文法，又不是右线性文法。2)G产生的语言L(G)={dambn
59、m≥1，n≥0}。3)能改写成等价的正规文法：S→Sb
60、AA→Aa
61、da其等价的正则表达式为：da+b*。
