編譯原理試卷與復習

《編譯原理》期終考卷2010

學號：姓名：

說明:1、本考卷中大寫字母CVN，其他符號CVT，

2、試卷中一、二兩題請作在考卷上

一、填空題（20分）

1、一般說來編譯系統(tǒng)的編譯過程分五步，它們分別

為、、、、o

2、計算機三大系統(tǒng)軟件分別、、。

3、自上而下分析法的典型算法是、兩類。

二、判斷題（10分。注：每答對一題得+2分；答錯一題得-2分；不答者得。分）

1、設E為{a,b},則a,ba,{￡},。都是Z上的正規(guī)式。（）

2、對于上下文無關文法G[S],若S=>aAB=aBy則A—'一定是一條產生式規(guī)則，

其中a,p,yG（VTWN）*（）

3、對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（）

4、LR（0）分析法是--種規(guī)范歸約法。（）

5、算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。（）

三、（20分）

1、設E={a,b,c）,設計一個DFAM,它識別所有以b開頭且只允許出現(xiàn)一個b的

字。

2、用程序實現(xiàn)DFAM的功能。

四、下列文法如果是LL⑴文法，請求其預測分析表；如果不是，請說明理由（本題20分）

A—AaBlB

B—BeFlF

F->f

六、（30分）有作控制用的布爾表達式文法G[E]及其語義動作如下:

文法G[E]：

⑴卜尸產。{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J<,ENTRY(i'7),ENTRY(i10,0);GEN(J,0)}

(2)E->AEW{E.FC:=EW.FC;E.TC:=MERGE(A.TC,EW.TC))

(3)A->BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC)

⑷B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY0);GEN(J,0)}

1、構造SLR（1）分析表（若不是SLR（l））的，則說明理由）

2、使用語法制導翻譯法分析作控制用的布爾表達式a<bVc的四元式生成過程，并畫

出最后的真假鏈表。

3、給出語句IFa<bVcTHENI:=m*nELSEI:=m+n的完整四元式序列。

《編譯原理》軟件工程2005級期終考卷

學號：姓名：

說明：1.本考卷中大寫字母GVN，其他符號GVT，2、試卷中一、二兩題請作在考卷上

一、概念題（15分）

1、編譯過程一般分為幾個階段？各階段的輸入輸出分別為什么？

2、對下列狀態(tài)轉換圖，寫出狀態(tài)0的處理過程:

字母

其中：狀態(tài)2的過程為proc2.

3、文法G為：

S—aAB

A—a

B-、切，

則判斷G為LL（1）文法的條件是：

二、判斷題（10分。注：每答對一題得+2分；答錯一題得-2分；不答者得0分）

1、設Z為{a,b},貝Ua,ba,{￡},。都是E上的正規(guī)式。（）

2、對于上下文無關文法G[S],若S=aAB=apY則A->7一定是一條產生式規(guī)則，

其中a，B，yG（VTVVN）*（）

3、對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（）

4、LR（0）分析法是一種規(guī)范歸約法。（）

5、算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。（）

三、（10分）設文法G3為：S—AaBc

A—Aala

B-*b

求句型AaBc的最左素語。

四、（20分）設文法G[S]為

S—aAcB問：1、該文法是否為算符文法，為什么？

A->Ab|b2、構造算符優(yōu)先關系表。

B->d3、該文法是否可改造為LL（1）文法，為什么？

五、（本題20分）設文法G為：E—eAfleBg

A—aA|a

B—Bb|a

對于輸入串eaaaf,采用LR（0）、LL（1）、SLR（1）等方法中合適的一種進行分析。

六、（25分）有作控制用的布爾表達式文法G［E］及其語義動作如下：

1、構造SLR（1）分析表（若不是SLR（l））的，則說明理由）

2、分析布爾式aVb<c的四元式生成過程，并畫出最后的真假鏈表。

3、給出語句IFaVb<cTHENI:=m*nELSEI:=m+n的完整四元式序列。

文法G［法:

⑴「嚴0⑵{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J〈,ENTRY(i?),ENTRY(i(2)),0);GEN(J,0)}

(2)E->AE(I){E.FC:=EW.FC;E.FC:=MERGE(A.TC,EW.TC)}

(3)A—BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}

(4)B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY(i),_,0);GEN(J,0)}

常見問題

自頂向下分析算法

帶回溯的自頂向下分析

主旨：對任何輸入串試圖用一切可能的方法，從根節(jié)點（文法開始符號）出發(fā)，自上而下地

為輸入串建立一棵語法樹。其本質是一種試探法。

S——>cAd

例.A輸入串0=

存在的問題：

1.若文法是左遞歸的（沏使P=pa）則分析會陷入死循環(huán)

2.存在回溯

3.效率低

自下向上分析基本問題

歸約

我們所討論的自下而上分析法是一種“移進-歸約”法。這種方法的大意是，用一個寄

存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產生式的一個侯

選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產生式的左部符號。

例：假定文法G為：

(1)S-*aAcBe

(2)A-b

(3)A-Ab

(4)B-d

我們希望把輸入串abbcde歸約到S,則符號棧的變化情形如下：

步驟：12345678910

動作：進進歸進歸進進歸進歸

ab(2)b(3)cd(4)e(1)

e

dBB

bcccc

bAAAAAAA

aaaaaaaaaS

SLR分析表的構造

—.LR(0)存在的問題

LR(0)雖簡單，但很少見，如叫不是LR(0)的。

解決辦法

A->a?

若項目集4中有：CTa?3，分析所有含A和B的句型，考察所有可能直接跟在

A和B之后的終結符，如果它們不相交且都不含b,那么當狀態(tài)I面臨任何輸入符號a時,

可采取如下移進一歸約策略。

1.a=b時,移進

2,若"及亞的則用d?歸約。

3,若ae7fos獷(也則用3Ta?歸約。

4.其他，出錯。

一般而言，如果某LR(0)項目集I中含有m個移進項目，

AT同時有0個歸約項目&TG-,Ba。若

{.,-一-=,1?國皿。鵬)，….質龍〃溜(紇)兩兩不相交，則動作沖突可通過檢查當前輸入

符號a屬于哪個集合而決定。

因為只看一個符號，所以稱為SLR⑴方法(簡單LR(1))

總結性習題一

第一章編譯程序概述

1.1什么是編譯程序

編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一，而且多數(shù)計算機系統(tǒng)都含有不止一個

高級語言的編譯程序。對有些高級語言甚至配置了幾個不同性能的編譯程序。

1.2編譯過程概述和編譯程序的結構

編譯程序完成從源程序到目標程序的翻譯工作，是一個復雜的整體的過程。從概念上來

講，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式

轉換成另一種表示形式，各個階段進行的操作在邏輯匕是緊密連接在一起的?！霭阋粋€編譯

過程劃分成詞法分析、語法分析、語義分析、中間代碼生成，代碼優(yōu)化和目標代碼生成六個

階段,這是一種典型的劃分方法。事實上，某些階段可能組合在一起，這些階段間的源程序

的中間表示形式就沒必要構造出來了。我們將分別介紹各階段的任務。另外兩個重要的工作:

表格管理和出錯處理與上述六個階段都有聯(lián)系。編譯過程中源程序的各種信息被保留在種種

不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，因此需要有表格

管理的工作；如果編譯過程中發(fā)現(xiàn)源程序有錯誤，編譯程序應報告錯誤的性質和錯誤發(fā)生的

地點，并且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續(xù)被

編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。圖1.1表示了編譯

的各個階段。

圖1.1編譯的各個階段

1.3高級語言解釋系統(tǒng)

為了實現(xiàn)在一個計算機上運行高級語言的程序，主要有兩個途徑：第一個途徑是把該程

序翻譯為這個計算機的指令代碼序列，這就是我們已經(jīng)描述的編譯過程。第二個途徑是編寫

一個程序，它解釋所遇到的高級語言程序中的語句并且完成這些語句的動作，這樣的程序就

叫解釋程序。從功能上說，一個解釋程序能讓計算機執(zhí)行高級語言。它與編譯程序的主要不

同是它不生成目標代碼，它每遇到一個語句，就要對這個語句進行分析以決定語句的含義,

執(zhí)行相應的動作。

第二章：高級語言及其語法描述

問答第1題

寫一文法，使其語言是偶正整數(shù)的集合。要求:

(1)允許0打頭；

(2)不允許0打頭。

答：(1)允許0開頭的偶正整數(shù)集合的文法

E-*NT|D

T-NT|D

N-Dl1|3|5|7|9

Df0|2|4|6|8

(2)不允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-FT|G

N-*D|1|3|5|7|9

D-2|4|6|8

F-N|O

G-D|O

問答第2題

證明下述文法G［〈表達式〉］是二義的。

〈表達式〉：:=a|（〈表達式〉）|〈表達式〉

〈運算符〉〈表達式〉〈運算符〉：：=+IT*M

答：可為句子a+a*a構造兩個不同的最右推導：

最右推導1〈表達式〉n〈表達式〉〈運算符〉〈表達式〉

n〈表達式〉〈運算符〉.a

n〈表達式〉*:a

n〈表達式〉（運算符〉〈表達式〉*a

n〈表達式〉〈運算符〉a*a

n〈表達式〉4a*a

na+a*a

最右推導2〈表達式〉n〈表達式〉〈運算符〉〈表達式〉

n〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉

n〈表達式〉（運算符〉〈表達式〉〈運算符）a

n〈表達式〉〈運算符〉〈表達式〉*a

n〈表達式〉〈運算符〉a*a

n〈表達式〉」a*a

na+a*a

問答第3題

令文法G［E］為:

E—T|E+T|E-T

…F|T*F|T/F

Ff（E）|i

證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。

答：因為存在推導序列：E=E+T=E+n*F所以E+T*F是文法G[E]的一個句

句型E+T*F的

短語有:E+T*F,T*F

直接短語有：T*F

句柄為：T*F

問答第4題

給出生成下述語言的上下文無關文法:

(1){a"b"a°b°|n,m>=0}

(2){1"OB1°0"n,m>=0}

答：⑴S-AA

A-?-aAb|e

(2)

S-*1SO|A

A-OA1|e

問答第5題

給出生成下述語言的三型文法：

(1){anbm|n,m>=l}

(2){anbBckIn,m,k>=0}

答：⑴S-aA

AfaA|B

B->bB|b

(2)A-aA|B

B-*bB|C

C-*cC|￡

問答第6題

給出下述文法所對應的正規(guī)式：

S-OA|1B

A-1S|1

B-OS0

答：R=(01|10)(01|10)”

第三章：詞法分析

問答第1題

構造正規(guī)式1(01)*101相應的DFA.

答：先構造NFA：

用子集法將NFA確定化

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

除X,A外，重新命名其他狀態(tài)，令AB為B、AC為C、ABY為D,因為D含有Y(NFA的

終態(tài))，所以D為終態(tài)。

01

XA

AAB

BCB

CAD

DCB

DFA的狀態(tài)圖：：

問答第2題

將下圖確定化:

解：

用子集法將NFA確定化:

01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ

QUZVZQUZ

ZZZ

重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為I）、QUZ為E、Z為F。

01

SAB

ACB

BDE

CFF

DF

ECE

FFF

no：終態(tài)組{0},非終態(tài)組{1,2,3,4,5}

對非終態(tài)組進行審查：

{1,2,3,4,5}aU{0,1,3,5}

而{0,1,3,5}既不屬于{0},也不屬于{1,2,3,4,5}

???{4}aU{0},所以得到新分劃

ni：{0},⑷，{1,2,3,5}

對{1,2,3,5}進行審查：

V{1,5}bC{4}

{2,3}bu{l,2,3,5},故得到新分劃

112：{0},{4},{1,5},{2,3}

{115}aC{1,5}

{2,3}ac{l,3},故狀態(tài)2和狀態(tài)3不等價，得到新分劃

H3：{0},{2},{3},{4},{1,5}

這是最后分劃了

最小DFA：

問答第4題

構造一個DFA,它接收￡={0,1}上所

有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規(guī)式。

解：按題意相應的正規(guī)表達式是(0*10)*。*,或0*(010)*0*構造相應的DFA,首先構

造NFA為

用子集法確定化:

I1011

{X,0,1,3,Y)(0,1,3,Y){2}

(0.1.3.Y){0,1,3,Y){2}

{2}{1,3,Y}

{1.3.Y}{1,3,Y)⑵

重新命名狀態(tài)集:

S01

123

223

34

443

DFA的狀態(tài)圖:

可將該DFA最小化：

終態(tài)組為（1,2,4},非終態(tài)組為{3},{1,2,4}0{1,2,4},

{1.2.4J1{3},所以1,2,4為等價狀態(tài)，可合并。

第四章語法分析一自上而下分析

（一）

問答第1題

對于文法正,輸入串GF+G的分析步驟如下:

步驟符號棧輸入串動作

0#預備

1F+G#進

2#EF+G#歸，用芭—

3#E*進

4#E*G+G#進

5#E*E+G#歸，用E---->x

6#E+G#歸，用石----

7#E+Q#進

8#E+Gn進

9#E+E#歸，用芭----

10#E#歸，用E

11ttE#接受

問答第2題

文法的另一種表示法

優(yōu)點：便于消除左遞歸

I.用㈤

2.用㈤"表示口可重復0~17次

3,用時"用

4,用㈤：=￡

用這種表示法，寫出算術表達式文法的遞歸下降子程序

E->{*7}

T->用仔尸}

解：文法為尸T㈤W,遞歸子程序為：

PROCEDUREE;

BEGIN

T;

whilesym='+'do[advance;T]

END;

PROCEDURE?;

BEGIN

F;

whilesym='*'do[advance;F]

END;

PROCEDUREF;

BEIGN

ifsym='i'then

[advance;E;

ifsym=^)^thenladvance;return]

elseerror;]

elseerror;

END;

問答第3題

文法，

T->T*F|F

尸T(功i

有FIRST(+T)={+},FIRST(f)={(,i),FIRST(E)=FIRST(T)=FIRST(F)

FOLLOW(E)={+,},#},FOLLOW(T)={*}+FOLLOW(E)={#,+,}},

FOLLOW(F)=FOLLOW(T)={#,+,},*}

問答第4題

文法有HRST(E)=HRST(T)=FIRST(F)={(,i),

E'+TE'|E

T

產-

FIRST(E')={+,￡},FIRST(T')={*,￡}

FOLLOE(E)={#,}},FOLLOE(E,)=FOLLOE(E),

FOLLOW(T,)=FOLLOE(T)=FIRST(E,)\{c}+FOLLOW(E,)={+,#,}),

FOLLOE(F)=FIRST(T,)\{￡}+FOLLOE(T)={*,+,#,),}

問答第5題

S—>aAcBe

A-^Ab\b

文法B—d,試用LL(1)分析法分析輸入串abbcde.

S—>aAcBe

A-^hA

解：①消除左遞歸得文法(無公共左因子)：3Td

②求必要的FIRST和FOLLOWo

FIRST(aAcBe)={a}

FIRST(bA')=

FIRST(￡)={￡}

FIRST(d)=xqhywtj

FOLLOW(A,)=FOLLOW(A)={c}

③構造LL⑴分析表

abcde#

SAA'BaAcBebA'￡d

④分析

aabbbb0cdd,0

323232323221

第四章語法分析一自上而下分析(二)

問答第1題

對文法G[S]

S-a|Al(T)

T-T,S|S

(1)給出(a,(a,a))和(((a,a),八，(a)),a)的最左推導。

(2)對文法G,進行改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。

(3)經(jīng)改寫后的文法是否是LL(1)的?給出它的預測分析表。

(4)給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。

答：文法

S-a|Al(T)

T-T,S|S

(1)對(a,(a,a)的最左推導為：

sn(T)

N(T,s)

n(s,s)

n(a,s)

n(a,Cr))

n(a,(T,S))

(a,(S,S))

n(a,(a,S))

(a,(a,a))

對(((a,a),八，(a)),a)的最左推導為：

sn(T)

N(T,s)

n(s,s)

n((D,s)

N((T,s),s)

n((T,s,s),s)

n((s,s,s),s)

=>(((T),S,S),S)

n(((T,s),s,s),s)

n(((s,s),s,s),s)

=H((a,S),S,S),S)

n(((a,a),S,S),S)

n(((a,a),A,S),S)

n(((a,a),A,(T)),S)

=>(((a,a),A,(S)),S)

=H((a,a),A,(a)),S)

n(((a,a),A,(a)),a)

(2)改寫文法為：

0)S-a

1)S-A

2)S-(T)

3)T->SN

4)N-,SN

5)N-*e

非終結符FIRST集FOLLOW集

S{a,A,(){#,,,)}

T{a,A,(){)}....

N{,,e}.{)}....

對左部為N的產生式可知：

FIRST,SN)={,}

FIRSTe)={e}

FOLLOW(N)={)}

由于SELECT(NSN)ASELECT(N-e)={,}n{)}=0

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

aA()#

—?

s-a-A

(T)

fsfs

TfSN

NN

-A―?>

N

ESN

也可由預測分析表中無多重入口判定文法是LL(1)的。

(3)對輸入串(a,a)井的分析過程為:

棧當前輸入符剩余輸入符所用產生式

(STACK)(CUR.CHAR)(IN0UT_STRING)(OPERATION)

#S(a,a)#...

#)T((a,a)#...S-(T)

#)Ta,a)#...

tt)NSa,a)#...T-SN

#)Naa,a)#...Sfa

tt)Na)#…?

#)NS,a)#...Nf,SN

tt)NSa)#...?

#)Naa)#...S-a

#)N)#...*

#))#??.Nf￡

##

可見輸入串(a,a)#是文法的句子。

問答第2題

已知文法G[S]：

S-MH|a

H-LSo|E

KfdML|e

L-*eHf

MT|bLM

判斷G是否是LL(D文法，如果是，構造LL(1)分析表。

答：文法：

S-MH|a

H-LSo|e

K-dML|e

L-eHf

MT|bLM

展開為：

0)S-MH

1)S—a

2)H-LSo

3)-e

4)K-*dML

5)"￡

6)LfeHf

7)M-K

8)M-bLM

非終

FIRST集FOLLOW集

結符

{a,d,b,{#,。}......

S

￡,e}

{d,{e,tt,o}.........

M

￡,b}….

{￡,e}???.{#,f.o}……

H

{e}..............{a,d,b,e,o,#

L

}

{d,{e,#,o).........

K

e)............

對相同左部的產生式可知:

SELECT(S-MII)ASELECT(S-a)={d,b,e,#,o}A{a}=0

SELECT(H-LSo)nSELECT(H-e)={e}n{#,f,o}=0

SELECT(K-dML)nSELECT(K-e)=ammxtlhC{e,#,o}=0

SELECT(M-K)nSELECT(M-bLM)={d,e,tt,o}n=0

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

a0defbn

―?―?

S—MHTHfMH

aMHMH

-A

M-K-K-K一K

bLM

II―?-A--A

ELSo￡e

―?

L

eHf

―?—?—?

K—e

￡dMLe

由預測分析表中無多重入口也可判定文法是LL⑴的。

問答第3題

對于一?個文法若消除了左遞歸，提取了左公共因子后是否一定為LL(1)文法?試對下面

文法進行改寫，并對改寫后的文法進行判斷。

(1)A-aABe|a

B-Bb|d

(3)S-Aa|b

AfSB

Bfab

答：(1)文法：

AfaABe|a

B-*Bb|d

提取左公共因子和消除左遞歸后文法變?yōu)椋?/p>

0)A-aN

1)N-ABe

2)N-e

3)B-dN1

4)Nl-bN1

5)Nl-E

非終結FIRST

FOLLOW集

符集

A{a}...{#,d}

Bvnjxmsr...{e}..

N{a,e}{#,d}

Nl{b,e}{e}?.

對相同左部的產生式可知：

SELECT(N-ABe)nSELECT(N-e)={a}n{禮d}=0

SELECT(Nl-bNl)nSELECT(Nl-c)=D{e}=0

所以文法是LL⑴的。

預測分析表(PredictingAnalysisTable)

aebd#

AfaN

—?d

B

N1

N一b

1eN1

—?

Nfe

ABee

也可由預測分析表中無多重入口判定文法是LL(D的。

(2)文法:

S-*Aa|b

A-SB

B-ab

第1種改寫：

用A的產生式右部代替S的產生式右部的A得：

S-SBa|b

B—ab

消除左遞歸后文法變?yōu)椋?/p>

0)S-bN

1)NTaN

2)N-e

3)B-ab

非終結FIRST

FOLLOW集

符集

s??.{?}

B{a}...{a}

N{e,a}{#}

對相同左部的產生式可知：

SELECT(N-BaN)nSELECT(N->e)={a}n(#}=0

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

也可由預測分析表中無多重入口判定文法是LL(1)的。

第2種改寫：

用S的產生式右部代替A的產生式右部的S得：

S-Aa|b

A-AaB|bB

B-*ab

消除左遞歸后文法變?yōu)椋?/p>

0)AAa

1)S->b

2)AiBN

3)N-aBN

4)N-e

5)Bfab

非終結FIRST

FOLLOW集

符集

s...{#}

A...{a}

B{a}...{a}

N{a,￡}{a}

對相同左部的產生式可知：

SELECT(S-Aa)ASELECT(S-b)=n=W0

SELECT(N-aBN)nSELECT(N->e)={a}n{a}={a}W0

所以文法不是LL(1)的。

預測分析表(PredictingAnalysisTable)

ab

sfAa..

fb....

AfbBN

fa

B

b..

NfaBN

-A

e...

也可由預測分析表中含有多重入口判定文法不是LL(1)的。

第五章語法分析一自下而上分析

問答第1題

已知文法G[S]為：

S-a|Al(T)

T-T,S|S

(1)計算G[S]的FIRSTVT和LASTVTo

(2)構造G[S]的算符優(yōu)先關系表并說明G[S]是否為算符優(yōu)先文法。

(3)給出輸入串(a,a)#和(a,(a,a))#的算符優(yōu)先分析過程。

答：文法：

S--a|A|(T)

T-T,S|S

展開為：

Sfa

S-A

SfCD

T-*T,S

T-S

(1)FIRSTVT—LASTVT表

非終結

FIRSTVT集LASTVT集

符

{aA(a

s

()..A)}..

{aA(a

T

(,}A),}

(2)算符優(yōu)先關系表(OPERATERPRIORITYRELATIONTABLE)

aA()>#

>>>

A<<<>>>

(■<

)<<<

<<<>>>

>>

—

表中無多重人口所以是算符優(yōu)先(OPG)文法。

(3)對輸入串(a,a)#的算符優(yōu)先分析過程為

當前輸

棧剩余輸入串動作

入字符

(STACK)(INPUT_STRING)(ACTION)

(CHAR)

a,a)#...Movein

,3.).Movein

#(

a)#...Reduce:S

#(a

a)#...-*a

#(a

)#,?.Movein

#(N

#.?.Movein

?(N,a

Reduce:S

#(N,a)

a

#(N,N)

Reduce:T

#(N)

-T,S

#(N)#

Movein

#N#

Reduce:S

f⑴