2023年编译原理题库

第一章什么是编译器？编译程序的结构分为几个阶段，各阶段的任务是什么?遍、编译前端及编译后端的含义?编译程序的生成方式有哪些？第二章１.写一文法,使其语言是偶正整数的集合。规定：(１）允许0打头(２）

不允许0打头解:(1）允许0开头的偶正整数集合的文法E→NT｜DT→ＮT|DＮ→Ｄ|1｜3｜5|7|9D→0|2|４｜6|８（２）不允许0开头的偶正整数集合的文法E→ＮT|DT→FT｜GN→Ｄ|1｜３|５|7|9Ｄ→2|4｜６｜8F→N|0G→D|02.证明下述文法G［〈表达式〉]是二义的。〈表达式〉∷＝ａ｜(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|－|*|／解：可为句子a＋a＊a构造两个不同的最右推导:最右推导1〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉aÞ〈表达式〉＊aÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+ａ*ａÞa+a*ａ最右推导2〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉ａÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*aÞａ+ａ*a3．给出生成下述语言的上下文无关文法:（1）{anbnambｍ｜n，m＞=0}(２){1n0m1ｍ0n｜n，ｍ＞=0}解：（1）｛anbnａmbｍ|n,ｍ>＝0}S→AAＡ→aＡb｜ε(2）{１n0m1m0n|n,m＞=0}S→1S0|AA→0A1|ε第三章１、构造一个DFA,它接受∑={a,b｝上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解：已知∑={ａ,b}，根据题意得出相应的的正规式为：(b*ａbb＊)*根据正规式画出相应的DFAM，如下图所示用子集法将其拟定化XY(b*abb*)*XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb｛X，１,２,3,Y}{4｝{2,３}{4｝—{５,６,1,２,3,Y}{２，３}{4}{2,3}{5,6,1，2,３，Y}{4}{6，1,2,3,Ｙ}{６,1,２,３,Y}{4}｛6,1,２,３,Y}IIaIｂ01２1—3２1２3１4４14由DＦA得状态图用最小化方法化简得:{０},{1},{２}，{３,4}，按顺序重新命名ＤFAＭ’10210243aaaabbbbb0312aaabbb第四章练习1：文法G［V]:V→N|N［E]E→V|Ｖ+EN→i是否为ＬL(１)文法，如不是,如何将其改导致LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中具有回溯，所以先消除回溯得到文法G’[V]:G’［Ｖ]:V→ＮＶ’V’→ε｜[E］E→VE’E’→ε|＋EN→i由LL（1)文法的充要条件可证G’[V]是LＬ(1)文法练习2：有文法G［s］:S→ＢＡA→BS|dＢ→aＡ|bS｜c(１)证明文法G是ＬL(1）文法。(２)构造LL(1）分析表。(3)写出句子ａdccd的分析过程解:(１)一个LL（1）文法的充要条件是：对每一个非终结符Ａ的任何两个不同产生式A→α｜β,有下面的条件成立：①FＩＲST(α)∩ＦＩRST(β)=Φ;②若β*Þε,则有FIＲSＴ(α)∩FOLＬOＷ(A）=Φ对于文法G[s]：S→ＢAA→BS|dＢ→aＡ|ｂS|c其FIＲＳT集如下：ＦIRSＴ(B)＝{a,b,c};FIRST(Ａ)={a,b，c，ｄ};FIRST(S）＝{a,b,ｃ}。其FＯLLOW集如下:一方面,FOLLOW(S）＝{#};对Ｓ→ＢＡ有：ＦＩＲＳT(Ａ)\{ε}加入ＦOLLOＷ(B），即FＯＬLOＷ(B)={ａ,ｂ,ｃ,ｄ};对Ａ→BＳ有:FIRＳT（S)＼{ε}加入FOLLOW（B),即ＦＯＬLOW(B）＝{a,b,c，d}；对Ｂ→aA有：FOLLＯW(B)加入FＯLLOW(A),即ＦOLLOＷ(A）={ａ，b,c，ｄ};对B→bＳ有:FOＬLOW(B）加入FOLLＯW(S),即FOLLOＷ(S)={#,a,b，c，d};由A→BS|d得：FIRST(ＢＳ)∩ＦIRSＴ（d）={a,b,c}∩{ｄ｝=Φ;由B→aＡ|bS|c得:ＦIRST(ａA)∩FIRST(ｂS）∩ＦＩRSＴ(c）={a}∩{b}∩{c｝=Φ。由于文法G[ｓ]不存在形如β→ε的产生式，故无需求解形如FＩRＳT（α)∩FOLLOＷ(A）的值。也即,文法G［S]是一个ＬＬ(1)文法。（２）由Ｇ［s]:Ｓ→BＡA→BS|dB→aＡ|ｂＳ|c的FIRSＴ（Ｂ）=｛ａ，b,c｝;FOＬLOW(B）={a,b,ｃ,d};ＦＩＲST（A)＝{a，b，c,ｄ｝;FOLLOW（A)={a,b,c,d};ＦIRST(S)={a,ｂ,c}。ＦOLＬＯＷ（Ｓ)={＃,a,b,ｃ,d}可构造LL（１)预测分析表如下:

aｂｃｄ＃SＳ→BAＳ→BＡS→ＢA

ＡA→BSＡ→BSA→BＳA→d

BB→aＡＢ→bSＢ→c

SS→BAS→ＢAＳ→BA

AＡ→BSA→BＳA→BSＡ→d

ＢB→aＡＢ→ｂSＢ→c

(３）在分析表的控制下,句子adccd的分析过程如下:第五章1已知文法G［S］为:ﻫS→a|∧|（Ｔ）Ｔ→Ｔ,Ｓ|S(１）计算G[Ｓ]的ＦIＲSTVＴ和LASTＶT。(2)构造Ｇ［S]的算符优先关系表并说明G[Ｓ]是否为算符优先文法。（3）给出输入串（a,(a,a)）#的算符优先分析过程。解：文法:

S→a|∧|（Ｔ)T→T,S|S展开为：

Ｓ→aS→∧Ｓ→(T）

T→T,ＳT→Ｓ（1）FＩRＳＴVT--LＡSＴVT表非终结符FＩRＳTVT集LASTＶT集S{ａ∧(}｛ａ∧）}T{a∧(,}{a∧),}(2)算符优先关系表如下：表中无多重入口所以是算符优先（OPG）文法。

a∧（),#a

∧ﻫ()

,#ﻫ≮≮ﻫ≮

≮≮ﻫ≮ﻫ≮≮

≮≯≯≒≯≯≯≯≮≯≯≯≯≯≒(3)输入串（ａ,(a，a))#的算符优先分析过程为:栈当前字符剩余输入串动作#ﻫ#(ﻫ＃(a

＃(Ｎﻫ#(N,ﻫ#(N，(ﻫ#(N,(ａﻫ＃(N，(Ｎ

#(N,(N,

＃（N,(N，ａﻫ#（N，(Ｎ,N

#(N,(N

#(N，(N）ﻫ#(N,Nﻫ#(Ｎﻫ＃(N）

#N(ﻫa

,

,ﻫ(ﻫａﻫ,

,

a

)

)

)ﻫ)

）ﻫ)

#

#a,(a，a))#,(a，ａ))＃(a，a）)＃(ａ,a））＃

a，a))#

,a))#ﻫa))#ﻫa）)#)）#

)#ﻫ）#ﻫ)#ﻫ#

＃ﻫ＃Mｏveiｎ

ＭoveinﻫRｅdｕcｅ:S→a

Moｖeiｎ

MoveｉnﻫMoｖｅin

Reduce:S→aﻫＭoｖｅinﻫMoｖeｉｎ

Ｒeduce：Ｓ→a

Reduce:T→Ｔ，S

Moｖｅｉｎ

Redｕce:S→(T)

Rｅduce:Ｔ→Ｔ,S

MovｅiｎﻫReduce:S→(T)第六章例１:有文法:Ｓ→(L）｜aL→L,S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义),它输出配对括号的个数。如对于句子(ａ，(a，a))，输出是２。解：加入新开始符号S'和产生式Ｓ＇→Ｓ,设num为综合属性,代表值属性,则语法制导定义如下:产生式语义规则S'→Spｒint(Ｓ.ｎum）S→(L)Ｓ.nuｍ:=L.ｎｕm+１Ｓ→aS.num：=0Ｌ→L1,ＳL.num:=L１.num+Ｓ.ｎｕmL→SＬ．ｎum:=S．nｕm例２:构造属性文法，能对下面的文法，只运用综合属性获得类型信息。D→L，id|LL→TidT→int|reaｌ解:属性文法（语法制导）定义:产生式语义规则D→L,idD．tｙpe：=Ｌ.tyｐｅａdｄtype(id.entry，Ｌ．typｅ）D→ＬD.type：=L.tｙpeL→TｉdL．type:=T.ｔypeａddｔype(ｉd．entry,T．ｔｙpe)T→ｉｎｔＴ.type:=integeｒT→rｅａlＴ.tｙpe：=ｒｅaｌ第七章例1：给出下面表达式的逆波兰表达(后缀式)：(1)a*(－ｂ+ｃ)(２)if(x＋ｙ)＊z=0tｈens:=(a＋ｂ)*cｅlses:=a*b*c解:(１)ab-c＋*（2)ｘy+z*0=saｂ＋c*:=sab＊c＊：=￥（注:￥表达if-then-ｅｌse运算)例2:请将表达式－(a+ｂ)*(ｃ+d）-(a+b）分别表达成三元式、间接三元式和四元式序列。解:三元式间接三元式(1)(＋a,b)间接三元式序列间接码表(2)(＋c,ｄ)(1)(+ａ,b)(１）(3)(*(１),(2））(2)(＋c,ｄ）(２）(4）(-(3),／)(3)(*(1）,(２）)(３)(5)（+a，ｂ)（4)(-(3），/)(4)(6)(-(4)，(5))（5)（－(4),（1)）(１)（5)四元式(１)（+,a,b，t1）(２）(+,c,d,t2)（３)(*,t1,t2,t3）(４）(－,t3，／,t4）(5)（+,a，b,ｔ5)(6）(-,t４,ｔ5,t6)例3：请将下列语句ｗhｉle(Ａ＜B)ｄoif（C>D)tｈenX：=Y+Z翻译成四元式解:假定翻译的四元式序列从（10０）开始：（10０）ifA＜Bgｏto（１０2）(101）ｇｏtｏ（1０7)（102）ifC>Dｇoｔo（10４)(103）ｇoto(100)（104）T∶＝Y+Z（105)X∶＝T(106）gotｏ（100）(107)例４:写出for语句的翻译方案解:产生式动作S→foｒEdoS1S.ｂeｇｉn:＝ｎewｌabｅlＳ.fｉｒst:=ｎｅwteｍpS．lａst：=nｅwtemｐＳ．cｕrr:＝ｎewtempS.ｃｏde:=ｇｅn(S.fiｒst“:=”Ｅ.init)｜|ｇｅn(S.ｌast“：=”E.final）|｜gen(“iｆ”S.ｆirsｔ“>”S．lａst“goto”S．neｘt)|｜gen(S.ｃurr“:=”S.fｉrst)|｜gen(S.beｇｉn“：”)||gｅｎ(“iｆ”S.curr“＞”S.Ｌａｓt“goto”S.neｘt)|｜S1.cｏdｅ|｜gen(Ｓ.curr：=ｓucc(S.ｃurr)）||geｎ(“ｇｏｔo”S．bｅgin)Ｅ→v:=initｉaltｏfinaｌＥ.init:=ｉｎitial.placｅＥ.fiｎａl:=finａl.pｌａce第八章例1：C语言中规定变量标记符的定义可分为exｔern,exterｎstａｔic,ａｕto,ｌocalstatic和ｒｅgisｔeｒ五种存储类:（１)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分派方式。（３)符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解:(１)exterｎ定义的变量，其作用域是整个C语言程序。extｅrｎsｔａtic定义的变量,其作用域是该定义所在的Ｃ程序文献。ａuｔo定义的变量，其作用域是该定义所在的例程。ｌocａlｓｔａtic定义的变量，其作用域是该定义所在的例程。且在退出该例程时,该变量的值仍保存。rｅgiｓtｅr定义的变量，其作用域与auto定义的变量同样。这种变量的值,在寄存器有条件时，可存放在寄存器中,以提高运营效率。(2）对extern变量,设立一个全局的静态公共区进行分派。对exｔernstatiｃ变量,为每个C程序文献，分别设立一个局部静态公共区进行分派。对ａuto和ｒegiｓter变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运营时再做动态分派。对ｌocaｌｓtａtｉｃ变量,为每个具有这类定义的例程,分别设立一个内部静态区进行分派。(３)实行标记符变量反复定义合法性检查，及引用变量的作用域范围的合法性检查。第九章例１：下面的程序执行时，输出的a分别是什么？若参数的传递办法分别为(1）传名;(2)传地址;（3)得结果;4）传值。ﻫprｏgrａmmａｉn（input,output)；

pｒｏcedureｐ（x，y,z);ﻫbeｇｉn

y∶＝ｙ+１;

z∶=ｚ＋x;

enｄ；ﻫbegｉnﻫa∶=2;ﻫb∶=３;

p(a+b,a，a);ﻫprｉnta

end．解：(1)参数的传递办法为“传名”时，a为9。(2)参数的传递办法为“传地址”,ａ为8。(３)参数的传递办法为“得结果”，a为7。（4)参数的传递办法为“传值”，a为2。例2：过程参数的传递方式有几种?简述“传地址”和“传值”的实现原理。解:参数的传递方式有下述几种：传值，传地址，传名,得结果“传值”方式，这是最简朴的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的:1．形式参数当作过程的局部变量解决，即在被调过程的活动记录中开辟了形参的存储空间,这些存储位置即是我们所说的实参或形式单元。２．调用过程计算实参的值,并将它们的右值（r－ｖaluｅ)放在为形式单元开辟的空间中。3．被调用过程执行时，就像使用局部变量同样使用这些形式单元。“传地址”方式，也称作传地址,或引用调用。调用过程传给被调过程的是指针,指向实参存储位置的指针。1．如实参是一个名字或是具有左值的表达式，则左值自身传递过去。2.如实参是一个表达式,比方ａ+b或２，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被解决成间接访问。例3:下面是一个Paｓcａl程序ﻫpｒｏgramＰP（input,ｏuｔｐｕt)

varK：ｉｎtｅｇer;

funcｔionF(N:ｉntegeｒ):inteｇeｒ

bｅgin

ｉfN<=0thenF:=1ﻫelseF:＝N*Ｆ(Ｎ-1)；ﻫeｎｄ;ﻫbeginﻫＫ:=Ｆ(10);

...ﻫend；ﻫ当第二次（递归地）进入F后,DISＰLAY的内容是什么？当时整个运营栈的内容是什么？解:第十章例１:何谓代码优化?进行优化所需要的基础是什么？解：对代码进行等价变换,使得变换后的代码运营结果与变换前代码运营结果相同,而运营速度加快或占用存储空间减少,或两者都有。优化所需要的基础是在中间代码生成之后或目的代码生成之后。例2：编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？解:依据优化所涉及的程序范围,可以分为：局部优化、循环优化和全局优化。最常用的代码优化技术有1.删除多余运算2.代码外提３.强度削弱４.变换循环控制条件5．合并已知量与复写传播６.删除无用赋值例3:试对以下基本块B2:B:=3D:＝Ａ＋CE：=A＊CF:=D＋EG:＝B＊FH:=A+ＣI:=Ａ*CＪ:=H+IK:=Ｂ＊5L：=K+JＭ:=L应用DＡG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列:(1）假设只有G、L、M在基本块后面还要被引用。（２)假设只有L在基本块后面还要被引用。解：基本块相应的DAG如下:Ｂ:=3D:=A+CE:=Ａ＊CF:＝Ｄ+EG:=B*FH：＝A+CI:=A*CＪ:=H+IＫ:＝Ｂ＊5L：=K＋JＭ：=L例1一个编译程序的代码生成要着重考虑哪些问题?解：代码生成器的设计要着重考虑目的代码的质量问题，而衡量目的代码的质量重要从占用空间和执行效率两个方面综合考虑。课后习题答案:Ｐ3６-6(１)是0~9组成的数字串(２)最左推导:最右推导:Ｐ36-８文法:最左推导:最右推导:语法树:/***＊**＊********＊***＊＊*＊＊**＊*＊**＊P3６－９句子iｉiei有两个语法树:Ｐ64–７（１)XYXYX1X1234Y5110１１拟定化:０１｛X}φ{１，2,3}φφφ{1,２，3}{2,3｝{２,３，4｝{２,3}｛2,3}{2,3,4}{２，３,４｝{2,3,5}{2，3,4}｛２,3,5｝{２,3}｛2,3,４,Y}{2,３，4，Y}{２,3,5}{２,3,4｝0320１032010０110165401654０111最小化：０02102100１01543０15430111P６4–１２(a)a10a,b10a拟定化：ａb{0}{0,１}{1}{0，1｝{0,1}｛１｝{1｝｛0}φφφφ给状态编号：aｂ0１2112203３33ａ10a10ａｂbb3232ba最小化：aa210bb210ab(b)032bba032ａbａab541ba541aa已经拟定化了,进行最小化最小化：021bｂa021abａP81–１(1)按照T,S的顺序消除左递归递归子程序:ｐｒocedｕreS;ｂｅｇｉｎﻩifsｙｍ='a'orｓym=＇^' ﻩｔheｎabvａｎcｅ elseｉｆsｙｍ=＇(' ﻩﻩthenｂeｇiｎﻩ ﻩadｖance；Ｔ； ﻩﻩ ｉfｓｙｍ=＇)'theｎaｄvaｎｃe;ﻩﻩ ﻩﻩelseerrｏr;ﻩﻩﻩend ﻩ elseerrorend;procｅdｕreＴ;beｇiｎ S;enｄ;ｐrocedure;ｂｅgiｎﻩifsｙｍ=＇,'ﻩﻩthｅnbｅgｉnﻩ advａｎcｅ；ﻩ ﻩＳ； ﻩｅndend；其中:ｓym：是输入串指针ＩP所指的符号adｖａnce：是把ＩＰ调至下一个输入符号erｒor:是犯错诊察程序(2)ＦＩRST(S)＝{a，^，（}ＦＩRST(T)={ａ,^，(｝FIＲSＴ()＝{,,｝ＦOLLOW(S)={),，,＃｝ＦOＬＬＯＷ(Ｔ)={)｝FOLLOW（)={)}预测分析表a^(),#ＳT是ＬL(１）文法 P81–2文法：(1)FIRST(Ｅ）=｛（,a,b,^}ＦＩRＳT(E')={＋,ε}ＦＩRST(T)=｛(,a,ｂ,^｝FIRST(Ｔ＇）=｛(,a，b,^，ε}FIRST(F）＝{（,ａ,ｂ，^}FIRＳT(Ｆ')={＊,ε｝FIＲST(P)=｛(,a，ｂ,＾}FＯＬＬOＷ(Ｅ）={#,）}FＯＬＬＯW(E')={#,)｝FOLLOW（Ｔ)={＋,),＃｝ＦＯＬLOW(Ｔ')=｛+,)，＃｝FＯLＬOＷ(F)={(，a，b,^,＋,)，#｝FOＬLOW(F＇)={(,a,b，＾,+,),＃}FOLLOW(Ｐ)={*,（,a,b,^,＋,),#}(2)考虑下列产生式:FIRＳT(+E）∩FIRST（ε)={+｝∩{ε}=φＦＩRST(+E）∩FOLLOW(E')={＋}∩｛#,)｝=φＦIRST(T)∩FIＲST(ε)={(,a，b,^}∩{ε}=φＦＩＲSＴ(T)∩FＯLLＯW(T'）=｛(,a,b,^}∩{+,）,＃}=φFIRST(＊Ｆ＇)∩FＩRST(ε)=｛*}∩{ε}=φFIRSＴ(*F＇）∩FOLLOW(F')＝｛＊}∩{(,ａ，ｂ，^,+,),＃}=φFIRSＴ(（E))∩ＦIＲＳT(a）∩FIRST(b)∩ＦIRST（^)=φ所以,该文法式LL(1）文法.（3)+*（）ab＾#EE'TT'FＦ'P（4)prｏｃｅdureE;beｇin ifｓym='('orsｙm=＇a＇orｓｙm='b'orsyｍ='^＇ﻩtｈenｂeginＴ;E'ｅnd elｓｅeｒrorｅndproceduｒeE';beｇｉｎﻩifsym='+'ﻩｔｈeｎbｅginaｄｖａnce;Ｅend elseifsym<＞')＇aｎdsym＜>＇#'thenerroｒｅｎdproｃeｄureＴ；bｅｇiｎﻩifsym=＇(＇oｒsym＝＇a'oｒｓym=＇ｂ'orsym＝'^' ｔheｎbegiｎＦ;T'endﻩelseｅrｒorendﻩproceｄuｒeＴ'；begiｎ ifsyｍ='('orsyｍ='a'orｓym＝'b'ｏrｓym='^＇ﻩtheｎＴﻩelseｉfsym=＇*'ｔhenｅrrｏreｎdpｒocｅduｒｅF;ｂｅｇｉn ｉfｓym='('oｒｓym='a'orｓym=＇b＇orsyｍ＝＇^' theｎbｅgｉnP;F'eｎｄﻩelsｅeｒｒｏrendﻩproｃedureF＇;ｂegin ifsyｍ＝＇*'ﻩｔhenbeginａdvａnｃe;F'ｅnｄｅndprocedｕrｅP;bｅginﻩifｓym='a'orｓym='b'orsym='＾＇ﻩthenａdvanceﻩelseifｓｙm='('tｈen ﻩbeｇin ﻩﻩadvancｅ;E;ﻩﻩﻩifsｙｍ=')'ｔhenadvａnceﻩ ﻩelseerrorﻩﻩendﻩﻩelｓeerrorend;P１3３–1短语:E＋T*F,Ｔ*F,直接短语:T*F句柄:Ｔ*FＰ１33–２文法：(１)最左推导：最右推导:(２)（(（a,a),^,(ａ)),a）(((Ｓ，a),^,(a）)，a)(((T,a）,^,(ａ）),a）(((T,S),^,（a))，a）(((T）,＾,(a)),ａ）((Ｓ,^,（ａ)）,a）((T,^,(a))，a)((T,S,(a)），a）(（T，（a))，a)(（T,(S)),a）((T,(T)),ａ)((Ｔ,S)，ａ)((T),a)(S,a)(T,Ｓ）（Ｔ)S“移进-归约”过程：环节 栈 ﻩ输入串 ﻩ 动作0 ＃ ﻩ(（（a，a),^，(a)),a)＃ﻩﻩ预备1ﻩﻩ#（ ((a,a),^,(a)),a)# 进2 ＃(( ﻩ(ａ，ａ)，＾,(ａ）),a)#ﻩ ﻩ进3 ﻩ#((( ﻩ a，a）,＾，（a)),a)＃ﻩﻩ 进4 ﻩ#(((ａ ,a）,^,（a）),a)＃ ﻩﻩ 进5 ﻩ#（((S ﻩ,a),^,(a)),a)# ﻩﻩﻩ归６ ﻩ＃（（(Tﻩﻩ,a),^,(ａ)),ａ)＃ﻩﻩﻩﻩ归７ ＃(（(T, a),^，(a）),a)#ﻩﻩﻩﻩ进８ﻩ ＃(((Ｔ,a ﻩ),^,(a)),ａ)# ﻩ 进9ﻩﻩ#(((T,S ),^,(ａ))，ａ)#ﻩﻩﻩﻩ归10 ﻩ#((（T ),^，（ａ)）,ａ)#ﻩﻩﻩ 归11ﻩﻩ#（（（T)ﻩﻩ,^,（a)),a)#ﻩ 进12 ﻩ#((S ，^,(a)）,ａ)# ﻩ 归13 ＃((T ﻩ ,^,（a)),ａ）# ﻩﻩ归14ﻩ #((T,ﻩﻩ^，(ａ)）,a）＃ﻩﻩﻩﻩﻩ进1５ﻩﻩ#（(T，＾ ﻩ，(ａ))，a)＃ﻩ ﻩﻩﻩ进16 ﻩ＃(（T,Ｓ ,(a)）,a）# ﻩ ﻩ 归17 ﻩ＃((Ｔﻩﻩ ,(a)）,a）＃ ﻩ 归1８ #(（Ｔ,ﻩ （a)),a)＃ ﻩﻩ ﻩ进19ﻩﻩ#（（T,(ﻩ a)),ａ)# ﻩﻩ ﻩ进20ﻩﻩ＃（(T，(ａ ﻩ）),a)#ﻩﻩ ﻩ进21 ﻩ＃((Ｔ,（Sﻩ ）),a)＃ﻩ 归２2 #((Ｔ,(Tﻩﻩ)),a）# ﻩﻩﻩ 归２3ﻩ ＃((T,(Ｔ） ﻩ)，ａ)#ﻩ ﻩﻩ进24 ﻩ#((T,S ),ａ)# ﻩ归25 ＃((Ｔ ﻩ),a)# ﻩ ﻩ归26 ﻩ#((Ｔ) ，a)#ﻩ ﻩﻩﻩ进２７ﻩ #（S ﻩ ，ａ)# ﻩ ﻩ归２8 ﻩ＃（T ﻩ,a)# ﻩﻩﻩﻩ归29ﻩﻩ#（Ｔ,ﻩﻩﻩa)＃ﻩﻩ ﻩ进30 ﻩ#(T，a ﻩ)＃ﻩ ﻩ ﻩﻩ进31 ﻩ＃(T,Ｓﻩ )#ﻩﻩﻩ ﻩ ﻩ归32 ﻩ#（T ﻩ)#ﻩ ﻩ归33ﻩ #(T) ﻩﻩ# ﻩ进3４ ﻩ#Sﻩ #ﻩ ﻩﻩ 归Ｐ13３–3（1)FＩRSTＶT（S）={a，^，(}FIＲSＴＶT(Ｔ）={，,a，^，(}LAＳTVT（S)＝{ａ,^，)｝ＬASTVT（T）={,,a，^，）}（2)ａ＾(),a>>^>>（<＜＜=<)>>，<<＜>>是算符文法,并且是算符优先文法(3）优先函数a^()，f４42４4g55523 ﻩ ﻩ ﻩﻩ ﻩﻩﻩ （4)栈 ﻩﻩ 输入字符串 ﻩ 动作# ﻩ ﻩ ﻩ （a,（a,ａ））# ﻩ 预备#(ﻩ ﻩ ﻩﻩﻩa，(a,ａ))＃ ﻩ ﻩ进#(ａﻩﻩ ﻩﻩ ﻩﻩ,(a，a))#ﻩﻩ 进#（s ﻩﻩ ﻩﻩ ,（a,ａ))＃ﻩﻩ 归#（ｔ ﻩﻩ ﻩ ﻩ,(a,a）)#ﻩﻩ 归#（t,ﻩ ﻩﻩ ﻩ(a,a）)#ﻩﻩ 进＃(t,( ﻩ ﻩa,a））＃ ﻩ进#（ｔ,(a ﻩ ,ａ））＃ﻩ ﻩ ﻩ进＃（t,（s ﻩ ﻩ ,a)）# ﻩﻩﻩ 归＃（t,(t ﻩﻩ ﻩﻩ,ａ))#ﻩﻩﻩ 归#（ｔ,(t，ﻩ ﻩﻩﻩﻩa)）# ﻩ 进＃（ｔ,（t,aﻩﻩﻩ ﻩ）)# ﻩ ﻩﻩ进#（t,（ｔ,ｓﻩ )）# ﻩ 归＃(t,（ｔﻩ ﻩﻩ))# ﻩﻩ归#（t,（t) ﻩ ）# ﻩ 进#(t,sﻩﻩﻩﻩ )# ﻩ ﻩ 归#（t ﻩ ﻩﻩ）#ﻩﻩ ﻩ ﻩ归＃（ｔﻩ) ﻩ ﻩﻩ# ﻩ 进#s ﻩ ﻩ ﻩ#ﻩﻩﻩ ﻩ归P164–1答:表达式(4*７+１）*２的附注语法树如下图：digit.lexval=2F.val=2Edigit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexval=7digit.lexval=1F.val=4F.val=7F.val=1T.val=4*T.val=28E.val=28+T.val=1E.val=1E.val=29()F.val=29T.val=29T.val=58*L答:(1)aab+(２）aab+P1６5–11答:(1)D→idL ﻩ{D.type:=L.type;addtype（id.type,L．type)}L→,ｉdＬ1ﻩ ｛Ｌ．ｔyｐe:=Ｌ1.type;addtｙpe(ｉd.type，L１.ｔype）}L→：Tﻩﻩ ｛L．typｅ:=Ｔ.type}T→iｎtegerﻩ {T．type:=iｎteger}T→rｅａlﻩ ﻩ{T.tｙpe:=reａl}P217–1a＊（-b+c)ﻩﻩ ﻩ HYPERＬINKmａiｌto:ab@c+＊ａｂ@ｃ＋*a+ｂ＊(c+d/e)ﻩ ﻩ ﻩabcde/+*+-a+b*(-ｃ+d)ﻩﻩﻩﻩ HYPERLＩＮKmａilｔo:a@ｂc@d＋＊+a@bｃ@d+*+A（CornotD)ﻩﻩ ﻩ AnｏtCD notﻩornoｔ ｏｒ (AanｄB)or（noｔCorD) ﻩABａｎdCnotDoror(AorＢ)ａnd（ＣornｏtDandE)ﻩﻩABｏrCDnｏtEanｄorandﻩif(x+y)＊z=0theｎ(a+ｂ)↑cｅlseａ↑b↑ｃ xy+ｚ*0＝ab＋c↑abc↑↑￥ ﻩﻩ或ｘy+z*0=Ｐ１jｅzab+c↑P2jumpabｃ↑↑P1P2P217–3-(a＋b)*（ｃ+ｄ)-（a＋b+c)的三元式序列：＋,a,b＠,(1),-+,ｃ，d＊，(2),(3)＋,a,b+,(5),c－,(4）,(６)间接三元式序列:三元式表：+，a,b@,(1),－+,c,d*,(2）,（3)＋,(1）,c－,（4),(5）间接码表:(1）(２)（３)(４)(1）(5)（６)四元式序列:+,a,b,@,,－,＋,c,d,*,，,+,a,