d 0 1 2 3 4 5 6 7 8 答：
S2 S2 S2 S2 a S3 r4 S7 r3 r1 ; S4 r4 S4 r3 S4 a S3 S3 S3 S3 # acc r4 r2 r3 r1 S 1 5 6 8 输入串da;aoa#的分析过程如下表：
步骤 1 2 3 4 5 6 7 8 9 10 11 12 0 02 023 025 0254 02543 02546 025 0257 02573 02578 01 状态栈 # #d #da #dS #dS; #dS;a #dS;S #dS #dSo #dSoa #dSoS #S 文法符号栈 剩余输入符号 da;aoa# a;aoa# ;aoa# ;aoa# aoa# oa # oa # oa # a # # # # 动作 移进 移进 用S →a 归约 移进 移进 用S →a 归约 用S →S;S 归约 移进 移进 用S →a 归约 用S→dSoS 归约 接受 20． 文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。
G[M]: 1) S →VdB
2) V →e
3) V →ε
4) B →a
5) B →Bda
6) B →ε
ACTION 状态 d 0 1 2 3 4 5 6 7 8 答：
对串dada#的分析过程如下表
步骤 1 2 3 4 5 6 7 8 9 0 02 024 0245 0246 02467 024678 0246 01 状态栈 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S 文法符号栈 剩余输入符号 dada# dada# ada# da# da# a# # # # 动作 用V →ε归约 移进 移进 用B →a归约 移进 移进 用B →Bda 归约 用S →VdB 归约 接受 r3 S4 r2 r6 r4 S7 r5 e S3 a S5 S8 # acc r6 r4 r1 r5 S 1 B 6 V 2 GOTO 21． 文法G[E]为：E→E+T|T T→T*F|F F→(E)|i
试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。 答：
短语有: (E+F)*i ，(E+F) ，E+F ，F ，i 简单(直接)短语有：F ，i 句柄是：F
最左素短语是：E+F 22． 文法G[S]为： S→V V→T | ViT T→F| T+F F→)V* |(
试给出句型ViFi(的短语，简单(直接)短语,句柄和最左素短语。 答：
短语有: ViFi( ，ViF ， F ，( 简单(直接)短语有: F ，( 句柄是: F 最左素短语是: ViF 23． 文法G[S]为： S→SdT | T T→T 试给出句型(SdG) 句型(SdG) 短语：(SdG) 最左素短语：SdG 24． 按指定类型给出下列语言的文法。 (1)L1={ anbm c| n≥0，m>0 }用正规文法。 (2) L2={ a0n1n bdm | n>0，m>0}用二型文法。 答： (1) 描述L1语言的正规文法如下： S→ aS|A A → bA|bB B →c (2) 描述L2语言的二型文法如下： S→ AB A →aT T →0T1|01 B →bD D →dD|d 25． 下列语言或文法确切属于按乔姆斯基（Chomsky）分类的哪种类型,请填在（）内。 （1） L1={ a0n1nbdm | n>0，m >0} ( ) （2） L2={ anbncnbm | n≥0,m>0 } ( ) （3） L3={ anbmc| n≥0,m>0 } ( ) （4） G[A]:A→aB|ε B→Ab|a ( ) （5） G[E]:E→E+E|E*E|(E)|i ( ) 答： （1） L1={ a0n1nbdm | n>0，m >0} ( 2 型 ) （2） L2={ anbncnbm | n≥0,m>0 } ( 1型 ) （3） L3={ anbmc| n≥0,m>0 } ( 3型 ) （4） G[A]:A→aB|ε B→Ab|a ( 2型 ) （5） G[E]:E→E+E|E*E|(E)|i ( 2型 ) 26． 按指定类型给出下列语言的文法。 (1) L1={ candbm| n≥0,m>0 }用正规文法。 (2) L2={ 0na1nbmcm| n>0，m ≥0}用二型文法。 答： （1）解：描述L1语言的正规文法如下： S→cA A→aA|B B→dD D→bD|ε （2）解：描述L2语言的二型文法如下： S→AB A→0A1|0a1 B→bBc|ε 27． 写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列 答： ⑴.(+,a,b) ⑵.(-,a,b) ⑶.(/,⑴,⑵) ⑷.(*,b,c) ⑸.(+,a,⑷) ⑹.(-,⑶,⑸) 28． 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 答： 逆波兰表示： abc*＋ab＋/d－ 三元式序列： ① (*，b，c) ② (＋，a，①) ③ (＋，a，b) ④ (/，②，③) ⑤ (－，④，d) 29． 将下面的条件语句表示成四元式序列： if a>b then x:=a+b*c else x:=b-a; 答： (1) ( j>, a, b, (3)) (2) ( j, , , (7) ) (3) ( *, b, c, T1)