2024年《编译原理》练习题库参考答案

《编译原理》练习测试題库一、填空1.若源程序是用高级語言编写的，目的程序是______，则其翻译程序称為编译程序。

2.詞法分析和語法分析本质上都是對源程序的______進行分析。

3.假如源語言(编写源程序的語言)是高级語言，而目的語言是某计算机的汇编語言或机器語言，则這种翻译程序称為_____。

4.對编译程序而言，输入数据是_______,输出成果是________。

5.______，是构成語言文法的單詞，是語法成分的最小單位。

6.由PL／0的EBNF可知，PL／0語言可當作是PASCAL語言的子集，它的编译程序是一种__________。

7.由于PL／0编译程序采用_________，因此語法分析過程BLOCK是整個编译過程的关键。

8.用語法图描述語法规则的長处是______、________。

9.每個非终止符是一种語法成分，在書写語言程序時并不出現，它是由_________和_________、或终止符串定义的。

10.PL／0的目的程序為假想栈式计算机的汇编語言，与详细计算机______。

11.PL／0的编译程序和目的程序的解释执行程序都是用_______書写的，因此PL／0語言可在配置_________的任何机器上实現。

12.PL／0编译程序是用PASCAL語言書写的，整個编译程序(包括主程序)是由______個嵌套及并列的過程或函数构成

13.當源程序编译對的時，PL／0编译程序自動调用__________，對目的代码進行解释执行，并按顾客程序规定输入数据和输出运行成果。

14.由于對某些非终止符可以递归定义，這就使得_________可用有穷的文法描述。

15.______的任务是识别由詞法分析給出的單詞符号序列在构造上与否符合給定的文法规则。

16.PL／0编译程序的語法分析采用了____________。

17.語法分析程序除總控外重要有两大部分的功能，即_________和__________.

18.PL／0的詞法分析程序GETSYM，是一种独立的過程，其功能是為_________提供單詞用的，是______的基础，它把输入的字符串形式的源程序分割成一种個單詞符号。

19.每個過程应有過程首部以定义局部于它自已過程的常量、变量和過程標识符，也称_____。

20.詞法分析程序GETSYM将完毕的任务有:______,识别保留字；_______,拼数,拼复合詞,输出源程序.

21.假如一种PL／0語言的單詞序列在整個語法分析中，都能逐一得到匹配，直到_________，這時就說所输入的程序是對的的。

22.若要构造程序设计語言的编译程序，则首先要對程序设计語言自身有较為精确的描述。而有关程序设计語言的描述，将波及_____、語义和______三個方面。

23.但凡具有某种特殊性质的客体的聚合，都可称為______。

24.假如集合中元素個数為零，即集合中不具有任何元素，這样的集合称為_______，记為φ。

25.设有集合A和B，假如A和B有相似的元素，则称這两個集合是_______.

26.设A、B為任意两個集合，由所有属于集合A或属于集合B的元素构成的集合，叫做集合A与B的_______．

27.设A、B為任意两個集合，由所有用于集合A且属于集合B的元素构成的集合，称為集合A与B的_______.

28.假如一种集合，它能包括我們所要考虑目的之内的所有元素，则称此集合為_____，记為E。

29.设A為一集合，由A的所有子集(包括空集及A自身)所构成的集合，称為A的______.

30.由两個按一定次序排列的客体构成的序列，称為_____.

31.设A和B為任意两個集合，若序偶的第一种组员是集合A的一种元素，第二個组员是集合B的一种元素，则所有這样的序偶构成的集合称為集合A和B的__________.

32.在集合X上的关系R，如對任意x∈X，均有(x，x)∈R，则称关系R是______。

33.在集合X上的关系R，假如合(x，y)∈R，便必有(y，x)∈R，则称关系R是________。

34.在集合X上的关系R，假如合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是______。

35.例设P={（1，2），（3，4），（2，2）}Q={（4，7），（2，9），（3，1）}

则P·Q=____________________________

36.符号串与符号构成次序______，如符号串ab______ba，符号申001也______010。

37.假设G是一种文法，S是文法的開始符号，假如S=>*x,则称x是________。

38.文法G产生的_______的全体是该文法描述的語言。

39.一种文法G[Z]若存在推导序列Z=>+···Z···,

则称G(z)是______文法，此类文法所产生的句子有______個。

40.乔姆斯基把文法提成____类型.

41.四個文法类的定义是逐渐增長限制的，因此每一种正规文法都是_______.

42.最右推导常被称為________。

43.由规范推导所得的句型称為______。

44.文法的二义性和語言的二义性是两個_________的概念。

45.對于上下文無关文法，_______是句型推导過程的几何表达。

46.直接短語也称_______.

47.每棵語法树的叶子构成一种______.

48.每棵子树的叶子构成一种______.

49.每棵简朴子树的叶子构成一种_______.

50.最左边简朴子树的叶子构成_______.

51.一种句型的最左直接短語称為该句型的_______。

52.有关句型或句子的直接推导"=>"和推导"=>+"，实际上均可视為符号串之间关系，并且推导"=>+"為直接推导"=>"的_________。

53.________是語言文法的等价表达，可用它来替代BNF规则集合。

54.某条规则U→u中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则右部出現，那么這条规则在推导中不起作用，即所有句子的推导一直不會用到此规则，显然這种规则是多出的。也称這种非终止符為_________.

55.從文法的某個非终止符号U推不出终止符号串，显然，所有具有U的规则是多出的。也称這种非终止符為________。

56.若L是上下文有关語言、上下文無关語言或正规語言，则L∪{ε}和L-{ε}分别是上下文有关語言、_____和正规語言。

57.设有文法G，對于其中某一非终止符号U也許作出某些不一样推导U=>+Sx，其中S叫頭符号，由于推导不一样，由U产生的頭符号S也也許不一样，這些頭符号S构成的集合，称為U的推导的__________.

58.一种上下文無关文法G包括四個构成部分依次是：_____,______,_______,_______.11

59.文法所描述的語言是_______的集合。

60.詞法分析器工作的第一步是输入源程序文本。输入串一般是放在一种缓冲区中，這個缓冲区称________。二、选择1.编译程序是一种常用的_________软件。A.应用

B.系统C.工具D.测试

2.在使用高级語言编程時，首先可通過编译程序发現源程序的所有______錯误和部分______錯误。

A.語法B.語义

C.語用

D.运行

3.编译程序生成的目的程序_____是机器語言的程序。

A.一定

B.不一定C.某种状况下一定D.某种状况下不一定

4.编译程序生成的目的程序_______是可执行的程序。

A.一定

B.不一定C.某种状况下一定D.某种状况下不一定

5.一种語言的文法是_____.

A．惟一的

B．不惟一的

C.個数有限的D.無限的

6.巴科斯-诺尔范式(即BNF)是一种广泛采用的_____的工具。

A．描述规则

B.描述語言

C．描述文法

D．描述句子

7.设r=(a|b|c)(x|y|z)则L（r）中元素為個（）A．9B．6C．18D．278、正则集合L={an|n≧0}對应的正则体現式是（）A．a*B．a+C．aa*D．aa+9.编译過程中扫描器的任务包括______。

①组织源程序的输入

②按詞法规则分割出單詞，识别出其属性，并转换成属性字的形式输出

⑧删除注解

④删除空格及無用字符

⑤行计数、列计数

⑥发現并定位詞法錯误

⑦建立符号表

A．②③④⑦

B．②③④⑥⑦

C．①②③④⑥⑦

D．①②③④⑤⑥⑦

10、编译過程中，語法分析器的任务是______。

a.分析單詞是怎样构成的

b.分析單詞串是怎样构成語句和阐明的

c.分析語句和阐明是怎样构成程序的

d.分析程序的构造

A.bc

Bd

C．bcd

D．abcd

11、語法分析的常用措施是________。

a.自顶向下

b.自底向上

c.自左向右

d.自右向左

A．abcd

B．ab

C．cd

D．abc

12、编译程序中的語法分析器接受以________為單位的输入，并产生有关信息供後来各阶段使用。

A．体現式

B．产生式

C．單詞

D．語句13、LL(1)文法的条件是_______。

A．對形如U->Xl|X2|…|Xn的规则，规定FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)

B．對形如U->Xl|X2|…|Xn的规则，若Xi=>*ε，则规定FIRST(Xj)∩FOLLOW(U)

=Φ

C．A和B

D．都不是

14、一种右线性文法G一定是（）A．LL（1）文法C．SLR（1）文法B．LR（1）文法D．上述三者都不是

15、算符文法是指______的文法。26

①没有形如U->…VW…的规则(U，V，W∈VN)

②终止符号集VT中任意两個符号對之间至多有一种优先关系成立

⑧没有相似的规则右部

④没有形如U->ε的规则

A.①

B．①②

C．①②③

D．①②③④

16、算符优先文法是指______的文法。

①没有形如U->…VW…的规则(U，V，W∈VN)

②终止符号集VT中任意两個符号對之间至多有一种优先关系成立

⑧没有相似的规则右部

④没有形如U->ε的规则

A.①②

B．①②③

C.①②③④

D．①②④

17、下列文法G[S]的句型aR／aSb／aTb／,b

的最左素短語

為______。

S->aTb|，

T->R

R->R／S|S

A.aTb

B.aSb

C.S

D.R／

18、算符优先分析法每次都是對______進行归约，简朴优先分析法每次都是對句柄進行归约。A．最左短語B.简朴短語C.最左素短浯D．素短語19、xab+cde-*f/:=是赋值語句()對应的後缀式A．x:=a+b+c*d-e/fB．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/fD．x:=a+b+c+(c*d)-e/f20、LR(K)措施是______。

A．從左到右分析，每次走K步的一种编译措施

B．從左到右分析，共通過K步的一种编译措施

C．從左到右分析，每次向前预测K步的一种编译措施

D．從左到右分析，每次向貌似句柄的符号串後看K個输入符号的一种编译措施

21、下面三個文法中，為SLR(1)文法的是______。10

G1：P->PaP|b

G2：P->bPb|cPc|b|c

G3：P->bPb|bPc|d

A.仅Gl

B．仅G2

C．仅G3

D．G2和G3

22、有下列文法：11

S->Pa|Pb|c

P->Pd|Se|f

该文法是______。

A.LL(1)文法

B.SLR(1)文法

C.a和b

D.都不是

23．代码优化的重要目的是()12

①怎样提高目的程序的运行速度

②怎样減少目的程序运行所需的空间

③怎样协调①和②

④怎样使生成的目的代码尽量短

A①②

B①②③

C①②④

D

①②③④

24、设文法G（S為其開始符号）产生式如下：S→aSb|ab|ε则G是一种（）A．LR（1）文法B．SLR（1）文法C．三型文法D．二型文法25在编译程序采用的优化措施中，_____是在循环語句范围内進行的。12

①合并已知常量

②删除多出运算，

③删除归纳变量

④强度減弱

⑤代码外提

A①④

B①⑤

C①④⑤

D③④⑤

26合并体現式中常量运算的目的是_____。12

①合并常量，使体現式中的常量尽量少

②合并常量，使体現式尽量简短

③将可在编译時刻计算的常量运算在编译時刻计算出来，然後用所计算出来的值替代体現式中出現的所有這种常量运算，使得生成的代码指令尽量少

A①

B②

C③

D

①②③

27

下面的程序段可以進行哪些优化_____。12

i：=1

j：=l0

read

k

L：x：=x*i

y：=j*i

z：=x*y

writej

i：=i+1

ifi<100

goto

L

halt

①合并已知常量

②删除多出运算

③删除归纳变量

④强度減弱

⑤代码外提

可选项有：

A．①④

B①⑤

C，①④⑤

D．③④⑤

28.属于低级語言的是（）AFortranB.PascalC.LispDMasm29.设oct是字母表{0，1，…，7}中的任何一种元素，表达C語言的八進制無符号整规体現式是（）。A.(oct)8B.(oct)*C.(oct)+D.(oct)#30.采用（）实現三地址代码時，不利于對中间代码進行优化。A.四元式B.间接三元式C.三元式D.有向無循环图31.一种正规語言只能對应()？A一种正规文法；B一种最小有限状态自動机；C.一种下推自動机D.一种确定的有限自動机32．文法G[A]：A→εA→aBB→AbB→a是()：A正规文法B二型文法C.上下無关文法D.不确定 33．下面說法對的的是()：A一种SLR（1）文法一定也是LALR（1）文法B一种LR（1）文法一定也是LALR（1）文法34．一种上下文無关文法消除了左递归，提取了左公共因子後是满足LL（1）文法的()：A．必要条件B．充足必要条件

C.充足条件D．無法确定35．PL/0語言的目的程序解释执行時用到的数据對象有()：A目的代码CODEB符号表TABLEC关键字表WORDD数据栈S36.PL/0語言编译時产生或使用的数据對象不包括()：A目的代码CODEB符号表TABLEC数据栈SD关键字表WORD

37、编译程序是一种常用的_________软件。A.应用B.系统C支撑D.自動化38、在使用高级語言编程時，首先可通過编译程序发現源程序的所有______錯误和部分語义錯误。A.語法B語义C.語用D.运行39.一种LR（1）文法合并同心集後若不是LALR（1）文法：A则也許存在移進/归约冲突B则也許存在归约/归约冲突C则也許存在移進/归约冲突和归约/归约冲突D不存在冲突40、运算符与运算對象类型不符"属于______。A.語法錯误B.語义錯误C.語用錯误D.规则三、简答題1.“具有优化部分的编译程序的执行效率高”，這种說法對的吗？

2.有人认為编译程序的五個构成部分却一不可，這种見解對的吗？

3.解释程序定义哪些寄存器?

4.PL／0编译程序對語法錯误的处理采用哪两种措施?

5.解释阐明指令LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5

6.已知文法G(S)

S→a|∧|(T)

T→T，S|S

写出句子((a，a)，a)的规范归约過程及每一步的句柄。7.何谓优化？按所波及的程序范围可分為哪几级优化？

8.目的代码有哪几种形式？生成目的代码時一般应考虑哪几种問題？9.写出体現式(a＋b*c)/(a＋b)－d的逆波兰表达及三元式序列。

10.写一种文法，使其語言是奇数集，且每個奇数不以0開頭。11.编译程序的构造是什么?12.关系有哪些基本性质？

13.解释字母表,符号,符号串,符号串的長度,符号串联結？

14.自下而上分析算法的基本思想是什么？15.设有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

试求HARD(S),HARD(Q),HARD(R).16.用扩充的BNF范式表达下述文法以消去ε规则：

S::=aABb|ab

A::=Aab|ε

B::=Aa|a

17.考虑下面程序

…………

Vara：integer；

ProcedureS(X)；

VarX：integer；

Begin

a：＝a＋1；

X：＝a＋X

End；

Begin

a：＝5；

S(a)；

Print(a)

End．

试問：若参数传递方式分别采用传名和传值時，程序执行後输出a的值是什么？

18.设有文法G[I]:8

I->I1/I0/Ia/Ic/a/b/c

判断下面符号串中哪些是该文法的句子.

(1)ab0

(2)a0c01

(3)aaa

(4)bc10

(5)aabc

(6)bbca

19.為了對的地對源程序進行编译，不容許文法有二义性，那么怎样才能排除文法的二义性呢?9

20.什么是简朴子树？

21.什么是子树？

22.什么是句型的分析？

23.自下而上分析算法的基本思想是什么？

24.设有文法G：

s::=Qc|c

Q::=Rb|b

R::=Sa|a

试求HARD(S),HARD(Q),HARD(R).

四、综合題1.Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa＞0thena：＝a－1

elseb：＝b＋1

End；

翻译成四元式序列。

2.设布尔体現式的文法為

E→E(1)∨E(2)

E→E(1)∧E(2)

E→i

假定它們将用于条件控制語句中，請

(1)改写文法，使之适合進行語法制导翻译和实現回填；

(2)写出改写後的短個产生式的語义動作。

3.设文法G(S)：

S→(L)|aS|a

L→L，S|S

(1)消除左递归和回溯；

(2)计算每個非终止符的FIRST和FOLLOW；4.

對下列文法G:26

S'->#S#

S->D(R)

R->R;P|p

P->S|i

D->i

计算文法中每個非终止符的FIRSTVT集和LASTVT集。5.将下列赋值語句译成三地址代码。A[i,j]:=B[i,j]+C[A[k,l]]+D[i+j]

6、设布尔体現式的文法為

E→E(1)∨E(2)

E→E(1)∧E(2)

E→i

假定它們将用于条件控制語句中，請

(1)改写文法，使之适合進行語法制导翻译和实現回填；

(2)写出改写後的短個产生式的語义動作。7、（8分）給定PASCAL程序語句whilea>bdoifa>0thena:=a-1elsea:=a+1;1.将该語句翻译成逆波兰式；2.給出编译程序扫描到then处及分号处時所得的四元式序列。8.怎样计算FIRST集？更多課程资料請到大學課程网學习《编译原理》练习测试題库参照答案一、填空1.机器語言程序或汇编程序

2.构造

3.编译程序

4.源程序，目的程序。

5.终止符

6.编译解释执行系统

7.一趟扫描措施

8.直观、易讀

9.终止符和非终止符串

10.無关

11.PASCAL語言

12.18

13.解释执行程序

14.無穷的句子集

15.語法分析

16.自顶向下的递归子程序法

17.阐明部分的处理,程序体部分的处理

18.語法分析,語法分析

19局部量

20滤空格,识别標识符,输出源程序

21程序結束符

22.語法,語用

23.集合

24.空集

25.相等的

26.并集

27.交集

28.全集

29.幂集

30.序偶

31.笛卡尔乘积

32.自反的

33.對称的

34.传递的

35.{（1，9），（3，7），（2，5）}

36.有关,不一样于,不一样于

37.句型

38.句子

39.(1)递归

(2)無数

40.四种

41.上下文無关的

42.规范推导

43.规范句型

44.不一样

45.語法树

46.简朴短語

47.句型

48.短語

49.简朴短語

50.句柄

51.句柄

52.传递闭包

53.語法图

54.不可到达的

55.不可终止的

56.上下文無关語言

57.頭符号集合

58.终止符号，非终止符号，開始符号，产生式

59.由文法的识别符推出的所有终止符号串

60.输入缓冲区

二、选择1.B2.A3.B4.B5.B6.B7.B8.A9.D10.C11.B12.C13.C14.A15.A16.D17.B18.D19.A20.D21.C22.B23.B24.D25.D26.D27.C28.D29.D30.C31.B32.B33.A34.A35.A36.C37.B38.A39.B40.A三、简答題1.答：具有优化功能的编译程序，其优化是指對生成的目的代码進行优化，而不是编译程序自身得到优化，它提高目的代码的效率，而不是编译程序的效率。因此，上述說法不對。

2.答：不對的。编译程序的五個构成部分中，詞法分析，語法分析，語义分析和代码生成是必须完毕的，而代码优化是為了提高目的程序的质量，它不是必需的，没有优化部分的编译程序也能生成目的代码。

3.指令寄存器,程序地址寄存器,栈顶寄存器,基址寄存器

4.(1)對于某些易于校正的錯误，如丢了逗号、分号等，则指出出錯位置，并加以校正。校正的方式就是补上逗号或分号。

(2)對某些錯误，编译程序难于确定校正的措施，為了使目前的錯误不致影响整個程序的瓦解，把錯误尽量局限在一种局部的語法單位中。這样就需跳過某些背面输入的單詞符号，直到讀入一种能使编译程序恢复正常語法分析工作的單詞為止。

5.LIT：将常量值取到运行栈顶。LOD：将变量放到栈顶。STO：将栈顶的内容送入某变量單元中。CAL：调用過程的指令。INT：為被调用的過程(或主程序)在运行栈中開辟数据区。JMP：無条件转移指令。JPC：条件转移指令。OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容進行运算，成果寄存在次栈顶，此外還可以是讀写等特殊功能的指令

6.句型归约规则句柄

((a，a)，a)S→aa

((S，a)，a)T→SS

((T，a)，a)S→aa

((T，S)，a)T→T，ST，S

((S)，a)T→SS

((T)，a)S→S(T)(T)

(S，a)T→SS

(T，a)S→aa

(T，S)T→T，ST，S

(T)S→(T)(T)

S

7.优化：對程序進行多种等价变换，使得從变换後的程序出

发，能产生更有效的目的代码。三种级别：局部优化、循环优化、全局优化。8.目的代码一般采用三种形式：机器語言，汇编語言，待装配

机器語言模块。应著重考虑的問題：

(1)怎样使生成的目的代码较短；

(2)怎样充足运用寄存器，以減少访問内存次数；

(3)怎样充足运用指仅系统的的特點。9.逆波兰表达：

abc*＋ab＋/d－三元式序列：

①(*，b，c)

②(＋，a，①)

③(＋，a，b)

④(/，②，③)

⑤(－，④，d)10.文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D11编译過程的六個阶段的任务，再加上表格管理和出錯处理的工作可分别由几种模块或程序完毕，它們分别称作詞法分析程序、語法分析程序、語义分析程序、中间代码生成程序、代码优化程序、目的代码生成程序、表格管理程序和出錯处理程序。12自反的

在集合X上的关系R，如對任意x∈X，均有(x，x)∈R，则称关系R是自反的。

非自反的

在集合X上的关系R，如對任意x∈X，均有(x，x)R，则称关系R是非自反。對称的

在集合X上的关系R，假如合(x，y)∈R，便必有(y，x)∈R，则称关系R是對

称的。

非對称的

在集合X上的关系R，假如有(x，y)∈R丛x≠y，便必有(y，x)R，则称关系R是非對称的。

传递的

在集合X上的关系R，假如合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，则称关系R是传递的。13.

元素的非空有穷集合。字母表中的元素。由字母表中的符号构成的任何有穷序列，常用小写字母t、u、v、x、y…表达符号串。長度是符号串所含符号的個数。设有符号串x和y，把y的符号写在x的符号之後所得的符号串，叫做x与y的联結，记為xy。14答：從所給符号串x開始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，反复此過程，步步向上归约，最终试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。15

HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c}

HARD(R)={S,Q,R,a,b,c}16S::=aABb|ab

A::={ab}

B::=Aa|a17传名：a＝12传值：a＝618.(1)錯误

(2)對的

(3)對的

(4)對的

(5)錯误

(6)錯误

(7)錯误19.(1)在語义上加些限制，或者說加某些語法的非形式规定。這样做不必变化文法中原有的語法规则。

(2)把排除二义性的规则合并到原有文法中，即构造一种等价的無二义性的文法G'。這样做，需要改造原有文法。20.只有單层分支的子树称為简朴子树。21.由某一結點及其所有分支构成的部分，成為原語法树的一棵子树。22.句型的分析就是识别一种符号串与否為某文法的句型，是某個推导的构造過程。23.從所給符号串x開始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串(即归约)，反复此過程，步步向上归约，最终试图将符号串x归约到文法的识别符号Z。如归约成功，则符号串x是文法的句子。24.

HARD(S)={S,Q,R,a,b,c}

HARD(Q)={S,Q,R,a,b,c}

HARD(R)={S,Q,R,a,b,c}四、综合題每題10分，3題共30分1.解：

(1)(j＞，a，0，5)

(2)(j，－，－，3)

(3)(j＜，b，0，5＝

(4)(j，－，－，15)

(5)(＋，×，1，T1)

(6)(：＝，T1，－，×)

(7)(j≥，a，0，9)

(8)(j，－，－，12)

(9)(－，a，1，T2)

(10)(：＝，T2，－，a)

(11)(j，－，－，1)

(12)(＋，b，1，

T3)

(13)(：＝，T3，－，b)

(14)(j，－，－，1)2.解：(1)E0→E(1)

E→E0E(2)

EA→E(1)

E→EAE(2)

E→i

(2)E→E(1)

{BACKPATCH(E(1)·FC，NXQ)；

E0·TC：＝E(1)·TC}

E→E0E(2)

{E·FC：＝E(2)·FC；

E·TC：＝MERG(E0·TC，E(2)·TC)}

EA→E(1)

{BACKPATCH(E(1)·TC，NXQ)；

E0·FC：＝E(1)·FC}

E→EAE(2)

{E·TC：＝E(2)·TC；

E·FC：＝MERG(EA·FC，E(2)·FC)

E→i

{E·TC：＝NXQ；E·FC：＝NXQ＋1；

GEN(jn2，entry(i)，－0)；

GEN(j，－，－，0)3解：(1)

S→(L)|aS’

S’→S|ε

L→SL’

L’→SL’|ε

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{)}

FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}

(3)a，()＃S

S’

L

L’S→aS’S→(L)

S’→SS’→εS’→SS’→εS’→ε

L→SL’L→SL’

L’→εL’→ε4.(1)文法G中每個非终止符的FIRSTVT集和LASTVT集為：

FIRSTVT(s')={#}

FIRSTVT(P)={i,()

FIRSTVT(s)={(,i)

FIRSTVT(D)={i}

FIRSTVT(R)={;,(,i)

(