【文章內(nèi)容簡介】 、證明下面文法是二義性的。P→PaP|PbP|cP|Pe|f 設(shè)一文法E→T|E+T|ET T→F|T*F|T/F F→(E)|i 證明E+T*(ET)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA將表達(dá)式（（B*D+A）/E+D）*F+G分別表示為三元式、四元式、逆波蘭式序列消除文法G[S]的左遞歸(G[S])G[S]：S→AB A→bB|Aa B→Sb|a 對下面的文法G[Z]Z→aB A→aB B→bB B→aA B→b 構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子三、問答題：(共50分)已知文法G S::=bBc|aAB A::=bAa|a B::=a|e寫出所有非終結(jié)符號的First集和Follow集，構(gòu)造預(yù)測分析表并給出輸入串a(chǎn)bbaaa分析過程。（10分） 正規(guī)式0（0|1）*1構(gòu)造該正規(guī)式所對應(yīng)的NFA（畫出狀態(tài)轉(zhuǎn)換圖）。將所求的NFA確定化和最小化。（分別畫出確定化和最小化的狀態(tài)轉(zhuǎn)換圖）。（10分）若有文法G（S）的產(chǎn)生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c構(gòu)造識別所有項目集規(guī)范族的DFA。（20分）判斷該文法是否是LR（0）文法，說明理由。判斷該文法是否是SLR（1）文法，說明理由。判斷該文法是否是LR（1）文法，說明理由。判斷該文法是否是LALR（1）文法，說明理由。簡述編譯的整個過程（10分）。德州學(xué)院期末考試試題（ 5 至 學(xué)年第 學(xué)期）課程名稱： 　　考試對象：　　　　　　　試卷類型： 　 　　考試時間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）要在某一臺機(jī)器上為某種語言構(gòu)造一個編譯程序，必須找掌握下述三方面的內(nèi)容：______。①高級語言 ②源語言 ③目標(biāo)語言 ④程序設(shè)計方法 ⑤編譯方法 ⑥測試方法 ⑦機(jī)器語言 可選項有 ①②③④⑤⑥⑦a、①③⑤ b、①②⑥ c、②③⑤ d、②④⑦“用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行?！边@種說法___________。a、不正確 b、正確若一個文法是遞歸的，則它所產(chǎn)生的句子個數(shù)___________。a、必定是無窮的 b、是有限個的 c、根據(jù)具體情況而定下列文法__________二義文法E::=EiT|T T::=T+F|iF|F F::=ET|(可選項有： a、是 b、不是 c、無法判斷。編譯程序的語法分析器接受以________為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。可選項有： a、表達(dá)式 b、產(chǎn)生式 c、 單詞 d、語句 文法G[Z]：Z→Be A→Ae|e B→Af D→f 中，________是多余產(chǎn)生式a、 Z→Be b、 A→Ae|e c、B→Af d、D→f算符優(yōu)先文法屬于________。a、自頂向下語法分析法 b、LR分析法 c、SLR分析法 d、自底向上語法分析法設(shè)有文法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}描述語言L={ambn|n≥m≥1}的文法是__________a、Z→ABb b、Z→ABb c、Z→Ab d、Z→aAbA→aA|a A→Aa|a A→aAb|a A→Ab|aAb|εB→bB|b B→aBb|b 一個句型中的最左_______稱為該句型的句柄。a、短語 b、直接短語 c、素短語 d、終結(jié)符號1通常高級語言的詞法規(guī)則可用正規(guī)式描述，詞法分析器可用_________來實現(xiàn)a、語法樹 b、有限自動機(jī) c、棧 d、堆1文法G[S]：S→AA A→Aa|a不是LR（1）文法，理由是_________。a、FIRST(S)∩FIRST(A)≠198。b、FIRST(A)∩FOLLOW(A)≠198。c、FIRST(Aa)∩FIRST(a)≠198。d、都不是1素短語是指_______的短語。①至少包含一個符號②至少包含一個非終結(jié)符號③至少包含一個終結(jié)符號④除自身外不再包含其它終結(jié)符號⑤除自身外不再包含其它非終結(jié)符號⑥除自身外不再包含其它短語⑦除自身外不再包含其它素短語可選項有：a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦ g、②⑦1給定文法G[S]：S→ACc A→aA|Sb C→Def D→hACDd|eC| E→bDe|ε 該文法是____________。 （1）右線性文法 （2）前后文無關(guān)文法 （3）左遞歸文法 （4）LL（1）文法可選項有：a、② b、③ c、②③ d、②③④1算符文法是指____________的文法。①沒有形如U→…VW…的規(guī)則 （U、V、W為非終結(jié)符）②終結(jié)符號集中任意兩個符號對之間至多有一種優(yōu)先關(guān)系成立③沒有相同的規(guī)則右部④沒有形如U→ε的規(guī)則可選項有a、① b、①② c、①②③ d、①②③④1下列正規(guī)表達(dá)式中________與(a|b)*(c|d)等價。a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)1若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部_______是該句型的句柄a、一定 b、不一定1前后文無關(guān)文法和正規(guī)文法所產(chǎn)生的語言類相比_______a、前后文無關(guān)文法產(chǎn)生的語言類大 b、正規(guī)文法產(chǎn)生的語言類大 c、兩者產(chǎn)生的語言類一樣大 d、無法比較1編譯過程中，比較常見的中間語言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹形表示可選項有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤LL（1）文法的條件是_______________。a、對形如U→X1|X2|…|Xn的規(guī)則，要求FIRST（Xi）)∩FIRST (Xj)=198。 (i≠j)b、對形如U→X1|X2|…|Xn的規(guī)則 若Xi222。* ε 則要求FIRST(Xj) ∩FOLLOW (U)=198。c、a和bd、都不是二、簡答題：（每小題5分，共30分）對于下面的文法G[S] S→Sa|Ab|b|c A→Bc|a B→Sb|b 構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串bcbabcba是否是該文法接受的句子設(shè)一文法G[T]：T→T*F|F F→F↑P|P P→(T)|i 證明T*P↑(T*F)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。Z→aZ|bZ|aA A→aB B→aA|b 將表達(dá)式（（A+B*D）/E+F）*F+G^E分別表示為三元式、四元式、逆波蘭式序列。（5分）消除文法G[S]的左遞歸G[S]：S→SA|A A→SB|B|(S)|() B→[S] | [ ]（5分）對下面的文法G[E]E→E+T|T|@T T→T*F|F F→P↑F|P P→i (+、@、*、↑、i是終結(jié)符號)構(gòu)造文法的算符優(yōu)先矩陣表，判斷此文法是否是算符優(yōu)先文法。三、問答題：（50分）已知文法G[S] S→eT|RT T→DR| e R→dR|e D→a|bd寫出所有非終結(jié)符號的First集和Follow集，構(gòu)造LL(1)分析表，判斷此文法是否是LL（1）文法。（10分） 給出正規(guī)式 (a|b)*bb(a|b)*構(gòu)造該正規(guī)式所對應(yīng)的NFA（畫出狀態(tài)轉(zhuǎn)換圖）。將所求的NFA確定化和最小化。（分別畫出確定化和最小化的狀態(tài)轉(zhuǎn)換圖）。（10分）若有文法G（S）的產(chǎn)生式如下：S→aAD|aBe|bBS|bAe A→g B→g D→d|e，構(gòu)造識別所有LR(1)項目集規(guī)范族的DFA。（20分）判斷該文法是否是LR（1）文法，說明理由，構(gòu)造LR（1）表。判斷該文法是否是LALR（1）文法，說明理由。簡述編譯的整個過程（10分）。德州學(xué)院期末考試試題（ 6 至 學(xué)年第 學(xué)期）課程名稱： 　　考試對象：　　　　　　　試卷類型： 　 　　考試時間： 分鐘一、 填空題（每空1分，共20分）假設(shè)G是一個文法，S是文法的開始符號，如果S*222。X，則稱X是 。喬姆斯基定義的四種形式語言分別為： 文法、 文法、 文法、 文法。設(shè)有文法G[I]： I→I1|I0|Ia|Ic|a|b|c ,下列符號串中是該文法的句子的有 （1）ab0 (2)a0c01 (3)aaa (4)bc10一個上下文無關(guān)文法G包含四個組成部分依次為：一組 ，一組 ，一個 ，以及一組 。確定的有窮自動機(jī)是一個 ，通常表示為 。編譯程序一般含有八部分，分別是 、 、 、 、 、 、 、 。二、 簡答題（每題5分，共30分）已知文法G[Z]：Z→U0|V1U→Z1|1V→Z0|0寫出全部由此文法描述的只含有四個符號的句子。文法G[N]為：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？設(shè)一文法G[S]S→（AS） S→（b） A→（SaA） A→（a）對于句子（（（b）a（a））（b）），寫出該句子的最左推導(dǎo)，畫出語法樹，寫出其全部短語，直接短語和句柄。 構(gòu)造下述文法G[S]的自動機(jī)： S→A0 A→A0|S1|0將表達(dá)式((a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列消除下列文法的左遞歸。S::=SaP|Sf|P P::=QbP|Q Q::=cSd|e三、 綜合題（共計50分） 把下圖確定化和最小化：（15分）0baaabbbbbaaa 已知文法G S::=bBc|aAB A::=bAa|a B::=a|e寫出所有非終結(jié)符號的First集和Follow集，構(gòu)造預(yù)測分析表并給出輸入串a(chǎn)bbaaa分析過程。（15分） 若有文法G（S）的產(chǎn)生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c構(gòu)造識別所有項目集規(guī)范族的DFA。（20分）判斷該文法是否是LR（0）文法，說明理由。判斷該文法是否是SLR（1）文法，說明理由。判斷該文法是否是LR（1）文法，說明理由。判斷該文法是否是LALR（1）文法，說明理由。德州學(xué)院期末考試試題（ 7 至 學(xué)年第 學(xué)期）課程名稱： 　　考試對象：　　　　　　　試卷類型： （1） 　 　　考試時間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）描述一個語言的文法是___________。a、唯一的 b、不唯一的 c、個數(shù)有限的匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序 b、機(jī)器語言程序 c、高級語言程序 d匯編語言或機(jī)器語言程序設(shè)有文法G[I]：I→I0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有___________________。①ab0 ②a0c01 ③aaa ④bc10 可選項有a、① b、②③④ c、③④ d、①②③④生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABC c、Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9 b、Z::=ABC