編譯原理復(fù)習(xí).doc

編譯技術(shù)命題指導(dǎo)意見教學(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. 語法分析B. 中間代碼生成C. 詞法分析D. 代碼生成答案：B3 編譯程序前三個(gè)階段完成的工作是( )。A. 詞法分析、語法分析和代碼優(yōu)化 B. 代碼生成、代碼優(yōu)化和詞法分析C. 詞法分析、語法分析和語義分析 D. 詞法分析、語法分析和代碼生成答案：C（2）遍的概念 填空題 2分1 編譯階段的活動(dòng)常用一遍掃描來實(shí)現(xiàn)，一遍掃描包括 和 。答案：讀一個(gè)輸入文件 寫一個(gè)輸出文件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)，決定它們的含義，建立起源程序的中間表示，分析部分經(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語句C單詞D標(biāo)識(shí)符答案：C3 掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即（ ）。A 字符 B單詞 C句子 D句型答案：B（2）詞法記號(hào)概念及屬性 填空題2分1 詞法記號(hào)是由 和 構(gòu)成的二元組。答案：記號(hào)名 屬性值2 詞法單元是源程序中匹配一個(gè) 的字符序列。答案：記號(hào)模式3 影響語法分析的決策， 影響記號(hào)的翻譯。答案：記號(hào)名 屬性（3）正規(guī)式與語言的對(duì)應(yīng)關(guān)系 選擇題 2分1 下面文法（ ）和正規(guī)表達(dá)式a*b描述的語言相同。A. Sab | aSbB. Sb | aSC. Sa | aSbD. Sa | Sb答案：B2 最多包含兩個(gè)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)*等價(jià)的正規(guī)式是（ ）。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：A第二章2.3.1,2.3.2 NFA,DFAC（1）NFA與DFA的概念 選擇題 2分1 有如圖所示的有窮自動(dòng)機(jī)，與之等價(jià)的正規(guī)式為（ ）。A. (0|1)*(000|111)(0|1)B. (0|1) (000|111)(0|1)C. (0|1)*(000|111)(0|1) *D. ，B ，C選項(xiàng)都不正確答案：C2 對(duì)于NFA和DFA模型說法錯(cuò)誤的是（ ）。A. DFA是NFA的特殊形式B. DFA與NFA的狀態(tài)轉(zhuǎn)換完全相同C. 都有唯一的開始狀態(tài)D. 都可以有多個(gè)接受狀態(tài)答案：B3 對(duì)于DFA模型，說法錯(cuò)誤的是（ ）。A. DFA從任何狀態(tài)出發(fā)，對(duì)于任何輸入符號(hào)，可有多個(gè)轉(zhuǎn)換B. 任何狀態(tài)都沒有轉(zhuǎn)換C. DFA有唯一的開始狀態(tài)D. DFA可以有多個(gè)接受狀態(tài)答案：A（2）NFA 的構(gòu)造 簡(jiǎn)答題 10分1 設(shè)有非確定的有自限動(dòng)機(jī)NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。請(qǐng)畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。答案：狀態(tài)轉(zhuǎn)換距陣為：d01ACA，BBCCC11011狀態(tài)轉(zhuǎn)換圖為：2 構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101。答案： 3 為（|a）b*）* 構(gòu)造非確定的有限自動(dòng)機(jī)，給出它們處理輸入串a(chǎn)babbab的轉(zhuǎn)換序列。答案：輸入串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è)S=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: 確定化：I0,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,4、2 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。答案：先構(gòu)造NFA：確定化： 重新命名，令A(yù)B為B、AC為C、ABY為D得： 所以，可得DFA為： 3 對(duì)于下圖所示NFA，回答下列問題：（1）用正規(guī)式描述該有限自動(dòng)機(jī)所表示的語言。（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,1,M,x,z ），其中：M(x,0)=z, M(y,0)=x,y, M(z,0)=x,z, M(x,1)=x, M(y,1)= ,M(z,1)=y, 構(gòu)造相應(yīng)的DFA并最小化。答案：根據(jù)題意有NFA圖:下表由子集法將NFA轉(zhuǎn)換為DFA：面將該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à)（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。 (3) 區(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(xiàn)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的DFA如下：2 給定下列自動(dòng)機(jī)：把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)DFA。答案：有狀態(tài)矩陣如圖：從而可得DFA如圖：3 （1）將下圖中的NFA M確定化為DFA M。 （2）將DFA M化簡(jiǎn)。答案：確定化: ab00,1110-0，10,11狀態(tài)編號(hào) ab01220-11210 a -a a2 b b 未簡(jiǎn)化的DFA最小化： 分為：終態(tài)集0,1 非終態(tài)集2 0,1a =1 0,1b = 2 所以：0,1 = 0 2 = 110 a - b a第二章2.4,2.5 詞法分析器的生成器; 第二章習(xí)題D（1）直接從語言構(gòu)造DFA 簡(jiǎn)答題5分1 寫出能產(chǎn)生字母表x,y上的不含兩個(gè)相鄰的x,且不含兩個(gè)相鄰的的全體符號(hào)串的有限狀態(tài)自動(dòng)機(jī)。答案：2 處于/* 和 */之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。答案：124start52othersothers/*/3 有語言 L=w|w (0,1)+，并且 w 中至少有兩個(gè)1 ，又在任何兩個(gè)1之間有偶數(shù)個(gè) 0 ，試構(gòu)造接受該語言的確定有限狀態(tài)自動(dòng)機(jī)。答案：（2）Lex 的功能 填空題 2分1 Lex是從基于正規(guī)式的描述來構(gòu)造 。答案：詞法分析器2 Lex程序包含三部分： 、 和輔助函數(shù)。答案：聲明 翻譯規(guī)則3 由Lex建立的 分析器通常作為 分析器的一個(gè)子程序。答案：詞法 語法第三章 3.1上下文無關(guān)文法E（1）上下文無關(guān)文法定義選擇題2分；1 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組（ ）。 A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式答案：D2 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是（ ）。A. 短語文法 B. 正則文法 C. 上下文有關(guān)文法D. 上下文無關(guān)文法答案：D3 文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_。A. 短語文法B. 正則文法C. 上下文有關(guān)文法D. 上下文無關(guān)文法答案：A（2）最左推導(dǎo)、最右推導(dǎo)簡(jiǎn)答題5分；1 文法 S-a|(T) T-T,S|S 對(duì) (a,(a,a) 和 (a,a),(a),a) 的最左推導(dǎo)。答案： 對(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) 對(duì)(a,a),(a),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),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a)2 設(shè)文法GE:E RP|P P (E)|i R RP+| RP* |P+|P*對(duì)i+i*(i+i)的最右推導(dǎo)。答案： E RP R(E) R(RP) R(Ri) R(P+i) R(i+i) RP*(i+i) Ri*(i+i) P+i*(i+i) i+i*(i+i3 考慮文法S-aSbS | bSaS |（a） 為句abab構(gòu)造兩個(gè)不同的最左推導(dǎo)，以此說明該文法是二義的。（b） 為abab構(gòu)造對(duì)應(yīng)的最右推導(dǎo)。答案：（3）分析樹簡(jiǎn)答題5分； 1 考慮文法S-aSbS | bSaS |（1） 為abab構(gòu)造對(duì)應(yīng)的分析樹。（2） 這個(gè)文法產(chǎn)生的語言是什么？答案：ETF(E)E+TFiTT*F（1）（2）該文法產(chǎn)生 a、b 個(gè)數(shù)相等的 ab 串（含空串）2 對(duì)于文法G(E): ET|E+TTF|T*FF(E)|i寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。答案：（1）ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i)（2）語法樹如右圖。3 令文法GS為： SABAaAb | abBb,（1）GS定義的語言L(G)是什么？（2）給出句子aabbb的最左推導(dǎo)，并給出其語法分析樹。答案：（1）SabBabb SaAbBaabbBaabbb SaAbBaaAbbBaaabbbBaaabbbb Sanbm(n=0,m=1)（2）s ABaAbBaabbBaabbbb/.（4）二義性概念選擇題2分1 如果文法G是無二義的，則它的任何句子（ ）。A. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C. 最左推導(dǎo)和最右推導(dǎo)必定相同 D. 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同答案：A2 如果一個(gè)文法G是無二義性文法，對(duì)于任何一個(gè)句子，該句子（ ）。A. 可能存在兩個(gè)不同的最左推導(dǎo)B. 可能存在兩個(gè)不同的最右推導(dǎo)C. 最左推導(dǎo)和最右推導(dǎo)不同D. 僅存在一個(gè)最左推導(dǎo)和一個(gè)最右推導(dǎo)答案：D3 若文法 G 定義的語言是無限集，則文法必然是（ ）。 A. 遞歸的 B. 前后文無關(guān)的C. 二義性的 D. 無二義性的答案：A第三章 3.2 語言和文法F（1）消除左遞歸填空題2分；1 一個(gè)文法是左遞歸的，如果它有非終結(jié)符A，對(duì)某個(gè)串a(chǎn)，存在推導(dǎo) 。答案：A=+Aa2 的分析方法不能用于左遞歸文法，因此需要消除左遞歸。答案：自上而下3 由形式為A-Aa的產(chǎn)生式引起的左遞歸稱為 。答案：直接左遞歸（2）提取左因子填空題2分；1 提取左因子用于產(chǎn)生適合于 的文法。答案：自上而下2 A-aB|aC，經(jīng)過提取左因子，原來的產(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）形式語言鳥瞰選擇題2分；1 Chomsky把文法分為4種類型，其中描述能力最強(qiáng)的是（ ）。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. LALR(1) 分析方法答案：A2 LL(1)分析法的名字中，第二個(gè)“L”的含義是（ ）。A. 自左向右進(jìn)行掃描B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程最左規(guī)約D. 向輸入串中查看一個(gè)輸入符號(hào)答案：B3 LL(1)分析法的名字中，第一個(gè)“L”的含義是（ ）。A. 自左向右進(jìn)行掃描B. 每次采用最左推導(dǎo)C. 采用最右推導(dǎo)的逆過程最左規(guī)約D. 向輸入串中查看一個(gè)輸入符號(hào)答案：A （2）構(gòu)造預(yù)測(cè)分析表（包括求FIRST、FOLLOW集）簡(jiǎn)答題10分；1 設(shè)文法 G(S)： SS aF|aF| aF F*aF|*a （1）消除左遞歸和回溯； （2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。答案：（1） S-aFS|aFS S-aFS| F-*aF F-F| （2） FIRST（S）a，+ FOLLOW（S） FIRST（S）+， FOLLOW（S） FIRST（F）* FOLLoW（F）（+， FIRST（F）*， FOLLOW（+，2 文法： S-MH|a H-LSo| K-dML| L-eHf M-K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。答案：各符號(hào)的FIRST集和FOLLOW集為： 預(yù)測(cè)分析表為： 由于預(yù)測(cè)分析表中無多重入口，所以可判定文法是LL(1)的。3 請(qǐng)給對(duì)文法GS進(jìn)行改寫成LL（1）文法，并給出改寫后文法的預(yù)測(cè)分析表，要求計(jì)算出改寫后文法各非終極符的FIRST和FOLLOW集合。S S*aA | aA| *aA A +aA | +a答案：改寫文法如下： S*aAS | aAS S*aAS | e A+aA AA | eFIRSTFOLLOWS*，a#S*,e#A+*,#A+,e*,#預(yù)測(cè)分析表：*a+#SS*aASS aASSS*ASSeAA+aAAAeAAAe（3）用預(yù)測(cè)分析表對(duì)輸入串進(jìn)行分析的過程簡(jiǎn)答題5分；1 給定LL(1)分析表：有輸入符號(hào)串i+i*i，寫出按上述算法識(shí)別此符號(hào)串的過程。答案：2 已知文法分析表：i+*()#-/EE-TGE-TGGG-+TGG-G-G-TGTT-FST-FSSS-S-*FSS-S-S-S-/FSFF-iF-(E)有輸入符號(hào)串i-i/i#，寫出按上述算法識(shí)別此符號(hào)串的過程，遇到錯(cuò)誤停止即可，不需要錯(cuò)誤恢復(fù)。答案：步驟分析棧 剩余字符 所用產(chǎn)生式 0#E i-i/i# E-TG1#GT i-i/i# T-FS2#GSF i-i/i# F-i3#GSi i-i/i# i匹配4#GS -i/i# S-5#G -i/i# G-TG6#GT- -i/i# -匹配7#GT i/i# T-FS8#GSF i/i# F-i9#GSi i/i# i匹配10#GS /i# S-/FS11#GSF/ /i# /匹配12#GSF /i# F出錯(cuò)3 已知文法分析表：a$(),#Sa$(T)TSFSFSFF,SF有輸入符號(hào)串(a,(a)#，寫出按上述算法識(shí)別此符號(hào)串的過程。答案：步驟分析棧 剩余字符 所用產(chǎn)生式 0#S (a,(a)# S-(T) 1#)T( (a,(a)# (匹配2#)T a,(a)# T-SF 3#)FS a ,(a)# S-a 4#)Fa a,(a)# a匹配5#)F ,(a)# F-,SF 6#)FS, ,(a)# ,匹配7#)FS (a)# S-(T) 8#)F)T( (a)# (匹配9#)F)T a)# T-SF 10#)F)FS a)# S-a 11#)F)Fa a)# a匹配12#)F)F )# F- 13#)F) )# )匹配14#)F )# F- 15#) )# )匹配16# # acc!第三章 3.4自下而上分析H（1）歸約概念選擇題2分；1 若a為終結(jié)符，則A- a為_項(xiàng)目。A. 歸約B. 移進(jìn)C. 接受D. 待約 答案：B2 移近-歸約分析為輸入串構(gòu)造分析樹是從（ ）開始的。A. 根結(jié)點(diǎn)B. 葉結(jié)點(diǎn)C. 中間結(jié)點(diǎn)D. 任一結(jié)點(diǎn)答案：B3 在每一步歸約中，一個(gè)子串和某個(gè)產(chǎn)生式的（ ）匹配，然后用該產(chǎn)生式的（ ）符號(hào)代替這個(gè)子串。A. 右部 左部B. 右部 右部C. 左部 右部D. 左部 左部答案：A（2）句柄概念選擇題2分；1 在規(guī)范歸約中，用（ ）來刻畫可歸約串。A. 直接短語B. 句柄C. 產(chǎn)生式D. 記號(hào)答案：B2 下面說法正確的是（ ）。A. 句柄是該句型中和一個(gè)產(chǎn)生式左部匹配的子串B. 文法是二義的，句柄是唯一的C. 文法無二義時(shí)，句柄可能是唯一的D. 以上說法都不對(duì)答案：D3 面說法錯(cuò)誤的是（ ）。A. 句柄是該句型中和一個(gè)產(chǎn)生式右部匹配的子串B. 文法是二義的，句柄可能不唯一C. 文法無二義時(shí)，句柄是唯一的D. 句型中能和產(chǎn)生式A-右部匹配的最左子串就是句柄答案：D第三章 3.5 LR分析器I（1）活前綴概念選擇題2分；1一個(gè)句型中的活前綴為（）A. 短語 B.簡(jiǎn)單短語 C.句柄 D.右句型的前綴，該前綴不超過最右句柄的右端答案：D2在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型( ) 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目答案：C3下列語句描述錯(cuò)誤的是（）A.活前綴不包含句柄的任何符號(hào)，此時(shí)期待從輸入串中看到該句柄對(duì)應(yīng)的產(chǎn)生式的右部所推導(dǎo)出的符號(hào)串B.活前綴只包含句柄的一部分符號(hào)，表明該句柄對(duì)應(yīng)的的產(chǎn)生式的右部子串已出現(xiàn)在棧頂，期待從輸入串中看到推導(dǎo)出的符號(hào)串C.活前綴已含有句柄的全部符號(hào)，表明該句柄對(duì)應(yīng)的產(chǎn)生式的右部已出現(xiàn)在棧頂D.活前綴只包含句柄的一部分符號(hào)，表明該句柄對(duì)應(yīng)的產(chǎn)生式的右部已出現(xiàn)在棧頂答案：D（2）構(gòu)造SLR分析表簡(jiǎn)答題20分；1 給定下列文法構(gòu)造其SLR分析表 E E + T F F* E T F a T T F F b T F 2 考慮文法E EE +|EE*|a，構(gòu)造它的SLR分析表3設(shè)有文法 SrD DD,i|i(1)證明該文法不是LR(1)文法，是SLR文法(2)給出該文法的SLR分析表答案：(1)構(gòu)造活前綴的DFA因?yàn)樵跔顟B(tài)出出現(xiàn)（移進(jìn)，歸約）沖突，所以不是LR(0)文法。因?yàn)閒ollow(S)=#，可以解決沖突，即若當(dāng)前單詞為，則移進(jìn)，；若當(dāng)前單詞為#，則歸約r(1)。所以是SLR 文法。(2)SLR分析表（3）構(gòu)造LR分析表簡(jiǎn)答題20分；1給定文法 GS：請(qǐng)構(gòu)造該文法的LR分析表 2 給定文法 （1）證明它是LR文法（2）構(gòu)造其LR分析表答案：（1）該文法LR的項(xiàng)集規(guī)范集如下：觀察上面的項(xiàng)目規(guī)范集可以發(fā)現(xiàn)，在項(xiàng)集0和3中，歸約項(xiàng)都是在面臨符號(hào) $ 時(shí)才發(fā)生，和移進(jìn)符號(hào)不同。所以，該文法是LR文法。（2）它的LR分析表如下圖所示狀態(tài)ACTIONGOTOab$SA0S4S2R2131Acc2R4R4R43S7S5R2634S4S285R46R17S7S598R3R3R39R33已知文法G(S) SBB BaB Bb構(gòu)造其LR分析表答案： LR分析表（4）構(gòu)造LALR分析表簡(jiǎn)答題20分；1給定下列文法，構(gòu)造其LALR分析表 S E S S S E E E + T | T E E + T E T T ( E ) | a T ( E ) T a 2有如下文法G(S)： SS SL=R SR L*R Li RL(1)寫出此文法的LALR分析表(2)根據(jù)文法的LALR分析表分析輸入串“i=*i#”的過程答案：(1)LALR分析表(2) “i=*i#”的LALR分析過程3給定文法G(S)構(gòu)造其LALR分析表。狀態(tài)ACTIONGOTOabcd$SBA0S6S3S41231acc2S73R5S84S9105S6S12116R7R7R77R28R39R510S1411S12R412R6R6R613R1（5）SLR分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作簡(jiǎn)答題5分；1已知文法及其SLR分析表，給出輸入串“ab#”的SLR分析過程。SLR分析表答案：2若有定義二進(jìn)制數(shù)的文法如下：SLR分析表為給出輸入串101.110 的分析過程。答案： 3 考慮以下的文法G（E）：E(L) | aLL , E | E其SLR分析表為給出輸入串(a) , a , (a , a)的SLR分析程序的動(dòng)作。答案：（6）LR分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作簡(jiǎn)答題5分；1已知文法G(S) SBB BaB Bb其LR分析表為假定輸入串為abab，請(qǐng)給出LR分析過程（按步驟給出狀態(tài)棧，符號(hào)，輸入串的變化過程）答案：2 給定文法 GS：該文法的LR分析表為 請(qǐng)給出輸入符號(hào)串a(chǎn)bab 的分析過程。答案：3已知文法G：的LR分析表如下：給出()的LR分析過程。答案：第三章 3.7 語法分析器的生成器J（1）Yacc的相關(guān)概念選擇題2分;1Yacc程序不包含下面的哪一部分（）A.聲明B.翻譯規(guī)則C.支持例程D.定義答案：D2下列說法正確的是( )A.lex是一個(gè)詞法分析器B.Yacc是一個(gè)語法分析器的生成器C.lex是一個(gè)語法分析器的生成器D.Yacc是一個(gè)語法生成器答案：B3用Yacc處理二義文法的兩大默認(rèn)規(guī)則為（）對(duì)于歸約-歸約沖突，選擇在Yacc程序中最先出現(xiàn)的那個(gè)產(chǎn)生式歸約對(duì)于歸約-歸約沖突，選擇在Yacc程序中后出現(xiàn)的那個(gè)產(chǎn)生式歸約對(duì)于移近-歸約沖突，優(yōu)先移近對(duì)于移近-歸約沖突，優(yōu)先歸約A B C D答案：A第四章 4.1 語法制導(dǎo)定義K（1）繼承屬性、綜合屬性的概念 選擇題 2分1描述文法符號(hào)的屬性有哪兩種（）L-屬性 R-屬性 綜合屬性 繼承屬性A. B. C. D.答案：B2下列說法正確的是A.綜合屬性值的計(jì)算依賴于分析樹中他的子節(jié)點(diǎn)的屬性值B.綜合屬性值的計(jì)算依賴于分析樹中他的兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的屬性值C.繼承屬性值的計(jì)算依賴于分析樹中他的子節(jié)點(diǎn)的屬性值D.綜合屬性值的計(jì)算依賴于分析樹中他的父節(jié)點(diǎn)的屬性值答案：A3對(duì)于產(chǎn)生式的繼承屬性，可能正確的語義規(guī)則是 （）A. B. C. D. 答案：C（2）S屬性定義的概念 填空題 2分1S屬性是僅僅使用 的語法制導(dǎo)定義。答案：綜合屬性2對(duì)于S屬性定義，分析樹中各結(jié)點(diǎn)屬性的計(jì)算是 完成的。答案：自下而上3分析樹中各結(jié)點(diǎn)屬性的計(jì)算中采用自下而上方法計(jì)算的屬性定義為 。答案：S屬性定義（3）注釋分析樹 填空題 2分1注釋分析樹的概念為 。答案：每個(gè)結(jié)點(diǎn)的屬性值都標(biāo)識(shí)出來的分析樹2 每個(gè)結(jié)點(diǎn)的屬性值都標(biāo)識(shí)出來的分析樹稱為 。答案：注釋分析樹3 注釋分析樹中計(jì)算各結(jié)點(diǎn)屬性值的過程稱為 。答案：注釋或修飾第四章 4.2 S屬性的計(jì)算L（1）S屬性定義的自下而上計(jì)算、棧操作 填空題 2分1在語法樹中，算符和關(guān)鍵字作為 結(jié)點(diǎn)。答案：內(nèi)部2S 屬性定義的計(jì)算中，拓展后分子棧的每個(gè)棧元素由 和 兩部分組成。答案：狀態(tài)域state 屬性域val3 S 屬性定義的計(jì)算中，若產(chǎn)生式的語義規(guī)則是，那么在XY規(guī)約成A之前，stacktop-1.Val中存放 的值。答案：x.val /X.x第四章 4.3 L屬性的計(jì)算M（1）L屬性定義的概念 選擇題 2分1下列關(guān)于L屬性定義的說法正確的是（）A.S屬性定義屬于L屬性定義B.變量類型聲明的語法制導(dǎo)定義不是一個(gè)L屬性定義C.L屬性定義中只包含綜合屬性D.L屬性定義中只包含繼承屬性答案：A2在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計(jì)算的是的繼承屬性，則他依賴于（）A的繼承屬性A的綜合屬性該產(chǎn)生式中左邊符號(hào)的屬性該產(chǎn)生式中右邊符號(hào)的屬性 A B C D答案：A3 在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計(jì)算短的可以是（）A的綜合屬性A的繼承屬性的繼承屬性的綜合屬性A B C D 答案：A （2）給定文法，寫出翻譯方案 簡(jiǎn)答題 10分1 為下列簡(jiǎn)化的程序文法： P D， D D；D|id：T|proc id；D；S。 寫一個(gè)翻譯方案，打印該程序中每個(gè)標(biāo)識(shí)符id的嵌套深度答案：令屬性n表示嵌套深度，下面是一個(gè)打印標(biāo)識(shí)符id嵌套深度的翻譯模式 P D.n：=1 D D D1.n：=D.n D1；D2.n：=D.n D2 D id：T print（，D.n） D proc id；print（，D.n） D1.n：=D.n+1 D1:S2 假設(shè)有以下文法 D L id L , id L1 | : T T integer | real建立一個(gè)翻譯模式, 把每一個(gè)標(biāo)識(shí)符的類型加入到符號(hào)表中。答案： D L id addtype(id.entry, L.type L , id L1 L.type= L1.type addtype(id.entry, L.type L : T L.type= T.type T integer T.type= 0 T real T.type= 1 用整數(shù)0表示整型, 1表示實(shí)型.3 考慮文法： S ( L)|a L L，S|S 寫一個(gè)翻譯模式，它打印出每個(gè)a在句子中的位置。例如，對(duì)于輸入串（a，（a，a）的結(jié)果是2,5,7.答案：引入屬性pos，得到的翻譯模式如下： S S.pos：=1； S S ( L L.pos:=S.pos+1; ) Sa print(S.pos); L L1.pos:=L.pos; L1 , S.pos:=L.pos+2; S L S.pos:=L.pos; S 第四章 4.4 L屬性的計(jì)算N（1）L屬性定義的自上而下分析中各種屬性與參數(shù)、返回值的映射關(guān)系填空題 2分1 設(shè)計(jì)翻譯方案時(shí)，必須保證動(dòng)作在引用屬性時(shí)其值已經(jīng)可用，在只有 屬性時(shí)，為每條語義規(guī)則建立一個(gè)賦值動(dòng)作，把該動(dòng)作放在對(duì)應(yīng)產(chǎn)生式的右部的末端，由此可以得到翻譯方案。答案：綜合2 L屬性定義的自上而下分析中設(shè)計(jì)翻譯方案時(shí)，若包含繼承屬性則產(chǎn)生式右部符號(hào)的 必須在先于這個(gè)符號(hào)的動(dòng)作中計(jì)算。答案：繼承屬性3 L屬性定義的自上而下分析中設(shè)計(jì)翻譯方案時(shí)，若包含繼承屬性則左部非終結(jié)符的 只能在他所引用的所有屬性都計(jì)算完后才能計(jì)算。答案：綜合屬性（2）L屬性定義的自下而上計(jì)算中輔助非終結(jié)符引入的目的 選擇題 2分1 L屬性定義的自下而上計(jì)算中的標(biāo)記非終結(jié)符說法正確的是（）A. 引入標(biāo)記非終結(jié)符可以刪除翻譯方案中嵌入的動(dòng)作B. 使L屬性定義的繼承屬性計(jì)算只出現(xiàn)在產(chǎn)生式左端C. 使L屬性定義的綜合屬性計(jì)算只出現(xiàn)在產(chǎn)生式右端D. 使L屬性定義的綜合屬性計(jì)算只出現(xiàn)在產(chǎn)生式左端答案：A2 L屬性定義的自下而上計(jì)算中引入標(biāo)記非終結(jié)符引入的目的錯(cuò)誤的是（）A. 刪除翻譯方案中嵌入的動(dòng)作B. 模擬綜合屬性的計(jì)算C. 模擬繼承屬性的計(jì)算D. 確定分析棧上屬性的位置答案：B3 L屬性定義的自下而上計(jì)算中處理繼承屬性時(shí)需要引入（）A. 標(biāo)記非終結(jié)符 B. 標(biāo)記終結(jié)符 C. 綜合屬性 D. L屬性答案：A第六章 6.1, 6.2局部、全局存儲(chǔ)分配O（1）襯墊區(qū)、對(duì)齊的概念 選擇題 2分1下列說法正確的是（）A. 襯墊區(qū)是指由于考慮對(duì)齊問題而引起的無用空間B. 局部數(shù)據(jù)存儲(chǔ)安排不存在對(duì)齊問題C. 局部數(shù)據(jù)的數(shù)據(jù)存儲(chǔ)安排與目標(biāo)機(jī)器的尋址限制無關(guān)D. 襯墊區(qū)是一定會(huì)出現(xiàn)的答案：A2關(guān)于襯墊區(qū)的定義，下列說法正確的是（）A. 襯墊區(qū)是在考慮對(duì)齊問題時(shí)增加的額外空間B. 襯墊區(qū)是指由于考慮對(duì)齊問題而引起的無用空間C. 襯墊區(qū)是局部數(shù)據(jù)在存儲(chǔ)的所需要的最大空間D. 襯墊區(qū)是局部數(shù)據(jù)在存儲(chǔ)的所需要的最小空間答案：B3 局部數(shù)據(jù)在存儲(chǔ)安排時(shí)，襯墊區(qū)是因?yàn)椋ǎ﹩栴}而引起的無用空間A. 對(duì)齊 B. 數(shù)據(jù)的順序 C . 數(shù)據(jù)類型 D. 空間答案：A（2）活動(dòng)記錄的內(nèi)容 簡(jiǎn)答題 5分1活動(dòng)記錄包括哪些內(nèi)容/答案：返回值，參數(shù)，控制鏈，訪問鏈，保存的機(jī)器狀態(tài)，局部數(shù)據(jù)，臨時(shí)數(shù)據(jù)2簡(jiǎn)述活動(dòng)記錄中的各個(gè)域及其用途。答案：返回值：用于返回本過程中給調(diào)用過程的值 參數(shù)：調(diào)用過程傳遞給本過程的參數(shù) 控制鏈：指向調(diào)用過程的指針 訪問鏈：用于引用存于其他活動(dòng)記錄的非局部數(shù)據(jù) 機(jī)器狀態(tài)：御用保存本過程調(diào)用前的機(jī)器狀態(tài) 局部數(shù)據(jù)：本過程內(nèi)部定義的局部變量 臨時(shí)數(shù)據(jù)：本過程計(jì)算中可能用到的臨時(shí)變量3簡(jiǎn)述活動(dòng)記錄的概念及其內(nèi)容答案：活動(dòng)記錄是存儲(chǔ)過程執(zhí)行一次所需局部信息的連續(xù)的存儲(chǔ)區(qū)。其內(nèi)容包括返回值，參數(shù)，控制鏈，訪問鏈，保存的機(jī)器狀態(tài)，局部數(shù)據(jù)，臨時(shí)數(shù)據(jù)（3）活動(dòng)樹的概念 簡(jiǎn)答題 5分1活動(dòng)樹有哪些特點(diǎn)？答案：每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)； 根結(jié)點(diǎn)代表主程序的活動(dòng)； 結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)； 結(jié)點(diǎn)a 處于結(jié)點(diǎn)b 的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。2什么是活動(dòng)樹？答案：用來描繪控制進(jìn)入和離開活動(dòng)的方式的樹3簡(jiǎn)介活動(dòng)樹的概念及其特點(diǎn)。答案：活動(dòng)樹是用來描繪控制進(jìn)入和離開活動(dòng)的方式的樹。其特點(diǎn)為：每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)；根結(jié)點(diǎn)代表主程序的活動(dòng)；結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)；結(jié)點(diǎn)a 處于結(jié)點(diǎn)b 的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。（4）控制棧、運(yùn)行棧的概念 填空題 2分1 把控制棧中的信息拓廣到包括過程活動(dòng)