编译原理复习参考题.doc

写一个文法，使其语言是奇数集，且每个奇数不以0开头。并画出串135的分析树。参考答案：S AD | DA AB | CB 0 | CC 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9D 1 | 3 | 5 | 7 | 9分析：其正则表达式为1-90-9*(13579) | (13579)。可将前一部分用左递归文法表示。4. 有文法G如下：S S(S) |试写出一个语法制导语义的属性文法，它输出配对的括号个数。参考答案：属性文法如下：S1 S2 ( S3 )S1.num = S2.num+S3.num+1S S.num = 0分析：前一个产生式将增加一个括号，并可能在S2或S3中重复匹配产生括号a. LL(1)文法一定无二义性。因为对任何LL(1)文法G，在其LL(1)分析表中没有产生冲突的产生式。故对文法G的语言L(G)中的每个句子(即记号串)w，其最左推导过程中的每一个推导步骤(均由LL(1)分析算法给出！)都是唯一确定的，因而该句子的分析树也是唯一确定的。根据定义，文法G无二义性。b. 二义性文法不会是LL(1)文法。因为对任何二义性文法G，必定存在某一个句子w，它有两个不同的分析树。因而，句子w有两个不同的最左推导。 因而，它至少存在一个不同的推导步骤，可以选择两个不同的产生式进行最左推导。因此，在该文法的LL(1)分析表中，至少有一个单元格中存在两个可选的产生式。因此，该文法G不会是LL(1)文法。c. 非二义性文法不一定是LL(1)文法。因为包含左递归和左因子的无二义性文法显然不是LL(1)文法。生成语言L(G)=albmclanbn, l=0, m=1, n=2的文法G是什么？它是chomsky那一型的文法？参考答案：S A BA aAc | DD bD | b (也可用左递归！)B aBb | aabb它是属于chomsky的第2型文法，即：上下文无关文法。分析：要掌握左、中、右递归文法的语言特征；注意怎样组合它们；注意最少的重复次数，它往往变成非终结符的基本情况的定义。3. 请写出在a,b上，不是a开头的，以aa结尾的字符串集合的正则表达式，并构造与之等价的DFA图。参考答案：正则表达式 = b(a|b)*aa 。12bb3ab4ab等价的DFA图如下：d.e.3. 一个人带着狼、山羊和白菜来到一条河边，想要到河对岸去。岸边有一条小船，小船只能装下这个人以及狼、山羊和白菜中之一。如果没有人照看，狼会吃掉山羊，山羊会吃掉白菜。试问它们能不能安全地渡河？如果可能，请用有穷自动机写出渡河的方法。参考答案：能安全地渡河。先定义：人=M，狼=W，山羊=G，白菜=C。字符集为每次渡河的成员，故=M，MW，MG，MC。状态集为河边和对岸的情况，用双竖线表示河。因此，开始状态为：MWGC|，接受状态为：|MWGC。DFA图如下：MWGC|WC|MGMGMWC|GMW|MGCMCC|MWGMWMWG|CMGMGC|WMGMWG|MWCMCMG|WCM|MWGCMG3. 已知文法G为： A aABc | a B Bb | d1) 试给出与G等价的LL(1)文法G;2) 构造G的LL(1)分析表;3) 给出输入串aadc的分析过程。参考答案：1) 对文法G提取左因子、消除左递归后，可得文法G如下：A aAA ABc |B dBB bB |2) 对文法G求First集合和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)分析表为：$dcbaMN,TAaAAAAAABcABdBBBBbBB从上表可知，文法G是LL(1)文法。3) 串aadc的分析过程用最左推导简单表示如下：(详细说明要基于LL(1)分析栈进行)A aA aABc aaABc aaBc aadBc aadc。4. 已知文法G为：S dABA aA | aB Bb |1) 试问G是否为正规文法，为什么？2) G产生的语言是什么？3) G能否改写为等价的正规文法？如能，请写出等价的正则表达式。参考答案：1) 文法G不是正规文法。因为它既