編譯程序總復(fù)習-例題

編譯程序總復(fù)習——例題1.編譯程序的功能和組織結(jié)構(gòu)2.編譯和解釋程序3.正則表達式NFA→DFA→DFA最小化句型→推導(dǎo)的語法樹→短語→簡單短語→句柄6.文法←→語言←→句子7.語法分析——自頂向下和自底向上（LL法、LR法）8.語法制導(dǎo)翻譯9.中間代碼10.中間代碼優(yōu)化11.目標代碼1.編譯程序的功能和組織結(jié)構(gòu)表處理詞法分析源程序目標程序錯誤處理語法分析語義分析目標代碼生成前端后端中間代碼優(yōu)化中間代碼生成2.編譯和解釋程序目標程序源程序編譯程序初始數(shù)據(jù)計算結(jié)果源程序解釋程序初始數(shù)據(jù)計算結(jié)果功能工作結(jié)果實現(xiàn)技術(shù)上解釋程序源程序的一個執(zhí)行系統(tǒng)源程序的執(zhí)行結(jié)果執(zhí)行中間代碼編譯程序源程序的一個轉(zhuǎn)換系統(tǒng)源程序的目標代碼把中間代碼轉(zhuǎn)換成目標程序解釋程序和編譯程序的區(qū)別解釋程序和編譯程序的根本區(qū)別：是否生成目標代碼3.正則表達式設(shè)文法G[A]:A→[BB→X]|BAX→Xa|Xb|a|b試求出文法G[A]產(chǎn)生的語言對應(yīng)的正則式。3.設(shè)文法G[A]:

A→[B

B→X]|BA

X→Xa|Xb|a|b

試求出文法G[A]產(chǎn)生的語言對應(yīng)的正則式。解:

[(a|b)(a|b)*]([(a|b)(a|b)*])*4.請構(gòu)造與正則式R=(a*b)*ba(a|b)*等價的狀態(tài)最少的DFA（確定有限自動機）。解：(1)NFA(2)NFA→DFA(3)DFA最小化5.有文法G[E]：ET|E+T|E-T

TF|T*F|T/F

Fi/(E)請判斷(E+T)*i+F是G的一句型嗎？如果是，請畫出它的推導(dǎo)的語法樹。并寫出語法樹的短語、簡單短語、句柄。有文法G[E]：ET|E+T|E-TTF|T*F|T/FFi/(E)(E+T)*i+F是G的一句型)E(+ETE+ETTFF*TiF每棵子樹的葉組成短語(E+T)*i+F(E+T)*I(E+T)E+TiF每棵簡單子樹的葉組成簡單短語E+TiF最左簡單子樹的葉組成句柄

E+T6.（1）設(shè)有文法G[S]=(,{S,B},S,{S→b|bB,B→bS}),該文法所描述的語言是_________。

（2）已知語言L={anbbn|n≥1}，則_______文法可以產(chǎn)生語言L。

（3）設(shè)有文法G[I]：

I→I1|I0|Ic|a|b|c該文法的句子有________

①ab0②a0c01③aaa④bc106.

（1）設(shè)有文法G[S]=(,{S,B},S,{S→b|bB,B→bS}),該文法所描述的語言是

L（G[S]={b2i+1|i≥0}

（2）已知語言L={anbbn|n≥1}，則

Z→aAb

A→aAb|b

上述文法可以產(chǎn)生語言L。（3）設(shè)有文法G[I]：

I→I1|I0|Ic|a|b|c該文法的句子有②③④。

①ab0②a0c01③aaa④bc107.

設(shè)有文法G[S]：

S→E

E→Aa|bB

A→cA|d

B→cB|d

構(gòu)造其LR(0)分析表并利用分析表判斷acccd是否為文法G[S]的句子。

7.

設(shè)有文法G[S]：

S→E

E→Aa|bB

A→cA|d

B→cB|d

構(gòu)造其LR(0)分析表并利用分析表判斷acccd是否為文法G[S]的句子。

解：（1）識別活前綴的自動機（2）LR分析表（3）LR分析過程——即判斷acccd是否為文法G[S]的句子8.在一個移入-規(guī)約的分析中采用以下的語法制導(dǎo)的翻譯模式，在按一產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。

A→aB{print“0”}

A→c{print“”}

B

→Ab{print“2”}

當分析器的輸入為aacbb時，打印的字符串是什么？分析器輸入為aacbb，打印的字符為12020bBcAAaBAab⑤④③②①A→aB{print“0”}

A→c{print“”}

B

→Ab{print“2”}9.

（1）表達式a*b-c-d$e$f-g-h*I中，運算符的優(yōu)先級由高到低依次為-、*、$，且均右結(jié)合，且相應(yīng)的后綴式為______。

（2）表達式-a+b*c+d+(e*f)/d*e,如果運算符的優(yōu)先級由高到低依次為-、+、*、/，且均左結(jié)合，則其后綴式為______。9.

（1）表達式a*b-c-d$e$f-g-h*I中，運算符的優(yōu)先級由高到低依次為-、*、$，且相應(yīng)的后綴式為abcd--*efgh--I*$$。

（2）表達式-a+b*c+d+(e*f)/d*e，如果運算符的優(yōu)先級由高到低依次為-、+、*、/，且均左結(jié)合，則其后綴式為

a-b+cd+ef*+*de*/。10.試寫出算術(shù)表達式

a+b*c-(c*b+a-e)/(b*c+d)

優(yōu)化后的四元式序列。11.目標代碼寫出下列表達式的目標代碼T:=C*（A+B）+（A+B）C:=A+BA:=（C*D）+（E-F）

寫出下列表達式的目標代碼T:=C*（A+B）+（A+B）C:=A+BA:=（C*D）+（E-F）解答：LOAD A,R1ADD B,R1LOAD C,R2MULT R1,R2ADD R1,R2STORE G,R2LOAD E,R2SUB F,R2STORE C,R1MULT D,R1ADD R2,R1STORE A,R2編譯器設(shè)計方案?C－慣用的詞法?C－語言的TinyMachine運行時環(huán)境?C－的語法和語義?使用C－和TM的編程設(shè)計?C－的程序例子這里定義了一個編程語言稱作C－Minus(或簡稱為C－)，這是一種適合編譯器設(shè)計方案的語言，它比TIN