【正文】 INT o AOPR o oCAL o A第三章一．填空題1．設(shè)A是符號(hào)串，且A=CD，則X3= 。一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是一組 ① 、一組 ② 、一組 ③ 、一組 ④ 、。5．文法G產(chǎn)生的 的全體是該文法描述的語(yǔ)言。7．已知文法G[E]：E：：=T|E+T|ETT：：=F|T*F|T/FF：：=（E）|i該文法的開始符號(hào)（識(shí)別符號(hào)）是① 終結(jié)符號(hào)集合VT是{② }，非終結(jié)符號(hào)集合VN是{③ }，句型T+T*F+i的簡(jiǎn)單短語(yǔ)有④. ，句柄為 ⑤ 。9．G[E]為: EE+T|ET TT*F|T/F|F F(E)|i 因?yàn)榇嬖谕茖?dǎo)序列: E=E+T=E+T*F 所以句型E+T*F 的短語(yǔ)有: ① 直接短語(yǔ)有: ② 句柄為: ③ 10．三型文法為： SaS|a 所描述的語(yǔ)言是{ an| n= }Sa|^|(T)TT,S|S(1) 下面對(duì)(a,(a,a)的推導(dǎo)為 推導(dǎo)：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T))=(a,(T,S)) =(a,(S,S))=(a,(a,S))=(a,(a,a))二 判斷題（ ） 1． 設(shè)G=（VN，VT，P，S），若P中的每一個(gè)產(chǎn)生式α→β滿足|β|≥|α|,僅僅S→ε除外，則文法G是上下文無(wú)關(guān)的或2型文法。（ ） 3． 設(shè)G=（VN，VT，P，S），若P中的每一個(gè)產(chǎn)生式α→β滿足α是一非終結(jié)符,則文法G是上下文有關(guān)的或2型文法。（ ） 5．若一文法G=（VN，VT，P，S）是3型文法，則該文法G一定是上下文有關(guān)文法。（ ）7．∑*具有可數(shù)的無(wú)窮數(shù)量的元素，ε∈∑*。（ ）10．已知語(yǔ)言L={anbn|n=1}，則文法A::=aAb|ε，可以產(chǎn)生語(yǔ)言L?？蛇x項(xiàng)有：a 文法G 的字匯表V中所有符號(hào)組成的符號(hào)串b 文法G的字匯表V 的閉包V*中的所有符號(hào)串c 由文法的識(shí)別符號(hào)推出的所有符號(hào)串d 由文法的識(shí)別符號(hào)推出的所有終結(jié)符號(hào)串3．一個(gè)語(yǔ)言的文法是 ?？蛇x項(xiàng)有：a Z::=aZb|aAb|b A::=aAb|bb Z::=aAb A::= aAb|b c Z::=AbB A::=Aa|a B::=Bb|bd A::=aAb A::=b5．設(shè)有文法G[I]：I→I1|I0|Ia|Ic|a|b|c下列符號(hào)串中是該文法的句子的有 。1．cc 可選項(xiàng)有： 2 4 2 47．一個(gè)句型中的最左 稱為該句型的句柄。3型文法也稱為（1） ，2型文法是（2） 。可選項(xiàng)有：→a →a A→aB c. a→d.10．.一個(gè)文法G包括四個(gè)組成部分依次為：一組（1），一組（2），一個(gè)（3），以及一個(gè)（4）可選項(xiàng)有： 11．設(shè)有文法G[S]：S：：=S*S|S+S|（S）|a該文法 二義性文法?？蛇x項(xiàng)有：a．并且 b．或者 c．連接 d．閉包13．G[E]為: EE+T|ET TT*F|T/F|F F(E)|i存在推導(dǎo)序列: E=E+T=E+T*F則E+T*F是一個(gè)a． 句型 b．句子14．已知文法G[E]：E→T|E+T|ET T→F|T*F|T/F F→(E)|i該文法的句型T+T*F+i的直接短語(yǔ)為（ ① ），該文法的句型T+T*F+I句柄為（ ② ）。2．為只包含數(shù)字、加號(hào)和減號(hào)的表達(dá)式，例如92+5，31，7等構(gòu)造一個(gè)文法。4．寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。不允許0打頭5．已知文法G: 〈表達(dá)式〉∷=〈項(xiàng)〉|〈表達(dá)式〉+〈項(xiàng)〉|〈表達(dá)式〉〈項(xiàng)〉 〈項(xiàng)〉∷=〈因子〉|〈項(xiàng)〉*〈因子〉|〈項(xiàng)〉/〈因子〉〈因子〉∷=（〈表達(dá)式〉）|i試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹。〈表達(dá)式〉∷=a|(〈表達(dá)式〉)|〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉∷=+||*|/7．令文法G［E］為：E→T|E+T|ETT→F|T*F|T/FF→(E)|i證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。（2） 該文法的產(chǎn)生式集合P可能有哪些元素？（3） 找出該句子的所有短語(yǔ)，簡(jiǎn)單短語(yǔ)，句柄。2．確定的有窮自動(dòng)機(jī)是一個(gè) 組。4. 編譯過(guò)程的第一個(gè)階段是 。6．如下有窮自動(dòng)機(jī)： 0,1 1 1 0 1CBAX Y該有窮自動(dòng)機(jī)為一個(gè)： ① （DFA/NFA），從圖中可看出初態(tài)集為{ ② }，終態(tài)集為：{ ③ }，有 ④ 個(gè)狀態(tài)。f(A,1)= ⑥ 。（ ）2．一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，∑，f , S , Z ） 其中之一K是有窮集，每個(gè)元素稱為一個(gè)狀態(tài)，∑為字母表，S∈K是唯 一的一個(gè)初態(tài)，f是轉(zhuǎn)換函數(shù)可為一個(gè)多值函數(shù)，若字母表∑含有n個(gè)輸入符，任何一個(gè)狀態(tài)可有n條以上的弧射出，而且每條弧以一個(gè)不同
的輸入字符標(biāo)記?？蛇x項(xiàng)有： b. 語(yǔ)法分析 c. 語(yǔ)義分析 d. 代碼生成 f. 表格管理 g. 出錯(cuò)管理2．通常高級(jí)語(yǔ)言的詞法規(guī)則可用正則式描述，詞法分析器可用（ ）來(lái)實(shí)現(xiàn)。 . b. 不可以 接受的。并給出該語(yǔ)言的正規(guī)式。目前常用的方法有 ②