编译原理第一次小作业

1、wordHomework1向首兴20140134211 .语法分析程序的主要任务是什么？简述自顶向下语法分析的思想。答：语法分析程序的任务：1,分析源程序的单词流是否符合语言的语法规则；2,报告语法错误；3,产生源程序的语法分析结果，以语法分析树或与之等价的形式体现出来。自顶向下语法分析的思想：从文法开始符号出发进行推导，每一步推导都对当前句型中剩余的某个非终结符进行扩展，进而获得文法的一个句型，直到产生出所期望的终结符串，如果不存在可以产生出所期望的终结符串的推导，则表明语法错误。2 .对文法GS:S-a|&l(T)T一T,S|S给出(a,(a,a)和(a,a),&,(a),

2、a)的最左推导。答：I .(a,(a,a):S一一(T,S)一(S,S)(a,S)一(a,(T)一(a,(T,S)一(a,(S,S)一(a,(a,S)一(a,(a,a)II .(a,a),&,(a),a):S一一(T,S)一(S,S)一(T),S)一(T,S),S)一(T,S,S),S)一(S,S,S),S)一(T),S,S),S)一(T,S),S,S),S)-(S,S),S,S),S)-(a,S),S,S),S)-(a,a),S,S),S)一(a,a),&,S),S)一(a,a),&,(T),S)一(a,a),&,(S),S)一(a,a),&,(a),

3、S)气(懒,硼3 .判断下面文法是否为LL(1)文法，并说明理由。(1)SfAB|PQxA一xyB一bcP一dP|£Q一aQ|e答：First(A)=xFollow(S)=#First(B)=bFollow(A)=bFirst(P)=d,eFollow(B)=#First(Q)=a,eFollow(Q)=xFirst(S)=x,d,aFollow(P)=a,xForS:First(AB)nFirst(PQx)=xnd,a,x=x由上验证：该文法不是LL(1)文法。(2)S一TPTf+PT|P-(S)Ia答：First(P)=(,aFollow(S)=#,)First(T)=+,歼ol

4、low(T)=(,aFirst(S)=+,aFollow(P)=+,(,a,#,)ForT:First(+PT)nFirst(e)丹n=?First(+PT)nFollow(T)=+n(,a=?ForP:First(S)nFirst(a)=(na=?由上验证：该文法是LL(1)文法。4 .验证如下文法是LL(1)文法。若是，则请构造递归下降分析程序。(1)E一Aa|BbA一cA|eBB一bdFollow(E) = #Follow(A) = aFollow(B) = a, b答：First(A)=c,eFirst(B)=bFirst(E)=c,e,bForE:First(Aa)nFirst(Bb

5、)=c,enb=ForA:First(cA)nFirst(eB)=cne=?由上验证：该文法是LL(1)文法，下面是递归下降分析程序:5 / 5voidParseEf)(lookahead)(ParseAfMjtchToken(a);b-Lp,e4h*.d5b：Par&eB(MatchToken(b);voidParseA()(lookihe»d).e:atchToktri(c);e：MitchTokente);Parsee();printf ( "syntax er rear)printf(Hhsyntaxerrornp)；)voidParst*B()(lookd

6、h«ad=b)(HjtchTc<en(b)；M5tChTc<en(d):)户Sffprintf("syntaiterror)S一ABA一aA|eB一bB|£Follow(S) = #Follow(A) = b, #Follow(B) = #答：First(A)=a,£First(B)=b,First(S)=a,b,£ForA:First(aA)AFirst(e)a=8=?First(aA)nFollow(A)=anb,#=?ForB:First(bB)nFirst(£)b=0£=?First(bB)nFollow

7、(B)=bn#=?由上验证：该文法是LL(1)文法，下面是递归下降分析程序:void ParseBf)voidPareA()(lookahead)Mnt i h 1 LtKKik(a)；ParseA);(10Qkahedd)b:MitchTok*rt(b)j Parsc0();pri ntf( 'syntax error h")prJntCsyfltax ""力p n") exit(U);b* »)lookaheadPorseA();Parsefl();(printf(MsyntaxerrornM);exit(B);5 .验证如下文法是

8、LL(1)文法。若是，则请构造文法的LL(1)分析表。(1)D一TLT一int|realLfidRR一,idR|£Follow(D) = #Follow(T) = idFollow(L) = #Follow(R)=的 s )i= n e = ?答:First(T)=int,realFirst(L)=idFirst(R)=,£First(D)=int,realForR:First(,idR)nFirst(First(,idR)nFollow(R)=idn#=?ForT:First(int)AFirst(real)=intAreal=由上验证：该文法是LL(1)文法，下面是LL

9、(1)分析表:intrealid,#DD一TLD一TLTT-intT一realLL一idRRR一,idRR一£(2)E f TE'E' f +E | eT 一 FT'T' 一 T |£F 一 PF'F' 一 *F |£P 一 (E) | a| &答:First(P) = (, a, &)First(F') = *, £First(F) = (, a, &First(T) = (, a, &First(T') = ( , a, &,£ Firs

10、t(E') = + , £ First(E) = (, a, &For 巳 First(+E) n First( £Follow(E) = #, )Follow(E') = #, )Follow(T) = +, #,) Follow(T') = +, #, ) Follow(F) = (, a, &, #, +, ) Follow(F') = (, a, &, #, +, )Follow(P) = *, (, a, &, #, +, ) 用H £ = ?First(+E)nFollow(E')

11、=+n#,)=ForT':First(T)FFirst(£)(=s,&Fe=?First(T)FFollow(T')=(,a,&F+,#,)=?ForF':First(*F)nFirst(e)*=A£=?First(*F)nFollow(F')=*n(,a,&,#,+,)=ForP:First(E)nFirst(a)=(Fa=?First(E)nFirst(&)=(n&=First(a)nFirst(&)=aF&=由上验证：该文法是LL(1)文法，下面是LL(1)分析表:+*()a&am

12、p;#EE一TE'E一TE'E一TE'E'E'一+EE'一eE'一eTTfFT'TfFT'TfFT'T'T'一eT'一TT'一eT'一TT'一TT'一eFF一PF'F一PF'F一PF'F'F'一eF'<*FF'一eF'一eF'一eF'一eF'一ePP一(E)P一aP一&6.消除如下文法的左递归(1)A一Ba|Aa|cB一Bb|Ab|d答：消除直接左递归：A一B

13、a|Aa|c=>ABaC|cCC一aC|eB一Bb|Ab|d=>BAbD|dDD一bD|s消除一般左递归：排列顺序：C=>D=>A=>BB一AbD|dD=>B一BaCbD|cCbD|dD=>B一cCbDE|dDEE一aCbDE|£最后结果：A-BaC|cCB一cCbDE|dDEC一aC|eD一bD|£E一aCbDE|£(2)A一Bx|Cz|wB一Ab|BcC一Ax|By|Cp答：消除直接左递归:B一Ab|Bc=>B一AbDD一cD|£C一Ax|By|Cp=>C一AxE|ByEE一pE|e消除一般左递归：排列顺序：A=>C=>B=>D=>E=>CBxxE|CzxE|wxE|ByE=>C一BxxEF|wxEF|ByEFB一AbD=>BB