《華中科技大學《編譯原理》編譯典型題解.ppt》由會員分享，可在線閱讀，更多相關《華中科技大學《編譯原理》編譯典型題解.ppt（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、典型題解,編譯原理,主講教師：周時陽,2,,根據(jù)課程基本知識點，結(jié)合測驗常見題型，討論典型題例解法。一般題型分為客觀題和主觀題兩類。其中，客觀題包括單項選擇題、多項選擇題和判斷題等，主觀題包括簡答題、計算題和證明題等。本課程考查的知識點，請參看《編譯原理》課程教學大綱和網(wǎng)絡版《課程內(nèi)容》中各章小結(jié)部分。,內(nèi)容摘要,3,一、單選題,1．文法所描述的語言是的集合。A.文法的字匯表V中符號組成的符號串B.文法的字匯表V中終結(jié)符號組成的符號串C.由文法開始符推導的符號串D.由文法開始符推導的終結(jié)符號串,D,2．生成能被5整除的正整數(shù)的文法G[Z]是________。A.G[Z]:Z→AC,A→BA|B
2、,B→0|1|2|…|9,C→0|5B.G[Z]:Z→AC,A→BA|ε,B→0|1|2|…|9,C→0|5C.G[Z]：Z→ADA0|A5，A→BA|ε，B→0|D，D→1|2|…|9D.G[Z]：Z→AC|C,A→BA|B,B→0|1|2|…|9,C→0|5,C,4,,,3．符號串a(chǎn)b1b2是文法G[A]：A→aB,B→bB|b的句子，該句子的句柄是________。A.b1B.b2C.aD.b1b2,解釋：,,,,,,B,5,,4．LL(1)文法中第一個L表示________。A.最左推導B.最左歸約C.從左到右識別輸入串D.規(guī)范歸約,C,5．對于LR(0)分析法，語法分析棧中存放的狀態(tài)
3、是識別規(guī)范句型_______的DFA狀態(tài)。A．前綴B.活前綴C.LR(0)項目D.句柄,B,6,6．算符文法是指的文法。①沒有形如U→...VW...的規(guī)則（U，V，W?VN）②VT中任意兩個符號之間至多存在一種算符優(yōu)先關系③沒有相同右部的規(guī)則④沒有形如U→ε的規(guī)則A.①B.①和②C.①、②和③D.①、②、③和④,A,7．下述語句類中，____________在編譯階段通常不產(chǎn)生可執(zhí)行代碼。A.變量說明語句B.流程控制語句C.輸入輸出語句D.賦值語句,A,7,8．在編譯程序采用的優(yōu)化方法中，是在循環(huán)語句范圍內(nèi)進行的。①合并已知常量②刪除多余運算③刪除歸納變量④運算強度削弱⑤代碼外提A.①④B.
4、①⑤C.①④⑤D.③④⑤,D,9．程序的基本塊是指_______。A.不含無條件轉(zhuǎn)移語句的程序段B.不含條件轉(zhuǎn)移語句的程序段C.不含停機的語句程序段D.僅含有一個入口語句和一個出口語句的順序程序段,D,8,二、多選題,1．符號串dbb是給定文法G[A]：A→dBC，B→aB|ε，C→bC|b的句子，試問其活前綴包括。A.εB.dC.dbD.dbb,2．已知字母表Σ=｛a，b｝,下列________是字母表Σ上的正規(guī)式。A.ab+aB.abc|b*C.(a|b)*D.ε,A、B,C、D,9,3．常見的自底而上語法分析方法有。A.遞歸下降分析B.算符優(yōu)先分析C.LL(1)預測分析D.LR分析,B、
5、D,4．一個文法是LR(0)文法一定也是。A.SLR(1)文法B.LR(1)文法C.LALR(1)文法D.OG文法,A、B、C,10,1．設A是符號串集，則A0＝ε。（）2．在形式語言中，最右推導的逆過程稱為規(guī)范歸約。（）3．一個語言的文法是唯一的。（）4．句型的每個直接短語都是某規(guī)則的右部。（）5．如果語言的文法是二義性，則該語言也是二義性的。（）6．任何正規(guī)文法都是上下文無關文法。（）7．符號表的主要作用是輔助語義分析和代碼生成。（）,三、判斷題,,√,,√,,√,√,11,1．構造一個高級語言的詞法分析程序的基本技術線路是什么？,四、簡述題,簡答：依據(jù)給定的源語言之單詞集，設計其正規(guī)文法
6、或正規(guī)式，之后等價地轉(zhuǎn)換成非確定有窮自動機，再通過子集法將其確定化，最終將確定有窮自動機最小化，最后依據(jù)最小化的確定有窮自動機，設計詞法分析程序。,12,五、填空題,1．編譯程序是一種翻譯程序，它將用戶用高級語言編寫的_______翻譯成等價的_________________的目標程序。2．有這樣一個推導過程，其每一步推導都是對符號串中最右的非終結(jié)符進行替換，我們把這種推導過程稱為____________________。3．屬性文法中的屬性分為綜合屬性和__________兩種。,源程序,匯編語言或機器語言,最右推導（或規(guī)范推導）,繼承屬性,13,,4．已知文法G[A]：A→(B)|a|ε
7、，B→B，A|A，該文法的開始符號是___，非終結(jié)符號集合為______，終結(jié)符號集合為_______。5．自下而上的語法分析方法的基本思想是從待識別的輸入串開始逐步______到文法的______。6．已知文法G[S]：S→AB,A→aAb|c,B→aBb|d，則對于非終結(jié)符A，F(xiàn)OLLOW(A)=______。,A,{A,B},{(,),a},歸約,開始符,{a,b,d},注解：FOLLOW可以采用依據(jù)定義直接計算，或依據(jù)教材所給算法計算。,14,,六、解答題,1.已知文法G[S]：S→*A，A→*∣0A1。(1)求文法G非終結(jié)符的FIRSTVT集和LASTVT集；(2)構造文法G算符優(yōu)先
8、關系分析表，并判斷G是否為算符優(yōu)先文法。,解：（1）計算FIRSTVT集和LASTVT集FIRSTVT(S)={*},LASTVT(S)={*,1}FIRSTVT(A)={0,*},LASTVT(A)={1,*},注解：FIRSTVT集和LASTVT集可以采用依據(jù)定義直接計算，或依據(jù)教材所給算法計算。,15,,顯然，文法G是OG文法、沒有空規(guī)則、任何兩個終結(jié)符之間至多存在一種算符優(yōu)先關系。所以文法G是算符優(yōu)先文法。,,(2)對于S→*A，F(xiàn)IRSTVT(A)，有：*0，**對于A→0A1，有：01對于A→0A1，F(xiàn)IRSTVT(A)，有：00，0*對于A→0A1，LASTVT(A)，有：11，
9、*1,FIRSTVT(A)={0,*},LASTVT(A)={1,*},構造文法G算符優(yōu)先關系分析表如下。,16,2.試設計文法描述語言L={0n12n+1|n≥1}。,解：G(S):S→0S11∣1,3.已知文法G[S]：S→AB，A→aAb|ab，B→Bc|ε，試寫出該文法描述的語言。,解：L(G(S))＝{anbncm︱n≥1,m≥0},4.將賦值語句a=b*(c+d)翻譯成四元式。,解：(+，c，d，T1)(*，b，T1，T2)(+，T1，，T3),17,5．構造正規(guī)式R＝0(10|01)*0的DFAM。,解：(1)根據(jù)正規(guī)式到轉(zhuǎn)換NFA方法，構造NFAM1,(2)根據(jù)NFA到DFA轉(zhuǎn)換方法，構造DFAM,18,6．給定文法G[S]：S→aSb|ε,試判斷G[S]是否為SLR(1)文法。,解：①改寫文法為G′[S′]:,G′[S′]:(0)S′→S(1)S→aSb(2)S→ε,②構造識別LR(0)活前綴DFA,③∵follow(s)＝{#,b}∴I0:{a}∩follow(s)＝Ф,I2:{a}∩follow(s)＝Ф故G[S]是SLR(1)文法,19,7.已知文法G[E]：E→EiT∣T，T→T+F∣iF∣F，F(xiàn)→E*∣(，試證明G[E]是二義性的。,解：∵句子(i(*存在如下兩棵不同的語法樹,∴G[E]是二義性的,20,
華中科技大學《編譯原理》編譯典型題解.ppt
