編譯技術(shù)復(fù)習(xí)題答案

/第一章：編譯系統(tǒng)概述一．單項(xiàng)選擇題1．編譯程序前三個(gè)階段完成的工作是〔C〕。A．詞法分析、語(yǔ)法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析C．詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D．詞法分析、語(yǔ)法分析和代碼優(yōu)化2．編譯程序絕大多數(shù)時(shí)間花在〔D〕上。A．出錯(cuò)處理B．詞法分析C．目標(biāo)代碼生成D．表格管理3．編譯程序是對(duì)〔C〕。A．匯編程序的翻譯B．高級(jí)語(yǔ)言程序的解釋執(zhí)行C．高級(jí)語(yǔ)言的翻譯D．機(jī)器語(yǔ)言的執(zhí)行4．在使用高級(jí)語(yǔ)言編程時(shí)，首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部〔A〕錯(cuò)誤。A．語(yǔ)法B．語(yǔ)義C．語(yǔ)用D．運(yùn)行二．填空題1．編譯程序首先要識(shí)別出源程序中每個(gè)(單詞)，然后再分析每個(gè)(句子)并翻譯其意義。2．通常把編譯過(guò)程分為分析前端與后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的(綜合)。3．對(duì)編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。4．對(duì)以下錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段〔詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成〕報(bào)告的?！?〕else沒有匹配的if〔語(yǔ)法分析〕〔2〕數(shù)組下標(biāo)越界〔語(yǔ)義分析〕〔3〕使用的函數(shù)沒有定義〔語(yǔ)法分析〕〔4〕在數(shù)中出現(xiàn)非數(shù)字字符〔詞法分析〕5．如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段：〔編譯階段〕和〔運(yùn)行階段〕。如果編譯程序生成的目標(biāo)程序是匯編語(yǔ)言程序，則源程序的執(zhí)行方式分成三個(gè)階段：〔編譯階段〕〔匯編階段〕和〔運(yùn)行階段〕。6．編譯程序在其工作過(guò)程使用最多的數(shù)據(jù)構(gòu)造是〔表〕，它記錄著源程序中各種信息，以便查詢或修改，在這些〔表〕中，尤以〔符號(hào)表〕最重要，它的生存期最長(zhǎng)，使用也最頻繁。三．簡(jiǎn)述題：1．編譯程序的工作分為那幾個(gè)階段答：詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)展的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)展綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。第二章詞法分析一．單項(xiàng)選擇題：1．語(yǔ)言是〔A〕。A．句子的集合B．產(chǎn)生式的集合C．符號(hào)串的集合D．句型的集合2．掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即〔B〕。A．字符B．單詞C．句子D．句型3．詞法分析的任務(wù)是〔A〕。A．識(shí)別單詞B．分析句子的含義C．識(shí)別句子D．生成目標(biāo)代碼4．DFA〔如下圖〕承受的字集為〔D〕。00

10YA．以0開頭的二進(jìn)制數(shù)組成的集合B．以0結(jié)尾的二進(jìn)制組成的集合C．含奇數(shù)個(gè)0的二進(jìn)制組成的集合D．含偶數(shù)個(gè)0的二進(jìn)制組成的集合5．詞法分析器的輸出結(jié)果是〔C〕。A．單詞的種別編碼B．單詞在符號(hào)表中的位置C．單詞的種別編碼和自身的值D．單詞自身值二．填空題：1．描述程序設(shè)計(jì)語(yǔ)言的詞法的機(jī)制是〔正則表達(dá)式〕，識(shí)別機(jī)制是〔有窮狀態(tài)自動(dòng)機(jī)〕。2．最小狀態(tài)DFA的含義是〔沒有多余狀態(tài)，沒有兩個(gè)狀態(tài)等價(jià)〕。3．確定有限自動(dòng)機(jī)DFA是〔NFA〕的一個(gè)特例。4．確定的有窮自動(dòng)機(jī)是一個(gè)〔五元組〕，通常表示為〔DFA=(S，∑，f,s0Z)〕。三、簡(jiǎn)述題：1．詞法分析答：詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。四．綜合應(yīng)用題：1．設(shè)有非確定的有自限動(dòng)機(jī)NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。請(qǐng)畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：01ACA，BBCCC狀態(tài)轉(zhuǎn)換圖為：1110112．有一臺(tái)自動(dòng)售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機(jī)器中投放≥3分的硬幣，便可得到一塊糖〔注意；只給一塊并且不找錢〕?！?〕寫出售貨機(jī)售糖的正則表達(dá)式；〔2〕構(gòu)造識(shí)別上述正則式的最簡(jiǎn)DFA。解：〔1〕設(shè)a=1,b=2,，則售貨機(jī)售糖的正則表達(dá)式為：a(b|a(a|b))|b(a|b)?！?〕畫出與正則表達(dá)式a(b|a(a|b))|b(a|b)對(duì)應(yīng)的NFA，如下圖：3．設(shè)={0，1}上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。解：構(gòu)造相應(yīng)的正規(guī)式：(0|1)*1(0|1)NFA:111043211043200確定化：(3分)I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}014321001004321001114．構(gòu)造一個(gè)DFA，使其承受={0，1}上0和1的個(gè)數(shù)都是偶數(shù)的字符串。解：5．構(gòu)造一個(gè)字母表{0，1}上的DFA，其承受的串中所含0的數(shù)目能被3除盡。解：6．寫出在={a,b}上不是a開頭的，以aa結(jié)尾的的字符串集合的正規(guī)表達(dá)式，并直接構(gòu)造與之等價(jià)的狀態(tài)最少的DFA。解：7．寫一個(gè)文法使其語(yǔ)言為L(zhǎng)(G)={anbncm|m，n≥1，n為奇數(shù)，m為偶數(shù)}。解：文法G(S)：8．構(gòu)造一個(gè)DFA，它承受={a，b}上所有包含ab的字符串。解：構(gòu)造相應(yīng)的正規(guī)式：(a|b)*ab(a|b)*010123645abbb確定化：I{0,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3}{1,2,4,5,6}{1,2}{1,2,3}{1,2}{1,2,4,5,6}{1,2,3,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,3,5,6}{1,2,4,5,6}{1,2,5,6}{1,2,3,5,6}{1,2,5,6}bbba543210aaaa543210abbb最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}bbaa01b3ba第三章程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述一．單項(xiàng)選擇題：1．如果文法G是無(wú)二義的，則它的任何句子α〔A〕。A．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定一樣B．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同C．最左推導(dǎo)和最右推導(dǎo)必定一樣

D．可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹一樣2．正規(guī)式M1和M2等價(jià)是指〔C〕。

A．M1和M2的狀態(tài)數(shù)相等

B．M1和M2的有向邊條數(shù)相等

C．M1和M2所識(shí)別的語(yǔ)言集相等D．M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等3．文法G所描述的語(yǔ)言是〔D〕的集合。A．文法G的字符表V中所有符號(hào)組成的符號(hào)串。B．文法G的字符表V的閉包V*中的所有符號(hào)串。C．由文法的識(shí)別符號(hào)推出的所有符號(hào)串。D．由文法的識(shí)別符號(hào)推出的所有4．語(yǔ)言L={anbbn|n≥1}，則下述文法，〔D〕可以產(chǎn)生語(yǔ)言L。A．Z→aZb|aAb|bB．A→aAbA→aAb|bA→bC．Z→AbBD．Z→aAbA→aA|aA→aAb|bB→bB|b5．正則表達(dá)式的運(yùn)算符的優(yōu)先順序?yàn)椤睠〕。A．|>*>·B．*>|>·C．*>·>|D．|>·>*6.ab3的另一種表示方法是〔〕。二．填空題：1．如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是〔二義性的〕。2．最右推導(dǎo)亦稱為〔標(biāo)準(zhǔn)推導(dǎo)〕，由此得到的句型稱為〔標(biāo)準(zhǔn)〕句型。3．對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為(句子)。4．2型文法又稱為〔上下文無(wú)關(guān)〕文法；3型文法又稱為〔正則〕文法。5．一個(gè)文法G是一個(gè)四元式(VT,VN,S,P)組成的。6．文法G產(chǎn)生的〔句子〕的全體是該文法描述的語(yǔ)言。7．L+可以寫成〔LL*〕。三．簡(jiǎn)述題1．一個(gè)文法是由哪幾局部組成的，各局部的功能是什么？解：一個(gè)文法G是一個(gè)四元式〔VT,VN,S,P〕其中：VT是一個(gè)終結(jié)符的非空有限集合，終結(jié)符通常用小寫字母表示；VN是一個(gè)非終結(jié)符的非空有限集合，非終結(jié)符通常用大寫字母表示；S是一個(gè)特殊的非終結(jié)符〔S∈VN〕，稱為開場(chǎng)符號(hào)。P是一個(gè)產(chǎn)生式〔規(guī)則〕的有限集合，每個(gè)產(chǎn)生式的形式是A→α，其中A∈VN，α∈(VT∪VN)*。第四章自上而下的語(yǔ)法分析一．單項(xiàng)選擇題：1．文法G[S]:S→xSx|y所識(shí)別的語(yǔ)言是〔C〕。A.xyxB.(xyx)*nyxn(n≥0)*yx*2．編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是〔〕。A．分析單詞是怎樣構(gòu)成的B．分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的C．分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的D．分析程序的構(gòu)造3．以下關(guān)于標(biāo)識(shí)符和名字的表達(dá)中，正確的為〔C〕。A．標(biāo)識(shí)符有一定的含義B．名字是一個(gè)沒有意義的字符序列C．名字有確切的屬性D．都不對(duì)二．填空題：1．編譯器常用的語(yǔ)法分析方法有(自底向上)和(自頂向下)兩種。2．在LL(1)文法，其中的第一個(gè)L代表〔從左向右掃描輸入〕，第二個(gè)L表示產(chǎn)生〔最左推導(dǎo)〕，1代表在決定分析器的每步動(dòng)作時(shí)〔向前看一個(gè)輸入符號(hào)〕。3．一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成局部是〔非終結(jié)符有限集合、終結(jié)符有限集合、產(chǎn)生式有限集合、開場(chǎng)符〕。4．一個(gè)文法G[Z]，假設(shè)存在推導(dǎo)序列Z→+…Z…,則稱G[Z]是〔遞歸〕文法，這類文法所產(chǎn)生的句子有〔無(wú)數(shù)〕個(gè)。5．描述語(yǔ)言L={ambn|n≥m≥1}的文法是：〔Z→aAb、A→Ab|aAb|ε〕。三．簡(jiǎn)述題1．簡(jiǎn)述自頂向下的語(yǔ)法分析方法。答：所謂自頂向下的語(yǔ)法分析方法就是從文法的開場(chǎng)符開場(chǎng)，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)展最左推導(dǎo)，試圖推導(dǎo)出文法的，使之與給定的輸入串。四．綜合應(yīng)用題：1．試驗(yàn)證如下文法G[E]是LL(1)文法:E→[F]E′E’→E|εF→aF’F’→aF’|ε其中E，F(xiàn)，E’，F(xiàn)’為非終結(jié)符解：各非終結(jié)符的FIRST集和FOLLOW集如下：FIRST〔E〕={[}FOLLOW〔E〕={＃}FIRST〔E′〕={[，ε}FOLLOW〔E′〕={＃}FIRST〔F〕={a}FOLLOW〔F〕={]}FIRST〔F′〕={a，ε}FOLLOW〔F′〕={]}對(duì)于E’→E|εFIRST(E)∩FOLLOW〔E’〕=φ對(duì)于F’→aF’|εFIRST〔aF’〕∩FOLLOW〔F’〕=φ所以,文法G[E]是LL〔1〕文法。2．設(shè)有文法G[A]的產(chǎn)生式集為:A→BaC|CbBB→Ac|cC→Bb|b試消除G[A]的左遞歸。解：不妨以A、B、C排序.先將A代入B中，然后消除B中左遞歸；再將A、B代入C中。再消除C中左遞歸。最后結(jié)果為:G[A]:A→BaC|CbBB→CbBcB'|cB'B'→aCcB'|εC→cB'bC'|bC'C'→bBcB'bC'|ε3.對(duì)文法G[S]： S→a|∧|(T)T→T,S|S(1)給出(a,(a,a)的最左推導(dǎo)。(2)對(duì)文法G，進(jìn)展改寫，消除左遞歸。(3)對(duì)修改后的文法求First和Follow集。(4)并給出它的預(yù)測(cè)分析表。(5)給出輸入串(a,a)#的分析過(guò)程，并說(shuō)明該串是否為G的句子。解：〔1〕對(duì)(a,(a,a)的最左推導(dǎo)為：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))(2)改寫文法為：S→aS→∧S→(T)T→SNN→,SNN→ε(3)非終結(jié)符First集Follow集S{a,∧,(}{#,,,)}T{a,∧,(}{)}N{,,ε}{)}(4)預(yù)測(cè)分析表：a∧(),#S→a→∧→(T)T→SN→SN→SNN→ε→,SN〔5〕對(duì)于輸入串〔a,a〕#的分析過(guò)程為：棧當(dāng)前輸入符剩余輸入符號(hào)使用的產(chǎn)生式#S(a,a)#S→(T)#)T((a,a)##)Ta,a)#T→SN#)NSa,a)##)Naa,a)##)N,a)#N→,SN#)NS,,a)##)NSa)#S→a#)Naa)##)N)#N→ε#))###可見輸入串〔a,a〕#是文法的句子。4.對(duì)文法G(S)：SSaT|aT|aTTaT|a(1)消除該文法的左遞歸和提取左公因子；(2)構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3)構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。解：〔1〕消除左遞歸：SaTS’|aTS’S’aTS’|εTaT|a提取左公因子：SaTS’|aTS’S’aTS’|εTaT’T’T|ε〔2〕FIRST(S)={a，}FOLLOW(S)={#}FIRST(S')={，ε}FOLLOW(S')={#}FIRST(T)={}FOLLOW(T)={，#}FIRST(T')={，ε}FOLLOW(T')={，#}〔3〕LL(1)分析表如下，該文法是LL(1)文法。a#SSaTS'SaTS'S'S'aTS'S’εTTaT'T'T'εT'TT'ε5.考慮文法G：Sa|^|(T)TT,S|S(1)消除文法G的左遞歸?！?〕用類C++語(yǔ)言寫出遞歸下降分析程序。假設(shè)由單詞種別構(gòu)成的源文件存放于文件Lex.txt中，如文件內(nèi)容。6.考慮以下文法G〔j相當(dāng)與endif〕：SfCtSj|fCtSes|aCi〔1〕提取文法的左因子?！?〕構(gòu)造預(yù)測(cè)分析表?！?〕判斷經(jīng)改寫的文法是否是LL(1)文法。解：〔1〕SfCtSS’|aS’eS|jCi(2)chart;ifstremcinf("lex.txt");voidmain(){cinf>>t;S();}voidS(){if(t=='a')cinf>>t;else{if(t=='f')cinf>>t;C();if(t=='t')cinf>>t;S();S'();}}voidS(){if(t=='e'){cinf>>t;S();}elseif(t=='j')cinf>>t;}voidC(){if(t=='i')cinf>>t;}〔3〕first(S)={f,a}first(S')={e,j}first(C)={i}ftaeji#SfCtSSaS’eSjCi表不含多重定義，因此該文法是LL(1)文法。第五章自下而上的語(yǔ)法分析一．單項(xiàng)選擇題：1．一個(gè)句型中稱為句柄的是該句型的最左〔D〕A．非終結(jié)符號(hào)B．短語(yǔ)C．句子D．直接短語(yǔ)2．假設(shè)a為終結(jié)符，則A→α．a(chǎn)β為〔B〕工程。A．歸約B．移進(jìn)C．承受D．待約3．在標(biāo)準(zhǔn)歸約中，用〔B〕來(lái)刻畫可歸約串。A．直接短語(yǔ)B．句柄C．最左短語(yǔ)D．短語(yǔ)4．假設(shè)工程集Ik含有A→α．，則在狀態(tài)K時(shí)，僅當(dāng)面臨的輸入符號(hào)a∈Follow(A)時(shí)，才采用“A→α．〞動(dòng)作的一定是〔D〕。A．LALR文法B．LR〔0〕文法C．LR〔1〕文法D．SLR〔1〕文法5．在LR〔0〕的ACTION子表中，如果某一行中存在標(biāo)記“rj〞的欄，則〔A〕。A．該行必定填滿rjB．該行未填滿rjC．其他行也有rjD．goto子表中也有rj二．填空題：1．一個(gè)LR分析器包括兩局部：一個(gè)總控程序和〔一張分析表〕。2．LR〔0〕分析法的名字中“L〞表示〔自左至右分析〕，“R〞表示〔采用最右推導(dǎo)的逆過(guò)程即最左歸約〕，“0”表示〔向右查看0個(gè)字符3．如果文法G的開場(chǎng)符是S，則G的拓廣文法G’是在G的根底上增加一個(gè)新的開場(chǎng)符號(hào)(S’)和產(chǎn)生式〔S’S〕。4．由于存在〔規(guī)約-移進(jìn)〕沖突，使得文法不是LR〔0〕，轉(zhuǎn)換LR〔0〕為SLR〔1〕文法，需要計(jì)算〔非終結(jié)符的follow集〕。三．簡(jiǎn)述題；1．簡(jiǎn)述自下而上的分析方法。答：所謂自下而上分析法就是從輸入串開場(chǎng)，逐步進(jìn)展“歸約〞，直至歸約到文法的開場(chǎng)符號(hào)；或者說(shuō)從語(yǔ)法樹的末端開場(chǎng)，步步向上“歸約〞，直到根節(jié)點(diǎn)。四．綜合應(yīng)用題：1．對(duì)于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短語(yǔ)、直接短語(yǔ)和句柄？答．句型baSb的語(yǔ)法樹如下圖。AASBbBSab圖五(2)句型baSb的的語(yǔ)法樹短語(yǔ)：baSb、ba、Sb、a直接短語(yǔ)：Sb、a句柄：a2．證明下述文法G：SaSbS|aS|d是二義性文法。解：一個(gè)文法，如果存在某個(gè)句子有不只一棵語(yǔ)法分析樹與之對(duì)應(yīng)，則稱這個(gè)文法是二義性文法。句子aadbd有兩棵語(yǔ)法樹。如以下圖：SaSaSSabSdddSSabSSad(1)(2)由此可知，SaSbS|aS|d定義的文法是二義性文法。3．對(duì)于文法G(S):〔1〕寫出句型b(Ma)b的最右推導(dǎo)并畫出語(yǔ)法樹?！?〕寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。SbMSbM(TMabL)〔1〕〔2〕短語(yǔ):Ma)，(Ma)，b(Ma)b直接短語(yǔ):Ma)句柄:Ma)4．文法Ｇ：A→aAd|aAb|ε判斷該文法是否是SLR(1)文法，假設(shè)是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。解：：文法：A→aAd|aAb|ε拓廣文法為G′，增加產(chǎn)生式S′→A假設(shè)產(chǎn)生式排序?yàn)椋骸?〕S'→A〔1〕A→aAd〔2〕A→aAb〔3〕A→ε由產(chǎn)生式知：First(S')={ε,a}First(A)={ε,a}Follow(S')={#}Follow(A)={d,b,#}G′的LR(0)工程集族及識(shí)別活前綴的DFA如以下圖所示：在I0中：A→.aAd和A→.aAb為移進(jìn)工程，A→.為歸約工程，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=所以在I0、I2中的移進(jìn)-歸約沖突，可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：stateActionGotoadb#A0S2R3R3R311acc2S2R3R3R333S4S54R1E1R15R2R2R2對(duì)于輸入ab#分析過(guò)程如下；步驟狀態(tài)棧符號(hào)棧輸入符動(dòng)作10#ab#shift202#ab#reduce3023#aAb#shift40235#aAb#reduce501#A#accept５．假設(shè)有定義二進(jìn)制數(shù)的文法如下：S→L·L|LL→LB|BB→0|1(1)試為該文法構(gòu)造LR分析表，并說(shuō)明屬哪類LR分析表。(2)給出輸入串101.110的分析過(guò)程。解：文法：S→L.L|LL→LB|BB→0|1拓廣文法為G′，增加產(chǎn)生式S′→S假設(shè)產(chǎn)生式排序?yàn)椋骸?〕S'→S〔1〕S→〔2〕S→L〔3〕L→LB〔4〕L→B〔5〕B→0〔6〕B→1由產(chǎn)生式知：Follow(S')={#}Follow(S)={#}Follow(L)={.,0,1,#}Follow(B)={.,0,1,#}G′的LR(0)工程集族及識(shí)別活前綴的DFA如以下圖所示：在I2中：B→.0和B→.1為移進(jìn)工程，S→L.為歸約工程，存在移進(jìn)-歸約沖突，因此所給文法不是LR(0)文法。在I2、I8中：Follow(s)∩{0，1}={#}∩{0，1}=所以在I2、I8中的移進(jìn)-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下：stateactiongoto.01#SLB0S4S51231acc2S6S4S5R273R4R4R4R44R5R5R5R55R6R6R6R66S4S5837R3R3R3R38S4S5R17對(duì)輸入串101.110#的分析過(guò)程：步驟狀態(tài)棧符號(hào)棧輸入串動(dòng)作００#101.110#shift１０５#101.110#reduce２０３#B01.110#reduce３０２#L01.110#shift４０２４#L01.110#reduce５０２７#LB1.110#reduce６２#L1.110#shift７０２５#L1.110#reduce８０２７#LB.110#reduce９２#L.110#shift１００２６#L.110#shift１１０２６５10#reduce１２０２６３10#reduce１３０２６８10#shift１４０２６８５0#reduce１５０２６８７0#reduce１６０２６８0#shift１７０２６８４#reduce１８０２６８７#reduce１９０１#S#accept分析成功,說(shuō)明輸入串101.110#是文法的句子。第六章語(yǔ)法制導(dǎo)翻譯與中間代碼生成一．單項(xiàng)選擇題：1．常用的中間代碼形式不含〔D〕。A．三元式B．四元式C．逆波蘭式D．語(yǔ)法樹2．代碼生成階段的主要任務(wù)是〔C〕。A．把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B．把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C．把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D．把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言3．四元式之間的聯(lián)系是通過(guò)〔B〕實(shí)現(xiàn)的。A．指示器B．臨時(shí)變量C．符號(hào)表D．程序變量4．有一語(yǔ)法制導(dǎo)翻譯如下所示：SbAb{cout<<〞1”A(B{cout<<“2”Aa{cout<<〞3”BAa){cout<<〞4”假設(shè)輸入序列b