.z.一、填空題|〔每題4分，共20分〕1.喬母斯基定義的3型文法〔線性文法〕產(chǎn)生式形式ABa|a,或AaB|a，A，B∈Vn,a,b∈Vt。2.語(yǔ)法分析程序的輸入是單詞符號(hào)，其輸出是語(yǔ)法單位。3型為B.aB的LR〔0〕工程被稱為移進(jìn)工程，型為Ba.B的LR〔0〕工程被稱為待約工程，4.在屬性文法中文法符號(hào)的兩種屬性分別為繼承屬性和綜合屬性。5、運(yùn)行時(shí)存貯管理方案有靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配和堆式存儲(chǔ)分配和方案。二.文法G(S)(1)ET|E+T(2)TF|F*F(3)F〔E〕|i〔1〕寫出句型〔T*F+i〕的最右推到并畫出語(yǔ)法樹。〔4分〕〔2〕寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄?！?分〕答：〔1〕最右推到〔2分〕E==>T==>F==>(E)==>(E+T)==>(E+F)==>(E+i)==>(T+i)==>(T*F+i)(2)語(yǔ)法樹〔2分〕〔3〕〔4分〕短語(yǔ)：〔T*F+i〕，T*F+i，T*F，i直接短語(yǔ)：T*F，i句柄：T*F三.證明文法G(S)：SSaS|ε是二義的?！?分〕答：句子aaa對(duì)應(yīng)的兩顆語(yǔ)法樹為：因此，文法是二義文法四.給定正規(guī)文法G〔S〕：(1)SSa|Ab|b(2)ASa請(qǐng)構(gòu)造與之等價(jià)的DFA。〔6分〕答：對(duì)應(yīng)的NFA為：〔6分〕狀態(tài)轉(zhuǎn)換表：ab{F}Φ{S}{S}{S,A}Φ{S,A}{S,A}{S}五.構(gòu)造識(shí)別正規(guī)語(yǔ)言b*a(bb*a)*b*最小的DFA〔要求寫出求解過程〕?！?5分〕答：〔1〕對(duì)應(yīng)的NFA〔5分〕〔2〕將〔1〕所得的NFA確定化：〔5分〕ab{0}{1，3}{0}{1,3}Φ{2，3}{2,3}{1,3}{2,3}〔5分〕六.文法G(S):(1)S^|a|(T)(2)TT,S|S試：〔1〕消除文法的左遞歸；〔4分〕〔2〕構(gòu)造相應(yīng)的first和follow集合?！?分〕答：〔1〕消除文法的左遞歸后文法G’〔S〕為：(1)S^|a|(T)(2)TST’|S(3)T’,ST’|ε〔4分〕〔2〕〔6分〕firstfollowSa^(#,)Ta^()T’,ε)七.文法G(S):(1)SSiA|A(2)AA+B|B(3)BA*|〔試構(gòu)造非終止符的firstVT和lastVT集合?！?0分〕答：〔10分〕firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(FollowS#FollowS#Ba,b,#(1)SBB(2)BaB(3)Bb的follow集合如表：試：〔1〕給出該文法的LR〔0〕工程集標(biāo)準(zhǔn)族劃分；〔2〕填寫相應(yīng)的SLR〔1〕的分析表?！?5分〕答：〔1〕LR〔0〕工程集標(biāo)準(zhǔn)族劃分(8分)II0S’.SS.BBB.aBB.bI1I2--I3--I4SBabI1S’S.I2SB.BB.aBB.bI5--I3--I4BabI3Ba.BB.aBB.bI6--I3--I4BabI4Bb.I5SBB.I6BaB.(2)SLR(1)分析表〔7分〕狀態(tài)ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九．設(shè)*語(yǔ)言的not-then-else語(yǔ)句的語(yǔ)法形式為：SnotEthenS1其語(yǔ)義解釋為：針對(duì)自上而下的語(yǔ)法分析器，(1)分段產(chǎn)生式；〔3分〕(2)寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作?！?分〕答：〔1〕分段產(chǎn)生式〔3分〕及語(yǔ)義動(dòng)作(7分)(1)RnotEthen{Backpatch〔$2.FC，n*q〕;$$.chain=$2.Tc}(2)SRS1{Backpatch〔$2.chain，n*q〕}一、填空題|〔每題4分，共20分〕1.喬母斯基定義的2型文法〔上下文無(wú)關(guān)文法〕產(chǎn)生式形式Aβ,A∈Vn,β∈V+。2.詞法分析程序的輸入是字符串，其輸出是單詞符號(hào)。3算符有限分析方法每次都是對(duì)最左素短語(yǔ)進(jìn)展規(guī)約。型為BaB.的LR〔0〕工程被稱為規(guī)約工程。4、寫出*:=b*(d-e)/(c-d)+e的逆波蘭式__*bde-*cd-/e+:=__。5、常用的兩種動(dòng)態(tài)存貯分配方法是__棧式存儲(chǔ)分配和堆式存儲(chǔ)__分配。

二．文法G(S):(1)S^|a|(T)(2)TT,S|S試：〔1〕寫出句型〔a,(a,a))的最左推到并畫出語(yǔ)法樹?！?分〕〔2〕寫出上述句子的短語(yǔ)，直接短語(yǔ)和句柄?！?分〕答：〔1〕最左推到〔2分〕S==>〔T〕==>〔T,S〕==>(S,S)==>(a,S)==>(a,(T))==>(a,(T,S))==>(a,〔S,S))==>(a,〔a,S))==>(a,〔a,a))(2)語(yǔ)法樹〔2分〕〔3〕〔4分〕短語(yǔ)：〔a,(a,a)〕，a,(a,a)，(a,a)，a,a,a直接短語(yǔ)：a句柄：a三．證明文法G(S)：SaSb|Sb|b是二義的。〔6分〕答：句子aabbbb對(duì)應(yīng)的兩顆語(yǔ)法樹為：因此，文法是二義文法四.給定正規(guī)文法G〔S〕：(1)SaA(2)AaB|bA〔3〕BaA|b請(qǐng)構(gòu)造與之等價(jià)的DFA?！?分〕答：對(duì)應(yīng)的DFA為：〔6分〕五.構(gòu)造識(shí)別正規(guī)語(yǔ)言(ab*|a)*最小的DFA〔要求寫出求解過程〕?！?5分〕答：〔1〕對(duì)應(yīng)的NFA〔5分〕〔2〕將〔1〕所得的NFA確定化：〔5分〕ab{1}{1,2}Φ{1,2}{1,2}{1,2}〔5分〕六.文法G(S):(1)S^|a|(T)(2)TST’|S(3)T’,ST’|ε試：求first和follow集合，構(gòu)造改文法的LL〔1〕分析表?！?0分〕答：文法相應(yīng)的first和follow集合〔5分〕firstfollowSa^(#,)Ta^()T’,ε)其LL〔1〕分析表如下：七.文法G(S):(1)SSiA|A(2)AA+B|B(3)BA*|〔非終止符的firstVT和lastVT集合如下:firstVTlastVTSi,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(試構(gòu)造算符的優(yōu)先關(guān)系表?！?0分〕答：i+()*I><<<+>><<>(>>>)<<<*>>>八文法G(S):(1)Sa|aAb|b|bBa(2)A1A0|ε(3)B1B0|ε求：該文法的LR〔0〕工程集標(biāo)準(zhǔn)族?！?5分〕答：九．設(shè)*語(yǔ)言的DO-while語(yǔ)句的語(yǔ)法形式為：SdoS1whileE其語(yǔ)義解釋為：針對(duì)自上而下的語(yǔ)法分析器，(1)分段產(chǎn)生式；〔3分〕(2)寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作?！?分〕答：〔1〕分段產(chǎn)生式〔3分〕G(S):(1)Rdo(2)URS1while(3)SUE