模板資料資源共享綜合題庫一、簡述編譯程序的功能，并解釋編譯程序和解釋程序的區(qū)別。答：編譯程序的功能：編譯程序的功能是把高級語言寫成的程序轉(zhuǎn)換成匯編語言程序或機器語言程序。編譯程序和解釋程序的區(qū)別：在計算機上執(zhí)行一個高級語言程序，編譯程序是首先通過編譯程序把源程序翻譯成機器語言程序，然后執(zhí)行目標程序；解釋程序是采用邊翻譯邊執(zhí)行的解釋執(zhí)行方式來執(zhí)行高級語言程序。二、編譯過程一般分為幾個階段？各階段的輸入輸出分別為什么？三、判斷題：（1）詞法分析器的輸入是符號串。（）×源程序（2）兩個有窮自動機等價是指它們的狀態(tài)數(shù)相等。（）×所識別的語言相等（3）表達式（┐a∨b）∧（c∨d）的逆波蘭表示為a┐b∨∧cd∨。（）×a┐b∨cd∨∧（4）非終結(jié)符可以有綜合屬性，但不能有繼承屬性。（）×也可以有繼承屬性（5）基本塊有一個入口語句和多個出口。（）×只有一個出口四、文法G[S]為：SaABAaB則判斷G為LL（1）文法的條件是什么？答：條件是：（1）文法G不含左遞歸；（2）對于每個非終結(jié)符，F(xiàn)irst(α)、First(β)、First(γ)兩兩不相交；（3）對于每個非終結(jié)符，不含能推出ε的產(chǎn)生式，故不考慮非終結(jié)符的First集和Follow集相交的情況。五、已知文法G[E]:E→E+T|TT→T*E|FF→(E)|i試畫出句型(T+i)*i+F的語法樹，并指出該句型的所有的短語，簡單短語和句柄。解：語法樹:EE+EE+TTT*EFFE()+ETTFiTFi(T+i)T+iTiF簡單短語：TiF句柄：T六、設有文法定義：<實型變量說明>→real<標識符表><標識符表>→<標識符表>，i<標識符表>→i將該文法縮寫后并拓廣為G[S’]如下：1.S’→S（此規(guī)則可以省略）2.S→rD3.D→D,i4.D→i試判別G[S’]文法為SLR(1)文法，并寫出該文法的SLR(1)矩陣。解：follow(S)=follow(S’)={#}follow(S)∩{，}=φ滿足上述條件則可利用SLR(1)方法。轉(zhuǎn)化情況如下：七、設文法G為：EeAf|eBg AaA|a BBb|a對于輸入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合適的一種進行分析。解：原文法不是LL（1）文法，因為存在左遞歸和左公共因子，故不能直接使用LL（1）分析法進行分析。步驟如下：1、拓廣文法：①E’→E②E→eAf③E→eBg④A→aA⑤A→a⑥B→Bb⑦B→a2、項目集規(guī)范族：Ba.Ba.由項目集規(guī)范族可判斷，原文法非LR（0）文法，因為8存在移進-規(guī)約沖突，4存在規(guī)約-規(guī)約沖突和移進-規(guī)約沖突，故不能直接使用LR（0）分析法進行分析。因此，使用SLR（1）分析法分析原文法。3、構造SLR（1）分析表如下：FOLLOW(A)={f}；FOLLOW(B)={b,g}；FOLLOW(E)={#}。ACTIONGOTO狀態(tài)abefg#ABE0S211acc2S4353S64S8r7r5r775S10S96r27r48S8r579r310r6r64、分析輸入串eaaaf如下：步驟狀態(tài)符號輸入串動作10#eaaaf#預備202#eaaaf#移進3024#eaaaf#移進40248#eaaaf#移進502488#eaaaf#移進602487#eaaAf#歸約70247#eaAf#歸約8023#aAf#歸約90236#aAf#移進1001#E#歸約11acc接受八、為句子a+a*a構造兩個不同的最右推導來證明下述文法G[〈表達式〉]是二義的。

〈表達式〉∷=a|(〈表達式〉)|〈表達式〉〈運算符〉〈表達式〉〈運算符〉∷=+|-|*|/答：

最右推導1〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉a

〈表達式〉*a

〈表達式〉〈運算符〉〈表達式〉*a

〈表達式〉〈運算符〉a*a

〈表達式〉+a*a

a+a*a

最右推導2〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉〈表達式〉〈運算符〉a

〈表達式〉〈運算符〉〈表達式〉*a

〈表達式〉〈運算符〉a*a

〈表達式〉+a*a

a+a*a九、構造正規(guī)式1(0|1)*101相應的DFA.答：先構造NFA：

用子集法將NFA確定化01XAAAABABACABACAABYABYACAB

除X，A外，重新命名其他狀態(tài)，令AB為B、AC為C、ABY為D，因為D含有Y（NFA的終態(tài)），所以D為終態(tài)。01XAAABBCBCADDCBDFA的狀態(tài)圖：:

十、將正規(guī)表達式0*(0|10)*0*確定化并化簡。解：首先構造NFA為

用子集法確定化：II0I1{X,0,1,3,Y}

{0,1,3,Y}

{2}

{1,3,Y}{0,1,3,Y}

{0,1,3,Y}

{1,3,Y}

{1,3,Y}{2}

{2}

{2}

重新命名狀態(tài)集：S011

2

3

42

2

4

43

3

3DFA的狀態(tài)圖：

可將該DFA最小化：

首先劃分終態(tài)組為{1,2,4}，非終態(tài)組為{3}。{1,2,4}0∈{1,2,4}，{1,2,4}1∈{3}，所以1,2,4為等價狀態(tài)，可合并為兩個狀態(tài)。十一、文法G[S]：試用LL(1)分析法分析輸入串a(chǎn)bbcde.解：①消除左遞歸得文法（無公共左因子）：②求必要的FIRST和FOLLOW。FIRST(S)=FIRS