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