編譯原理第一次小作業(yè)

1、wordHomework1向首興20140134211 .語法分析程序的主要任務(wù)是什么？簡(jiǎn)述自頂向下語法分析的思想。答：語法分析程序的任務(wù)：1,分析源程序的單詞流是否符合語言的語法規(guī)則；2,報(bào)告語法錯(cuò)誤；3,產(chǎn)生源程序的語法分析結(jié)果，以語法分析樹或與之等價(jià)的形式體現(xiàn)出來。自頂向下語法分析的思想：從文法開始符號(hào)出發(fā)進(jìn)行推導(dǎo)，每一步推導(dǎo)都對(duì)當(dāng)前句型中剩余的某個(gè)非終結(jié)符進(jìn)行擴(kuò)展，進(jìn)而獲得文法的一個(gè)句型，直到產(chǎn)生出所期望的終結(jié)符串，如果不存在可以產(chǎn)生出所期望的終結(jié)符串的推導(dǎo)，則表明語法錯(cuò)誤。2 .對(duì)文法GS:S-a|&l(T)T一T,S|S給出(a,(a,a)和(a,a),&,(a),

2、a)的最左推導(dǎo)。答：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 .判斷下面文法是否為L(zhǎng)L(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由上驗(yàn)證：該文法不是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=?由上驗(yàn)證：該文法是LL(1)文法。4 .驗(yàn)證如下文法是LL(1)文法。若是，則請(qǐng)構(gòu)造遞歸下降分析程序。(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=?由上驗(yàn)證：該文法是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#=?由上驗(yàn)證：該文法是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 .驗(yàn)證如下文法是

8、LL(1)文法。若是，則請(qǐng)構(gòu)造文法的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=由上驗(yàn)證：該文法是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&=由上驗(yàn)證：該文法是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|£最后結(jié)果：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