編譯原理復習題

-.z.一、填空題：〔10分，第1小題每2個1分，其余每空1分〕1、編譯程序一般含有八局部，分別是、、、、、、、。2、編譯程序與解釋程序的根本區(qū)別是3、一個上下文無關文法G包括四個組成局部依次為：一組_____、一個_____、一組_____、一組______。4、設G是一個文法，S是文法的開場符號，如果S**，則稱*是。二、選擇題〔本大題共15小題，每題1分，共15分〕1、編譯程序生成的目標程序是機器語言程序。A、一定B、不一定2、設有文法G[S]=〔,{S,B},S,{S→b|bB,B→bS}〕,該文法描述的語言是。A、bi|i≥0B、b2i|i≥0C、b2i+1|i≥0D、b2i+1|i≥13、設有文法G[S]： S→S*S|S+S|〔S〕|a該文法二義性文法A、是B、不是C、無法判斷4、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。A、匯編語言程序B、機器語言程序C、高級語言程序D、匯編語言或機器語言程序5、給定文法A→bA|cc,下面符號串中，為該文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①B、①③④⑤C、①⑤D、①④⑤E、①②③④⑤6、語法分析的常用方法是。①自頂向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③7、語言L={anbbn|n≥1}，則下述文法中，可以產(chǎn)生語言LA、Z→aZb|aAb|bA→aAb|bB、A→aAbA→bC、Z→AbBA→aA|aB→bB|bD、Z→aAbA→aAb|b8、以下正規(guī)表達式中________與(a|b)*(c|d)等價。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)9、算符優(yōu)先分析法每次都是對進展歸約。A、最左短語B、直接短語C、句柄D、素短語E、最左素短語10、簡單優(yōu)先分析法每次都是對進展歸約A、最左短語B、直接短語C、句柄D、素短語E、最左素短語11、以下文法G[S]]：S→AAA→Aa|a不是LR〔1〕文法，理由是A.、FIRST(S)∩FIRST〔A〕≠B、FIRST〔A〕∩FOLLOW〔A〕≠C、FIRST〔Aa〕∩FIRST〔a〕≠D、都不是12、設有文法G[E]：E→E*E|E+E|〔E〕|a該文法LR〔1〕文法A、是B、不是C、無法判斷13、對于文法G[A]：A→aABe|BaB→dB|有人說，因為FIRST〔aABe〕∩FOLLOW〔A〕≠并且FIRST〔Ba〕∩FOLLOW〔A〕≠，所以文法G[A]不是LL〔1〕文法。這種說法A、正確B、不正確14、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：A、①④B、①⑤C、①⑥D(zhuǎn)、②④E、③⑤F、③⑦G、②⑦15、表達式A*〔B-C*〔C/D〕〕的逆波蘭式為A、ABC-CD/**B、ABCCD/*-*C、ABC-*CD/*D、都不正確三、簡答題〔共35分〕(10分)現(xiàn)有文法G[E]:E→E+T|E-T|TT→T*F|T/F|FF→(E)|i畫出句型E+F*〔E+i〕的語法樹,找出它的短語，直接短語，句柄和素短語(5分)對下面的文法G[S]構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aba是否是該文法承受的句子：S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB(10分)將下面具有的NFA確定化SSABZaba(5分)求出以下文法所產(chǎn)生語言對應的正規(guī)式。S→aAA→bA|aB|bB→aA。(5分)構(gòu)造識別下面正規(guī)式的NFA〔a|b〕*ba。選擇題〔本大題共20小題，每題1分，共20分〕1、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序b、機器語言程序c、高級語言程序d匯編語言或機器語言程序2、描述一個語言的文法是___________。a、唯一的b、不唯一的c、個數(shù)有限的3、生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A4、設有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④5、現(xiàn)有前綴表示的表達式文法G1：E::=-EEE::=-EE::=a|b|c則文法的句子—a-bc的所有可能語法樹有______棵。a、1b、2c、3d、46、一個上下文無關文法G包括四個組成局部依次為：一組_____、一個_____、一組_____、一組______。a、字符串b、字母數(shù)字串c、產(chǎn)生式d、完畢符號e、開場符號f、文法g、非終結(jié)符號h、終結(jié)符號7、語法分析的常用方法是_________：①自頂向下②自底向上③自左向右④自右向左可選項有：a、①②③④b、①②c、③④d、①②③8、以下文法__________二義文法E::=EiT|TT::=T+F|iF|FF::=E*|(可選項有：a、是b、不是c、無法判斷。9、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦10、LR〔K〕文法是_________。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。11、在編譯中產(chǎn)生語法樹是為了____________。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼12、文法的二義性和語言的二義性是兩個____________概念。a、不同b、一樣c、無法判斷13、下述正規(guī)表達式中________與(a*+b)*(c+d)等價。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可選項有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤_______這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：a、存在b、不存在c、無法判定是否存在15、LL〔K〕文法________二義性的。a、都是b、都不是c、不一定都是16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可選項有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波蘭表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_______________。①便于進展存儲空間的組織②利于目標代碼優(yōu)化③利于編譯程序的移植④利于目標代碼的移植⑤利于提高目標代碼的質(zhì)量可選項有：a、②④b、①②③c、③④①d、②③④⑤20、代碼優(yōu)化的主要目標是_____________。①如何提高目標程序的運行速度②如何減少目標程序運行所需的空間。專業(yè)年級〔本、?？啤?*______________姓名專業(yè)年級〔本、?？啤?*______________姓名________________密封線④如何使生成的目標代碼盡可能簡短可選項有：a、②④b、①②③c、③④①d、②③④簡答題：〔每題5分，共35分〕證明下面文法是二義性的。S::=ibtSeS|ibtS|a現(xiàn)有文法S::=SaA|AA::=AbB|BB::=cSd|e請證實是文法的一個句型，并寫出該句型的所有短語、素短語以及句柄。求出以下文法所產(chǎn)生語言對應的正規(guī)式。S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA將表達式((a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列消除以下文法的左遞歸。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e給出與以下圖的NFA等價的正規(guī)文法。S0S2S0S2S1S3bεε7、對根本塊P畫出DAG圖B:=3D:=A+CE::=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在根本塊出口之后活潑，寫出優(yōu)化后的四元式序列。1、文法G1：P→aPQR|abR，RQ→QR，BQ→bb，bR→bc，cR→cc，它是chomsky哪一型文法？A、0型B、1型C、2型D、3型2、編譯程序必須完成的工作有①詞法分析②語法分析③語義分析④代碼生成⑤中間代碼生成⑥代碼優(yōu)化①②③④B、①②③④⑤C、①②③④⑥D(zhuǎn)、①②③④⑤⑥3、LR〔K〕文法________二義性的。A、都是B、都不是C、不一定都是4、語法分析的常用方法是________。①自頂向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③5、用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標代碼后才能投入運行，這種說法A、不正確B、正確6、生成非0開頭的正偶數(shù)集的文法是______________。A、Z::=ABCB、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9C、Z::=ABCD、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|97、文法G所描述的語言是的集合A、文法G的字匯表V中所有符號組成的符號串B、文法G的字匯表V的閉包V*中的所有符號串C、由文法的開場符號推出的所有符號串D、由文法的開場符號推出的所有終結(jié)符號串。8、給定文法G[I]:I→I1|I0|Ia|Ic|a|b|c,下面符號串中，為該文法句子的是。①ab0②a0c01③aaa④bc10A、①B、②③④C、③④D、①②③④9、____這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：A、存在B、不存在C、無法判定是否存在10、LR〔K〕文法是_________。A、從左到右分析，共經(jīng)過K步的一種編譯方法。B、從左到右分析，每次向前預測K步的一種編譯方法。C、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。D、從左到右分析，每次走K步的一種編譯方法。11、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波蘭表示是___________。A、a-bc*cd-/b-a*+-B、a-bc*/cd-b-a*+-C、abc*cd-b-a*+/--D、a-bc*cd-b-a*+/-12、設有文法G[S]=〔,{S,B},S,{S→b|bB,B→bS}〕,該文法描述的語言是。A、{b2i+1|i≥1}B、{b2i+1|i≥0}C、{bi|i≥0}D、{b2i|i≥013、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：A、①④B、①⑤C、①⑥D(zhuǎn)、②④E、③⑤F、③⑦G、②⑦14、算符優(yōu)先分析屬于分析方法。A、自頂向下B、自底向上C、自左向右D、自右向左15、簡單優(yōu)先分析法每次都是對進展歸約A、最左短語B、直接短語C、句柄D、素短語E、最左素短語16、文法G[S]：S→aSS→WS→UU→aV→bVV→acW→aW其中的全部無用符號是A、W，V，UB、V，bC、W，V，a,b,cD、W，V，b，c17、程序根本塊是指A、一個子程序B、一個僅有一個入口和一個出口的語句C、一個沒有嵌套的程序段D、一組順序執(zhí)行的程序段，僅有一個入口和一個出口18、設有文法G[Z]：Z→Z*Z|Z+Z|〔Z〕|a該文法二義性文法A、是B、不是C、無法判斷19、以下正規(guī)表達式中________與(a|b)*(c|d)等價。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)20、語法分析的任務是①分析單詞是怎樣構(gòu)成的②分析單詞串是如何構(gòu)成語句和說明的③分析語句和說明是如何構(gòu)成程序的④分析程序的構(gòu)造A、②③B、②③④C、③④D、①②③④二、〔簡答題，共計20分〕1、(10分)文法G〔T)：T→T*F|FF→F↑P|PP→(T)|i(1)寫出句型T*P↑〔T*F〕推導過程，畫出語法樹；(2)寫出句型T*P↑〔T*F〕的短語、直接短語、句柄和素短語。2、(5分)構(gòu)造識別下面正規(guī)式的NFAb〔aa|bb〕*ab3、〔5分〕消除文法G[S]的左遞歸G[S]：S→ABA→bB|AaB→Sb|a三、〔綜合題，共計30分〕1、(10分)將下面具有的NFA確定化和最小化SSABZaba專業(yè)年級〔本、?？啤?*______________姓名________________密封線2、(10分)〔1〕對下面的文法G[Z]Z→aBA→aBB→bBB→aAB→b構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法承受的句子〔2〕寫出G[Z]文法相應的正規(guī)式：3、〔10分〕設有以下文法G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|D→Se|〔1〕求出文法中每個非終結(jié)符的FOLLOW集〔2〕該文法是LL〔1〕文法嗎？構(gòu)造LL〔1〕分析表一、選擇題〔本大題共20小題，每題1分，共20分〕1、描述一個語言的文法是___________。a、唯一的b、不是唯一的c、個數(shù)有限的2、簡單優(yōu)先分析法每次都是對___________進展歸約。a、最左短語b、直接短語c、句柄d、素短語e、最左素短語3、設有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④4、LR〔K〕文法________二義性的。a、都是b、都不是c、不一定都是5、一個上下文無關文法G包括四個組成局部依次為：一組_____、一個_____、一組_____、一組______。a、字符串b、字母數(shù)字串c、產(chǎn)生式d、完畢符號e、開場符號f、文法g、非終結(jié)符號h、終結(jié)符號6、文法G所描述的語言是__________的集合a、文法G的字匯表V中所有符號組成的符號串b、文法G的字匯表V的閉包V*中的所有符號串c、由文法的開場符號推出的所有符號串d、由文法的開場符號推出的所有終結(jié)符號串。7、設有文法G[Z]：Z→Z*Z|Z+Z|〔Z〕|a該文法_______二義性文法a、是b、不是c、無法判斷8、語法分析的常用方法是_________：①自頂向下②自底向上③自左向右④自右向左可選項有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、文法的二義性和語言的二義性是兩個____________概念。a、不同b、一樣c、無法判斷12、在編譯中產(chǎn)生語法樹是為了____________。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼13、以下正規(guī)表達式中________與(a|b)*(c|d)等價。a、〔a*|b*〕(c|d)b、〔a*|b*〕*(c|d)c、(ab)*(d|c)d、〔a*b*〕(cd)_______這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：a、存在b、不存在c、無法判定是否存在文法G[S]：S→aSS→WS→UU→aV→bVV→acW→aW其中的全部無用符號是〔〕a、〔W，V，U〕b、〔V，b〕c、〔W，V，a,b,c〕d、〔W，V，b，c〕16、ab3的另一種表示方法是〔〕a、abbbb、abababc、abbaabd、aaabbb17、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波蘭表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_______________。①便于進展存儲空間的組織②利于目標代碼優(yōu)化③利于編譯程序的移植④利于目標代碼的移植⑤利于提高目標代碼的質(zhì)量可選項有：a、②④⑤b、①②③c、③④①d、②③④⑤20、設有文法G[S]=〔,{S,B},S,{S→b|bB,B→bS}〕,該文法描述的語言是〔〕。a、{b2i+1|i≥1}b、{b2i+1|i≥0}c、{bi|i≥0}d、{b2i|i≥0}二、簡答題：〔每題5分，共30分〕1、證明下面文法是二義性的。P→PaP|PbP|cP|Pe|f2、設一文法E→T|E+T|E-TT→F|T*F|T/FF→(E)|i證明E+T*(E-T)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出以下文法所產(chǎn)生語言對應的正規(guī)式。S→bS|aAA→aA|bBB→aA|bC|bC→bS|aA4、將表達式〔〔B*D+A〕/E+D〕*F+G分別表示為三元式、四元式、逆波蘭式序列5、消除文法G[S]的左遞歸(G[S])G[S]：S→ABA→bB|AaB→Sb|a6、對下面的文法G[Z]Z→aBA→aBB→bBB→aAB→b構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法承受的句子一、選擇題〔本大題共20小題，每題1分，共20分〕1、要在*一臺機器上為*種語言構(gòu)造一個編譯程序，必須找掌握下述三方面的內(nèi)容：______。①高級語言②源語言③目標語言④程序設計方法⑤編譯方法⑥測試方法⑦機器語言可選項有①②③④⑤⑥⑦a、①③⑤b、①②⑥c、②③⑤d、②④⑦2、"用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標代碼后才能投入運行。〞這種說法___________。a、不正確b、正確3、假設一個文法是遞歸的，則它所產(chǎn)生的句子個數(shù)___________。a、必定是無窮的b、是有限個的c、根據(jù)具體情況而定4、以下文法__________二義文法E::=EiT|TT::=T+F|iF|FF::=ET|(可選項有：a、是b、不是c、無法判斷。5、編譯程序的語法分析器承受以________為單位的輸入，并產(chǎn)生有關信息供以后各階段使用?？蛇x項有：a、表達式b、產(chǎn)生式c、單詞d、語句6、文法G[Z]：Z→BeA→Ae|eB→AfD→f中，________是多余產(chǎn)生式a、Z→Beb、A→Ae|ec、B→Afd、D→f7、算符優(yōu)先文法屬于________。a、自頂向下語法分析法b、LR分析法c、SLR分析法d、自底向上語法分析法8、設有文法G[S]=〔{a}，{S,B}，S，{S→a|aB,B→aS}〕,該文法描述的語言是_____a、{ai|i≥0}b、{a2i|i≥0}c、{a2i+1|i≥0}d、{a2i+1|i≥1}9、描述語言L={ambn|n≥m≥1}的文法是__________a、Z→ABbb、Z→ABbc、Z→Abd、Z→aAbA→aA|aA→Aa|aA→aAb|aA→Ab|aAb|εB→bB|bB→aBb|b10、一個句型中的最左_______稱為該句型的句柄。a、短語b、直接短語c、素短語d、終結(jié)符號11、通常高級語言的詞法規(guī)則可用正規(guī)式描述，詞法分析器可用_________來實現(xiàn)a、語法樹b、有限自動機c、棧d、堆12、文法G[S]：S→AAA→Aa|a不是LR〔1〕文法，理由是_________。a、FIRST(S)∩FIRST(A)≠b、FIRST(A)∩FOLLOW(A)≠c、FIRST(Aa)∩FIRST(a)≠d、都不是13、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦14、給定文法G[S]：S→ACcA→aA|SbC→DefD→hACDd|eC|E→bDe|ε該文法是____________。〔1〕右線性文法〔2〕前后文無關文法〔3〕左遞歸文法〔4〕LL〔1〕文法可選項有：a、②b、③c、②③d、②③④15、算符文法是指____________的文法。①沒有形如U→…VW…的規(guī)則〔U、V、W為非終結(jié)符〕②終結(jié)符號集中任意兩個符號對之間至多有一種優(yōu)先關系成立③沒有一樣的規(guī)則右部④沒有形如U→ε的規(guī)則可選項有a、①b、①②c、①②③d、①②③④16、以下正規(guī)表達式中________與(a|b)*(c|d)等價。a、〔a*|b*〕(c|d)b、〔a*|b*〕*(c|d)c、(ab)*(d|c)d、〔a*b*〕(cd)17、假設一個句型中出現(xiàn)了*一產(chǎn)生式的右部，則此右部_______是該句型的句柄a、一定b、不一定18、前后文無關文法和正規(guī)文法所產(chǎn)生的語言類相比_______a、前后文無關文法產(chǎn)生的語言類大b、正規(guī)文法產(chǎn)生的語言類大c、兩者產(chǎn)生的語言類一樣大d、無法比擬19、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④b、②③④c、③④①⑤d、②③④⑤20、LL〔1〕文法的條件是_______________。a、對形如U→*1|*2|…|*n的規(guī)則，要求FIRST〔*i〕)∩FIRST(*j)=(i≠j)b、對形如U→*1|*2|…|*n的規(guī)則假設*i*ε則要求FIRST(*j)∩FOLLOW(U)=c、a和bd、都不是二、簡答題：〔每題5分，共30分〕1、對于下面的文法G[S]S→Sa|Ab|b|cA→Bc|aB→Sb|b構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串bcbabcba是否是該文法承受的句子2、設一文法G[T]：T→T*F|FF→F↑P|PP→(T)|i證明T*P↑(T*F)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出以下文法所產(chǎn)生語言對應的正規(guī)式。Z→aZ|bZ|aAA→aBB→aA|b4、將表達式〔〔A+B*D〕/E+F〕*F+G^E分別表示為三元式、四元式、逆波蘭式序列。5、〔5分〕消除文法G[S]的左遞歸G[S]：S→SA|AA→SB|B|(S)|()B→[S]|[]專業(yè)專業(yè)年級〔本、?？啤?*______________姓名________________密封線E→E+T|T|TT→T*F|FF→P↑F|PP→i(+、、*、↑、i是終結(jié)符號)構(gòu)造文法的算符優(yōu)先矩陣表，判斷此文法是否是算符優(yōu)先文法。填空題〔每空1分，共20分〕1、假設G是一個文法，S是文法的開場符號，如果S**，則稱*是。2、喬姆斯基定義的四種形式語言分別為：文法、文法、文法、文法。3、設有文法G[I]：I→I1|I0|Ia|Ic|a|b|c,以下符號串中是該文法的句子的有〔1〕ab0(2)a0c01(3)aaa(4)bc104、一個上下文無關文法G包含四個組成局部依次為：一組，一組，一個，以及一組。5、確定的有窮自動機是一個，通常表示為。6、編譯程序一般含有八局部，分別是、、、、、、、。簡答題〔每題5分，共30分〕1、文法G[Z]：Z→U0|V1U→Z1|1V→Z0|0寫出全部由此文法描述的只含有四個符號的句子。2、文法G[N]為：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？3、設一文法G[S]S→〔AS〕S→〔b〕A→〔SaA〕A→〔a〕對于句子〔〔〔b〕a〔a〕〕〔b〕〕，寫出該句子的最左推導，畫出語法樹，寫出其全部短語，直接短語和句柄。構(gòu)造下述文法G[S]的自動機：S→A0A→A0|S1|05、將表達式((a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列6、消除以下文法的左遞歸。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e一、選擇題〔本大題共20小題，每題1分，共20分〕1、描述一個語言的文法是___________。a、唯一的b、不唯一的c、個數(shù)有限的2、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序b、機器語言程序c、高級語言程序d匯編語言或機器語言程序3、設有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④4、生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|95、一個上下文無關文法G包括四個組成局部依次為：一組_____、一個_____、一組_____、一組______。a、字符串b、字母數(shù)字串c、產(chǎn)生式d、完畢符號e、開場符號f、文法g、非終結(jié)符號h、終結(jié)符號6、現(xiàn)有前綴表示的表達式文法G1：E::=-EEE::=-EE::=a|b|c則文法的句子—a-bc的所有可能語法樹有______棵。a、1b、2c、3d、47、以下文法__________二義文法E::=EiT|TT::=T+F|iF|FF::=E*|(可選項有：a、是b、不是c、無法判斷。8、語法分析的常用方法是_________：①自頂向下②自底向上③自左向右④自右向左可選項有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、文法的二義性和語言的二義性是兩個____________概念。a、不同b、一樣c、無法判斷12、在編譯中產(chǎn)生語法樹是為了____________。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼13、下述正規(guī)表達式中________與(a*+b)*(c+d)等價。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可選項有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤_______這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：a、存在b、不存在c、無法判定是否存在15、LL〔K〕文法________二義性的。a、都是b、都不是c、不一定都是16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可選項有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波蘭表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_______________。①便于進展存儲空間的組織②利于目標代碼優(yōu)化③利于編譯程序的移植④利于目標代碼的移植⑤利于提高目標代碼的質(zhì)量可選項有：a、②④b、①②③c、③④①d、②③④⑤20、代碼優(yōu)化的主要目標是_____________。①如何提高目標程序的運行速度②如何減少目標程序運行所需的空間。專業(yè)年級〔本、專科〕**______________姓名專業(yè)年級〔本、專科〕**______________姓名________________密封線④如何使生成的目標代碼盡可能簡短可選項有：a、②④b、①②③c、③④①d、②③④二、簡答題：〔每題5分，共30分〕1、寫一個文法使其語言為L(G)={anbmambn|m,n≥1}。2、對于文法G(E):ET|E+TTF|T*FF(E)|i〔1〕寫出句型(T*F+i)的最右推導并畫出語法樹。〔2〕寫出上述句型的短語，直接短語、句柄和素短語。3、求出以下文法所產(chǎn)生語言對應的正規(guī)式。S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA4、將表達式((a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列5、消除以下文法的左遞歸。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e6、給出與以下圖的NFA等價的正規(guī)文法。S0S2S0S2S1S3bcεε選擇題〔本大題共20小題，每題1分，共20分〕1、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：A、①④B、①⑤C、①⑥D(zhuǎn)、②④E、③⑤F、③⑦G、②⑦2、表達式ab+cd+*的逆波蘭式表達式所表示的中綴形式的表達式是A、a+b+c*dB、(a+b)*(c+d)C、(a+b)*c+dD、a+b*c+d3、Chomsky的3型語言是這樣一種語言，其產(chǎn)生式限制為〔、、為字符串〕。A、A→B、A→aA→aBC、→D、A→4、設有文法G[S]=〔,{S,B},S,{S→b|bB,B→bS}〕,該文法描述的語言是。A、bi|i≥0B、b2i|i≥0C、b2i+1|i≥0D、b2i+1|i≥15、設有文法G[S]： S→S*S|S+S|〔S〕|a該文法二義性文法A、是B、不是C、無法判斷6、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。A、匯編語言程序B、機器語言程序C、高級語言程序D、匯編語言或機器語言程序7、給定文法A→bA|cc,下面符號串中，為該文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①B、①③④⑤C、①⑤D、①④⑤E、①②③④⑤8、遞歸下降分析語法分析的屬于分析方法。A、自頂向下B、自底向上C、自左向右D、自右向左9、語言L={anbbn|n≥1}，則下述文法中，可以產(chǎn)生語言LA、Z→aZb|aAb|bA→aAb|bB、A→aAbA→bC、Z→AbBA→aA|aB→bB|bD、Z→aAbA→aAb|b10、假設一個句型中出現(xiàn)了*一產(chǎn)生式的右部，則此右部________是句柄。A、一定B、不一定11、考慮文法G[A]：A→A∨B|BC→∧DB→BC|D→〔A〕|i,該文法LL(1)文法。A、是B、不是12、簡單優(yōu)先分析法每次都是對進展歸約A、最左短語B、直接短語C、句柄D、素短語E、最左素短語13、以下文法G[S]：S→AAA→Aa|a不是LR〔1〕文法，理由是A.、FIRST(S)∩FIRST〔A〕≠B、FIRST〔A〕∩FOLLOW〔A〕≠C、FIRST〔Aa〕∩FIRST〔a〕≠D、都不是14、設有文法G[E]：E→E*E|E+E|〔E〕|a該文法LR〔1〕文法A、是B、不是C、無法判斷15、對于文法G[A]A→ABe|BaB→dB|有人說，因為FIRST〔aABe〕∩FOLLOW〔A〕≠并且FIRST〔Ba〕∩FOLLOW〔A〕≠，所以文法G[A]不是LL〔1〕文法。這種說法A、正確B、不正確16、以下正規(guī)表達式中________與(a|b)*(c|d)等價。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)17、假設一個句型中出現(xiàn)了*一產(chǎn)生式的右部，則此右部_______是該句型的句柄A、一定B、不一定18、前后文無關文法和正規(guī)文法所產(chǎn)生的語言類相比_______A、前后文無關文法產(chǎn)生的語言類大B、正規(guī)文法產(chǎn)生的語言類大C、兩者產(chǎn)生的語言類一樣大D、無法比擬19、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：A、①③④B、②③④C、③④①⑤D、②③④⑤20、LL〔1〕文法的條件是_______________。A、對形如U→*1|*2|…|*n的規(guī)則，要求FIRST〔*i〕)∩FIRST(*j)=(i≠j)B、對形如U→*1|*2|…|*n的規(guī)則假設*i*ε則要求FIRST(*j)∩FOLLOW(U)=C、a和bD、都不是二、綜合題：〔共35分〕1、(10分)對于文法G(S):(1)寫出句型b(Ma)b的最右推導并畫出語法樹。(2)寫出上述句型的短語，直接短語和句柄。(5分)對下面的文法G[S]構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)abca是否是該文法承受的句子：S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d(10分)將下面具有的NFA確定化eeS0S2S3mnS1專業(yè)年級〔本、?？啤?*______________姓名________________密封線4、(5分)求出以下文法所產(chǎn)生語言對應的正規(guī)式。S→aSS→bAS→bA→aS5、(5分)構(gòu)造識別下面正規(guī)式的NFAab〔a|b〕*一、選擇題〔本大題共20小題，每題1分，共20分〕1、文法的二義性和語言的二義性是兩個____________概念。a、不同b、一樣c、無法判斷2、在編譯中產(chǎn)生語法樹是為了____________。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼3、下述正規(guī)表達式中________與(a*+b)*(c+d)等價。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可選項有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤4、______這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：a、存在b、不存在c、無法判定是否存在5、LL〔K〕文法________二義性的。a、都是b、都不是c、不一定都是6、現(xiàn)有前綴表示的表達式文法G1：E::=-EEE::=-EE::=a|b|c則文法的句子—a-bc的所有可能語法樹有______棵。a、1b、2c、3d、47、以下文法__________二義文法E::=EiT|TT::=T+F|iF|FF::=E*|(可選項有：a、是b、不是c、無法判斷。8、語法分析的常用方法是_________：①自頂向下②自底向上③自左向右④自右向左可選項有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、描述一個語言的文法是___________。a、唯一的b、不唯一的c、個數(shù)有限的12、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序b、機器語言程序c、高級語言程序d匯編語言或機器語言程序13、設有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④14、生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|915、一個上下文無關文法G包括四個組成局部依次為：一組_____、一個_____、一組_____、一組______。a、字符串b、字母數(shù)字串c、產(chǎn)生式d、完畢符號e、開場符號f、文法g、非終結(jié)符號h、終結(jié)符號16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可選項有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、編譯過程中，比擬常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波蘭表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_______________。①便于進展存儲空間的組織②利于目標代碼優(yōu)化③利于編譯程序的移植④利于目標代碼的移植⑤利于提高目標代碼的質(zhì)量可選項有：a、②④b、①②③c、③④①d、②③④⑤20、代碼優(yōu)化的主要目標是_____________。①如何提高目標程序的運行速度②如何減少目標程序運行所需的空間。專業(yè)年級〔本、?？啤?*______________姓名專業(yè)年級〔本、?？啤?*______________姓名________________密封線④如何使生成的目標代碼盡可能簡短可選項有：a、②④b、①②③c、③④①d、②③④二、簡答題：〔共30分〕(5分)證明下面文法是二義性的。P::=PaP|PbP|cP|Pe|f(10分)對于文法G(E):ET|E+TTF|T*FF(E)|i(1)寫出句型T*F+i1*i2的最右推導并畫出語法樹。(2)寫出上述句型的短語，直接短語、句柄、素短語和最左素短語。3、(5分)求出以下文法所產(chǎn)生語言對應的正規(guī)式。S::=aAA::=bA|aB|bB::=aA4、(5分)寫出表達式a+b*(c-d)對應的逆波蘭式、三元式序列和抽象語法樹。5、(5分)寫一個文法使其語言為L(G)={anbncm|m,n≥1，n為奇數(shù)，m為偶數(shù)}。一、選擇題〔本大題共20小題，每題1分，共20分〕1、描述一個語言的文法是___________。a、唯一的b、不唯一的c、個數(shù)有限的2、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序b、機器語言程序c、高級語言程序d匯編語言或機器語言程序3、設有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④4、生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8