編譯原理復(fù)習(xí)題2017(含試卷)

1、 編譯原理期末考試試卷(B卷)三、應(yīng)用題(1、4、5每題10分，2、3每題15分，共60分)1、為正規(guī)式(a|b)*a(a|b)構(gòu)造等價(jià)且狀態(tài)最少的確定有限自動(dòng)機(jī)。(要求給出主要步驟)2、有文法如下：S-BAA-BS|dB-aA|bS|c.計(jì)算文法的每個(gè)非終結(jié)符的FIRST和FOLLOW集合；.判斷文法是否LL(1)文法，如果是，給出其預(yù)測(cè)分析表，否則說明理由。4、有文法如下：T-T*F|FF-PF|PP-(T)|i證明T*iP是該文法的一個(gè)句型，但不是規(guī)范句型;指出T*iP的所有短語、直接短語、素短語、句柄。三、應(yīng)用題(1、4、5每題10分，2、3每題15分，共60分)1、對(duì)于符號(hào)串T*iP

2、存在如下推導(dǎo)：(或畫一顆語法樹證明是句型)TnT*FnT*PFnT*PPnT*iP所以T*iP是該文法的一個(gè)句型，但不存在一個(gè)規(guī)范推導(dǎo)能推導(dǎo)出該句型，所以不是規(guī)范句型。(5分)短語：T*iP、iP、i、p直接短語：i、p素短語：i句柄：i2、已知文法GSS-S*aF|aF|*aFF-+aF|+a消除文法左遞歸和提公共左因子答：消除左遞歸S-aFS|*aFSSf*aFS|&F-+aF|+a提公共左因子,文法G(S)S-aFS|*aFSS-*aFS|&F-+aFF-F|e3、設(shè)文法G(S):S|a|(T)T-T,S|S消除左遞歸；構(gòu)造相應(yīng)的FIRST和FOLLOW集合;構(gòu)造預(yù)測(cè)分析表(1)消除左遞

3、，文法變?yōu)镚S：S|aTST|S|aTST|SI此文法無左公共左因子。4、設(shè)文法G(S):S(T)|aS|aTT,S|S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的FIRST和FOLLOW集合;構(gòu)造預(yù)測(cè)分析表。.(1)S(L)|aSSS|eLSLFIRST(S)=a,(,eFIRST(L)=,eFOLLOW(S)=,),#FOLLOW(L)=)L,SL|eFIRST(S)=a,(,eFIRST(L)=,eFOLLOW(S)=,),#FOLLOW(L)=)FIRST(S)=a,(FIRST(L)=a,(FOLLOW(S)=,),#FOLLOW(L)=)(3)()a#SS(L)SaSSSSSeSSSeSe

4、LLSLLSLL,SLLLe5、已知文法G(S)：Sa|(T)TT,S|S給出句子(a,a),a)的最左推導(dǎo)并畫出語法樹；給出句型(T,a,(T)所有的短語、直接短語、素短語、最左素短語、句柄和活前綴。解：(1)最左推導(dǎo)：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a)語法樹：如圖A-16所示。a圖A-16(a,(a,a)的語法樹(2)句型(T,a,(T)的短語、直接短語、素短語、最左素短語、句柄、活前綴及語法樹(圖A-17)。短語：aIIT,aII(T)IIT,a,(T)II(T,a,(T)直接短語：aII(T)素短語：aII(T)最左素短語：a句柄：a活前綴：II(II(TII(T,II(T,aS(T)T,ST,S(T)a圖A-17(T,a,(T)的語法樹6、構(gòu)造下列正則表達(dá)式的確定性的有限狀態(tài)自動(dòng)機(jī)。(12%)aba(a|b)*a7、設(shè)Y=0,1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。(8分)答：構(gòu)造相應(yīng)的正規(guī)式：(0I1)*1(0I1)(3分)NFA:（2分）00確定化：（3分