大連理工大學(xué)編譯原理復(fù)習(xí)

1、大連理工大學(xué)編譯原理復(fù)習(xí)編譯技術(shù)命題指導(dǎo)意見(jiàn)教學(xué)內(nèi)容知識(shí)點(diǎn)及題型第一章編譯器概述A(1)編譯的階段劃分選擇題2分1編譯程序絕大多數(shù)時(shí)間花在()上。A.出錯(cuò)處理B.詞法分析C.目標(biāo)代碼生成D.符號(hào)表管理答案：D2()和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A.語(yǔ)法分析B.中間代碼生成C.詞法分析D.代碼生成答案：B3編譯程序前三個(gè)階段完成的工作是()。A.詞法分析、語(yǔ)法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析和語(yǔ)義分析D.詞法分析、語(yǔ)法分析和代碼生成答案：C(2)遍的概念填空題2分1編譯階段的活動(dòng)常用一遍掃描來(lái)實(shí)現(xiàn)，一遍掃描包括和。答案：讀一個(gè)輸入文件寫(xiě)一個(gè)輸出文件2

2、將編譯程序分成若干個(gè)“遍”是為了 。答案：使程序的結(jié)構(gòu)更加清晰3編譯器從邏輯上可以分為 7個(gè)階段，其中，可以作天-個(gè)后端遍的是 階段。答案：代碼生成(3)前端和后端的劃分簡(jiǎn)答題5分1什么是前端？5分答案：編譯器分成分析和綜合兩大部分。分析部分揭示源程序的基本元素和它們所形成的層次結(jié)構(gòu)，決定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。2什么是后端？5分答案：編譯器分成分析和綜合兩大部分。綜合部分從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序，它經(jīng)常被稱為后端。3什么是前端？什么是后端？5分答案：編譯器分成分析和綜合兩大部分。分析部分揭示源程序的基本元素和它們所形成的 層次結(jié)構(gòu)，決

3、定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。綜合 部分從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序，它經(jīng)常被稱為后端。第二章2.1 2.2詞法記號(hào)的定義及描述B(1)詞法分析器的功能選擇題2分1詞法分析程序的輸出結(jié)果是()。A.單詞的種別編碼B.單詞在符號(hào)表中的位置C.單詞的種別編碼和單詞屬性值D.單詞的單詞屬性值答案：C2詞法分析器用于識(shí)別。A.字符串B.語(yǔ)句C.單詞D.標(biāo)識(shí)符答案：C3掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ) 法單位即()。A. 字符B ,單詞C.句子D.句型答案：B(2)詞法記號(hào)概念及屬性填空題2分1詞法記號(hào)是由和構(gòu)成

4、的二元組。答案：記號(hào)名屬性值2詞法單元是源程序中匹配一個(gè) 的字符序列。答案：記號(hào)模式3 影響語(yǔ)法分析的決策， 影響記號(hào)的翻譯。答案：記號(hào)名屬性(3)正規(guī)式與語(yǔ)言的對(duì)應(yīng)關(guān)系選擇題2分1卜面文法()和正規(guī)表送式a*b描述的語(yǔ)言相同。A. S 一 ab | aSbB. S -b | aSC. S fa | aSbD. S -a | Sb答案：B2最多包含兩個(gè)a的a,b上的語(yǔ)言()。A. (a| £ )b*(a| £ )B. b*ab*ab*|b*ab*C. b*(a|b*)(a|b*)b*D. b*(a|£ )b*(a|b*)b*答案：D3與(a|b)*等價(jià)的正規(guī)式是(

5、)。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：AC(1) NFA與DFA的概念選擇題2分1有如圖所示的有窮自動(dòng)機(jī)，與之等價(jià)的正規(guī)式為()。第二章 2.3.1,2.3.2 NFA,DFAA. (0|1)*(000|111)(0|1)B. (0|1) (000|111)(0|1)C. (0|1)*(000|111)(0|1) *D. A, B , C選項(xiàng)都不止確答案：C2對(duì)于NFA和DFA模型說(shuō)法錯(cuò)誤的是(A. DFA是NFA勺特殊形式B. DFA與NFA勺狀態(tài)轉(zhuǎn)換完全相同C.都有唯一的開(kāi)始狀態(tài)D.都可以有多個(gè)接受狀態(tài)答案：B3對(duì)于DFA模型，說(shuō)法錯(cuò)誤的是()A

6、. DFA從任何狀態(tài)出發(fā)，對(duì)于任何輸入符號(hào)B.任何狀態(tài)都沒(méi)有e轉(zhuǎn)換C. DFA有唯一的開(kāi)始狀態(tài))。O,可用多個(gè)轉(zhuǎn)換55 / 65D. DFA可以有多個(gè)接受狀態(tài)答案：A(2) NFA的構(gòu)造簡(jiǎn)答題10分1設(shè)有非確定的有自限動(dòng)機(jī) NFA M=(A, B, C, 0,1, A, C),其中：(A , 0)=C (A , 1)=A , B (B , 1)=C (C , 1)=C。請(qǐng)畫(huà)出狀態(tài)轉(zhuǎn)換距陣和 狀態(tài)轉(zhuǎn)換圖。答案：狀態(tài)轉(zhuǎn)換距陣為：01ACA, BBCCC11_狀態(tài)轉(zhuǎn)換圖為:2構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101答案：3為(ea) b*) *構(gòu)造非確定的有限自動(dòng)機(jī)，給出它們處理輸入串a(chǎn)b

7、abbab的轉(zhuǎn)換序列。答案：一 Or- 一輸入串a(chǎn)babbab的轉(zhuǎn)換序列:0 1456789 145678 789 1456789 10 或者 0 1456789 1456789 1236789 1456789 10(3) NFA轉(zhuǎn)化為DFA 簡(jiǎn)答題10分1設(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:II 0I10,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4Q確定化：

8、2構(gòu)造正規(guī)式1(0|1)*101 相應(yīng)的DFA答案：先構(gòu)造NFAA fiC口所以，可得DFA為:確定化:01y A nB AC ABYA ACA AC?AAB 記ABVAB重新命名，令 AB為B、AC為C、ABY為D得:1A B RE>B3對(duì)于下圖所示 NFA回答下列問(wèn)題:(1)用正規(guī)式描述該有限自動(dòng)機(jī)所表示的語(yǔ)言。(2)由NFA轉(zhuǎn)為DFA(3)構(gòu)造最簡(jiǎn)DFA答案：(1) (a|b)*a(a|b)*(2)(3)(4) DFA的化簡(jiǎn)簡(jiǎn)答題10分1已知 NFA= ( x,y,z,0,1Mx,z)，其中:4 ,M(z,1)=y, 構(gòu)M(x,0)=z, M(y,0)=x,y, M(z,0)=x,

9、z, M(x,1)=x, M(y,1)二造相應(yīng)的DFA并最小化。答案：根據(jù)題意有NFA圖：F表由子集法將 NFA轉(zhuǎn)換為DFAI1-z&u"您切I： - i-茹K1)BWHyleClr, iE % yILr, y置艮7AF1網(wǎng)力工】FEf, eEyl1面將該DFA最小化:(1)首先將它的狀態(tài)集分成兩個(gè)子集：P1=A,D,E,P2=B,C,F(2)區(qū)分 P2:由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C,所以 F, C 等價(jià)。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E, 而 D, E 不等價(jià)(見(jiàn)下步)，從而 B 與

10、 C, F 可以區(qū) 分。有 P21=C,F,P22=B。 區(qū)分P1:由于A, E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A, E可以區(qū)分，有 P11=A,E,P12=D。(4)由于F(A,0)=B,F(E,0)=F, 而B(niǎo), F不等價(jià)，所以 A, E可以區(qū)分。綜上所述，DFA可以區(qū)分為P=A , B , D, E , C, F。所以最小化的DFA如2給定下列自動(dòng)機(jī)開(kāi)始點(diǎn)愁絳止?fàn)顟B(tài)把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)DFA答案：有狀態(tài)矩陣如圖：芻bnb+i=。1-2+J0, 12T* =。2 "0112-21012+012/1m2"從而可得DFA如圖:3(1)將下圖中的 NFA M確

11、定化為 DFA M。(2)將DFA M化簡(jiǎn)。答案：確定化：ab00,11100, 10,111狀態(tài)編號(hào)ab01220112未簡(jiǎn)化的DFA最小化：分為：終態(tài)集0,1非終態(tài)集20,1 a =1 0,1 b = 2所以：0,1 =02 =1(1)直接從語(yǔ)言構(gòu)造 DFA 簡(jiǎn)答題5分1寫(xiě)出能產(chǎn)生字母表x,y上的不含兩個(gè)相鄰的 x,且不含兩個(gè)相鄰的y的全體符號(hào)串的 有限狀態(tài)自動(dòng)機(jī)。答案：2處于/*和*/之間的串構(gòu)成注解，注解中間沒(méi)有*/。畫(huà)出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。答案：第二章2.4,2.5 詞法分析器的生成器；第二章習(xí)題3有語(yǔ)言L=w|w (0,1)+ ,并且w中至少有兩個(gè)1 ,又在任何兩個(gè)1

12、之間有偶數(shù)個(gè) 0，試構(gòu)造接受該語(yǔ)言的確定有限狀態(tài)自動(dòng)機(jī)。答案：1 *(2) Lex的功能填空題2分1 Lex是從基于正規(guī)式的描述來(lái)構(gòu)造 。答案：詞法分析器2 Lex 程序包含三部分： 、和輔助函數(shù)。答案：聲明翻譯規(guī)則3由Lex建立的分析器通常作為 分析器的一個(gè)子程序。答案：詞法 語(yǔ)法第三章3.1上下文無(wú)關(guān)文法E(1)上下文無(wú)關(guān)文法定義選擇題2分;1 一個(gè)上下文無(wú)關(guān)文法 G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組()。A.句子B.句型C.單詞D.產(chǎn)生式答案：D2文法分為四種類型，即 0型、1型、2型、3型。其中2型文法是()。A.短語(yǔ)文法B.正則文法C.上下

13、文后關(guān)義法D.上卜文無(wú)關(guān)文法答案：D3文法分為四種類型，即 0型、1型、2型、3型。其中。型文法是 。A.短語(yǔ)文法B.正則文法C.上下文后關(guān)義法D.上下文無(wú)關(guān)文法答案：A(2)最左推導(dǎo)、最右推導(dǎo)簡(jiǎn)答題5分;1文法S->aF|(T)T->T,S|S對(duì)(a,(a,a) 和(a,a),A,(a),a)的最左推導(dǎo)。答案：又(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)X(a,a),A,(a),

14、a)的最左推導(dǎo)為：S=>(T) =>(T,S) =>(S,S) =>(T),S)=>(T,S),S) =>(T,S,S),S) =>(S,S,S),S)=>(T),S,S),S) =>(T,S),S,S),S) =>(S,S),S,S),S)=>(a,S),S,S),S) =>(a,a),S,S),S) =>(a,a),A,S),S)=>(a,a),A,(T),S) =>(a,a),A,(S),S) =>(a,a),A,(a),S)=>(a,a),A,(a),a)2設(shè)文法GE:E 一 RP|P

15、P 一 (E)|iR - RP+| RP* |P+|P*對(duì)i+i*(i+i)的最右推導(dǎo)。Ri*(i+i)答案：E RP R(E) R(RP) R(Ri) R(P+i) R(i+i) RP*(i+i)P+i*(i+i) i+i*(i+i3 考慮文法 S->aSbS | bSaS |£(a)為句abab構(gòu)造兩個(gè)不同的最左推導(dǎo)，以此說(shuō)明該文法是二義的。(b)為abab構(gòu)造對(duì)應(yīng)的最右推導(dǎo)。答案：W= Im aSbS=abSaSbS-> iisr &b百3b3n工加ababs=Im abab-1)L £= Im aSbS=>己n Mm n Im abahsn

16、 Im abzah-Q可加,對(duì)卜句子&b共存在兩個(gè)不同的顯左推導(dǎo)，所以該文法是二文城(b)=rft> asx>srmn rm aSb=> rmnta abSaSbn rm aSbaSb=>abSab：=> rzii e.Sfc a匕n rm obab'- n e abab ©(3)分析樹(shù)簡(jiǎn)答題5分;1 考慮文法 S->aSbS | bSaS |£(1)為abab構(gòu)造對(duì)應(yīng)的分析樹(shù)。(2)這個(gè)文法產(chǎn)生的語(yǔ)言是什么？答案：(1) E T F (E)(E+T)(E+F)(E+i)(T+i)(T*F+i)(2)語(yǔ)法樹(shù)如右圖。3令文法

17、G網(wǎng)為：S 一 ABAf aAb | abB 一 b,(1) GS定義的語(yǔ)言L(G)是什么？(2)給出句子aabbb的最左推導(dǎo)，并給出其語(yǔ)法分析樹(shù)。答案：(2) S abB abbSaAbB aabbB aabbbSaAbB aaAbbB aaabbbB aaabbbbSanbm(n>=0,m>=1)(3) s AB aAbB aabbB aabbbb悟濘不折料(4)二義性概念選擇題2分1如果文法G是無(wú)二義的，則它的任何句子a ()。A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它

18、們對(duì)應(yīng)的語(yǔ)法樹(shù)相同答案：A2如果一個(gè)文法 G是無(wú)二義性文法，對(duì)于任何一個(gè)句子，該句子()。A.可能存在兩個(gè)不同的最左推導(dǎo)B.可能存在兩個(gè)不同的最右推導(dǎo)C.最左推導(dǎo)和最右推導(dǎo)不同D.僅存在一個(gè)最左推導(dǎo)和一個(gè)最右推導(dǎo)答案：D3若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是()。A.遞歸的B.前后文無(wú)關(guān)的C.二義性的D.無(wú)二義性的答案：A第三章3.2語(yǔ)言和文法F(1)消除左遞歸填空題2分;1 一個(gè)文法是左遞歸的，如果它有非終結(jié)符A,對(duì)某個(gè)串a(chǎn),存在推導(dǎo)。答案：A=>+Aa2 的分析方法不能用于左遞歸文法，因此需要消除左遞歸。答案：自上而卜3由形式為A->Aa的產(chǎn)生式引起的左遞歸稱為 。答案：直

19、接左遞歸(2)提取左因子填空題2分;1提取左因子用于產(chǎn)生適合于 的文法。答案：自上而卜2 A->aB|aC ,經(jīng)過(guò)提取左因子，原來(lái)的產(chǎn)生式成為 和。答案：A->aA' A ' ->B|C3對(duì)于懸空else的文法stmt -> if expr then stmt else stmt|if expr then stmt|other提取左因子后的文法成為 和。答案：stmt->if expr then stmt optional_else_part | other optional_else_part->else | &(3)形式語(yǔ)言鳥(niǎo)瞰選

20、擇題2分;1 Chomsky把文法分為4種類型，其中描述能力最強(qiáng)的是()。A. 0型B. 1型C. 2型D. 3型答案：A2文法分為四種類型，即0型、1型、2型、3型。其中1型文法是()。A.短語(yǔ)文法B.正則文法C.上下文后關(guān)義法D.上卜文無(wú)關(guān)文法答案：C3文法分為四種類型，即0型、1型、2型、3型。其中3型文法是()。A.短語(yǔ)文法B.正則文法C.上下文后關(guān)義法D.上卜文無(wú)關(guān)文法答案：B第三章3.3自上而下分析G(1) LL(1)文法概念選擇題2分;1 3在卜面的各種編譯方法中，屬于自頂阿卜的語(yǔ)法分析算法的是()。A. LL(1)分析方法B. LR(K)分析方法C. SLR分析方法D. LAL

21、R(1) 分析方法答案：A2 LL(1)分析法的名字中，第二個(gè)“L”的含義是()。A.自左向右進(jìn)行掃描B.每次采用最左推導(dǎo)C.采用最右推導(dǎo)的逆過(guò)程一一最左規(guī)約D.向輸入串中查看一個(gè)輸入符號(hào)答案：B3 LL(1)分析法的名字中，第一個(gè)“L”的含義是()。A.自左向右進(jìn)行掃描B.每次采用最左推導(dǎo)C.采用最右推導(dǎo)的逆過(guò)程一一最左規(guī)約D.向輸入串中查看一個(gè)輸入符號(hào)答案：A(2)構(gòu)造預(yù)測(cè)分析表(包括求FIRST、FOLLOWS)簡(jiǎn)答題10分;1設(shè)文法G(S):S -S + aF|aF| + aFF 一*aF|*a(1)消除左遞歸和回溯；(2)構(gòu)造相應(yīng)的 FIRST和Follow 集合。答案：(1)S-&

22、gt;aFS'| + aFS'S'-> +aFS'| £F->*aF'F'->F|£(2)FIRST (S) = a, + FIRST (S' ) = +, s FIRST ( F) = * FIRST (F' ) = * , £ 2文法: S->MH|a H->LSo| £ K->dML| £ L->eHfFOLLOW(S) = #FOLLOW(S') = #FOLLoW (F) = (+,#FOLLOW( + , #M->

23、K|bLM判斷G是否為L(zhǎng)L(1)文法，如果是，構(gòu)造 LL(1)分析表。答案：各符號(hào)的FIRST集和FOLLOW1為：FIRSTFOLLOW二伊M植Jbk即H 3便印L0)K小1M郵1預(yù)測(cè)分析表為:ad6fb#sM->KH£*£L->eHFK_> E->dML££由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是LL(1)的。3請(qǐng)給對(duì)文法 GS進(jìn)行改寫(xiě)成 LL (1)文法，并給出改寫(xiě)后文法的預(yù)測(cè)分析表，要求計(jì)算出改寫(xiě)后文法各非終極符的FIRST和FOLLO僚合。S 一 S*aA | aA| *aAA- +aA | +a答案：改寫(xiě)文法如下：

24、S*aAS' | aAS 'S ' *aAS' |A+aA'A ' A |FIRSTFOLLOWS*，a#S，*，#A+*,#A，+, *,#預(yù)測(cè)分析表：*a+#SS *aAS'S aASS，S'*AS'S，AA +aA'AAA AA(3)用預(yù)測(cè)分析表對(duì)輸入串進(jìn)行分析的過(guò)程簡(jiǎn)答題5分;1給定LL(1)分析表：有輸入符號(hào)串i+i*i ,寫(xiě)出按上述算法識(shí)別此符號(hào)串的過(guò)程。 答案：步 9余幗物A,串1 所用產(chǎn)生或1HE十ii力E -TE'2METi T 泗T-*FT'3 Er 卜i+ i * i*>

25、K -t4；ET ii+1 * t±cS7ET+ i * i»T、r6注EH i "E -AJfc1；£ TAt j * i»A-fa*E'T +t 述9言E Ti * i#T-*Hi。和屋T Fi i#Ffi11-ir r ii / i#12NET 1"*Y卜，13并 E T FM* iffMf *L4 iff15仃ETFT«F ri1GttE TJii#17WETITTr-*i1ft#rE'9nit介析成功.2已知文法分析表:i+*()#-/EE->TGE->TGGG->+TGG->

26、; £G-> £G->-TGTT->FST->FSSS-> £S->*FSS-> £S-> £S-> £S->/FSFF->iF->(E )有輸入符號(hào)串i-i/i#,寫(xiě)出按上述算法識(shí)別此符號(hào)串的錯(cuò)誤恢復(fù)。答案步驟分析棧剩余字符所用產(chǎn)生式0#Ei-i/i#E->TG1#GTi-i/i#T->FS2#GSFi-i/i#F->i3#GSii-i/i#i匹配4#GS-i/i#S->A5#G-i/i#G->-TG6#GT-i/i#-匹配7#GT

27、i/i#T->FS8#GSFi/i#F->i9#GSii/i#i匹配10#GS/i#S->/FS11#GSF/i#/匹配12#GSF/i#F出錯(cuò)3已知文法分析表:,遇到錯(cuò)誤停止即可，不需要a$(),#S一 a一$一 (T)T一 SF一 SF一 SFF一£一,SF有輸入符號(hào)串(a,(a)# ,寫(xiě)出按上述算法識(shí)別此符號(hào)串的過(guò)程。答案：步驟分析棧剩余字符所用產(chǎn)生式0#S(a,(a)#S->(T)1#)T(a,(a)#(匹配2#)Ta,(a)#T->SF3#)FSa ,(a)#S->a4#)Faa,(a)#a 匹配5#)F,(a)#F->,SF6#)

28、FS,(a)#,匹配7 #)FS(a)#S->(T)8 #)F)T(a)#(匹配9 #)F)Ta)#T->SF10 #)F)FSa)#S->a11 #)F)Faa)#a 匹配12 #)F)F)#F->A13 #)F)#)匹配14 #)F)#F->a15 #)#)匹配16 #acc!第三章3.4自下而上分析H(1)歸約概念選擇題2分;1若a為終結(jié)符，則A-> a , a 3為項(xiàng)目。A.歸約B.移進(jìn)C.接受D.待約答案：B2移近-歸約分析為輸入串構(gòu)造分析樹(shù)是從（A.根結(jié)點(diǎn)B.葉結(jié)點(diǎn)C.中間結(jié)點(diǎn)D. 結(jié)點(diǎn)答案：B3在每一步歸約中，一個(gè)子串和某個(gè)產(chǎn)生式的（ 號(hào)代替這

29、個(gè)子串。A.右部左部B.右部右部C.D.左部左部答案：A）開(kāi)始的。）匹配，然后用該產(chǎn)生式的（2）句柄概念選擇題2分;1在規(guī)范歸約中，用（）來(lái)刻畫(huà)可歸約串。A.直接短語(yǔ)B.句柄C.產(chǎn)生式D.記號(hào)答案：B2卜面說(shuō)法正確的是（）。A.句柄是該句型中和一個(gè)產(chǎn)生式左/B匹配的子串B.文法是二義的，句柄是唯一的C.文法無(wú)二義時(shí)，句柄可能是唯一的D.以上說(shuō)法都不對(duì)答案：D3面說(shuō)法錯(cuò)誤的是（）。A.句柄是該句型中和一個(gè)產(chǎn)生式右部匹配的子串B.文法是二義的，句柄可能不唯一C.文法無(wú)二義時(shí)，句柄是唯一的D.句型中能和產(chǎn)生式 A-> 3右部匹配的最左子串3就是句柄答案：D第三章3.5 LR分析器I（1）活前綴

30、概念選擇題2分;1 一個(gè)句型中的活前綴為（）A.短語(yǔ)B.簡(jiǎn)單短語(yǔ)C.句柄D.右句型的前綴，該前綴不超過(guò)最右句柄的右端答案：D2在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型（） 的DFA狀態(tài)。A.句柄B.前綴C.活前綴D. LR（0）項(xiàng)目答案：C3卜列語(yǔ)句描述錯(cuò)誤的是（）A.活前綴不包含句柄的任何符號(hào)，此時(shí)期待從輸入串中看到該句柄對(duì)應(yīng)的產(chǎn)生式A的右部所推導(dǎo)出的符號(hào)串B.活前綴只包含句柄的一部分符號(hào)，表明該句柄對(duì)應(yīng)的的產(chǎn)生式A1 2的右音B子串1已出現(xiàn)在棧頂，期待從輸入串中看到2推導(dǎo)出的符號(hào)串C.活前綴已含有句柄的全部符號(hào)，表明該句柄對(duì)應(yīng)的產(chǎn)生式A的右1FB已出現(xiàn)在棧頂D.活前綴只包含句柄的一

31、部分符號(hào)，表明該句柄對(duì)應(yīng)的產(chǎn)生式A 的右部 已出現(xiàn)在棧頂 答案：D(2)構(gòu)造SLR分析表簡(jiǎn)答題20分;1 給定F列文法構(gòu)造其SLR分析表EE + TFF*ETFaTT FFbTFrf1#SD0r2S11ok2i6D33,4r(1)4i55rrr（2）r（2）6r(3)r(3)r(3)（3）構(gòu)造LR分析表簡(jiǎn)答題20分;1給定文法 GS:S AA BA|B aB |b請(qǐng)構(gòu)造該文法的LR分析表狀態(tài)ActionGoto口B114一SAL0S4S5i-31231accnZ二】3S4二：5r3634二,二7 i5r5r5r56r2； r4 r4 42 給定文法S AS |A aA|b(1)證明它是LR文法

32、(2)構(gòu)造其LR分析表答案：(1)該文法LR的項(xiàng)集規(guī)范集如下：Io T ?S, $ S ?AS, $ S ?, $ A ?aA, $/a/b A ?b, $/a/bIi T S?, $I2 A b?, $/a/bI3 S A?S, $S ?AS, $S ?, $ A ?aA, $ A ?b, $I4 A a?A, $/a/b A ?aA, $/a/b A ?b, $/a/bI5 A b?, $16 S AS?, $17 A a ?A, $ A ?aA, $ A ?b, $?I8 A aA?, $/a/b 19 A aA?, $觀察上面的項(xiàng)目規(guī)范集可以發(fā)現(xiàn)，在項(xiàng)集0和3中，歸約項(xiàng)都是在面臨符號(hào)$

33、 '時(shí)才發(fā)生,和移進(jìn)符號(hào)不同。所以，該文法是 LR文法。(2)它的LR分析表如下圖所示狀態(tài)ACTIONGOTOab$SA0S4S2R2131Acc2R4R4R43S7S5R2634S4S285R46R17S7S598R3R3R39R33已知文法G(S)SBBBaBBb構(gòu)造其LR分析表答案：LR分析表狀毒ACTIONGOTOab#&0白121ux2浦fi753s4S4r3r35rl5s697小8f212yri(4)構(gòu)造LALR分析表簡(jiǎn)答題20分;1給定下列文法，構(gòu)造其 LALR分析表SES，SSEEE + T | TEE + TETT(E )1 aT(E )Taactionsot

34、o十r)a$sET0sS 10123 81acc2s6 13rl38r3r3r349s4 9s5 107 n385 10r5r5r56 13s4 9s5 1011 157 14s6 13U2 1611 15r2遛r(nóng)21216r4r4r42有如下文法G(S'):S'SSL=RSRL*RLiRL(1)寫(xiě)出此文法的LALR分析表(2)根據(jù)文法的LALR分析表分析輸入串“ i=*i# "的過(guò)程答案：(1)LALR分析表態(tài)ACTIONGOTO=.1一:;#SLR0*電a2312A3心4S5鳳8756鼻事X97口3K_Js小9rl(2)“i=*i# "的LALR分析過(guò)程

35、步驟狀態(tài)符號(hào)棧剩余輸入串動(dòng)作t0#移進(jìn)ss205m=*i#歸的4 I.Ti302#L=*i#移進(jìn)S64 1026#L=叫#移進(jìn)5450264#L=*i#移進(jìn)S56 111264$#L=*歸妁川LtI7U264N#L=*L#IH約 r5 RtL，二li：M7#L=*R*歸約 r3 L->*Kgnz6fi#L-L#歸約r5 RtL10。工69#L=R#M約 rl S-> L=R1101#S#接受3給定文法G(S)S dBb|Ba|cb|AAB cA Ac|b構(gòu)造其LALR分析表。狀態(tài)ACTIONGOTOabcd$SBA0S6S3S41231acc2S73R5S84S9105S6S121

36、16R7R7R77R28R39R510S1411S12R412R6R6R613R1(5) SLR分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作簡(jiǎn)答題5分;1已知文法A aAd |aAb|及其SLR分析表，給出輸入串“ ab#"的SLR分析過(guò)程。SLR分析表狀態(tài)(State)AciionGotoadb#A0S2r3r3r3J1acc2曉r3r3 r333S4S54rirlrl5F r2理I r2答案:狀態(tài)棧 t state stack)法符號(hào)棧剩余輸入串 inpur left)動(dòng)作(action)Lab4 .Shiftb 2Reduce by ;A 1 tb 2 3PaAbtr .Shif

37、tQ 2 3 5Ab*by : A -* 苗.；上0 1pA耳，2若有定義二進(jìn)制數(shù)的文法如下:S L?L|LL LB | B B 0|1SLR分析表為狀態(tài)(State)AcxionGoto01二S . B012345618S4 S5 aceS6S4S5r2rirli-lrlt5r5r5r5r6 r6S4S5r3r3r3r3S4S5rl1 2 378 3卜7給出輸入串101.110的分析過(guò)程。 答案：狀態(tài)棧(state stack)丈法符號(hào)法剩余輸入串動(dòng)作(action.)(inpur Iefl)0¥ML 1109.Shift 5打QLUO告deduce by ;B -10 3鈿Cl.

38、 1103.Reduce by ;S -*LB0 2亂CL 1103.,.Shift0 2 4禮01.110ftRgducu by :B -*00 2 7札BL HO生Reduce by :S LB 2禮1.110.ShiftC 2 3i?Ll10二一，Reduce by :B -*10 2 74LB.UOS.Reduce by :S -*LE。2禮.nos.Shift0 2 5抗no 琮一-Shift0 2 6 5110#.Reduce by :B0 2 6 3軋,B10?Reduce by ;S -B0 2 6s禮L10#.,.ShifT0 2 S 8 5北* L1。口Keduce by :B -*10 2 5 8 7#L, LB席，deduce by :S -LB0 2 6 8即L0#.Shifi0 2 6 8 4ftLLO#p 9 qdeduce by : B 00 2 6 8 7#LLB«Eeductr by : S -*LL。145丁 E 0 小3考慮以下的文法 G (E):E一 (L) | aL-L, E | E其SL的析表為狀態(tài)ACTIONGOTO(a)r*SELQ5?5311acc2S3513Rj*s后s75Rq6R1RlRl7S3Q8叼叼