【正文】 b(B b 歸約8bAb歸約9bAb移進(jìn)10S接受 A=6, B=16傳值 A=2, B=4(G)={danbm |n0, m≥0}： 因為文法G[S]存在句子aa有兩個不同的最左推導(dǎo)，所以文法G[S]是是二義性的。print a end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? , 使其語言為 L(G)={anbncm| n0為奇數(shù)， m0為偶數(shù)}:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。b:=2。z:=z+x。={a,b}，則正規(guī)式a*b|b*a 表示的正規(guī)集是什么？？其作用是什么？：…procedure print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? ＋b*(cd)/e的逆波蘭式和三元序列。 b:=3。 z:=y*z+xend。13. 基本的優(yōu)化方法有哪幾種？14. 寫一個文法G, 使其語言為 L(G)={abn| n≥0}15. 考慮下面的程序：…procedure p(x, y, z)。8. 寫一個文法G, 使其語言為 L(G)={albmclanbn| l=0, m=1, n=2} 9. 已知文法G(S):S→a| (T)T→T,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a..(..=..)..,....請計算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。Print A, B end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 A, B的值是什么? 5．文法G(S)S→dABA→aA| aB→Bb| ε描述的語言是什么？6. 證明文法G(S) S→SaS| ε 是二義性的。B:=A*2。z:=z*z。4. 考慮下面的程序：…procedure四、簡答題：, 使其語言為 不以0開頭的偶數(shù)集。 ，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。，至少含有一個終結(jié)符，并且，除它自身外不再含任何更小的素短語。，根據(jù)每個產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法 叫做語法制導(dǎo)翻譯。，有時為了確定詞性，需超前掃描若干個字符。，S劃文法的開始符號，假定αβδ是文法G的一個句型，如果有SαAδ且Aβ，則稱β是句型αβδ相對非終結(jié)符A的短語。，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。，用它可形成和產(chǎn)生一組合式的程序。，記錄該過程的各外層過程的最新活動記錄的起始地址。三、名詞解釋題：。（上下文無關(guān)）文法；3型文法又稱為（正則 ）文法。，僅含終結(jié)符號的句型稱為 ( 句子 )。， FORTRAN采用( 靜態(tài)策略， PASCAL采用( 動態(tài))策略。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進(jìn)行的。而且實際上至少要有一個（終 ）態(tài)。（ 分析表 ）和一個（ 符號棧 ）進(jìn)行聯(lián)合控制的。(傳地址），（傳值），（傳名），可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)（棧式）動態(tài)分配和（堆式）動態(tài)分配。（ 源程序中 ）中識別出一個個（ 單詞符號 ）。 ，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。 ( )答案：1. 2. 3. 4.√ 5.√ 6. 7. 8. 9.√ 10. 11.12.√ 13. 14.√ 15.√ 16.√ 17. 18.√ 19.√ 20. 21.√ 22.√二、填空題： （ 詞法分析） ，（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標(biāo)代碼生成 ）五個階段。 ( )。 ( )。 ( )。 ( )。 ( )。 ( )。 X ( )，不利于對中間代碼進(jìn)行優(yōu)化。 （ ）。 （ ）。 （ ）。 其SLR(1)分析表為： 對輸入串a(chǎn)b給出分析過程為： 一、是非題：，可以是終結(jié)符或非終結(jié)符。對于I2來說有也有與I0完全相同的結(jié)論。A AaAd|aAb|ε 下面構(gòu)造它的LR(0)項目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進(jìn)歸約沖突，該文法不是LR(0)文法。 　?。?0分）已知文法 AaAd|aAb| ε 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab 給出分析過程。解：該語句的四元式序列如下(其中EE2和E3分別對應(yīng)A＜C∧B＜D、A≥1和A≤D，并且關(guān)系運算符優(yōu)先級高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (j,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 1135. 已知文法 G[S] 為 S → aSb|Sb|b ，試證明文法 G[S] 為二義文法。else while (A ≤ D)A=A+2。解：消除文法G[S]的左遞歸： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε3. 試為表達(dá)式 w+(a+b)*(c+d/(e10)+8) 寫出相應(yīng)的逆波蘭表示。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。 6．局部優(yōu)化是在__基本塊___范圍內(nèi)進(jìn)行的一種優(yōu)化。4．一個LR分析器包括兩部分：一個總控程序和___一張分析表__。 2．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進(jìn)行___詞法分析__并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用?！?D．( ) 代碼外提10．編譯程序使用_____區(qū)別標(biāo)識符的作用域。 　C．( ) 刪除多余運算　　A. ( ) 強(qiáng)度削弱 D．( ) A┐B∨∧CD∨ 8. 優(yōu)化可生成_____的目標(biāo)代碼?！. ( ) ┐AB∨∧CD∨ 　　　　B．( ) A┐B∨CD∨∧ 　　B．( ) 臨時變量 　C．( ) 符號表 D．( ) 以上三項都是 6．四元式之間的聯(lián)系是通過_____實現(xiàn)的。C．( ) 編譯方法 　A．( )源程序　A．( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 　　　B．( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 　　　C．( ) 最左推導(dǎo)和最右推導(dǎo)必定相同 　 B．( ) (xyx)* C．( ) xnyxn(n≥0) B．( ) M1和M2的有向邊條數(shù)相等　C．( ) M1和M2所識別的語言集相等 　　D．( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3． 文法G：S→xSx|y所識別的語言是_____。 　 　 ()二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1．詞法分析器的輸出結(jié)果是_____。 ()9．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 (√ )7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。()3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)?！毒幾g原理》考試試題及答案（匯總）一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分）1．編譯程序是對高級語言程序的解釋執(zhí)行。( )2．一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。 (√ )4．語法分析時必須先消除文法中的左遞歸 。 (√)6．逆波蘭表示法表示表達(dá)式時無須使用括號。 ()8．進(jìn)行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 ( )10．一個語義子程序描述了一個文法所對應(yīng)的翻譯工作?！．( ) 單詞的種別編碼 　　　　　　B．( ) 單詞在符號表中的位置 　C．( ) 單詞的種別編碼和自身值 　　D．( ) 單詞自身值2． 正規(guī)式 M 1 和 M 2 等價是指_____。 　A．( ) M1和M2的狀態(tài)數(shù)相等 　A．( ) xyx D．( ) x*yx* 4．如果文法G是無二義的，則它的任何句子α_____。 　　　D．( )可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同 5．構(gòu)造編譯程序應(yīng)掌握______?！　　．( ) 目標(biāo)語言 　A．( ) 指示器 D．( ) 程序變量 7．表達(dá)式(┐A∨B)∧(C∨D)的逆波蘭表示為_____。C．( ) AB∨┐CD∨∧ 　A．( ) 運行時間較短 　 　　B．( ) 占用存儲空間較小　C．( ) 運行時間短但占用內(nèi)存空間大 　　　 D．( ) 運行時間短且占用存儲空間小9．下列______優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的?！　　?B．( ) 刪除歸納變量 　A. ( ) 說明標(biāo)識符的過程或函數(shù)名　B．( ) 說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次　C．( ) 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 　D. ( ) 標(biāo)識符的行號三、填空題(每空1分，共10分)1．計算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。3．自上而下分析法采用___移進(jìn)__、歸約、錯誤處理、___接受__等四種操作。5．后綴式abc/所代表的表達(dá)式是___a/(bc)__。四、簡答題（20分）1. 簡要說明語義分析的基本功能。2. 考慮文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左遞歸及提取公共左因子。解： w a b + c d e 10 / + 8 + * +4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (AC ∧ BD) { if (A ≥ 1) C=C+1。}。證明： 　　　　　由文法G[S]：S→aSb|Sb|b，對句子aabbbb對應(yīng)的兩棵語法樹為：　　 因此，文法G[S]為二義文法。解：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有： S39。對于I0來說有：FOLLOW(A)∩{a}={b,d,}∩{a}=Φ，所以在I0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,時歸約，為其他時報錯。這就是說，以上的移進(jìn)歸約沖突是可以解決的，因此該文法是SLR(1)文法。 ( )。 （ ）。 （ ）。 ( )。 （ ），語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 X ( )，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。 ( )(1)文法。 ( )(1)文法一定是無二義的。 ( )，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。 ( )。