编译原理复习题.doc

编译原理复****题设G=<VN,VT,P,<S>)是上下文无关文法,产生式集合P中任意一个产生式应具有什么样的形式?若G是正则文法呢?答:一般形式为<v>→a,<v>ÎVN,aÎ(VN∪VT>*。 若G是正则文法,则一般形式为<A>→a<B>或<A>→a,<A>、<B>ÎVN,aÎVT<或<A>→<B>a,<A>→a)。b5E2RGbCAP何谓二义性文法?试举一例说明。答:若文法G的一个句子对应有两棵或两棵以上不同的推导树,则称该句子是二义性的。产生二义性句子的文法称为二义性文法,否则该文法是无二义性的。p1EanqFDPw 例子:给定文法G[<R>]:<R>→<R>*|<R><R>|a|b考察句子ab*,它有两棵不同的推导树,如下所示:试正确消除下述传递图的e弧,使其接收的语言不变。1-e-Se11110e,100ee+ABCDEFG答:试将下述程序段翻译成三地址形式的中间代码表示。①5+6´<a+b)。答::100:t1:=a+b 101:t2:=6*t1 102:t3:=5+t2②ØAÚ<BÙ<CÚD))。答:200: ifAgoto202 201: gotoT 202: ifBgoto204 203: gotoF204: ifCgotoT 205: goto206 206: ifDgotoT 207: gotoF③forj:=1to10doa[j+j]:=0。答:300: j:=1301: ifj10gotoNEXT302: i:=j+j303: a[i]:=0304: goto301④while(a+b<cORa=b>while(a<5ANDb<10>{a=a+1。b=b+1。}答:三地址代码如下: 100: t:=a+b 101: ift<cgoto105 102: goto103 103: ifa=bgoto105 104: goto0 105: ifa<5goto107 106: goto100 107: ifb<10goto109 108: goto100 109: a:=a+1 110: b:=b+1 111: goto105 112: ⑤ifx>ythenx:=10elsex:=x+y。答:400: ifxygoto402401: goto404402: x:=10403: goto405404: x:=x+y405:试判定下述文法G[<S>]是否是LR<1)文法?为什么?<S>→<A><A><A>→<A>a<A>→a答:1)因为对文法G[<S>]存在的句子aaa,有两棵不同的推导树,。,G[<S>]不是LR(1>文法。2)可构造文法G[<S>]的状态集,考虑增广文法G[<S’>],。[<S’>]的LR(1>状态集状态T项目集输入符号下一状态0[<S’>→·<S>⊥,Ù]<S>1[<S>→·<A><A>,⊥]<A>2[<A>→·<A>a,a]<A>2[<A>→·a,a]a31[<S’>→<S>·⊥,Ù]⊥Accept2[<S>→<A>·<A>,⊥]<A>[<A>→<A>·a,a]a4[<A>→·<A>a,a/⊥]<A>[<A>→·a,a/⊥]a43[<A>→a·,a]a#34[<A>→<A>a·,a]a#2[<A>→a·,a/⊥]a/⊥#3到