編譯原理-答疑-作業(yè)-問題匯總

1、程序設(shè)計語言編譯原理程序設(shè)計語言編譯原理答疑、作業(yè)問題匯總答疑、作業(yè)問題匯總 二、高級語言及其語法描述二、高級語言及其語法描述 P36P36 7 7、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0 0開頭。開頭。解：解：GS: SA|BA|BCAGS: SA|BA|BCA B1|2|3|4|5|6|7|8|9 B1|2|3|4|5|6|7|8|9 CB|0|C CB|0|C C C A1|3|5|7|9 A1|3|5|7|9 錯誤錯誤1). GS: S1|1+2S 1). GS: S1|1+2S 錯誤錯誤2). S(|1|2|2). S(|1|2|

2、9|9）A A A(0|1|2| A(0|1|2|9|)C|AA|9|)C|AA CA|(1|3|5|7|9) CA|(1|3|5|7|9) BNFBNF范式中，只有范式中，只有，| |是元符號，是元符號，（）是有意義的。（）是有意義的。產(chǎn)生式中不允許運(yùn)算產(chǎn)生式中不允許運(yùn)算P36 8P36 8、令文法為：、令文法為：GE: ET|E+T|E-TGE: ET|E+T|E-T TF|T TF|T* *F|T/FF|T/F F(E)|i F(E)|i給出給出i+ii+i* *i i 的最左、最右推導(dǎo)的最左、最右推導(dǎo)解：最左推導(dǎo)：解：最左推導(dǎo)： E = E+T = T+T = F+T = i+T =

3、i+TE = E+T = T+T = F+T = i+T = i+T* *F F = i+F = i+F* *F = i+iF = i+i* *F = i+iF = i+i* *i i錯誤錯誤1). E E+T T+T F+T i+T i+T1). E E+T T+T F+T i+T i+T* *F F i+F i+F* *F i+iF i+i* *F i+iF i+i* *i i 產(chǎn)生式規(guī)則定義使用的元符號；產(chǎn)生式規(guī)則定義使用的元符號； = = 推導(dǎo)運(yùn)算符號；推導(dǎo)運(yùn)算符號；P36 8P36 8、令文法為：、令文法為：GE: ET|E+T|E-TGE: ET|E+T|E-T TF|T TF|T

4、* *F|T/FF|T/F F(E)|i F(E)|i給出給出i+ii+i* *i i 的最左、最右推導(dǎo)的最左、最右推導(dǎo)解：最左推導(dǎo)：解：最左推導(dǎo)： E = E+T = T+T = F+T = i+T = i+TE = E+T = T+T = F+T = i+T = i+T* *F F = i+F = i+F* *F = i+iF = i+i* *F = i+iF = i+i* *i i錯誤錯誤2). E = E+T = T+T = F+T = F+T2). E = E+T = T+T = F+T = F+T* *F F = F+F = F+F* *F = i+FF = i+F* *F = i

5、+iF = i+i* *F = i+iF = i+i* *F F認(rèn)為：必須先將非終結(jié)符推導(dǎo)到最后一個層次的非終結(jié)符認(rèn)為：必須先將非終結(jié)符推導(dǎo)到最后一個層次的非終結(jié)符后，統(tǒng)一替換成終結(jié)符。后，統(tǒng)一替換成終結(jié)符。最左推導(dǎo)：當(dāng)有多個非終結(jié)符時，先替換最左邊的最左推導(dǎo)：當(dāng)有多個非終結(jié)符時，先替換最左邊的VnVn. .P36 11P36 11、給出下面語言的相應(yīng)文法、給出下面語言的相應(yīng)文法 L L4 4= = 1 1n n0 0m m1 1m m0 0n n | n,m0 | n,m0解：解：GSGS： S1S0|AS1S0|A A0A1| A0A1|錯誤錯誤1). S1S0|A1). S1S0|A A

6、0A1|01 A0A1|01錯誤錯誤2). SABC2). SABC A1A| A1A| B0B1|01| B0B1|01| C0C| C0C|對：對：m=0 m=0 的句子，無法描述。的句子，無法描述。A A、C C 出現(xiàn)的次數(shù)并不能保證出現(xiàn)的次數(shù)并不能保證一致，可以推出：一致，可以推出： 1100110 1100110 的句子。的句子。P64 7P64 7、構(gòu)造下列正規(guī)式的、構(gòu)造下列正規(guī)式的DFADFA： 1(0|1)1(0|1)* *101101解：正規(guī)式解：正規(guī)式=NFA=DFA=NFA=DFA 1) 1) 正規(guī)式正規(guī)式= NFA= NFA 采用轉(zhuǎn)換系統(tǒng)：采用轉(zhuǎn)換系統(tǒng)：XY UV U|

7、Va aU*XYUVXY XYaXAYUVXAY UXY1(1|0)*1012Y11101 X(1|0)*Y Y3 31 X X1 1 2 2101 0|1Y Y3 31 X X1 1 2 2104 40 5 511Y Y3 31 X X1 1 2 2104 40 5 511解：解：2) NFA=DFA ( 2) NFA=DFA ( -closure, a-closure, a弧轉(zhuǎn)換弧轉(zhuǎn)換IaIa ) ) ：I II I0 0I I1 1xx1,2,31,2,31,2,31,2,32,32,32,3,42,3,42,32,32,32,32,3,42,3,42,3,42,3,42,3,52,3,

8、5 2,3,42,3,42,3,52,3,52,32,32,3,4,y2,3,4,y2,3,4,y2,3,4,y 2,3,52,3,5 2,3,42,3,4正規(guī)式的正規(guī)式的狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣易出現(xiàn)問題處：易出現(xiàn)問題處：1 1、矩陣中的內(nèi)容均為集合，、矩陣中的內(nèi)容均為集合， 注意書寫形式注意書寫形式。2 2、I Ia a 是從是從I I集合出發(fā)，經(jīng)過集合出發(fā)，經(jīng)過 a a可以到達(dá)的結(jié)點(diǎn)，及其可以到達(dá)的結(jié)點(diǎn)，及其 閉包，必須先到達(dá)。如例閉包，必須先到達(dá)。如例 中中1,2,31,2,3的的I I0 0不包括不包括1 1。3 3、空集不必考慮轉(zhuǎn)換關(guān)系。、空集不必考慮轉(zhuǎn)換關(guān)系。解：解：2) NFA

9、=DFA ( 2) NFA=DFA ( -closure, a-closure, a弧轉(zhuǎn)換弧轉(zhuǎn)換IaIa ) ) ： 重新命名狀態(tài)集合：重新命名狀態(tài)集合：I II I0 0I I1 1xx1,2,31,2,31,2,31,2,32,32,32,3,42,3,42,32,32,32,32,3,42,3,42,3,42,3,42,3,52,3,5 2,3,42,3,42,3,52,3,52,32,32,3,4,y2,3,4,y2,3,4,y2,3,4,y 2,3,52,3,5 2,3,42,3,4正規(guī)式的正規(guī)式的狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣重新命名后的重新命名后的狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣S S0 01

10、 11 1- -2 22 23 34 43 33 34 44 45 54 45 53 36 66 65 54 4注意：注意： 空集不必參與命名。空集不必參與命名。解：解：2) NFA=DFA ( 2) NFA=DFA ( -closure, a-closure, a弧轉(zhuǎn)換弧轉(zhuǎn)換IaIa ) ) ： 根據(jù)重新命名后的狀態(tài)轉(zhuǎn)換矩陣，畫出狀態(tài)轉(zhuǎn)換圖：根據(jù)重新命名后的狀態(tài)轉(zhuǎn)換矩陣，畫出狀態(tài)轉(zhuǎn)換圖：重新命名后的重新命名后的狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣S S0 01 11 1- -2 22 23 34 43 33 34 44 45 54 45 53 36 66 65 54 46 64 41 1 12 20 0

11、 3 3105 50 1110 1P81 1P81 1、考慮下面文法考慮下面文法GS:GS: Sa|(T Sa|(T) ) TT,S|S 1 TT,S|S 1）消去）消去G G的左遞歸的左遞歸解：文法中，解：文法中，T T有左遞歸產(chǎn)生式，故消去：有左遞歸產(chǎn)生式，故消去： S a|(TS a|(T) ) T ST T ST T ,ST| T ,ST| 不必要的工作：不必要的工作： S a|(TS a|(T) ) T aT T aT |T|(T)T |T|(T)T T ,ST| T ,ST|注意：注意： 只有當(dāng)文法中有間接左遞只有當(dāng)文法中有間接左遞歸的情況，要消除間接左歸的情況，要消除間接左遞歸時

12、，才需要將文法符遞歸時，才需要將文法符號代入某些規(guī)則。號代入某些規(guī)則。P81 1、2）判定改造后的文法是否是）判定改造后的文法是否是LL(1)的？的？解：改造后的文法解：改造后的文法GS:GS: S a|(T S a|(T) ) T ST T ST T ,ST| T ,ST| 判定方法判定方法1 1：求出：求出FirstFirst集合，集合，F(xiàn)ollowFollow集合，并驗(yàn)證：集合，并驗(yàn)證： 1)1)、若：、若：AA1 1 | |2 2 | | | |n n 則：則：FIRST(FIRST(i i)FIRST()FIRST(j j)= i)= ij j2)2)、AA1 1 | |2 2 |

13、| | |n n 若：若：FIRST(FIRST(i i) )，則：，則：FIRST(A)FOLLOW(A)=FIRST(A)FOLLOW(A)=V VT TFirstFirstV VN NFirstFirstFirstFirsta aaaS Sa,(a,(T)(T)( T Ta,(a,(STSTa,(a,( (T T, , ,ST,ST,) )解：文法解：文法GS:GS: Sa|(T Sa|(T) ) TST TST T,ST|T,ST| V VN NS ST TTTFollowFollow #,)#,) )1)1)、對：、對：Sa|(TSa|(T) ) FIRST(a)FIRST FIRS

14、T(a)FIRST()=()= FIRST(a)FIRST(T FIRST(a)FIRST(T)=)= FIRST()FIRST(T)= FIRST()FIRST(T)= 對：對：T T,ST,ST| FIRST(,ST| FIRST(,ST)FIRST()FIRST()=)=2)2)、 T T ,ST ,ST| FIRST(| FIRST() ) FIRST(T FIRST(T)FOLLOW(T)FOLLOW(T)= GS)= GS是是LL(1)LL(1)的。的。判定文法是否為判定文法是否為LL(1)LL(1) 若要得出結(jié)論：若要得出結(jié)論： 文法不是文法不是LL(1),LL(1),只要找出一

15、個不滿足的條件即可。只要找出一個不滿足的條件即可。若要得出結(jié)論：若要得出結(jié)論： 文法是文法是LL(1),LL(1),必須驗(yàn)證每一個條件。必須驗(yàn)證每一個條件。書上書上P82P82， 3 3 題，按上述方法作。題，按上述方法作。V VN NFirstFirstFirstFirstS Sa,(a,(T)(T)(T Ta,(a,(STST a,(a,(T T, , , ,ST,ST,V VN NFollowFollowS S #,)#,)T T) ) T T)文法文法GS:GS: Sa|(T Sa|(T) ) TST TST T,ST| T,ST| a(),#SSaSS(T)TTSTTST TSTTT

16、T,ST 判定方法判定方法2 2：求出預(yù)測分析表，檢查是否有多重入口：求出預(yù)測分析表，檢查是否有多重入口： 預(yù)測分析表中，沒有多重入口，預(yù)測分析表中，沒有多重入口， GS GS是是LL(1)LL(1)的。的。計算計算FollowFollow集合時，容易出現(xiàn)的問題：集合時，容易出現(xiàn)的問題：為什么：若為什么：若B B 是一個產(chǎn)生式是一個產(chǎn)生式, , 或或AAB B是一個產(chǎn)生式，而是一個產(chǎn)生式，而= =* * ( (即即 FIRST(FIRST() )），）， 則把則把FOLLOW(A)FOLLOW(A)加至加至FOLLOW(B)FOLLOW(B)中？中？答：答： aFOLLOW(A) S=aFOL

17、LOW(A) S=* * Aa Aa, a V, a VT T對于：對于： AAB B ，則可有，則可有S=S=* *BaBa, , 所以：所以：aFOLLOW(BaFOLLOW(B) )。對于：對于：AAB B，則可有，則可有S=S=* *B Ba a， 而而 =* * ，所以，所以aFOLLOW(BaFOLLOW(B) )。P133 1P133 1、令文法、令文法GE:GE: EE+T|T TT EE+T|T TT* *F|F F(E)|iF|F F(E)|i證明證明E+TE+T* *F F 是它的句型，找：短語，直接短語，句柄是它的句型，找：短語，直接短語，句柄解：解：E=E+T=E+T

18、E=E+T=E+T* *F F E+T E+T* *F F 是句型。是句型。 畫出語法樹畫出語法樹 短語：短語：T T* *F F，E+TE+T* *F F 直接短語：直接短語：T T* *F F 句柄：句柄：T T* *F F錯誤錯誤1) 1) 短語是：短語是：i1,i2,i3i1,i2,i3錯誤錯誤2) 2) 短語中包括：短語中包括：E+TE+T短語必須是句型中的一部分。短語必須是句型中的一部分。短語可以由非終結(jié)符構(gòu)成。短語可以由非終結(jié)符構(gòu)成。EE+TT T* *F FP133 3P133 3、文法、文法GS: Sa|(TGS: Sa|(T) TT,S|S) TT,S|S1) 1) 求求F

19、IRSTVTFIRSTVT，LASTVT 2) LASTVT 2) 求優(yōu)先關(guān)系求優(yōu)先關(guān)系解：解：FIRSTVT(S)= a,( FIRSTVT(S)= a,( FIRSTVT(T)=a,(, , FIRSTVT(T)=a,(, , 其中，前其中，前3 3項(xiàng)取自項(xiàng)取自S S LASTVT(S)=a,) LASTVT(S)=a,) LASTVT(T)=a,), , LASTVT(T)=a,), ,1 1、函數(shù)的自變量函數(shù)的自變量 為非終結(jié)符為非終結(jié)符2 2、優(yōu)先關(guān)系的寫、優(yōu)先關(guān)系的寫 法。法。 如如 . . , , 不能寫作不能寫作 a a ( () ), ,a a. . . . . . . .

20、( ( . . . . . .= =. .= = . . , , . . . . . . P217 1 P217 1 寫出表達(dá)式的后綴式寫出表達(dá)式的后綴式a a* *(-b+c) = abc(-b+c) = abc+ +* * 用用 表示單目運(yùn)算表示單目運(yùn)算“取負(fù)取負(fù)”(A or B) and (C or not D and E(A or B) and (C or not D and E） = A B or C D not E and or and= A B or C D not E and or and 布爾表達(dá)式中，約定：布爾表達(dá)式中，約定： 運(yùn)算優(yōu)先級：運(yùn)算優(yōu)先級： and and 高于

21、高于 ororP217 3P217 3、將表達(dá)式、將表達(dá)式 (a+b)(a+b)* *(c+d)-(a+b+c(c+d)-(a+b+c) ) 分別分別 表示成三元式、間接三元式、四元式表示成三元式、間接三元式、四元式三元式：三元式：(1)(1) (+, a, b )(+, a, b )(2)(2) (,(1), -) (,(1), -)(3)(3) (+, c, d ) (+, c, d )(4)(4) ( (* *,(2),(3),(2),(3)(5)(5) (+, a, b ) (+, a, b )(6)(6) (+,(5),c ) (+,(5),c )(7)(7) (-,(4),(6)

22、(-,(4),(6)按自左向右掃描，歸按自左向右掃描，歸約順序應(yīng)該如此。約順序應(yīng)該如此。間接三元式：間接三元式：(1)(1) (+, a, b )(+, a, b )(2)(2) (,(1), -) (,(1), -)(3)(3) (+, c, d ) (+, c, d )(4)(4) ( (* *,(2),(3),(2),(3)(5)(5) (+,(1),c ) (+,(1),c )(6)(6) (-,(4),(5) (-,(4),(5)間接碼表間接碼表(1)(1) (2)(2) (3)(3) (4)(4) (1)(1)(5)(5)(6)(6)必須有必須有“間接碼表間接碼表”P217 3P2

23、17 3、將表達(dá)式、將表達(dá)式 (a+b)(a+b)* *(c+d)-(a+b+c(c+d)-(a+b+c) ) 分別分別 表示成三元式、間接三元式、四元式表示成三元式、間接三元式、四元式四元式：四元式：(1)(1) (+, a, b (+, a, b ，T1 )T1 )(2)(2) (, T1, - ,T2 ) (, T1, - ,T2 )(3)(3) (+, c, d , T3 ) (+, c, d , T3 )(4)(4) ( (* *, T2,T3, T4 ), T2,T3, T4 )(5)(5) (+, a, b , T5 ) (+, a, b , T5 )(6)(6) (+, T5,

24、 c, T6 ) (+, T5, c, T6 )(7)(7) (-, T4,T6 ,T7 ) (-, T4,T6 ,T7 )四元式四元式(5)(5)不能省略，要到不能省略，要到優(yōu)化階段方可以處理。優(yōu)化階段方可以處理。此處只是說此處只是說“便于優(yōu)化便于優(yōu)化”，但并不進(jìn)行優(yōu)化工作。但并不進(jìn)行優(yōu)化工作。P218 6P218 6、分析：、分析：A or (B and not not(CA or (B and not not(C or D) or D) 解答要點(diǎn)：解答要點(diǎn)：1 1、按照文法，寫出當(dāng)前符號串的歸約步驟、按照文法，寫出當(dāng)前符號串的歸約步驟2 2、每一步歸約時，同時完成相應(yīng)的語義工作，、每一步

25、歸約時，同時完成相應(yīng)的語義工作， 如：產(chǎn)生四元式，定義語義屬性變量的值，如：產(chǎn)生四元式，定義語義屬性變量的值， 調(diào)用語義函數(shù)（調(diào)用語義函數(shù)（mergemerge，backpatchbackpatch）將四元式）將四元式 進(jìn)行拉鏈處理，返填處理等。進(jìn)行拉鏈處理，返填處理等。 merge(Pmerge(P1 1,P,P2 2) )：函數(shù)：函數(shù) P P1 1: : P P2 2: : merge(P1,P2)P P2 2: : E E2 2.falselist=103, E.falselist=103, E7 7.falselist=106(104).falselist=106(104)， E E8

26、 8.falselist=Merge(E.falselist=Merge(E2 2.falselist,E.falselist,E7 7.falselist)=106.falselist)=106(100)(jnz, A , 0 )(100)(jnz, A , 0 )(101)(j , ,102)(101)(j , ,102)(102)(jnz, B ,104)(102)(jnz, B ,104)(103)(j , , 0 )(103)(j , , 0 )(104)(jnz, A , 0 )(104)(jnz, A , 0 )(105)(j , ,106)(105)(j , ,106)(106

27、)(jnz, B ,104)(106)(jnz, B ,104)(107)(j , , 0 )(107)(j , , 0 )(100)(jnz, A , 0 )(100)(jnz, A , 0 )(101)(j , ,102)(101)(j , ,102)(102)(jnz, B ,104)(102)(jnz, B ,104)(103)(j , , 0 )(103)(j , , 0 )(104)(jnz, A ,(104)(jnz, A ,103103) )(105)(j , ,106)(105)(j , ,106)(106)(jnz, B ,104)(106)(jnz, B ,104)(10

28、7)(j , , 0 )(107)(j , , 0 )已知定義：已知定義： A1.10,1.20A1.10,1.20， B1.20 B1.20 求：求： AI+1,J:=AI,J+BI+JAI+1,J:=AI,J+BI+J 解答要點(diǎn)：解答要點(diǎn)：1 1、按照文法，寫出當(dāng)前符號串的歸約步驟、按照文法，寫出當(dāng)前符號串的歸約步驟2 2、每一步歸約時，同時完成相應(yīng)的語義工作，、每一步歸約時，同時完成相應(yīng)的語義工作， 如：產(chǎn)生四元式，定義語義屬性變量的值，如：產(chǎn)生四元式，定義語義屬性變量的值， elist.ARRAY,elist.DIM,L.offset,L.PLACEelist.ARRAY,elist.

29、DIM,L.offset,L.PLACE 等。等。主要問題：主要問題：1 1、對：、對：I+1,I+1,先產(chǎn)生一條四元式，算出表達(dá)式的值先產(chǎn)生一條四元式，算出表達(dá)式的值2 2、規(guī)約順序，自左向右。、規(guī)約順序，自左向右。P237 7P237 7、1)1)掃描到掃描到getsymgetsym過程體之前的棧符號表過程體之前的棧符號表Program P(input,output); const norw=13; var l,k: integer; word:array1.norwof char; procedure getsym; var i,j:integer; procedure getch(wo

30、rd:real); begin end; getch begin i:=1;k:=i+j ; end; getsym name info preT Topop8 8 getchgetch0 07 7j j8 86 6i i7 75 5 getsymgetsym0 04 4 WordWord5 53 3K K4 42 2L L3 3 1 1 norwnorw2 26level1D D 表表pascalpascal語言符號表的實(shí)現(xiàn)中，如何保證標(biāo)識符的作用語言符號表的實(shí)現(xiàn)中，如何保證標(biāo)識符的作用域？（即：內(nèi)層過程可以訪問外層的變量，但外層過域？（即：內(nèi)層過程可以訪問外層的變量，但外層過程無法訪問內(nèi)層過程的名字）程無法訪問內(nèi)層過程的名字）答：內(nèi)層可引用包圍它的外層定義的標(biāo)識符：實(shí)現(xiàn)答：內(nèi)層可引用包圍它的外層定義的標(biāo)識符：實(shí)現(xiàn)時，通過逐層向外查找符號表實(shí)現(xiàn)。同名時，內(nèi)層時，通過逐層向外查找符號表實(shí)現(xiàn)。同名時，內(nèi)層定義的名字優(yōu)先被查找到，因此以內(nèi)層定義的名字定義的名字優(yōu)先被查找到，因此以內(nèi)層定義的名字為準(zhǔn)；內(nèi)層沒有定義時，訪問外層定義的名字。為準(zhǔn)；內(nèi)層沒有定義時，訪問外層定義的名字。而內(nèi)層定義的名字（如：而內(nèi)層定義的名字（如：getchgetch中的參數(shù)中的參數(shù)word