【正文】 c01 ③aaa ④bc10A、① B、②③④ C、③④ D、①②③④ ____這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示：A、存在 B、不存在 C、無(wú)法判定是否存在LR（K）文法是_________。D、從左到右分析，每次走K步的一種編譯方法。①至少包含一個(gè)符號(hào)②至少包含一個(gè)非終結(jié)符號(hào)③至少包含一個(gè)終結(jié)符號(hào)④除自身外不再包含其它終結(jié)符號(hào)⑤除自身外不再包含其它非終結(jié)符號(hào)⑥除自身外不再包含其它短語(yǔ)⑦除自身外不再包含其它素短語(yǔ)可選項(xiàng)有：A、①④ B、①⑤ C、①⑥ D、②④ E、③⑤ F、③⑦ G、②⑦1算符優(yōu)先分析屬于 分析方法。　T→T*F|F（10分）對(duì)于文法G[S]：S→aBb | aAa |bAb|bBa A→x B→x （1）判斷該文法是否是LR（1）文法，構(gòu)造LR（1）分析表（2）判斷該文法是否是LALR（1）文法，說(shuō)明理由德州學(xué)院期末考試試題（ 4 至 學(xué)年第 學(xué)期）課程名稱(chēng)： 　　考試對(duì)象：　　　　　　　試卷類(lèi)型： （1） 　 　　考試時(shí)間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）描述一個(gè)語(yǔ)言的文法是___________。a、都是 b、都不是 c、不一定都是一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分依次為：一組_____、一個(gè)_____、一組_____、一組______。b、從左到右分析，每次向前預(yù)測(cè)K步的一種編譯方法。①至少包含一個(gè)符號(hào)②至少包含一個(gè)非終結(jié)符號(hào)③至少包含一個(gè)終結(jié)符號(hào)④除自身外不再包含其它終結(jié)符號(hào)⑤除自身外不再包含其它非終結(jié)符號(hào)⑥除自身外不再包含其它短語(yǔ)⑦除自身外不再包含其它素短語(yǔ)可選項(xiàng)有：a、①④ b、①⑤ c、①⑥ d、②④ e、③⑤ f、③⑦ g、②⑦1文法的二義性和語(yǔ)言的二義性是兩個(gè)____________概念。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹(shù)形表示可選項(xiàng)有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤1a（b*c/（cd）+（b）*a）的逆波蘭表示是___________。P→PaP|PbP|cP|Pe|f 設(shè)一文法E→T|E+T|ET T→F|T*F|T/F F→(E)|i 證明E+T*(ET)是它的一個(gè)句型，并指出該句型的全部短語(yǔ)，直接短語(yǔ)，句柄和素短語(yǔ)。將所求的NFA確定化和最小化。判斷該文法是否是SLR（1）文法，說(shuō)明理由。德州學(xué)院期末考試試題（ 5 至 學(xué)年第 學(xué)期）課程名稱(chēng)： 　　考試對(duì)象：　　　　　　　試卷類(lèi)型： 　 　　考試時(shí)間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）要在某一臺(tái)機(jī)器上為某種語(yǔ)言構(gòu)造一個(gè)編譯程序，必須找掌握下述三方面的內(nèi)容：______。a、必定是無(wú)窮的 b、是有限個(gè)的 c、根據(jù)具體情況而定下列文法__________二義文法E::=EiT|T T::=T+F|iF|F F::=ET|(可選項(xiàng)有： a、是 b、不是 c、無(wú)法判斷。a、短語(yǔ) b、直接短語(yǔ) c、素短語(yǔ) d、終結(jié)符號(hào)1通常高級(jí)語(yǔ)言的詞法規(guī)則可用正規(guī)式描述，詞法分析器可用_________來(lái)實(shí)現(xiàn)a、語(yǔ)法樹(shù) b、有限自動(dòng)機(jī) c、棧 d、堆1文法G[S]：S→AA A→Aa|a不是LR（1）文法，理由是_________。d、都不是1素短語(yǔ)是指_______的短語(yǔ)。a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)1若一個(gè)句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部_______是該句型的句柄a、一定 b、不一定1前后文無(wú)關(guān)文法和正規(guī)文法所產(chǎn)生的語(yǔ)言類(lèi)相比_______a、前后文無(wú)關(guān)文法產(chǎn)生的語(yǔ)言類(lèi)大 b、正規(guī)文法產(chǎn)生的語(yǔ)言類(lèi)大 c、兩者產(chǎn)生的語(yǔ)言類(lèi)一樣大 d、無(wú)法比較1編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有___________。* ε 則要求FIRST(Xj) ∩FOLLOW (U)=198。（5分）消除文法G[S]的左遞歸G[S]：S→SA|A A→SB|B|(S)|() B→[S] | [ ]（5分）對(duì)下面的文法G[E]E→E+T|T|T T→T*F|F F→P↑F|P P→i (+、*、↑、i是終結(jié)符號(hào))構(gòu)造文法的算符優(yōu)先矩陣表，判斷此文法是否是算符優(yōu)先文法。（分別畫(huà)出確定化和最小化的狀態(tài)轉(zhuǎn)換圖）。簡(jiǎn)述編譯的整個(gè)過(guò)程（10分）。設(shè)有文法G[I]： I→I1|I0|Ia|Ic|a|b|c ,下列符號(hào)串中是該文法的句子的有 （1）ab0 (2)a0c01 (3)aaa (4)bc10一個(gè)上下文無(wú)關(guān)文法G包含四個(gè)組成部分依次為：一組 ，一組 ，一個(gè) ，以及一組 。文法G[N]為：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的語(yǔ)言是什么？設(shè)一文法G[S]S→（AS） S→（b） A→（SaA） A→（a）對(duì)于句子（（（b）a（a））（b）），寫(xiě)出該句子的最左推導(dǎo)，畫(huà)出語(yǔ)法樹(shù)，寫(xiě)出其全部短語(yǔ)，直接短語(yǔ)和句柄。（20分）判斷該文法是否是LR（0）文法，說(shuō)明理由。德州學(xué)院期末考試試題（ 7 至 學(xué)年第 學(xué)期）課程名稱(chēng)： 　　考試對(duì)象：　　　　　　　試卷類(lèi)型： （1） 　 　　考試時(shí)間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）描述一個(gè)語(yǔ)言的文法是___________。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 d、Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分依次為：一組_____、一個(gè)_____、一組_____、一組______。a、從左到右分析，共經(jīng)過(guò)K步的一種編譯方法。素短語(yǔ)是指_______的短語(yǔ)。⑥ 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可選項(xiàng)有:a、① b、② c、③ d、④ e、⑤ f、④⑤ g、③④⑤1 _______這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示： a、存在 b、不存在 c、無(wú)法判定是否存在1LL（K）文法________二義性的。a、abc*cdba*+/ b、abc*cdba*+/c、abc*cd/ba*+ d、abc*/cdba*+1在編譯程序中安排中間代碼生成的目的是_______________。對(duì)于文法G(E): E174。（2） 寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)、句柄和素短語(yǔ)。S0S2S1S3 a b c ε ε三、問(wèn)答題：（共計(jì)50分） 已知文法G A::=aABe|a B::=Bb|d（1） 給出與上述文法等價(jià)的LL（1）文法G’。構(gòu)造文法G(S)：(1) S 174。假定輸入串為abab，請(qǐng)給出LR分析過(guò)程(即按照步驟給出狀態(tài)，符號(hào)，輸入串的變化過(guò)程)（15分）。 A、bi | i≥0 B、b2i | i≥0 C、b2i+1 | i≥0 D、b2i+1 | i≥1設(shè)有文法G[S]： S→S*S|S+S|（S）|a 該文法 二義性文法 A、是 B、不是 C、無(wú)法判斷匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。A、一定 B、不一定 1考慮文法G[A]：A→A∨B|B C→∧D B→BC| D→（A）|i, 該文法 LL(1)文法。 D、都不是 1設(shè)有文法G[E]：E→E*E|E+E|（E）|a 該文法 LR（1）文法 A、是 B、不是 C、無(wú)法判斷1對(duì)于文法G[A] A→ABe|Ba B→dB|e 有人說(shuō)，因?yàn)镕IRST（aABe）∩FOLLOW（A）≠198。A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)1若一個(gè)句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部_______是該句型的句柄A、一定 B、不一定1前后文無(wú)關(guān)文法和正規(guī)文法所產(chǎn)生的語(yǔ)言類(lèi)相比_______A、前后文無(wú)關(guān)文法產(chǎn)生的語(yǔ)言類(lèi)大 B、正規(guī)文法產(chǎn)生的語(yǔ)言類(lèi)大 C、兩者產(chǎn)生的語(yǔ)言類(lèi)一樣大 D、無(wú)法比較1編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有___________。* ε 則要求FIRST(Xj) ∩FOLLOW (U)=198。S→aS S→bA S→b A→aS (5分)構(gòu)造識(shí)別下面正規(guī)式的NFAab（a|b）*四、綜合題（共45分）(10分)計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。a、不同 b、相同 c、無(wú)法判斷在編譯中產(chǎn)生語(yǔ)法樹(shù)是為了____________。a、1 b、2 c、3 d、4下列文法__________二義文法E::=EiT|T T::=T+F|iF|F F::=E*|(可選項(xiàng)有： a、是 b、不是 c、無(wú)法判斷。c、從左到右分析，每次向貌似句柄的符號(hào)串后看K個(gè)輸入符號(hào)的一種編譯方法。a、唯一的 b、不唯一的 c、個(gè)數(shù)有限的1匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、字符串 b、字母數(shù)字串 c、產(chǎn)生式 d、結(jié)束符號(hào) e、開(kāi)始符號(hào) f、文法 g、非終結(jié)符號(hào) h、終結(jié)符號(hào)1下面的文法是__________。①便于進(jìn)行存儲(chǔ)空間的組織②利于目標(biāo)代碼優(yōu)化③利于編譯程序的移植④利于目標(biāo)代碼的移植⑤利于提高目標(biāo)代碼的質(zhì)量可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④⑤代碼優(yōu)化的主要目標(biāo)是_____________。T|E+TT174。(5分) 求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式。（10分）構(gòu)造正規(guī)式 (0|1)*00 相應(yīng)的DFA并進(jìn)行化簡(jiǎn)。（3） 判斷該文法是否是LR（1）文法，說(shuō)明理由。 a T | a T | 218。 a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。①ab0 ②a0c01 ③aaa ④bc10 可選項(xiàng)有a、① b、②③④ c、③④ d、①②③④生成非0開(kāi)頭的正偶數(shù)集的文法是______________。語(yǔ)法分析的常用方法是_________：①自頂向下 ②自底向上 ③自左向右 ④自右向左 可選項(xiàng)有：a、①②③④ b、①② c、③④ d、①②③LR（K）文法是_________。d、從左到右分析，每次走K步的一種編譯方法。a、語(yǔ)法分析 b、語(yǔ)義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼1下述正規(guī)表達(dá)式中________與(a*+b)*(c+d)等價(jià)。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹(shù)形表示可選項(xiàng)有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤1a（b*c/（cd）+（b）*a）的逆波蘭表示是___________。③如何協(xié)調(diào)①和② ④如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④二、簡(jiǎn)答題：（每小題5分，共30分）1 證明下面文法是二