編譯原理考試習(xí)題及答案.ppt

1、編程語(yǔ)言，Chapter 3。詞法分析，編譯原理參考答案，2020/7/31，CH.3 .練習(xí)問(wèn)題8(P64)。)，8 .提供以下正則表達(dá)式：(1)以01結(jié)尾的二進(jìn)制字符串；正則表達(dá)式(0|1)*01 (2)是可除以5的十進(jìn)制整數(shù)。允許任意零開(kāi)始：(0|1|2|3|4|5|6|7|8|9)*(0|5)允許零開(kāi)始渡邊杏(不包括零本身):(0|5)(2) 1 (1010 * | 1 (010) * 1) * 0，2020/7/31，7。配置以下正式的相應(yīng)NFA:(p64 .)(2) 1 (1010 * | 1 (010) * 1) * 0，7。(2) 1 (1010 * | 1 (010) * 1

2、 *，2020/7/31，CH.3 .練習(xí)問(wèn)題14 (p64)，(1)公式： (10)高級(jí)語(yǔ)言和語(yǔ)法說(shuō)明、編譯原理參考答案、CH.2 .練習(xí)問(wèn)題6(P36)。)，6 .語(yǔ)法L(G6為3360N D |注：集合標(biāo)記不正確。L(G6)=所有由0，1，2，3，4，5，6，7，8，9=09數(shù)字組成的數(shù)字字符串可以給出0到(2)文章0127注意：步驟1和的區(qū)別；2)無(wú)法寫(xiě)入解析：0127最左側(cè)的導(dǎo)出：nnddddddddddddd01 DDD 012d 0127 0127 0127最右側(cè)的導(dǎo)出：NNDN 7 ND7 N27 ND27 N127D 1270127，CH.2 .練習(xí)8(，)最右側(cè)的派生e t

3、 * f t *(e)t *(e t)t *(e f)t *(e I)t *(t I)t *(f I)t *(I)t *(I)f，2020/7/31，CH.2 .練習(xí)問(wèn)題9(P36)。)，9說(shuō)明：根據(jù)定義，只要能給出反例，iiiei不是唯一的反例。編譯原理參考答案，編程語(yǔ)言，Chapter 5。自下而上語(yǔ)法分析，2020/7/31，CH.5 .練習(xí)問(wèn)題1(P133)。)，1 .語(yǔ)法G1: ee t |，證明從1:牙齒起始符號(hào)E派生到E T*F。E E T E T*F E T*F是G1的句型。球體： E T*F是相對(duì)于非終結(jié)器E的文章模式。T*F是相對(duì)于鄭智薰終結(jié)器t的文章模式。直接短語(yǔ)： T*

4、F相對(duì)于規(guī)則TT*F的句子的直接短語(yǔ)句柄： T*F，2020/7/31，CH.5 .練習(xí)題1(P133)。)，1 .語(yǔ)法G1是ee t，證明2:可以構(gòu)造E T*F的語(yǔ)法樹(shù)。E T*F是G1的文章樣式，如右圖所示。證明3:(也可以通過(guò)一般化證明) (如果概念很熟悉，可以直接列出球體、直接球體、句柄，而無(wú)需說(shuō)明)球體： E T*F，T*F直接球體3360t * f句柄3360 T*F，2020/7/，(1) : (a，(A，A)的最左側(cè)衍生：s(t)(t)(t，s) (s，s) (a，s) (a，(t A).根據(jù)牙齒規(guī)范，給出了“遷移-歸約”過(guò)程，并給出了語(yǔ)法樹(shù)的自下而上構(gòu)造過(guò)程。2020/7/3

5、1，CH.5 .練習(xí)問(wèn)題2(P133)。)，2 .(2)。給定(a，(a，a)“轉(zhuǎn)入-回約”；(2)解析： (a，(a，a)的移動(dòng)-契約程序：步驟符號(hào)堆疊輸入字串工作處理碼1 # (a，(a，a)# a2 #(；(A，A)#約T S a 6 #(T，(A，a)#移動(dòng)，7 #(T，(A，a)#移動(dòng)(8 # (t，) (2)解析： (a，(a，a)的移動(dòng)-契約程序：步驟符號(hào)堆疊輸入字串工作處理碼17 # (T) #約T，S (T) 18 # (T) )；Sa|(T) TT，S|S，(1)解決方案3360(運(yùn)行相應(yīng)的算法)first vt (s)=a，(first vt (t)=，Sa|(T) TT

6、，S|S，(2)解決方案3360 first vt (s)=a，(first vt (t)=，a，(ll G2優(yōu)先于運(yùn)算符，.Sa|(T) TT，S|S，最左側(cè)的素食區(qū)，2020/7/31，.Sa|(T) TT，S|S，最左邊素語(yǔ)法，2020/7/31，5。(1)語(yǔ)法考慮列出SAS|b ASA|a牙齒語(yǔ)法的所有LR(0)項(xiàng)目，CH.5 .練習(xí)問(wèn)題5(P134)。)，解釋(1):擴(kuò)展語(yǔ)法，加入ss擴(kuò)展語(yǔ)法的LR(0)項(xiàng)目：s . s . s . as SAS | b ASA | a，1)擴(kuò)展語(yǔ)法，添加SS，2)繪制DFA(2)標(biāo)識(shí)結(jié)構(gòu)語(yǔ)法SAS|b ASA|a的LR(0)項(xiàng)目集規(guī)范族和前綴的DF

7、A。0:s . s . as . b a . sa a a . a，53360 asa . sa . s . as . b a . a . a，73360 SAS . as . 43360 aa。2:sa.s.as SAS|b ASA|a a.a，63360as.a.sa a.a s.as.b，和；不是LR(0)語(yǔ)法！狀態(tài)1，狀態(tài)5，編譯原理參考答案，編程語(yǔ)言，Chapter 4。由上而下剖析，2020/7/31，CH.4 .練習(xí)問(wèn)題1(P81)。)，1，然后為每個(gè)非終結(jié)器創(chuàng)建沒(méi)有回溯的重復(fù)子例程。，解釋(1)刪除后語(yǔ)法g1:sa | | (t) tst，ST |，ch.4 .練習(xí)問(wèn)題1(P8

8、1)。)，解釋(1)無(wú)回溯的迭代子節(jié)目3360 sa Begin if sym=a or sym=then advance else if sym=(then Begin advance；t；if sym=)then advance else error end else error end；CH.4 .練習(xí)問(wèn)題1(P81)。)，解釋(1)無(wú)回溯的迭代子節(jié)目： TST過(guò)程T；begin S；T end，求解(1)無(wú)回溯迭代子節(jié)目： T，ST | procedure T；Begin if sym=，then begin advances；T end End，CH.4 .練習(xí)問(wèn)題1(P81)。)，

9、(2)修訂的語(yǔ)法是LL(1)嗎？給它預(yù)測(cè)分析的票。因?yàn)樽髠?cè)刪除語(yǔ)法G1 :sa | | (t) TST，St |，(2) G1 :語(yǔ)法不包含左側(cè)遞歸。Sa | | (t) first (a)=a，first ()=，first(t)=(，集不徐璐相交且不包含。T，T，ST| FIRST(，ST )=，F(xiàn)IRST()=()=，其交集為空。但是，F(xiàn)IRST(T)=FIRST(，ST )FIRST()=，但是FOLLOW(T)=) FIRST(T)=，因此G1不會(huì)與LL()，2020/7/31，CH.4 .練習(xí)問(wèn)題1(P81)。)，(2)構(gòu)造G1的預(yù)測(cè)分析表：對(duì)Sa|(T)與tstfirst (a)=a first預(yù)測(cè)分析表