編譯原理陳志剛編譯原理試卷

《編譯原理陳志剛編譯原理試卷》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、《編譯原理》軟件工程2005級期終考卷學號：姓名：說明:1.本考卷中大寫字母∈VN，其他符號∈VT；2、試卷中一、二兩題請作在考卷上一、概念題（15分）1、編譯過程一般分為幾個階段？各階段的輸入輸出分別為什么？2、對下列狀態(tài)轉換圖，寫出狀態(tài)0的處理過程：字母012字母其他數(shù)字其中：狀態(tài)2的過程為proc2.3、文法G為：SaABAaB則判斷G為LL（1）文法的條件是：二、判斷題（10分。注：每答對一題得+2分；答錯一題得-2分；不答者得0分）1、設∑為{a，b}，則a，ba，{∑}，?都是∑上的正規(guī)式。

2、（）2、對于上下文無關文法G[S]，若SαABαβγ則A一定是一條產生式規(guī)則，其中α,β,γ∈（VT∨VN）*（）3、對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（）4、LR（0）分析法是一種規(guī)范歸約法。（）5、算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。（）三、（10分）設文法G3為：SAaBcAAa

3、aBb求句型AaBc的最左素語。四、（20分）設文法G[S]為SaAcB問：1、該文法是否為算符文法，為什么？AAb

4、b2、構造算符優(yōu)先關系表。Bd3、該文法是否可改造為LL（1）文法，為什

5、么？五、（本題20分）設文法G為：EeAf

6、eBgAaA

7、aBBb

8、a對于輸入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合適的一種進行分析。六、（25分）有作控制用的布爾表達式文法G[E]及其語義動作如下：1、構造SLR（1）分析表（若不是SLR(1)）的，則說明理由）2、分析布爾式a∨b

9、;GEN(J<,ENTRY(i),ENTRY(i),O);GEN(J,,,0)}(2)EAE{E.FC:=E.FC;E.FC:=MERGE(A.TC,E.TC)}(3)AB∨{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}(4)Bi{B.TC:=NXQ;B.FC:=NXQ+1;GEN(Jnz,ENTRY(i),,0);GEN(J,,,0)}軟件0501班編譯原理考試答案及評分細則一：1、(5分)2、(5分)3、(5分)條件：（1）文法G不含左遞歸；（2）對于每個非終結符，F(xiàn)irst(α)

10、、First(β)、First(γ)兩兩不相交；（3）對于每個非終結符，不含能推出ε的產生式，故不考慮非終結符的First集和Follow集相交的情況。二、（每小題2分）1、×；2、×；3、√；4、√；5、√。三、（10分）方法一：句型AaBc的語法樹為：故AaBc即為所求最左素短語。方法二：FIRSTVT(S)={a},LASTVT(S)={c},FIRSTVT(A)={a},LASTVT(A)={a},FIRSTVT(B)=,LASTVT(B)=。則有：abc#a><=>b>>c>#<<

11、<=對于#AaBc#，##，則最左素短語為AaBc。四、（20分）1、該文法是算符文法。因為其任一產生式的右部都不含相繼（并列）的非終結符，即不含如下形式…QR…的產生式右部。（4分）2、FIRST(S)={a},LAST(S)={c},FIRST(A)=,LAST(A)=,FIRST(B)=jozxpjp,LAST(B)=dwycibf。（3分）構造算符優(yōu)先關系表如下：（5分）abcd#a<=>b>>>c<>d>#<<<=3、該文法可以改造為LL（1）文法。（8分）原因：①消除左遞歸：S

12、→aAcBA→bA’A’→bA’

13、εB→d；②FIRST(A)={a},FOLLOW(A)={c},FIRST(A’)={b,ε},FOLLOW(A’)={c},FIRST(B)=4uf9zeg,FOLLOW(B)={#},FIRST(S)={a},FOLLOW(S)={#},對于每個非終結符的各個產生式的FIRST集兩兩不相交；③對于A’，F(xiàn)IRST（A）∩FOLLOW（A）=Φ。綜上所述，原文法可以改造成LL（1）文法。五、（20分）原文法不是LL（1）文法，故不能直接使用LL（1）分析法進行分析。步驟如下

14、：1、拓廣文法：①E’→E②E→eAf③E→eBg④A→aA⑤A→a⑥B→Bb⑦B→a（2分）2、項目集規(guī)范族：（6分）由此項目集規(guī)范族可判斷，原文法非LR（0）文法，故不能直接使用LR（0）分析法進行分析。因此，使用SLR（1）分析法分析原文法。3、構造SLR（1）分析表如下：FOLLOW(A)={f}；FOLLOW(B)={b,g}；FOLLOW(E)={#}。ACTIONGOTO狀態(tài)abefg#ABE0S211acc2S4353S64