07級編譯原理期末復習

1、07級編譯原理期末復習一、概念編譯器；詞法分析器；語法分析器；lex；yacc； 代碼生成器；編譯系統(tǒng)；單詞（token）；屬性（attribute）；符號表； 上下文無關文法（cfg）；語言；字符串；正則表達式；前綴；后綴；子串；語法產(chǎn)生式；終結符；非終結符； 重寫規(guī)則；屬性文法；繼承屬性；綜合屬性；語義規(guī)則；語義動作；自頂向下分析（top-down）；自底向上分析（bottom-up）；dfa；nfa；ll；算符優(yōu)先算法；slr；lr；lalr； 狀態(tài)轉(zhuǎn)換表；語法分析表；回溯；消除左遞規(guī)；提取左因式；右遞規(guī)； 最左推導；最右推導；規(guī)約；句型；句子（sentence）；句柄（handle）；

2、語法樹；移進-規(guī)約沖突；規(guī)約-規(guī)約沖突； 棧幀；棧指針；活動記錄/幀；存儲分配策略；函數(shù)參數(shù)傳遞；lr(0)項目集；lr(1)項目集；同心集； 中綴表示；后綴表示；前綴表示；三地址表示；rtl；二、幾個重要的關系 正則表達式語言； 語法語言； 正則表達式語法； llslrlrlalr； 中綴表示前、后綴表示； 最右推導句柄； 最左、最右推導語法分析；三、算法消除左遞歸和提取左公共因子；thompson構造法；子集構造法；正則表達式直接構造dfa；構造first集合；構造follow集合；構造ll(1)語法分析表；構造lr(0)項目集；構造slr(1)語法分析表；構造lr(1)項目集；構造lr(

3、1)/lalr(1)語法分析表；構造屬性文法（左遞規(guī)，右遞規(guī)，運算表達式，類型聲明）；構造語法制導翻譯的語義動（包括自頂向下和自底向上）；三地址表示的代碼生成；匯編表示的代碼生成； http:/ 將下列中綴式改寫為逆波蘭式。 (1) -a*(b+c)(d-e) (2) (a*d+c)/d+e)*f+g (3) a+x4(cd*3) (4) abc+d*ef recursive消除下列文法的左遞歸性。 （1）ssasa asbab a(s)a( ) bsb (2) sassb asaaa (3) s(t)sa sts tt,s re/ll 構造識別如下正規(guī)語言的dfa： 01(0|1) *1 對

4、于如下的文法，topdown語法分析。 pbegin d; x end xd;x xsy y;sy y ll 驗證下列文法是否為ll(1)文法。 (1)sabscda aabac bdecec cdfd dfede e (2) saabbcds aasda bsacbec bcsf ccgc dabdd slr對于下列的文法，試分別構造它們的lr(0)項目集規(guī)范族及識別全部活前綴的dfa。 (1)sasbsasc sab (2) scasccb acaaa bccbbb (3) sassbsasss sc (4)saaab aa slr下列文法是否為slr(1)文法?若是，構造相應的slr(1

5、)分析表，若不是，則闡明其理由。 (1) ssabsbr rsra (2)sasabsba aaaab bb (3)sasbsbsa sab (4)saasbb acada bcbddb lr/lalr 對于文法gs: saaba abab bb (1) 構造lr(1)分析表； (2) 給出用lr(1)分析表對輸入符號串a(chǎn)bab的分析過程。 ar下面文法給出是pascal說明的文法，寫出變量類型的一個屬性文法。decl -var-list: type var-list - var-list, id | idtype -int | float 文法規(guī)則語義規(guī)則declvar-list: type

6、var-list.dtype=type.dtypevar-list1var-list2, idvar-listidtypeintegertype.dtype = integertyperealtype.dtype = realvar-list2.in=var-list1.dtypevar-list2.dtype=var-list2.inid.in=var-list1.dtypeid.in = var-list.dtypevar-list2.dtype=var-list1.dtypeid.dtype=var-list1.dtypeid.dtype = var-list.dtype 請按語法制導的

7、定義，將后綴表達式翻譯請按語法制導的定義，將后綴表達式翻譯成中綴表達式。注意，不允許出現(xiàn)冗余括成中綴表達式。注意，不允許出現(xiàn)冗余括號，后續(xù)表達式的文法如下：號，后續(xù)表達式的文法如下： e-ee+ e-ee* e-id 語法制導定義語法制導定義 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 s-e print e.code e-e1e2+ e.code=e1.code|+|e2.code; e.op=+ e-e1e2* if e1.op=+ and e2.op=+ then e.code=(|e1.code|)|*|(|e2.code|); else if e1.op=+then e.code=(|e1.co

8、de|)|*|e2.code; else if e2.op=+then e.code=e1.code|*|(|e2.code|); else e.code=e1.code|*|e2.code|; e一一id e.code:=id.lexeme; 假設變量的說明是由下列文法生成的：假設變量的說明是由下列文法生成的： di l l,i l | :t tinteger | real 1）建立一個語法制導定義，把每一個標志）建立一個語法制導定義，把每一個標志符的類型加在符號表中符的類型加在符號表中 2）為）為1）構造一個預翻譯程序）構造一個預翻譯程序 1)type為綜合屬性，代表類型屬性，為綜合屬性，

9、代表類型屬性， 函數(shù)函數(shù)addtype實現(xiàn)向符號表中實現(xiàn)向符號表中i對應項填類型信息。對應項填類型信息。 語法制導定義語法制導定義 產(chǎn)生式產(chǎn)生式 語義動作語義動作 di l d.type:=l.type addtype(i.entry, d.type) l,i l1 l.type:=l1.type addtype(i.entry, l.type) l:t l.type:=t.type tinteger t.type:=integer treal t.type:=real b) 采用遞歸下降分析法編寫預翻譯程序：采用遞歸下降分析法編寫預翻譯程序： procedure d; begin if lo

10、okahead=id then begin match(id); d.type=l; addtype(id.entry,d.type) end else error end function l: datatype; begin if lookahead=, then begin match(,); if lookahead=id then begin match(id); l.type=l; addtype(id.entry,l.type); return(l.type) end else error end else if lookahead=: then begin match(:);

11、l.type=t; return(l.type) end else error end function t: datatype; begin if lookahead=integer then begin match(integer); return(integer) end else if lookahead=real then begin match(real); return(real) end else error end 下面文法產(chǎn)生的表達式是對整型和實型常數(shù)應用下面文法產(chǎn)生的表達式是對整型和實型常數(shù)應用算符算符+形成的。當兩個整數(shù)相加時形成的。當兩個整數(shù)相加時,結果為整數(shù)，結果為

12、整數(shù)，否則為實數(shù)。否則為實數(shù)。 e tr r + tr| tnum.num | num a)給出語法制導定義確定每個子表達式的類型。給出語法制導定義確定每個子表達式的類型。 b) 把表達式翻譯成前綴形式，并且決定類型。試把表達式翻譯成前綴形式，并且決定類型。試用一元運算符用一元運算符inttoreal把整型值轉(zhuǎn)換為相等的實把整型值轉(zhuǎn)換為相等的實型值，以使得前綴表達式中兩個運算對象是同類型值，以使得前綴表達式中兩個運算對象是同類型的。型的。 a)設設type是綜合屬性，代表各非終結符的是綜合屬性，代表各非終結符的“類型類型”屬性屬性 設設in是繼承屬性，是繼承屬性， 翻譯方案翻譯方案 產(chǎn)生式產(chǎn)生

13、式 語義規(guī)則語義規(guī)則 et r r.in:=t.type e.type:=r.s r+ t r1 if (r.in=integer) and (t.type=integer) then r1.in:=integer else r1.in :=real r.s:=r1.s r r.s:=r.in tnum.num t.type:=real tnum t.type:=integer b) 設屬性設屬性s和和i用于傳遞屬性用于傳遞屬性type，屬性，屬性t和和j用于傳遞屬性用于傳遞屬性val。 翻譯方案翻譯方案 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 et r r.i:=t.type r.j:=t.val e.type:=r.s e.val:=r.t r+t r1 if (r.i=integer) and (t.type=integer) then begin r1.i:=integer print(+,r.j,t.val) r1.j:=r.j+t.val end else begin r1.i :=real if r.i=integer then begin r.i:=real r.j:=inttoreal(r.j) end if t.type=integ