資源描述：
《編譯原理復(fù)習(xí) (2).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、1.合并LR（1）同心集后有可能產(chǎn)生歸約歸約沖突對(duì)2.一個(gè)基本塊不能確定一個(gè)賦值是否真的有用對(duì)3每一個(gè)文法都能改寫成LL（1）文法錯(cuò)4.編譯程序與具體的機(jī)器有關(guān)，也與具體的語(yǔ)言有關(guān)對(duì)5.一個(gè)語(yǔ)言的文法是唯一的錯(cuò)6.過(guò)程與過(guò)程調(diào)用中，信息交換的方法是全局變量的使用和參數(shù)傳遞對(duì)7.在編譯程序中，安排中間代碼生成的目的是便于代碼優(yōu)化和便于目標(biāo)程序的移植對(duì)8.編譯中的語(yǔ)義處理是指兩個(gè)功能即審查每一個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義和執(zhí)行真正的翻譯對(duì)9.程序基本塊是指一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口錯(cuò)10.存在這樣的一些語(yǔ)言他們能夠被確定的
2、有限自動(dòng)機(jī)識(shí)別，但是不能用正規(guī)式表示。錯(cuò)二、填空題：11.要在某一臺(tái)機(jī)器上為某一種語(yǔ)言構(gòu)造一個(gè)編譯程序，必須掌握機(jī)器指令、語(yǔ)言文法、（操作系統(tǒng)）三方面內(nèi)容。12.設(shè)G是一個(gè)給定的文法，S是文法開(kāi)始符號(hào)，如果S—>X，那么X是文法G的句子。(X是終結(jié)符串）13.在一個(gè)典型的編譯過(guò)程中，不僅包括詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等5個(gè)部分，還包括出錯(cuò)處理程序和表格處理程序，其中，詞法分析器用于識(shí)別單詞符號(hào)，語(yǔ)法分析器用來(lái)發(fā)現(xiàn)源程序中的語(yǔ)法結(jié)構(gòu)。編譯方式與解釋方式的根本區(qū)別是是否需要整體考慮，遞歸下降子程序分析法
3、是自上向下的分析法。14.語(yǔ)法分析的任務(wù)是識(shí)別給定的終結(jié)符串是否為給定文法的句子。15.語(yǔ)法分析最常用的兩類方法是自上而下和自下而上分析方法，16.在有限自動(dòng)機(jī)中，兩個(gè)狀態(tài)等價(jià)一致性條件蔓延性條件。17.LR分析法中，每個(gè)項(xiàng)目的含義與原點(diǎn)的位置有關(guān)，概括的說(shuō)，原點(diǎn)的左部表示已識(shí)別的句柄部分，原點(diǎn)的右部表示期待的后綴部分。18.在構(gòu)造LR項(xiàng)目集規(guī)范族時(shí)，新項(xiàng)目集是組成的，合并LR（1）項(xiàng)目集規(guī)范族的同心集所產(chǎn)生的沖突一定是歸約沖突。19.語(yǔ)法制導(dǎo)翻譯比較接近于形式化，它用屬性文法工具來(lái)表達(dá)程序設(shè)計(jì)語(yǔ)言的語(yǔ)義，每個(gè)產(chǎn)生式對(duì)應(yīng)的都給它
4、配上語(yǔ)義動(dòng)作來(lái)進(jìn)行翻譯用。已知文法G[S]：S→MH
5、aH→LSo
6、εK→dML
7、εL→eHfM→K
8、bLM判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。答案：文法展開(kāi)為：0）S→MH1）S→a2）H→LSo3）H→ε4）K→dML5）K→ε6）L→eHf7）M→K8）M→bLM非終結(jié)符FIRST集FOLLOW集S{a,d,b,ε,e}{#,o}........M{d,ε,b}....{e,#,o}......H{ε,e}.....{#,f,o}......L{e}......{a,d,b,e,o,#}K{d,ε}.
9、.....{e,#,o}......對(duì)相同左部的產(chǎn)生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=空SELECT(H→LSo)∩SELECT(H→ε)={e}∩{#,f,o}=空SELECT(K→dML)∩SELECT(K→ε)=kkck062∩{e,#,o}=空SELECT(M→K)∩SELECT(M→bLM)={d，e,#,o}∩=空所以文法是LL(1)的。預(yù)測(cè)分析表：aodefb#S→a→MH→MH→MH→MH→MHM→K→K→K→bLM→KH→ε→LSo→ε→εL→eHfK→ε→
10、dML→ε→ε由預(yù)測(cè)分析表中無(wú)多重入口也可判定文法是LL(1)的。題2中當(dāng)程序編譯到r的過(guò)程體時(shí)的名字表table的內(nèi)容為：Namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0過(guò)程p的入口（待填）5avariable1dxqprocedure1過(guò)程q的入口4sprocedure1過(guò)程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2過(guò)程r的入口5evariable3dxfvariable3dx+1構(gòu)造下列正規(guī)式相應(yīng)的DFA
11、.1(0
12、1) *101(1)先構(gòu)造NFA：用子集法將NFA確定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D，因?yàn)镈含有Y（NFA的終態(tài)），所以D為終態(tài)。.01X.AAABBCBCADDCBDFA的狀態(tài)圖：:給出下述文法所對(duì)應(yīng)的正規(guī)式：S→0A
13、1BA→1S
14、1B→0S
15、0答案：解方程組S的解：S=0A
16、1BA=1S
17、1B=0S
18、0將A、B產(chǎn)生式的右部代入S中S=01S
19、01
20、10S
21、10=（01
22、10）S
23、（01
24、10）所以：S=(01
25、10)*(0
26、1
27、10)證明文法：S→A$A→BaBb
28、DbDaB→εD→ε是LR(1)但不是SLR(1)。(其中'$'相當(dāng)于'#')答案：文法：A→BaBb
29、DbDaB→εD→ε拓廣文法為G′，增加產(chǎn)生式S′→A若產(chǎn)生式排序?yàn)椋?S'→A1A→BaBb2A→DbDa3B→ε
