大連理工大學編譯原理復(fù)習

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

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

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

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

5、)。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：AC(1) NFA與DFA的概念選擇題2分1有如圖所示的有窮自動機，與之等價的正規(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選項都不止確答案：C2對于NFA和DFA模型說法錯誤的是(A. DFA是NFA勺特殊形式B. DFA與NFA勺狀態(tài)轉(zhuǎn)換完全相同C.都有唯一的開始狀態(tài)D.都可以有多個接受狀態(tài)答案：B3對于DFA模型，說法錯誤的是()A

6、. DFA從任何狀態(tài)出發(fā)，對于任何輸入符號B.任何狀態(tài)都沒有e轉(zhuǎn)換C. DFA有唯一的開始狀態(tài))。O,可用多個轉(zhuǎn)換55 / 65D. DFA可以有多個接受狀態(tài)答案：A(2) NFA的構(gòu)造簡答題10分1設(shè)有非確定的有自限動機 NFA M=(A, B, C, 0,1, A, C),其中：(A , 0)=C (A , 1)=A , B (B , 1)=C (C , 1)=C。請畫出狀態(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)造非確定的有限自動機，給出它們處理輸入串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 簡答題10分1設(shè)=0, 1上的正規(guī)集S由倒數(shù)第二個字符為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(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對于下圖所示 NFA回答下列問題:(1)用正規(guī)式描述該有限自動機所表示的語言。(2)由NFA轉(zhuǎn)為DFA(3)構(gòu)造最簡DFA答案：(1) (a|b)*a(a|b)*(2)(3)(4) DFA的化簡簡答題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)集分成兩個子集：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 等價。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E, 而 D, E 不等價(見下步)，從而 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, F不等價，所以 A, E可以區(qū)分。綜上所述，DFA可以區(qū)分為P=A , B , D, E , C, F。所以最小化的DFA如2給定下列自動機開始點愁絳止狀態(tài)把此自動機轉(zhuǎn)換為確定自動機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化簡。答案：確定化：ab00,11100, 10,111狀態(tài)編號ab01220112未簡化的DFA最小化：分為：終態(tài)集0,1非終態(tài)集20,1 a =1 0,1 b = 2所以：0,1 =02 =1(1)直接從語言構(gòu)造 DFA 簡答題5分1寫出能產(chǎn)生字母表x,y上的不含兩個相鄰的 x,且不含兩個相鄰的y的全體符號串的 有限狀態(tài)自動機。答案：2處于/*和*/之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。答案：第二章2.4,2.5 詞法分析器的生成器；第二章習題3有語言L=w|w (0,1)+ ,并且w中至少有兩個1 ,又在任何兩個1

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

13、文后關(guān)義法D.上卜文無關(guān)文法答案：D3文法分為四種類型，即 0型、1型、2型、3型。其中。型文法是 。A.短語文法B.正則文法C.上下文后關(guān)義法D.上下文無關(guān)文法答案：A(2)最左推導、最右推導簡答題5分;1文法S->aF|(T)T->T,S|S對(a,(a,a) 和(a,a),A,(a),a)的最左推導。答案：又(a,(a,a)的最左推導為：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)的最左推導為：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*對i+i*(i+i)的最右推導。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)造兩個不同的最左推導，以此說明該文法是二義的。(b)為abab構(gòu)造對應(yīng)的最右推導。答案：W= Im aSbS=abSaSbS-> iisr &b百3b3n工加ababs=Im abab-1)L £= Im aSbS=>己n Mm n Im abahsn

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

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

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

19、接左遞歸(2)提取左因子填空題2分;1提取左因子用于產(chǎn)生適合于 的文法。答案：自上而卜2 A->aB|aC ,經(jīng)過提取左因子，原來的產(chǎn)生式成為 和。答案：A->aA' A ' ->B|C3對于懸空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)形式語言鳥瞰選

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

21、R(1) 分析方法答案：A2 LL(1)分析法的名字中，第二個“L”的含義是()。A.自左向右進行掃描B.每次采用最左推導C.采用最右推導的逆過程一一最左規(guī)約D.向輸入串中查看一個輸入符號答案：B3 LL(1)分析法的名字中，第一個“L”的含義是()。A.自左向右進行掃描B.每次采用最左推導C.采用最右推導的逆過程一一最左規(guī)約D.向輸入串中查看一個輸入符號答案：A(2)構(gòu)造預(yù)測分析表(包括求FIRST、FOLLOWS)簡答題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是否為LL(1)文法，如果是，構(gòu)造 LL(1)分析表。答案：各符號的FIRST集和FOLLOW1為：FIRSTFOLLOW二伊M植Jbk即H 3便印L0)K小1M郵1預(yù)測分析表為:ad6fb#sM->KH£*£L->eHFK_> E->dML££由于預(yù)測分析表中無多重入口，所以可判定文法是LL(1)的。3請給對文法 GS進行改寫成 LL (1)文法，并給出改寫后文法的預(yù)測分析表，要求計算出改寫后文法各非終極符的FIRST和FOLLO僚合。S 一 S*aA | aA| *aAA- +aA | +a答案：改寫文法如下：

24、S*aAS' | aAS 'S ' *aAS' |A+aA'A ' A |FIRSTFOLLOWS*，a#S，*，#A+*,#A，+, *,#預(yù)測分析表：*a+#SS *aAS'S aASS，S'*AS'S，AA +aA'AAA AA(3)用預(yù)測分析表對輸入串進行分析的過程簡答題5分;1給定LL(1)分析表：有輸入符號串i+i*i ,寫出按上述算法識別此符號串的過程。 答案：步 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 )有輸入符號串i-i/i#,寫出按上述算法識別此符號串的錯誤恢復(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出錯3已知文法分析表:,遇到錯誤停止即可，不需要a$(),#S一 a一$一 (T)T一 SF一 SF一 SFF一£一,SF有輸入符號串(a,(a)# ,寫出按上述算法識別此符號串的過程。答案：步驟分析棧剩余字符所用產(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為項目。A.歸約B.移進C.接受D.待約答案：B2移近-歸約分析為輸入串構(gòu)造分析樹是從（A.根結(jié)點B.葉結(jié)點C.中間結(jié)點D. 結(jié)點答案：B3在每一步歸約中，一個子串和某個產(chǎn)生式的（ 號代替這

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

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

31、部分符號，表明該句柄對應(yīng)的產(chǎn)生式A 的右部 已出現(xiàn)在棧頂 答案：D(2)構(gòu)造SLR分析表簡答題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分析表簡答題20分;1給定文法 GS:S AA BA|B aB |b請構(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的項集規(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?, $觀察上面的項目規(guī)范集可以發(fā)現(xiàn)，在項集0和3中，歸約項都是在面臨符號$

33、 '時才發(fā)生,和移進符號不同。所以，該文法是 LR文法。(2)它的LR分析表如下圖所示狀態(tài)ACTIONGOTOab$SA0S4S2R2131Acc2R4R4R43S7S5R2634S4S285R46R17S7S598R3R3R39R33已知文法G(S)SBBBaBBb構(gòu)造其LR分析表答案：LR分析表狀毒ACTIONGOTOab#&0白121ux2浦fi753s4S4r3r35rl5s697小8f212yri(4)構(gòu)造LALR分析表簡答題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)寫出此文法的LALR分析表(2)根據(jù)文法的LALR分析表分析輸入串“ i=*i# "的過程答案：(1)LALR分析表態(tài)ACTIONGOTO=.1一:;#SLR0*電a2312A3心4S5鳳8756鼻事X97口3K_Js小9rl(2)“i=*i# "的LALR分析過程

35、步驟狀態(tài)符號棧剩余輸入串動作t0#移進ss205m=*i#歸的4 I.Ti302#L=*i#移進S64 1026#L=叫#移進5450264#L=*i#移進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分析器對輸入串進行分析的格局變化和相應(yīng)動作簡答題5分;1已知文法A aAd |aAb|及其SLR分析表，給出輸入串“ ab#"的SLR分析過程。SLR分析表狀態(tài)(State)AciionGotoadb#A0S2r3r3r3J1acc2曉r3r3 r333S4S54rirlrl5F r2理I r2答案:狀態(tài)棧 t state stack)法符號棧剩余輸入串 inpur left)動作(action)Lab4 .Shiftb 2Reduce by ;A 1 tb 2 3PaAbtr .Shif

37、tQ 2 3 5Ab*by : A -* 苗.；上0 1pA耳，2若有定義二進制數(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的分析過程。 答案：狀態(tài)棧(state stack)丈法符號法剩余輸入串動作(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?？贙educe 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叼叼