編譯原理作業(yè)題

1、-編譯原理復(fù)習(xí)資料-06軟件工程四班-第二章2.1 設(shè)字母表A=a，符號串x=aaa，寫出下列符號串及其長度：x0,xx,x5以及A+和A*.x0=(aaa)0= | x0|=0 xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15A+ =A1 A2 . A n =a,aa,aaa,aaaa,aaaaa A* = A0 A1 A2 . A n =,a,aa,aaa,aaaa,aaaaa 2.2 令=a，b，c，又令x=abc，y=b，z=aab，寫出如下符號串及它們的長度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=

2、7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3 設(shè)有文法GS：S=SS*|SS+|a，寫出符號串a(chǎn)a+a*規(guī)范推導(dǎo)，并構(gòu)造語法樹。S => SS* => Sa* => SS+a* => Sa+a* => aa+a*SSS*SS+aaa2.4 已知文法GZ：Z=U0V1 、 U=Z11 、 V=Z00 ,請寫出全部由此文法描述的只含有四個符號的句子。Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>

3、U001=>1001Z=>V1=>Z01=>V101=>01012.5 已知文法GS： S=AB A=aA B=bBcbc , 寫出該文法描述的語言。A=aA描述的語言: an|n>=0B=bBcbc描述的語言：bncn|n>=1L(GS)=anbmcm|n>=0,m>=12.6 已知文法E=TE+TE-T 、 T=FT*FT/F 、 F=(E)i，寫出該文法的開始符號、終結(jié)符號集合VT、非終結(jié)符號集合VN。開始符號：EVt=+, - , * , / ,（ , ）, iVn=E , F , TETE+FTE+iFT*T2.7 對2.6題的文

4、法，寫出句型T+T*F+i的短語、簡單短語以及句柄。短語：T+T*F+i T+T*F i i T T*F簡單短語：i T*F T句柄：T2.8 設(shè)有文法GS：S=S*S|S+S|(S)|a，該文法是二義性文法嗎？SSS*S+SaaaSSS+S*Saaa根據(jù)所給文法推導(dǎo)出句子a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。2.9 寫一文法，使其語言是奇正整數(shù)集合。 A:=1|3|5|7|9|NAN:=0|1|2|3|4|5|6|7|8|92.10給出語言anbm|n,m1的文法。 GS: S:=AB A:=aA|a B:=bB|b第三章3.1 有正則文法GZ：Z:=Ua|Vb，U:=

5、Zb|b，V:=Za|a ，畫出該文法的狀態(tài)圖，并檢查句子abba是否合法。解：該文法的狀態(tài)圖如下：SUVZaaabbb句子abba合法。3.2 狀態(tài)圖如圖3.35所示，S為開始狀態(tài)，Z為終止?fàn)顟B(tài)。寫出相應(yīng)的正則文法以及V，Vn和Vt。SAZabab圖3-35狀態(tài)圖 解： 左線性文法GZ: 右線性文法GS:Z:=Ab|bS:=aA|b A:=Aa|aA:=aA|bV=Z,A,a,bV=S,A,a,bVn=Z,AVn=S,AVt=a,bVt=a,b3.3 構(gòu)造下列正則表達(dá)式相應(yīng)的NFA： 1(1|0)*|0 1(1010*|1(010)*1)*0解：正則表達(dá)式：1(1|0)*|01、SZ1(1|

6、0)*|02、SZ1(1|0)*03、SAZ01014、q0q1010,1q2正則表達(dá)式：1(1010*|1(010)*1)*00135462101010780101101a,baa3.4 將圖3.36的NFA M確定化圖3.36 狀態(tài)圖 解：abq0=00,11q1=0,10,11q2=10DFA:q0q1q2ababa3.5 將圖3.37的DFA化簡。014253aaaaaabbbbbb圖3.37 DFA狀態(tài)圖 解：劃分ab0,112,42,3,4,51,0,3,53,5,2,4劃分ab0,112,42,40,13,53,53,52,4q0=0,1q1=2,4q2=3,5化簡后的DFA：q

7、0q1q2baaabb第四章4.1 對下面文法，設(shè)計遞歸下降分析程序。 SaAS|(A) , AAb|c解：首先將左遞歸去掉，將規(guī)則AAb|c 改成 Acb非終結(jié)符號S的分析程序如下：過程S INPUTSYM=aINPUTSYM=下一個符號YNINPUTSYM=(INPUTSYM=下一個符號YINPUTSYM=)INPUTSYM=下一個符號YNN出口錯誤錯誤過程A過程S過程A非終結(jié)符號A的分析程序如下：過程A INPUTSYM=cINPUTSYM=下一個符號YINPUTSYM=bN錯誤INPUTSYM=下一個符號Y出口N4.2 設(shè)有文法GZ： Z=(A) , A=a|Bb , B=Aab若采用

8、遞歸下降分析方法，對此文法來說，在分析過程中，能否避免回溯？為什么？解：若采用遞歸下降分析方法，對此文法來說，在分析過程中不能避免回朔。因為規(guī)則A=a|Bb和規(guī)則B=Aab構(gòu)成了間接左遞歸，不滿足實現(xiàn)沒有回溯的遞歸下降分析方法的條件（1）（書P67），且規(guī)則 A: := a|Bb，F(xiàn)IRST(a)=a，F(xiàn)IRST(Bb)=a，即此規(guī)則候選式的首符號集有相交，不滿足實現(xiàn)沒有回溯的遞歸下降分析方法的條件（2）（書P67），在分析過程中，將造成回溯。改寫文法可避免回溯：將規(guī)則B=Aab代入規(guī)則A=a|Bb得：A=a|Aabb，再轉(zhuǎn)換成：A=aabb，可避免回溯。4.3 若有文法如下，設(shè)計遞歸下降分析

9、程序。 <語句><語句><賦值語句>| <賦值語句>ID=<表達(dá)式> <表達(dá)式><項>|<表達(dá)式><項>|<表達(dá)式><項> <項><因子>|<項>*<因子>|<項>/<因子> <因子>ID|NUM|(<表達(dá)式>)解：首先，去掉左遞歸<語句><語句><賦值語句>|改為： <語句><賦值語句><表達(dá)式>

10、<項> | <表達(dá)式> + <項> | <表達(dá)式> - <項> 改為：<表達(dá)式><項>（+ | -）<項><項><因子> | <項> * <因子> | <項> / <因子> 改為：<項><因子>（* | /）<因子>則文法變?yōu)椋?lt;語句><賦值語句> <賦值語句>ID=<表達(dá)式> <表達(dá)式><項>（+ | -）<項&g

11、t; <項><因子>（* | /）<因子> <因子>ID|NUM|(<表達(dá)式>)<語句><賦值語句>非終結(jié)符號 <語句> 的分析程序如下：FIRST(<賦值語句>)=ID語句INPUTSYM=IDNY賦值語句出口<賦值語句>ID=<表達(dá)式>非終結(jié)符號 <賦值語句> 的分析程序如下：賦值語句INPUTSYM=ID錯誤NINPUTSYM=下一個符號INPUTSYM=錯誤NINPUTSYM=下一個符號Y表達(dá)式出口<表達(dá)式><項>（+

12、| -）<項>非終結(jié)符號 <表達(dá)式> 的分析程序如下：表達(dá)式INPUTSYM=+NINPUTSYM=-INPUTSYM=下一個符號Y出口項NY<項><因子>（* | /）<因子>非終結(jié)符號 <項> 的分析程序如下：復(fù)值語句的分析程序項INPUTSYM=*NINPUTSYM=/INPUTSYM=下一個符號Y出口因子NY項<因子>ID|NUM|(<表達(dá)式>)非終結(jié)符號 <因子> 的分析程序如下：因子INPUTSYM=IDY出口INPUTSYM=NUMINPUTSYM=下一個符號NYNINPU

13、TSYM=(INPUTSYM=下一個符號Y表達(dá)式INPUTSYM=)錯誤NY錯誤N4.4 有文法GA：A:=aABe|，B:=Bb|b（1）求每個非終結(jié)符號的FOLLOW集。（2）該文法是LL(1)文法嗎？（3）構(gòu)造LL(1)分析表。解：（1） FOLLOW(A)=First(B)#=b,# FOLLOW(B)=e,b（2） 該文法中的規(guī)則B:=Bb|b為左遞歸，因此該文法不是LL(1)文法（3） 先消除文法的左遞歸（轉(zhuǎn)成右遞歸），文法變?yōu)椋篈:=aABe|，B:=bB，B=bB|，該文法的LL(1)分析表為：更常用且簡單的LL(1)分析表：aeb#AAaABeAABBbBBBBbB4.5 若

14、有文法A(A)A|（1）為非終結(jié)符A構(gòu)造FIRST集合和FOLLOW集合。（2）說明該文法是LL(1)的文法。解：（1）FIRST(A)(, FOLLOW(A)，#（2）該文法不含左遞歸；FIRST（(A)A）=(，F(xiàn)IRST（）=，F(xiàn)IRST（(A)A）FIRST（）=，且FOLLOW(A)，#，F(xiàn)IRST（(A)A） FOLLOW(A) =，因此，該文法滿足LL(1)文法的條件，是LL(1)文法。4.6 利用分析表4-1，識別以下算術(shù)表達(dá)式，請寫出分析過程。（1）i+i*i+i（2）i*(i+i+i)解：（1）i+i*i+i步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#Ei+i*i+i#PO

15、P,PUSH(ET)ETE2#ETi+i*i+i#POP,PUSH(TF)TFT3#ETFi+i*i+i#POP,PUSH(i)Fi4#ETii+i*i+i#POP,NEXTSYM5#ET+i*i+i#POPT6#E+i*i+i#POP,PUSH(ET+)E+TE7#ET+i*i+i#POP,NEXTSYM8#ETi*i+i#POP,PUSH(TF)TFT9#ETFi*i+i#POP,PUSH(i)Fi10#ETii*i+i#POP,NEXTSYM11#ET*i+i#POP,PUSH(TF*)T*FT12#ETF*i+i#POP,NEXTSYM13#ETFi+i#POP,PUSH(i)Fi14

16、#ETii+i#POP,NEXTSYM15#ET+i#POPT16#E+i#POP,PUSH(ET+)E+TE17#ET+i#POP,NEXTSYM18#ETi#POP,PUSH(TF)TFT19#ETFi#POP,PUSH(i)Fi20#ETii#POP,NEXTSYM21#ET#POPT22#E#POPE23#ACCEPT（2）i*(i+i+i)步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#Ei*(i+i+i)#POP,PUSH(ET)ETE2#ETi*(i+i+i)#POP,PUSH(TF)TFT3#ETFi*(i+i+i)#POP,PUSH(i)Fi4#ETii*(i+i+i)#POP,

17、NEXTSYM5#ET*(i+i+i)#POP,PUSH(TF*)T*FT6#ETF*(i+i+i)#POP,NEXTSYM7#ETF(i+i+i)#POP, PUSH()E()F(E)8#ET )E(i+i+i)#POP,NEXTSYM9#ET )Ei+i+i)#POP,PUSH(ET)ETE10#ET ) ETi+i+i)#POP,PUSH(TF)TFT11#ET ) E TFi+i+i)#POP,PUSH(i)Fi12#ET ) E Tii+i+i)#POP,NEXTSYM13#ET ) E T+i+i)#POPT14#ET ) E +i+i)#POP,PUSH(ET+)E+TE15#E

18、T ) ET+i+i)#POP,NEXTSYM16#ET ) ETi+i)#POP,PUSH(TF)TFT17#ET ) ETFi+i)#POP,PUSH(i)Fi18#ET ) ETii+i)#POP,NEXTSYM19#ET ) ET+i)#POPT20#ET ) E+i)#POP,PUSH(ET+)E+TE21#ET ) E T+i)#POP,NEXTSYM22#ET ) E Ti)#POP,PUSH(TF)TFT23#ET ) E TFi)#POP,PUSH(i)Fi24#ET ) E Tii)#POP,NEXTSYM25#ET ) E T)#POPT26#ET ) E)#POPE27

19、#ET )#POP,NEXTSYM28#ET #POPT29#E#POPE30#ACCEPT4.7 考慮下面簡化了的C聲明文法：<聲明語句><類型><變量表>；<類型>int|float|char<變量表>ID,<變量表>|ID（1） 在該文法中提取左因子。（2） 為所得的文法的非終結(jié)符構(gòu)造FIRST集合和FOLLOW集合。（3） 說明所得的文法是LL(1)文法。（4） 為所得的文法構(gòu)造LL(1)分析表。（5） 假設(shè)有輸入串為“char x，y，z；”，寫出相對應(yīng)的LL(1)分析過程。解：（1） 規(guī)則<變量表>

20、ID,<變量表>|ID提取公因子如下：<變量表>ID（,<變量表>|）增加新的非終結(jié)符<變量表1>，規(guī)則變?yōu)椋?lt;變量表>ID<變量表1><變量表1>，<變量表>| C聲明文法改變?yōu)椋?<聲明語句><類型><變量表>；<類型>int|float|char<變量表>ID<變量表1><變量表1>，<變量表>|（2） FIRST(<聲明語句>)FIRST(<類型>)int，float，ch

21、arFIRST(<變量表>)IDFIRST(<變量表1>)，F(xiàn)OLLOW(<聲明語句>)#FOLLOW(<類型>)FIRST(<變量表>)IDFOLLOW(<變量表>)FOLLOW(<變量表1>)；（3） 所得文法無左遞歸，且FIRST（int）FIRST（float）FIRST（char）FIRST（，<變量表>）FIRST（）FIRST（，<變量表>）FOLLOW(<變量表1>)因此，所得文法為LL(1)文法。（4） 所得的文法構(gòu)造LL(1)分析表如下所示：更常用且簡單的

22、LL(1)分析表：；intfloatcharID，#<聲明語句><聲明語句><類型><變量表>；<聲明語句><類型><變量表>；<聲明語句><類型><變量表>；<類型><類型>int<類型>float<類型>char<變量表><變量表>ID<變量表1><變量表1><變量表1><變量表1>,<變量表>（5） 輸入串“char x，y，z；”相對應(yīng)的

23、LL(1)分析過程如下：步驟分析棧余留輸入串分析表元素所用產(chǎn)生式1#<聲明語句>char x，y，z；#POP ，PUSH(；<變量表><類型>)<聲明語句><類型><變量表>；2#；<變量表><類型>char x，y，z；#POP ，PUSH(char)<類型>char3#；<變量表> charchar x，y，z；#POP,NEXTSYM4#；<變量表>x，y，z；#POP ，PUSH(<變量表1>ID)<變量表>ID<變量表1&

24、gt;5#；<變量表1>xx，y，z；#POP,NEXTSYM6#；<變量表1>，y，z；#POP ，PUSH(<變量表>，)<變量表1>，<變量表>7#；<變量表>，y，z；#POP,NEXTSYM8#；<變量表>y，z；#POP ，PUSH(<變量表1>ID)<變量表>ID<變量表1>9#；<變量表1>yy，z；#POP,NEXTSYM10#；<變量表1>，z；#POP ，PUSH(<變量表>，)<變量表1>，<變量表>11#；<變量表>，z；#POP,NEXTSYM12#；<變量表>z；#POP ，PUSH(<變量表1>ID)<變量表>ID<變量表1>13#；<變量表1>zz；#POP,NEXTSYM14#；<變量表1>；#POP<變量表1>15#；#POP,NEXTSYM16#ACCEPT一、 （20分）對于文法G(S)：S(A)|a， AA+S|S(1)給出句型（a+（A）的最左推導(dǎo)。(2)畫出句型（a+（A）的語法