【正文】 +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、③④⑤______這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示： a、存在 b、不存在 c、無(wú)法判定是否存在LL（K）文法________二義性的。 a、都是 b、都不是 c、不一定都是現(xiàn)有前綴表示的表達(dá)式文法G1：E::=EE E::=E E::=a|b|c則文法的句子—abc的所有可能語(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ú)法判斷。語(yǔ)法分析的常用方法是_________：①自頂向下 ②自底向上 ③自左向右 ④自右向左 可選項(xiàng)有：a、①②③④ b、①② c、③④ d、①②③LR（K）文法是_________。a、從左到右分析，共經(jīng)過(guò)K步的一種編譯方法。b、從左到右分析，每次向前預(yù)測(cè)K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號(hào)串后看K個(gè)輸入符號(hào)的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。素短語(yǔ)是指_______的短語(yǔ)。①至少包含一個(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描述一個(gè)語(yǔ)言的文法是___________。a、唯一的 b、不唯一的 c、個(gè)數(shù)有限的1匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語(yǔ)言程序 b、機(jī)器語(yǔ)言程序 c、高級(jí)語(yǔ)言程序 d匯編語(yǔ)言或機(jī)器語(yǔ)言程序1設(shè)有文法G[I]：I→I0|I1|I a|Ic|a|b|c下列符號(hào)串中是該文法的句子的有___________________。①ab0 ②a0c01 ③aaa ④bc10 可選項(xiàng)有a、① b、②③④ c、③④ d、①②③④1生成非0開(kāi)頭的正偶數(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 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|91一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分依次為：一組_____、一個(gè)_____、一組_____、一組______。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下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x 可選項(xiàng)有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b1編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹(shù)形表示可選項(xiàng)有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤1a（b*c/（cd）+（b）*a）的逆波蘭表示是___________。a、abc*cdba*+/ b、abc*cdba*+/c、abc*cd/ba*+ d、abc*/cdba*+1在編譯程序中安排中間代碼生成的目的是_______________。①便于進(jìn)行存儲(chǔ)空間的組織②利于目標(biāo)代碼優(yōu)化③利于編譯程序的移植④利于目標(biāo)代碼的移植⑤利于提高目標(biāo)代碼的質(zhì)量可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④⑤代碼優(yōu)化的主要目標(biāo)是_____________。①如何提高目標(biāo)程序的運(yùn)行速度②如何減少目標(biāo)程序運(yùn)行所需的空間。③如何協(xié)調(diào)①和② ④如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④二、簡(jiǎn)答題：（共30分） (5分) 證明下面文法是二義性的。P::=PaP|PbP|cP|Pe|f (10分) 對(duì)于文法G(E):E174。T|E+TT174。F|T*FF174。(E)|i(1) 寫(xiě)出句型T*F+i1*i2的最右推導(dǎo)并畫(huà)出語(yǔ)法樹(shù)。(2) 寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。(5分) 求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式。S::=aA A::=bA|aB|b B::=aA(5分) 寫(xiě)出表達(dá)式a+b*(cd)對(duì)應(yīng)的逆波蘭式、三元式序列和抽象語(yǔ)法樹(shù)。(5分)寫(xiě)一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)={anbncm| m,n≥1，n為奇數(shù)，m為偶數(shù)}。三、問(wèn)答題：（共計(jì)50分）已知文法G S::=aBc|bAB A::=aAb|b B::=b|e構(gòu)造預(yù)測(cè)分析表并給出輸入串baabbb分析過(guò)程。（10分）構(gòu)造正規(guī)式 (0|1)*00 相應(yīng)的DFA并進(jìn)行化簡(jiǎn)。(15分) 若有文法G（S）的產(chǎn)生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（15分）（1） 判斷該文法是否是LR（0）文法，說(shuō)明理由。（2） 判斷該文法是否是SLR（1）文法，說(shuō)明理由。（3） 判斷該文法是否是LR（1）文法，說(shuō)明理由。（4） 判斷該文法是否是LALR（1）文法，說(shuō)明理由。 （10分）對(duì)文法G(S)：S 174。 S 218。 a T | a T | 218。 a TT 174。 217。 a T | 217。 a(1) 消除該文法的左遞歸和提取左公因子；(2) 構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3) 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。德州學(xué)院期末考試試題（ 10 至 學(xué)年第 學(xué)期）課程名稱(chēng)： 　　考試對(duì)象：　　　　　　　試卷類(lèi)型： 　 　　考試時(shí)間： 分鐘一、選擇題（本大題共20小題，每小題1分，共20分）描述一個(gè)語(yǔ)言的文法是___________。a、唯一的 b、不唯一的 c、個(gè)數(shù)有限的匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語(yǔ)言程序 b、機(jī)器語(yǔ)言程序 c、高級(jí)語(yǔ)言程序 d匯編語(yǔ)言或機(jī)器語(yǔ)言程序設(shè)有文法G[I]：I→I0|I1|I a|Ic|a|b|c下列符號(hào)串中是該文法的句子的有___________________。①ab0 ②a0c01 ③aaa ④bc10 可選項(xiàng)有a、① b、②③④ c、③④ d、①②③④生成非0開(kāi)頭的正偶數(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 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、字符串 b、字母數(shù)字串 c、產(chǎn)生式 d、結(jié)束符號(hào) e、開(kāi)始符號(hào) f、文法 g、非終結(jié)符號(hào) h、終結(jié)符號(hào)現(xiàn)有前綴表示的表達(dá)式文法G1：E::=EE E::=E E::=a|b|c則文法的句子abc的所有可能語(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ú)法判斷。語(yǔ)法分析的常用方法是_________：①自頂向下 ②自底向上 ③自左向右 ④自右向左 可選項(xiàng)有：a、①②③④ b、①② c、③④ d、①②③LR（K）文法是_________。a、從左到右分析，共經(jīng)過(guò)K步的一種編譯方法。b、從左到右分析，每次向前預(yù)測(cè)K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號(hào)串后看K個(gè)輸入符號(hào)的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。素短語(yǔ)是指_______的短語(yǔ)。①至少包含一個(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è)____________概念。a、不同 b、相同 c、無(wú)法判斷1在編譯中產(chǎn)生語(yǔ)法樹(shù)是為了____________。a、語(yǔ)法分析 b、語(yǔ)義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼1下述正規(guī)表達(dá)式中________與(a*+b)*(c+d)等價(jià)。? 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、都是 b、都不是 c、不一定都是1下面的文法是__________。S::=aAa|aBb|bAb|bBa A::=x B::=x 可選項(xiàng)有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b1編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有___________。①波蘭表示②逆波蘭表示③三元式④四元式⑤樹(shù)形表示可選項(xiàng)有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤1a（b*c/（cd）+（b）*a）的逆波蘭表示是___________。a、abc*cdba*+/ b、abc*cdba*+/c、abc*cd/ba*+ d、abc*/cdba*+1在編譯程序中安排中間代碼生成的目的是_______________。①便于進(jìn)行存儲(chǔ)空間的組織②利于目標(biāo)代碼優(yōu)化③利于編譯程序的移植④利于目標(biāo)代碼的移植⑤利于提高目標(biāo)代碼的質(zhì)量可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④⑤代碼優(yōu)化的主要目標(biāo)是_____________。①如何提高目標(biāo)程序的運(yùn)行速度②如何減少目標(biāo)程序運(yùn)行所需的空間。③如何協(xié)調(diào)①和② ④如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短可選項(xiàng)有：a、②④ b、①②③ c、③④① d、②③④二、簡(jiǎn)答題：（每小題5分，共30分）1 證明下面文法是二義性的。P::=PaP|PbP|cP|Pe|f設(shè)一文法S→AB S→c A→bA A→a B→aSb B→c 對(duì)于句子bbaacb寫(xiě)出其全部短語(yǔ)，直接短語(yǔ)和句柄。求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式。S::=aA A::=bA|aB|b B::=aA表達(dá)式（a+b）*c/de*f分別表示三元式、四元式