課程測試試題(04A卷)

I、命題院(部)：數學與計算機科學學院

n、課程名稱：編譯原理n、I測試學

期：2022—2022學年度第1學期

IV、測試對象：數計、國交學院計科專業2004級1、2、國交班

V、問卷頁數(A4)：3頁VI

、答卷頁數(A4)：4頁—

VII、考試方式：閉卷(開卷、閉卷或者課程小論文，請填寫清晰)

VIIL問卷內容：(請老師在出題時安排緊湊，填空題象征性的留出一點空格,

學生將所有的答案做在答題紙上的規定位置，并寫清晰大題、小題的題號)

一、填空題(共30分，30個空，每空1分)

1、典型高級程序設計語言編譯系統的工作過程普通分為六個階段，即詞法分析、語法

分析、語義分析、中間代碼生成、、目標代碼生成。編譯階段的兩種組合方式是_____組

合法和按遍組合法，這兩種組合方式的主要參考因素都是的特征。

2、Chomsky將文法按其所表示語言的表達能力，由高往低分為四類：0型，1型，2型，

3型文法。其中，2型文法也稱^_，它的所有規則a―哪茜足：ae—,pG((VUV)*NT

且_____，僅當懺時例外。

3、現代編譯系統多采用方法，即在語法分析過程中根據各個規則所相聯的或

者所對應的語義子程序進行翻譯的辦法。該方法使用為工具來說明程序設計語言的語

義。

4、構造與NFAM等價的正規文法G的方法如下：(1)對轉換函數f(A,a)=B或者f(A,

￡)=B,改成形如____或者____的產生式；(2)對可識別終態Z,增加一個產生式：_____，

5、代碼生成要考慮的主要問題：充分利用_的問題、選擇一的問題、選擇一的

問題。

僅設有窮自動機M=(K,,f,S,Z),若當M為____時，滿足20￡皓，aDzOez,或者當

M為____時，滿足咯a)=P￡Z,則稱符號串a￡*可被M所_____。

7、符號表中每一項對應一個多元組。符號表項的組織可分為—組織、組織、—組

織等。

8、對于A￡V忠義A的后續符號集：FOLLO\y(A)={a|S=*>uAp,aGV,且a￡____,

u￡V*(3￡V+;若_貝iJ#￡FOLLOW(A)。也可以定義為：FOLLOW(A)={alS=*>...Aa...,

aGV^o若有,則規定#￡FOLLOW(A)。

9、基本塊的定義：一個基本塊是指程序中一個執行的語句序列，其中惟獨一個入

口和一個出口。入口是程序第一個語句或者轉移語句的目標語句，或者轉移語句的后繼第一

個語句。出口是程序或者轉移語句。在基本塊范圍內的優化稱為。

10、預測分析器由預測分析表、先進后出棧(用來存放分析過程的語法符號)和____三

部份組成。其中預測分析表是一個二維矩陣，其形式為M[A,a],其中A￡V,總任￥或者#。

若有產生式A—a,使得■則將A—儂入M[A,a]中。(書寫時，通常省’略規則左部，

只填—a。)對所有的MIA,a的W己為出錯。

二、簡述題(共20分，4個小題，每小題5分)

1、簡述將NFA轉換為最小化DFA的步驟。

2、簡述靜態存儲分配、棧式存儲分配和堆式存儲分配的特點和主要用途。

3、以表達式a:=b*(-c)+b/(-d)為例，簡述常用的三種中間代碼表示形式。

4、簡述判別文法G是否為LL(1)文法的步驟和將一個非LL(1)文法轉換為LL(1)文法的

方法。

三、應用題(共50分)

1、有文法G[SJ：(12分)

S—>aAS|aA—>SbA|SS|ba

⑴證明aabbaa是文法的一個句子。（3分）

（2）構造句子aabbaa的語法樹。（3分）

⑶指出該句子的所有短語、直接短語和句柄。（6分）

2、對文法G[E1：（15分）

ETE#E一E+T|TT->T*F|FF->FF|PP->（E）|i

（1）計算G[E]的FIRSTVT和LASTVTo（5分）

⑵構造G舊]的算符優先關系表,并說明G[E]是否為算符優先文法。（5分）

（3）給出輸入串w=i+i#的算符優先分析過程。（5分）

3、對以下基本塊：（8分）

A：=5B：=R+rTO：=A+BTl：=2*A

T2：=B+AT3：=A+AXI：=T1+T2X2：=T0*T3

（1）畫出基本塊的DAG圖。（3分）

（2）根據DAG結點原來的構造順序重寫四元式。（2分）

（3）假設基本塊出口后惟獨XI,X2還被引用，試寫出優化后的四元式序列。（3分）

4、對文法G[S']：（15分）

0）S'TS1）S->A2）S-B3）A->aAe

4）A-a5）B—bBd6）B—b

⑴試構造G[S]的LR（0）項忖集規范族DFA。（4分）

（2）試構造G[S]的SLR⑴分析表，并判斷它是否為SLR⑴文法。（4分）

⑶試用SLR（1）方法分析輸入串aae#0（4分）

（4）G[S]是否為LR（0）、LR⑴和LALR（l）文法？為什么？（3分）

課程測試試題（04B卷）

I、命題院（部）：數學與計算機科學學院

n、課程名稱：編譯原理u、I測試學

期：2022—2022學年度第1學期

IV、測試對象：數計、國交學院計科專業2004級1、2、國交班

V、問卷頁數（A4）：3頁

VI、答卷頁數（A4）：4頁

VII、考試方式：閉卷（開卷、閉卷或者課程小論文，請填寫清晰）

VIII、問卷內容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格,

學生將所有的答案做在答題紙上的規定位置，并寫清晰大題、小題的題號）

一、填空題（共30分，30個空，每空1分）

I、典型編譯過程普通分為詞法分析、語法分析、語義分析、_____（并非所有的編譯程

序都包含此階段）、代碼優化、目標代碼生成六個階段，其中詞法分析的任務是對構成源程

序的字符串進行掃描和分解，識別出一（如標識符等）符號；為代碼生成階段采集類型信息，

并進行類型審查和違背語言規范的報錯處理是一的任務。

2、文法是一些規則的有窮集合，它是以有窮規則集來刻劃無窮___集合的工具。文法

的四元組表示6=（丫加3,P,3）中4不素V,V分別是非空有限的o且二者

交集為（P；P為產生式/規則集，是文法的核心部份：S￡V,晨文法的開始符號（或者識別符），

它是一個非終結符，至少要在一條規則中作為浮現。

3、構造LR（0）項目集規范族的項目類型分為四種：形如A->a.a的、形如

的待約項目、形如A—唧的歸約項目、形如STOI'KJo

4、一個優先關系矩陣對應的優先函數：所表示優先關系惟一的矩陣不一定存在優

先函數；當兩個終結符對之間無優先關系時，可以將相應元素置出錯信息，而使用—卻

無法識別這種情況，不能準確指出出錯位置。

5、在編譯程序中用符號表來存放語言中浮現的有關的語義特征屬性信息。程序設

計語言中通用的標識符屬性主要有如下幾種：符號名、符號的、符號的存儲類別、符

號的_____、符號變量的存儲分配信息及數組的內情向量等其它屬性。

6、如果文法G=（V“V\P，S）中不存在形如A->…BC…的產生式，其中B、C

為非終結符，則稱之為____在此基礎上，如果a,b￡VT,a三b,?ab,a>b至_______有一個成

立，則稱之為o

7、分為三類：____的機器語言代碼；的機器語言代碼；匯編語言（宏匯編）。

8、在程序流中，一個循環必須具有以下性質：1）.即序列中任意兩點都可達，

若惟獨一個結點，則有一條返回本身的回邊；2）,即從序列外某結點，有一條有向邊

指向它，或者它為圖中首結點。

9、LR分析步驟：1）置輸入指針ipl旨向輸入串的第一個符號；令S是棧頂狀態，a是ip所

指向的符號;將#壓入符號棧，將開始狀態0壓入狀態棧；2）根據分析表重復執行如下過程：如

果action[,Sa]=S.,則把____A符號棧，把____入狀態棧，并使ip指向下一個輸入符號；如果

action[S^l=,r則從由頂彈出第j條規則右部串長|0個|符號，把_____壓入符號棧，將_____壓入狀態

棧，并盜出規則AT。；如果action[Sz]=a,cc則分析成功，否則報錯。

10、過程（函數）是結構化程序設計的主要手段。調用與被調用過程兩者之間的信息主要

通過或者參數來傳遞。參數分為,常用的參數傳遞方式有傳地址、傳值、傳名等。

二、簡述題（共20分，4個小題，每小題5分）

I、簡述運行目標程序時所需空間的種類。

2、簡述算符優先分析算法的步驟和算符優先分析方法的優、缺點。

3、簡述代碼優化的概念和分類，并列舉出四種以上常用的代碼優化技術。

4、簡述判別任意給定的一個_L下文無關文法G[S]是否為LALR（l）文法的過程。

三、應用題（共50分）

1、有文法G[E]：（16分）

E—T+E|TT->T*F|FF->（E|）i

（1）證明T+T*F+i是文法的一個句型。（3分）

（2）構造型T+T*F+i的語法樹。（3分）

⑶指出該句型的所有短語、直接短語和句柄。（7分）

（4）指出該句型的所有素短語和最左素短語。（3分）

2、將下列條件語句翻譯成四元式的中間代碼形式：（6分）

ifa<borc<dande>fthensielses2

3、有正規文法G[SJ：（12分）

S->aA|bBA一Sb|bB->aS|a

⑴構造對應的正規式R，使得L（R）=L（G）。（3分）

（2）構造對應的NFA狀態圖，使得L（M）=L（R）o（3分）

（3）將所得NFA確定化為DFA。（3分）

（4）將所得DFA最小化。（3分）

4、對表達式文法G[E]：（16分）

E->E-T|TT—TAF|FF->（E|）a

⑴判斷G[E]是否為LL（D文法。若不是，改造為LL（1）文法。（8分）

⑵構造預測分析表，并對輸入串w=a-a%#進行預測分析。（8分）

課程測試試題（03A卷）

---------------以-下為教師填寫---------------

I、命題院（部）：數學與計算機科學學院

n、課程名稱：編譯原理u、I測試學期：

2005—2022學年度第1學期

IV、測試對象：數計學院計算機科學技術專業2003級1、2、3班V、

問卷頁數（A4）：4頁_

VI、答卷頁數（A4）：6頁

VIL考試方式：閉卷（開卷、閉卷或者課程小論文，請填寫清晰）

VIII、問卷內容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格，

學生將所有的答案做在答題紙上的規定位置，并寫清晰大題、小題的題號）

一、填空（30分）

1、將編譯過程的各階段劃分為前端或者后端和將編譯程序分遍的主要參考因

素都是（）和（）的特征。

2、（）是一種語法分析程序的自動構造工具，用它可以直接構造各種語言

的語法分析器；而（）是一種詞法分析程序的自動構造工具，用它可以直接構造

各種語言的詞法分析器。

3、假設G網是一個文法，如有S*x,則稱x是該文法G的（）；文法G產生的（）

的全體稱為該文法所描述的語言。

4、所謂2型文法就是指（）文法，若用G=（V,V,P,S）表示它，則NT

它要求G中的所有規則a-p都滿足：a是（），而p屬于（VUV）,。n

5、文法中形如U-U的規則稱為（）規則；由不可達的非終結符或者不可終

止的非終結符作為左部的規則稱為（）規則。在實用文法中普通不允許含有這兩

類規則。

6、在用五元組表示的確定的有窮自動機DFAM=（K,V,F,S,Z）中，元素V

表示字母表；元素S表示惟一的初態，它是狀態集K的一個元素；元素F表示（）；元素

Z表示終態集，它是狀態集K的一個（）。

7、語法分析方法分為自上而下與自下而上兩類，自上而下的分析方法方要有

遞歸子程序分析法和（）；而自下而上的分析方法主要有（）和“<分析方法。

8、LR（0）項目集規范族中的項目可分為四類，它們是移進項目、（）、歸約

項目和接受項目。其中，接受項目是（）的一種特例。

9、將非LL（1）文法轉換為等價的LL（D文法所采用的兩種方法是（）和（）o但這

兩種方法并不能保證所有的非1X（1）文法都能轉換為等價的LL（1）文法。

10、通常局部優化是指基本塊內的優化，所謂基本塊是指程序中一順序執行

的語句序列，其中惟獨一個（）語句和一個（）語句。

11、算符優先分析時，在句型NaN…aNaNa…aNaN…中，尋覓的「2

Miii+1i+|jj+lj+lj+2

最左素短語NaNa...aN中的終結符應滿足下優先關系：（）、（）、（）。

IIH-I141jj4|

12、在編譯程序中符號表用來存放語言程序中浮現的有關標識符的屬性信息，

這些信息集中反映了標識符的語義特征屬性。符號表的功能可以歸結為三個主要

方面，即（卜作為上下文語義合法性檢查的依據和作為（）的依據。

13、根據優先關系矩陣計算優先函數可用迭代法或者優先關系圖法，但先關

系圖方法計算出來的優先函數不一定有效，當（）時，所得的優先函數無效，這

時也說明該優先關系矩陣不存在優先函數。

14、當一個過程調用其他過程時，調用過程和被調用過程之間的通信經由非

局部變量或者經由參數傳遞，常用的參數傳遞方式有（）、（）等。

15、現代不少編譯程序都采用（）翻譯方法，它是指在語法分析過程中，隨

著分析的步步發展，根據每一個規則所對應的語義子程序或者語義動作進行翻譯

的辦法。這種方法使用（）為工具來說明程序設計語言的語義。

二、結合你所熟悉的一門高級語言的編譯系統，簡述典型編譯程序在各個工作

階段的任務。（共7分）

三、給定正規式R=（01110）（01110>,要求：（10分）

1、構造對應的正規文法G,使得L（G）=L（R）。（4分）

2、構造對應的NFAM狀態圖，使得L（M）=L（R）。（3分）

3、將所得NFAM確定化為DFA。（3分）

四、現有文法GI0：（共10分）

E-E+T|E-T|T

T—T*F|T/F|F

F->i|（E）

1、證明：E-F*①是文法的一個句型。（3分）

2、構造句型E-F*（i）的語法推導樹。（2分）

3、指出該句型所有短語、直接短語和句柄。（5分）

五、任意給定一個文法G[S]：（10分）

1、給出判斷G[S]是否為LL（1）文法的步驟。（4分）

2、如果G圖是LL⑴文法，怎樣構造它的預測分析表？（3分）

3、怎樣根據預測分析表對給定的某個輸入串進行預測分析？（3分）

六、現有文法G[E]：（共15分）

E—E;D|D

D-^DCT）|H

H—a|（E）

T—T*E|E

1、計算G[E]的FIRSTVT和LASTVT；（4分）

2、構造G[E]的算符優先關系表,并說明G[E]是否為算符優先文法；（5分）

3、給出輸入串（a*a）#的算符優先分析過程，并據此說明算符優先分析方法的優點

和缺點。（6分）

七、現有文法G[S，]：（共18分）

0）SJS

1）S->L=R

2）S->R

3）L—*R

4）L->i

5）R->L

1、構造G[S]的LR（0）項目集規范族DFA,并據此判斷G[S，]是否為LR（0）文法或

者SLR⑴文法。（6分）

2、構造G[S]的LR（1）項目集規范族DFA,并據此判斷G[S]是否為LR（1）文

法或者LALR⑴文法。（6分）

3、給出相應的LALR⑴分析表。（3分）

4、簡述LR分析算法。（3分）

課程測試試題（03B卷）

--------------以一下為教師填寫---------------

I、命題院（部）：數學與計算機科學學院

II、課程名稱：編譯原理U、I測試學期：

2005-2022學年度第1學期

IV、測試對象：數計學院計算機科學技術專業2003級1、2、3班

V、問卷頁數（A4）：4頁

VI、答卷頁數（A4）：6頁

VII、考試方式：閉卷（開卷、閉卷或者課程小論文，請填寫清晰）

VIIL問卷內容：（請老師在出題時安排緊湊，填空題象征性的留出一點空格，

學生將所有的答案做在答題紙上的規定位置，并寫清晰大題、小題的題號）

一、判斷（15分）

1、編譯程序是一種語言翻譯程序，它將源語言程序翻譯成功能等價的目標

語言程序。

2、所謂規則或者產生式是指形如a一娥者之三。的（％份有序對，其中a是字母表V

的正閉包元素，而。是字母表V的閉包元素。

3、設文法G=（V,V,P,S）,若P中的每一個規則都是A-aB或者A—a,

TN

其中A和B是非終結符，而a是終結符，則稱此文法G為正規文法或者3型文法。

4、實用文法中不得含有形如U-U的有害規則，也不得含有由不可達或者不

可終止的非終結符所構成的多余規則。

5、對任意給定的一個正規式R,都可以將它轉換為與之功能等價的正規文法，

或者與之功能等價的有窮自動機。

6、LEX是一個用于構造各種各樣語言的詞法分析程序；YACC是一個用于

構造各種各樣語言的語法分析程序。

7、假設現有五元組表示的有窮自動機M=（K,V,F,S,Z）,若M是NFA,

則S表示初態，且S具有惟一性，它是狀態集K的一個元素。

8、算符優先分析方法和LR分析方法都是自下而上的分析方法，它們的分析

過程實際上就是規范歸約過程。

9、LR（O）項目集規范族中的項目由兩部份構成，一部份是心，即原來的LR（1）

項目，另一部份是向前搜索符號集。

10、所謂優化實質上是對代碼進行等價變換，使得變換后的代碼運行結果與

變換前的代碼運行結果相同，但運行速度或者占用的存儲空間加大。常用的優化

技術看?刪除多余運算、代碼外提、弓雖度削弱、變換循環控制條件、合并已知變量

與復寫傳播等。

11、對一個不包含空規則的算符文法，如果文法中的任意兩個終結符構成的

符號對之間最多惟獨大于、小于和等于三種優先關系中的一種成立，則稱該算符

文法為算符優先文法。

12、目標程序運行時的動態數據存儲區分為堆區和棧區，它用于存放可變數

據以及管理過程活動的控制信息。

13、在語法分析過程中，隨著分析的步步發展，根據每一個規則所對應的語

義子程序或者語義動作進行翻譯的辦法，稱為語法制導翻譯，它被現代不少編譯

程序所采用。

14、可歸前綴本身就是活前綴，它是包含句柄在內的活前綴。

15、符號表用來存放語言程序中浮現的有關標識符的屬性信息，這些信息集

中反映了標識符的語義特征屬性。

二、將表達式A:=B*（C-D）/D：（共9分）

3、翻譯成逆波蘭式的中間代碼形式。（2分）

4、翻譯成四元式的中間代碼形式。（4分）

5、將譯成的四元式用DAG表示。（3分）

三、現有文法35：供12分）

ETE+T|E-T|T

T—T*F|T/F|F

FTKE）

6、證明：F+T*（E）是文法的一個句型。（3分）

7、構造句型F+T*（E）的語法推導樹。（3分）

8、指出該句型所有短語、直接短語和句柄。（6分）

四、給定正規式R=d（a|bc）d,要求：（12分）

4、構造對應的NFAM狀態圖，使得L（M）=L（R）。（4分）

5、將所得NFAM確定化和最小化。（8分）

五、現有文法G[S]：（共16分）

STS;D|D

DTD（T）|H

H->m|（S）

T-T*S|S

1、計算G⑶的FIRSTVT和LASTVT；（4分）

2、構造G[S]的算符優先關系表,并說明G[S]是否為算符優先文法；（6分）

3、給出輸入串（m*m）#的算符優先分析過程。（4分）

4、根據分析過程總結算符優先分析方法的優缺點。（2分）

六、已知G[S]：（18分）

S—>（A）|a|b

AfS|S

1、給出（4（b,b））的最左推導。（3分）

2、判斷該文法是否為LL（1）文法。若是，直接給出它的預測分析表；若不是,

先將其改寫為LL⑴文法，再給出它的預測分析表；（10分）

3、給出輸入串（b,b）#的分析過程，并說明該串是否為G[S]的句子。（5分）

七、對給定文法G[S]:（共18分）

0）S'—S

1）S->A

2）S—B

3）A—>aAc

4）A—a

5)B—bBd

6)B—b

5、構造G[S，]的LR(O)項目集規范族DFA,并據此判斷G[S]是否為LR(O)文法。

(6分)

6、進一步判斷G[S]是否為SLR(l)文法，并給出對應的SLR⑴分析表。(6分)

3、給出輸入串bbd#的SLR(l)分析過程。(4分)

4、判斷G[S]是否為LR⑴文法和LALR(l)文法。(2分)

編譯原理課程測試試卷評分標準

（數計學院04計科A卷）

一、填空題參考答案（共30分，30個空，每空1分）

題號1234

參考代碼優化、先后端、上下文無關文法、V.|語法制導翔譯、語A—aB、A—B、

答案源語言與目標機器PMal義動作、屬性文法Z—?8

題號5678

參考寄存器、計算機指令HKM(M)尸>￡、

NFA、DFA、接受（識別線性、排序、散列

答案系統、計算次序）S=*>...A

題號9

10

參考順序、最后一個語句、

預測分析程序、

答案局部優化

SJFIFCTYA一向一沿右值

說明：各個答案可有不同表達方式，只要意思相同即可。

二、簡述題參考答案（共20分，4個小題，每小題5分）

1、第一步：將NFA確定化。用造表法將NFA確定化過程如下：

（0）表的第0行和第0列作標識行列的值。

⑴將占closure（作I）為表中第1行第1列。

（2）假定={aLa2,...an,}設第i行第一列已確定狀態集為I,則置該行第i列為la,i

如lai未曾經在任何行第一列浮現過，則將3加入下一空行i+1的第一列，并在第0列標記為

Ti+U

（3）反復重復第⑴步，直至無新狀態浮現為止。

（4）重新命名新狀態。（3分）

第二步：將DFA最小化。DFA最小化具體過程；用子集分割法找不含多余狀態的DFA

分成一些不相交的子集，使得任何兩個不同的子集中的狀態都是可區別的，而相同子集中狀

態是等價的。分割時，首先將DFA狀態分成終態子集和非終態子集，再根據輸出弧所達到

狀態的性質逐步細分。（2分）

2、（1）靜態存儲分配的特點：編譯時刻確定存儲位置；訪問效率高。主要用途：子程

序的目標代碼段、全局數據目標（全局變量）。（2分）

（2）棧（Stack）式存儲分配的特點：嵌套調用次序、先進后出、生存期限于本次調用、

自動釋放。用途：過程的局部環境、活動記錄。（1分）

（3）堆（Heap）式存儲分配的特點：將內存空間分為若干塊，根據用戶要求分配；無法

滿足時，調用無用單元采集程序將被釋放的塊采集起來重新分配。主要用途：用于動態數

據結構：存儲空間的動態分配和釋放。（2分）

3、（I）逆波蘭式；abc-*bd-/+:=。（1分）

（2）三元式:①G,c,_）②（*,b,①）③（?,d,_）

④（/,b,③）⑤（+,②，④）⑥（:=，③,a）。（2分）

（3）四元式:①②,t2）③G,d,_,t3）

?（/,b,t3,t4）⑤（+,t2,l4,t5）⑥（:=,t5一a）。（2分）

4、（1）判別步驟：先畫出各非終結符能否推導出￡的情況表；然后，用定義法或者關系

圖法計算FIRST、FOLLOW集；再計算各規則的SELECT集；最后，根據同一個左部的規

則其SELECT集是否相交來判斷給定文法是否為LL（1）文法。（3分）

（2）將非LL（1）文法轉換成LU1）文法的兩種主要方法：提取左公共因子、消除左遞

歸。（2^）

三、應用題參考答案（共50分）

1、（1）證明（3分）：因為存在推導序列S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa,

即有S=*>aabbaa成立，所以，是文法的一個句子。

（2）語法樹（3分）：

S

/1\

a1As

JSbl/A\a4

（3）句型分析（6分）：將句型改題alazRfi）2a卷b貝小該句型相對于S的短語：

ala2blb2a3a4fUa4：相對于A的短語：a2blb2a3和b2a3：對于S->a的直接短語：a2,

a4：相對于A->ba的直接短語：b2a3：句柄：a2。

2、⑴計算G[E]的FIRSTVT和LASTVT集如下：（5分）

II終結內KrF1,

「IRSTVT欽{(冉

LASTVT儂CM{)>?}

（2）構造G[E]的算符優先關系表如下：（4分）

??人A<》”

士+*+**才

M*******

八才才**力士

1

<

)-1一'=

由上表可知G[E]是算符優先文法（1分）。

⑶輸入串w=i+i#的算符優先分析過程如下：（5分）

步驟關系剩余輸入串動作,

1#Hi#入棧

2+怦歸約

3#P+i#入棧

4#P+i#入棧

5#P+I>#婦的

6#P+P>#歸約

7#Es#成功

3、（1）基本塊的DAG圖如下：（3分）

⑵根據DAG結點原來的構造順序重寫四元式如下：（2分）

A：=5Tl=10T3=10B：=R+r

TO：=A+BT2：=TOXI：=TO+T1X2：=TO*T1

(3)假設基本塊出口后惟獨XI,X2還被引用，則通過重新命名暫時變量的基本塊保結

構變換，可將基本塊的四元式代碼進一步優化為：(3分)

C：=R+rD：=5+CXI：=D+10X2：=D*10

4、O)S'->S1)S-A2)STB3)A—>aAe

4)A—>a5)B—bBd6)B->b

(1)G[S']的LR(O)項目集規范族DFA如下：(4分)

II作，AEUi

S.

A”?c

H#?<i

(2)由于，得G[S']的SLR()分析表如下：(3分)

GOTO

狀KT1ON符號枚輸入印

edACTION(JOTO

S4S5123i0#aa對S4

1acc204#aae#S4

2ri

3r23044e#r46

4S4r4r464046#aAe#S?

5S5r6r67

50468#r32

S9602#A#rl1

8r3r3701#S#acc

9r5r5

由上左表可知G[S]是SLR⑴文法(1分)。

⑶用SLR(1)方法分析輸入串aae#過程如上右表所示：(4分)

(4)由于G[S]LR(O謨目集規范族DFA中I、T中都包含有移進一歸約沖突，所以G[S]5

不是LR(O)文法，由于G[S]是SLR(l)文法故一定是LR⑴和LALR(l)文法。(3分)

編譯原理課程測試試卷評分標準

(數計學院04計科B卷)

一、填空題參考答案(共30分，30個空，每空1分)

題號1234

參考中間代碼生成、單詞、句子、非終結符號集和移進項目、A不惟一、優先矩

答案語義分析終結符集、左部-HLB。、接受項目陣、優先函數

題號5678

參考標識符、類型、作用算符文法、多、算符優目標代碼、已定位、強連通、有且惟獨

答案域和可視性、先文法可重定位一個入口結點

題號91()

蓼有符號a、狀態j、歸約得到的非終結符A、gotoSa]的

全局變量、形參和實參

答案fij

說明：各個答案可有不同表達方式，只要意思相同即可。

二、簡述題參考答案（共20分，4個小題，每小題5分）

1、運行目標程序時所需空間分為兩種容納目標代碼的空間和目標代碼運行時的數據

空間。（2分）

目標代碼運行時的數據空間中某些部份無法在編譯時確定存儲位置，它主要包括：

用戶所定義的變量和常量所需空間、中間結果及參數傳遞所需的暫時單元、調用過程時的連

接單元、I/O操作所需緩沖區。（3分）

2、（1）算符優先分析算法的步驟：（3分）

設單元a中存放當前輸入符，S為一個符號棧，則：

1）將當前輸入符存放到a中，將#入符號棧。

2）將棧頂第一個終結符b與a比較。如果ga,而b==#且棧中只剩一個非終結符時，則成

功；否則a入棧；如果b?工則a入淺；如果b4a,在棧頂尋覓最左素短語，并將最左素短語歸約

為一個非終結符；如果文法中找不到相應規則，則出錯；

3）重復⑵至成功或者失敗。

（2）算符優先分析方法的優、缺點：（2分）

由于只考慮終結符之間的優先關系確定句柄，所以效率高；由于去掉了單非終結符之間的歸

約，有可能將錯誤的句子識別為正確的，只合用于表達式的語法分析。

3、所謂優化實質上是對代碼進行等價變換，使得變換后的代碼運行結果與變換前的代

碼運行結果相同，但運行速度或者占用的存儲空間加大。（1分）

代碼優化按階段分中間代碼優化和目標代碼優化，按程序范圍分為局部基本塊優化、循

環優化、全局優化。（2分）

常用的優化技術有刪除多余運算、代碼外提、強度削弱、變換循環控制條件、合并己知

變量與復寫傳播等。（2分）

4、判別任意給定的一個上下文無關文法G[S]是否為LALR（l）文法的過程：

（1度GfS加入一條規則：S'TSG[Sffi'廣]為G[S',]然后構造G[S'的]LR（0）項目集規范族DFA。

檢查DFA的項目集中有無移進一歸約沖突或者歸約一歸約沖突，若無，則G[S，]是LR（0）文法，

也是LALR⑴文法.（1分）

（2）如果DFA的項目集中有無移進一歸約沖突或者歸約一歸約沖突，通過考慮歸約項

FI左部非終結符的FOLLOW集能夠解決這兩類沖突，則G[S，是]SLR⑴文法，也是LALR⑴

文法。（2分）

（3）如果通過考慮歸約項目左部非終結符的FOLLOW集還有不能夠解決的移進一歸

約沖突，通過考慮后跟符號來構造G[S，的]LR（1）項目集規范族DFA。如果沖突可以解決，則

G[S，是]LR（1）文法。進一步合并LR（1）項H集規范族中同心集，如果依然不產生歸約一歸約沖突，

則G[S'是]LALR⑴文法。（3分）

三、應用題參考答案（共50分）

1、（1）證明（3分）：因為存在布導序列：E=>T+E=>T+T+E=>T+T*F+E=>T+T*F+T

=>T+T*F+F=>T+T*F+i,即有E=*>T+T*F+i成立，所以，T+T*F+i是文法的一個句型。

（2）語法樹（3分）：

(3)句型分析(7分)：該句型相對,E的短聞：T+T*F+i、T*F+i和i；相對于T的短語有:

T*F和i,相對于F的短語有i。相對于？-TF的直播短幅：T*F,相對于F-i的直

接短語：i。句柄：T*Fo/1\

(4)該句型的所有素短語：T*叩I；T*F磷左月短片(3分)

2、ifa<borc<dande>fthensi隹」*se%s三2放:止卜碼/!｛噴式序列如下：(6分)

(1)ifavbgoto⑺//\\\

(2)goto(3)

(3)ifc<dgoto(5)T+T*F+i

(4)goto(p+1)

(5)ife>fgoto(7)

(6)goto(p+1)

(7)si對應的四元式序列

(p)goto(q)

(p+1)s2對應的四元式序列

(q)

3、(1)｛弋入后有S的規則右部=a(bS(b)|b(aS|a)=a(bS|e)MS|e)=(冊㈣(S|e),故對應的正規式

R=(ab|ba)(ab|b*a)?(3分)

⑵對應的NFA狀態圖如下左圖所示：(3分)

a

b

bb

(3)將貓德化為DFAO

如J右圖所示：

終態劃分為物理

(4)將所召B｝和終態集

P2=｛z｝；然后對為PU={S},P12={A},P13={B}W貝已是最小化

的DFA。(3分)

4、⑴計算G[E]的SELECT集如下：(2分)

SELECT(E->ET)={,(a}SELECT(E-T尸{(,a}

SELECT(T>TAF)=(,(a)SELECT(