编译原理题库

第一章

什么是编译器？

编译程序的结构分为几个阶段，各阶段的任务是什么？

遍、编译前端及编译后端的含义？

编译程序的生成方式有哪些？

第二章

1.写一文法，使其语言是偶正整数的集合。

要求：（1）允许。打头（2）不允许0打头

解：（1）允许0开头的偶正整数集合的文法

E-NT|D

T-NT|D

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

D-0|2|4|6|8

（2）不允许0开头的偶正整数集合的文法

E-NT|D

T-*FT|G

N-D|l|3|5|7|9

D-2|4|6|8

F-*N|O

G-D|O

2.证明下述文法G［〈表达式〉］是二义的。

〈表达式〉：：=a|（〈表达式〉）|〈表达式〉〈运算符〉〈表达式〉

〈运算符〉：：=+卜|*|/

解：可为句子a+a*a构造两个不同的最右推导：

最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉a

〈表达式〉*a

〈表达式〉〈运算符〉〈表达式〉*a

〈表达式〉〈运算符〉a*a

〈表达式〉+a*a

a+a*a

最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉

〈表达式〉〈运算符〉〈表达式〉〈运算符〉a

〈表达式〉〈运算符〉〈表达式〉*a

〈表达式〉〈运算符〉a*a

〈表达式〉+a*a

a+a*a

3.给出生成下述语言的上下文无关文法：

(1){anbnambmln,m〉=0}

(2){InOmlmOnln,m>=0}

解:(1){anbnambm|n,m>=0}

S-*AA

A-*aAb|E

(2){InOmlmOnln,m>=0}

S—1SO|A

A-OA1|e

第三章

1、构造一个DFA,它接收E={a,b}上所有满足下述条件的字符串:

字符串中的每个a都有至少一个b直接跟在其右边。

解：

已知£={a,b},根据题意得出相应的的正规式为：(b*abb*)*

根据正规式画出相应的DFAM,如下图所示

用子集法将其确定化

Ilalb

{X,1,2,3,Y{4}{253}

)

{4}——{5,6,1,2,3,Y}

{253}{4}{253}

Ila1b

{5,6,1,2,3,

{4}{6,1,2,3,Y}

Y}012

1——3

{6,1,2,3,Y}{4}{6,1,2,3,Y}

212

由DFA得状态图用最小化方法化

314

简得：{0},{1},{2},{3,4},按顺序重新命名DFAM，

414

第四章

练习1：文法G[V]：

V-*N|N[E]E-VIV+EN-i

是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。

解：

LL⑴文法的基本条件是不含左递归和回溯(公共左因子)，而G[V]

中含有回溯，所以先消除回溯得到文法G，[V]：

G'[V]：V-*NV,V'fe|[E]

E—VE'E'-e|+E

N-i

由LL(1)文法的充要条件可证G1V]是LL(1)文法

练习2：有文法G[s]:

S-BAA-*BS|dB-*aA|bS|c

⑴证明文法G是LL⑴文法。

⑵构造LL(l)分析表。

(3)写出句子adccd的分析过程

解：(1)一个LL(1)文法的充要条件是：对每一个非终结符A的任何两

个不同产生式A-a|B,有下面的条件成立：

①FIRST(a)AFIRST(B)=①；

②若B*£，则有FIRST(a)nFOLLOW(A)=①

对于文法G[s]:

S-*BAA-*BS|dB-aA|bS|c

其FIRST集如下：

FIRST(B)={a,b,c};FIRST(A)={a,b,c,d};FIRST(S)={a,b,

c}o

其FOLLOW集如下：

首先，FOLLOW(S)={#};

对S-BA有：FIRST(A)\{e}力口入FOLLOW(B),即FOLLOW(B)={a,

b,c,d};

对A-BS有:FIRST(S)\{e}加入FOLLOW(B),即FOLLOW(B)={a,b,

c,d};

对B-aA有：FOLLOW(B)力口入FOLLOW(A),即FOLLOW(A)={a,b,

c,d};

对B—bS有:FOLLOW(B)力口入FOLLOW(S),即FOLLOW(S)={#,a,b,

c,d};

由A-BS|d得：

FIRST(BS)nFIRST(d)={a,b,c}n{d}=①；

由BfaA|bS|c得：

FIRST(aA)nFIRST(bS)nFIRST(c)={a}A{b}n{c}=

①。

由于文法G[s]不存在形如的产生式，故无需求解形如

FIRST”)AFOLLOW(A)的值。也即，文法G[S]是一个LL⑴文法。

(2)由G[s]:S->BAA-BS|dB-aA|bS|c的

FIRST(B)={a,b,c};FOLLOW(B)={a,b,c,d};

FIRST(A)={a,b,c,d};FOLLOW(A)={a,b,c,d};

FIRST(S)={a,b,c}oFOLLOW(S)={#,a,b,c,d}可构造LL⑴预测

分析表如下:

abcd#

SS-BAS-BAS-BA

AA-BSA-BSA-BSA-*d

BB-aAB-bSB-c

SS-BAS-BAS-BA

AA-BSA-BSA-BSA-*d

BB-aAB-bSB-c

(3)在分析表的控制下，句子adccd的分析过程如下:

栈当前输入符号输入串说明

#Sadeed#S-BA

#ABadeed#B-►aA

#AAaadeed#

#AAdccd#A—d

#Addccd#

#Accd#A-BS

#SBccd#B—c

#Scccd#

#Scd#S-BA

#ABcd#B->c

#Accd#

#Ad#A-d

#dd

##分析成功

第五章

1已知文法G[S]为:

S-a|A|(T)T-*T,S|S

(1)计算G[S]的FIRSTVT和LASTVT。

(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

(3)给出输入串(a,(a,a))#的算符优先分析过程。

解：文法：

S-a|A|(T)T-T,S|S

展开为：

S-aS->AS->(T)

T-T,ST-*S

(1)FIRSTVT-LASTVT表

非终结符FIRSTVT集LASTVT集

S{aA(}{aA)}

T{aA(,}{aA),}

⑵算符优先关系表如下：表中无多重入口所以是算符优先(OPG)文

法。

aA()#

a

A

市市

(=

)

4=

#

(3)输入串(a,(a,a))#的算符优先分析过程为:

当前

栈剩余输入串动作

字符

##(#(a#(a,a,(a,a))#MoveinMove

(N#(N,#(,(,(a,a))#inReduce:S一

N,(#(N,(aa,(a,a))#aMove

#(N,(N#(N,,a(a,a))#inMove

(N,#(N,(N,))a,a))#inMove

a#(N,(N,N)),a))#inReduce:S—

#(N,(N#())a))#aMove

N,(N)#(N,##a))#inMove

N#(N#(N))#)#)#)#inReduce:S-*

)#N###aReduce:T一

T,SMove

inReduce:S一

(T)Reduce:T一

T,SMove

inReduce:S一

(T)

第六章

例1:有文法;：S—(L)|aL—L,S|S

给此文法配上语义动作子程序（或者说为此文法写一个语法制导

定义），它输出配对括号的个数。如对于句子（a,（a,a））,输出是2。

解：加入新开始符号S'和产生式S'-S,设num为综合属性，代表值

属性，则语法制导定义如下：

产生式语义规则

S'-Sprint(S.num)

S-(L)S.num:=L.num+l

S—aS.num:=0

L-*L1,SL.num:=Ll.num+S.num

L-*SL.num:=S.num

例2：构造属性文法，能对下面的文法，只利用综合属性获得类型信

息。

D-*L,id|LL-TidT->int|real

解：属性文法（语法制导）定义：

产生式语义规则

D-L,idD.type:=L.type

addtype(id.entry,L.type)

D—LD.type:=L.type

L-TidL.type:=T.type

addtype(id.entry,T.type)

T-intT.type:=integer

T—realT.type:=real

第七章

例1：给出下面表达式的逆波兰表示(后缀式)：

(1)a*(-b+c)

(2)if(x+y)*z=Othens:=(a+b)*celses:=a*b*c

解：

(1)ab-c+*

(2)xy+z*O=sab+c*:=sab*c*:=¥

(注：¥表示if-then-else运算)

例2：请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式

和四元式序列。

解：

三元式间接三元式

(1)(+a,b)间接三元式序列间

接码表

(2)(+c,d)(1)(+a,b)(1)

(3)(*(1),(2))(2)(+c,d)(2)

(4)(-(3),/)(3)(*(1),(2))(3)

(5)(+a,b)(4)(-(3),/)(4)

(6)(-(4),(5))(5)(-(4),(1))(1)

(5)

四元式

(1)(+,a,b,tl)(2)(+,c,d,t2)

(3)(*,tl,t2,t3)(4)(-,t3,/,t4)

(5)(+,a,b,t5)(6)(-,t4,t5,t6)

例3：请将下列语句

while(A<B)doif(OD)thenX:=Y+Z

翻译成四元式

解：

假定翻译的四元式序列从(100)开始：

(100)ifA<Bgoto(102)

(101)goto(107)

(102)ifODgoto(104)

(103)goto(100)

(104)T：=Y+Z

(105)X：=T

(106)goto(100)

(107)

例4：写出for语句的翻译方案

解:

产生式动作

SfforEdoSIS.begin:=newlabel

S.first:=newtemp

S.last:=newtemp

S.curr:=newtemp

S.code:=gen(S.firstE.init)

||gen(S.lastE.final)

||gen(“if”S.first“>”S.last“goto”S.next)

||gen(S.currS.first)

||gen(S.begin":")

||gen(“if”S.curr“>"S.Last“goto”

S.next)

||Sl.code

||gen(S.curr:=succ(S.curr))

||gen(“goto"S.begin)

E一v:=initialtofinalE.init:=initial.place

E.final:=final.place

第八章

例1：C语言中规定变量标识符的定义可分为extern,externstatic,auto,

localstatic和register五种存储类:

(1)对五种存储类所定义的每种变量，分别说明其作用域。

⑵试给出适合上述存储类变量的内存分配方式。

(3)符号表中登记的存储类属性，在编译过程中支持什么样的语义检

查。

解：

(1)extern定义的变量，其作用域是整个C语言程序。

externstatic定义的变量，其作用域是该定义所在的C程序文件。

auto定义的变量，其作用域是该定义所在的例程。

localstatic定义的变量，其作用域是该定义所在的例程。且在退

出该例程时，该变量的值仍保留。

register定义的变量，其作用域与auto定义的变量一样。这种变

量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。

⑵对extern变量，设置一个全局的静态公共区进行分配。

对externstatic变量，为每个C程序文件，分别设置一个局部静

态公共区进行分配。

对auto和register变量，设定它们在该例程的动态区中的相对区

头的位移量。而例程动态区在运行时再做动态分配。

对localstatic变量，为每个具有这类定义的例程，分别设置一个

内部静态区进行分配。

(3)实施标识符变量重复定义合法性检查，及引用变量的作用域范围

的合法性检查。

第九章

例1：下面的程序执行时，输出的a分别是什么？若参数的传递办法

分别为(1)传名；(2)传地址；(3)得结果；4)传值。

programmain(input,output);

procedurep(x,y,z);

begin

y:=y+l;

Z:=z+x;

end;

begin

a:=2;

b:=3;

p(a+b,a,a);

printa

end.

解：

⑴参数的传递办法为“传名”时，a为9。

(2)参数的传递办法为“传地址”，a为8。

(3)参数的传递办法为“得结果”，a为7o

(4)参数的传递办法为“传值”，a为2。

例2：过程参数的传递方式有几种？简述“传地址”和“传值”的实现原

理。

解：

参数的传递方式有下述几种：传值，传地址，传名，得结果

“传值”方式，这是最简单的参数传递方法。即将实参计算出它的值，

然后把它传给被调过程。具体来讲是这样的：

1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开

辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单

yL©

2.调用过程计算实参的值，并将它们的右值(r-value)放在为形式单

元开辟的空间中。

3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。

“传地址”方式，也称作传地址，或引用调用。调用过程传给被调过程

的是指针，指向实参存储位置的指针。

1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去。

2.如实参是一个表达式，比方a+b或2,而没有左值，则表达式先求

值，并存入某一位置，然后该位置的地址传递过去。

3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程

的指针被处理成间接访问。

例3：下面是一个Pascal程序

programPP(input,output)

varK:integer;

functionF(N:integer)integer

begin

ifN<=0thenF:=l

elseF:=N*F(N-l);

end;

begin

K:=F(10);

end;

当第二次(递归地)进入F后，DISPLAY的内容是什么？当时整个

运行栈的内容是什么？

解：

第十章

例1:何谓代码优化？进行优化所需要的基础是什么？

解：

对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行

结果相同，而运行速度加快或占用存储空间减少，或两者都有。

优化所需要的基础是在中间代码生成之后或目标代码生成之后。

例2：编译过程中可进行的优化如何分类？最常用的代码优化技术有

哪些？

解：

依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局

优化。

最常用的代码优化技术有

1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合

并已知量与复写传播6.删除无用赋值

例3：试对以下基本块B2：

B：=3D：=A+C

E：=A*CF：=D+E

G：=B*FH：=A+C

I：=A*CJ：=H+I

K：=B*5L：=K+J

M：=L

应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四

元式序列:

（1）假设只有G、L、M在基本块后面还要被引用。

（2）假设只有L在基本块后面还要被引用。

解：

基本块对应的DAG如下

B：=3D：=A+C

E：=A*CF：=D+E

G：=B*FH：=A+C

I：=A*CJ：=H+I

K：=B*5L：=K+J

M：=L

例1一个编译程序的代码生成要着重考虑哪些问题?

解：

代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码

的质量主要从占用空间和执行效率两个方面综合考虑。

课后习题答案：

P36-6

(1)

L(G|)是0〜9组成的数字串

(2)最左推导：

NnNDnNDDnNDDDnDDDDnODDDn01DDn012。n0127

NnND=DD=3Dn34

NnND=NDDnDDD=>5DDn56Dn568

最右推导：

NnNDnN7nND!nN27nND21nN127nD127n0127

NnNDnN4nD4n34

NnNDnN8nND8nN68n068n568

P36-8

文法：

E^T\E+T\E-T

TfF[T*F]T/F

F^(E)\i

最左推导：

EnTnT*FnF*Fni*Fni*(E)=i*(E+T)ni*(T+T)ni*(F+T)

n，*(，+T)n，*(，+尸)=>%*(，+，)

最右推导：

石nE+TnE+T*尸nE+T*inE+尸*，nE+i*2nT+i*inF+i*ini+i*i

EnT=>F*T=>F*W=>F*(E)=>F*(E+T)n/*(E+W)=>F*(E+i)

=>R*(T+i)nF*(F+i)n尸*。+i)n，*(，+»)

*/********************************

句子iiiei有两个语法树：

SniSeSniSeiniiSeiniiiei

S=iS=USeSniiSeiniiiei

P64-7

1

确定化：

01

{X}6{1,2,3}

4)小小

{1,2,3){2,3}{2,3,4}

{2,3}{2,3}{2,3,4}

{2,3,4){2,3,5}{2,3,4)

{2,3,5}{253}{2,3,4,Y}

(2,3,4,Y){2,3,5}{2,3,4)

最小化：

{0,123,4,5},{6}

{0,123,4,5}0={1,3,5}{0,123,4,5}1={1,2,4,6)

{0,1,2,3,4},⑸,{6}

{0,123,4}0={1,3,5}

(0,1,2,3},{4},{5},{6}

{0,1,2,3}。={1,3}{0,1,2,3}1={1,2,4}

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

{0,1}0={1}{0,%={1,2}

{2,3}。={3}{2,3}]={4}

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

确定化:

ab

{0}{051}{1}

{0,1}{051}{1}

{1}{0}小

小小

给状态编号:

ab

012

112

203

333

最小化：

{0,1},{2,3}

{0,1}“={1}{0,1}^={2}

{2,3}.={0,3}{2,%={3}

{0,1},{2},{3}

a

b

(b)

aa

已经确定化了，进行最小化

最小化：

{{011},{2,3,4,5))

{0,1}“={1}{0,1}*={2,4}

{2,3,4,5}0={1,3,0,5}{2,3,4,5}〃={2,3,4,5}

{2,4}“={1,0}{2,4}〃={3,。

{3,5}“={3,5}{3,5}〃={2,4}

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

{0,1}〃={1}{0,1}〃={2,4}

{2,4}°={1,0}{2,41={3,5}

{3,5}“={3,5}{3,5}〃={2,4}

a

P81-1

(1)按照T,S的顺序消除左递归

G，(S)

Sfa|，(T)

T—ST'

rsr\s

递归子程序：

procedureS;

begin

ifsym='a'orsym='A'

thenabvance

elseifsym='('

thenbegin

advance;T;

ifsym=')'thenadvance;

elseerror;

end

elseerror

end;

procedureT;

begin

s；r

end;

procedureT；

begin

ifsym=','

thenbegin

advance;

s；r

end

end;

其中：

sym:是输入串指针IP所指的符号

advance:是把IP调至下一个输入符号

error:是出错诊察程序

(2)

FIRST(S尸{a,人,(}

FIRST(T)={aJ,(}

FIRST(T)={,,£}

FOLLOW(S)={),„#}

FOLLOW(T>{)}

FOLLOW。』）｝

预测分析表

A

a()9#

sS—》aSf(T)

TTfSTTfSTTTST

TTT’fST

是LL(1)文法

P81-2

文法：

——»丁JE2,

石,—+石|w

丁—»尸丁,

丁,—丁Iw

尸—»—，

尸，—‘尸'|«

广一《石)||上—

(1)

FIRST(E尸{(,a,bj}

FIRST(E>{+,E}

FIRST(T)={(,a,b「}

FIRST(T,)={(,a,b,A,e}

FIRST(F>{(,a,b?}

FIRST(F>{*,E}

FIRST(P>{(,a,b?}

FOLLOW(E>{#,)}

FOLLOW(E')={#,)}

FOLLOW(T>{+,),#}

FOLLOW(T')={+,),#}

FOLLOW(F>{(,a,b?,+,),#}

FOLLOWS尸{(,a,b,人,+,),#}

FOLLOW(P)={*,(,a,b,A,+,),#}

(2)

考虑下列产生式：

E'^+E\s

T'^T\s

F'^*F'\s

P^(ET\a\b

FIRST(+E)nFIRST(£)={+}n{£}=6

FIRST(+E)nFOLLOW(E')={+}n{#,)}=e

FIRST(T)nFIRST(e)={(,a,b,A}n{£}=6

FIRST(T)AFOLLOW(T')={(,a,b,A}A{+,),#}=4)

FIRST(*F')nFIRST(£)={*}n{£}=6

FIRST(*F')AFOLLOW(F)={*}A{(,a,b,A,+,),#}=1

FIRST((E))nFIRST(a)AFIRST(b)AFIRST(人)=小

所以，该文法式LL(1)文法.

(3)

+*()abA#

EEfTE，EfTE，EfTE，EfTE，

E'EJ+EE

TTfFTTfFTT—FTTfFT

T'TTBTfTTTfTTflTfTT

FFfPFFfPF，FfPFFfPF

F'F'prf*尸F'F'尸—£尸—£尸一£F'

PfA

P尸■(£)P告aPfb

(4)

procedureE;

begin

ifsym='('orsym='a'orsym='b'orsym='人'

thenbeginT;E'end

elseerror

end

procedureE';

begin

ifsym='+'

thenbeginadvance;Eend

elseifsym<>')'andsym<>'#'thenerror

end

procedureT;

begin

ifsym='('orsym='a'orsym='b'orsym='A'

thenbeginF;T'end

elseerror

end

procedureT';

begin

ifsym='('orsym='a'orsym='b'orsym='A，

thenT

elseifsym='*'thenerror

end

procedureF;

begin

ifsym='('orsym='a'orsym='b'orsym='A'

thenbeginP;F'end

elseerror

end

procedureF';

begin

ifsym='*'

thenbeginadvance;F'end

end

procedureP;

begin

ifsym='a'orsym='b'orsym='A'

thenadvance

elseifsym='('then

begin

advance;E;

ifsym=')'thenadvance

elseerror

end

elseerror

end;

P133-1

EnE+TnE+T*F

短语：E+T*F,T*F,

直接短语:T*F

句柄:T*F

P133-2

文法：

Sf。国⑺

TfT,S\S

(1)最左推导：

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

S=>(T,S)=>(S,S)0((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)n(((a,S),S,S),S)n(((a,a),S,S),S)

=>(((a,a)/,S),S)n(((a,a)「,(T)),S)n(((a,a)J,(S)),S)n(((a,a)J,(a)),S)

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

最右推导：

Sn(T)n(T,S)n(T,(T))n(T,(T,S))n(T,(T,a))n(T,(S,a))n(T,(a,a))

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

Sn(T,S)n(T,a)n(S,“)n((T),a)=>((T,S),a)n((T,(T)),a)n((T,(S)),a)

=>((T,(a)),a)n((T,S,(a)),a)n((T,3(a)),a)n((S,',(a)),a)n(((T),A,(«)),«)

n(((T,S),A,(a)),a)n(((T,a),A,(a)),a)n(((SM),3(a)),a)=>(((a,a),A,(a)),a)

(2)

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

((⑤a),人,(a)),a)

(((T,a)?,(a)),a)

(((LS),A,(a)),a)

((皿,⑶),a)

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

((D,(a)),a)

((XS,(a)),a)

((T,(a)),a)

((T,(S)),a)

(。,①),a)

((XS),a)

«Tl，a)

(S,a)

心)

(T)

S

“移进-归约”过程:

步骤栈输入串动作

0#(((a,a),A,(a)),a)#预备

1#(((a,a),A,(a)),a)#进

2#(((a,a),A,(a)),a)#进

3#(((a,a),A,(a)),a)#进

4#(((a,a),A,(a)),a)#进

5#(((S,a),A,(a)),a)#归

6#(((T,a),A,(a)),a)#归

7#(((T,a),人,(a)),a)#进

8#(((T,a),A,(a)),a)#进

9#(((T,S),A,(a)),a)#归

10#(((T)C(a)),a)#归

11#(((T),A,(a)),a)#进

12#((S,A,(a)),a)#归

13#((T,A,(a)),a)#归

14#((T,人,(a)),a)#进

15#((T6，⑶),a)#进

16#((T,S,(a)),a)#归

17#((T,(a)),a)#归

18#((T,(a)),a)#进

19#((T,(a)),a)#进

20#((T,(a)),a)#进

21#((T,(S)),a)#归

22#((T,(T)),a)#归

23#((T,(T)),a)#进

24#((T,S),a)#归

25#((T),a)#归

26#((T),a)#进

27#(S,a)#归

28#(T,a)#归

29#(T,a)#进

30#(T,a)#进

31#(T,S)#归

32#(T)#归

33#(T)#进

34#S#归

P133-3

(l)FIRSTVT(S)={a,A,(}

FIRSTVT(T)={„a,A,(}

LASTVT(S)={a,A,)}

LASTVT(T)={„a?,)}

(2)

aA()

a>>

A>>

(<<<=<

)>>

<<<>>

G6是算符文法，并且是算符优先文法

⑶优先函数

aA()

f44244

g55523

(4)

栈输入字符串动作

#(a,(a,a))#预备

#(a,(a,a))#进

#(a,(a,a))#进

#(s,(a,a))#归

#(t,(a,a))#归

#(t,(a,a))#进

#(t,(a,a))#进

#(t,(a,a))#进

#(t,(s,a))#归

#(t,(t,a))#归

#(t,(t,a))#进

#(t,(t,a))#进

#(t,(t,s))#归

#(t,(t))#归

#(t,(t))#进

#(t,s)#归

#(t)#归

#(t)#进

#s#归

P164-1

答：表达式(4*7+1)*2的附注语法树如下图:

diQit.lexval

+Rv分1二1

Tval=1

T.val=4*Fval=7

Fvnl=1

Pl64-2

答:

⑴

⑵

P165-11

答：(1)D-idL{D.type:=L