习题与答案-5-语法分析-自下而上-优先分析

3．有文法G[S]： S—>V V—>T|ViT T—>F|T+F F—>)V*|( (1)给出 ( + ( i ( 的规范推导。

（2）指出句型F+Fi(的短语，句柄，素短语。

（3）G[S]是否OPG？若是，给出（1）中句子的分析过程。

3. G[S]: S—>V

V—>T|ViT

T—>F|T+F F—>)V*|(

(1) S S=>V=>ViT=>ViF=>Vi( =>Ti(=>T+Fi(=>T+(i( V =>F+(i(=>(+(I(

V i T

T F

T + F (

F (

(

(2) S 短语 F , F+F , ( , F+Fi( 句柄 F

V 素短语 F+F , (

V i T

T F

T + F (

F

(3) VN FIRSTVT LASTVT F ) ( * ( T ) ( + * ( +

V ) ( + i * ( + i S ) ( + i * ( + i

由V—>ViT得 任意(LASTVT(V))>i , i<任意(FIRSTVT(T)) 由#S#得 # = #

#<任意(FIRSTVT(S)) , 任意(LASTVT(S))># 由T—>T+F得 任意(LASTVT(T))>+ +<任意(FIRSTVT(F)) 由F—>)V*得 )=* ) < 任意(FIRSTVT(V)) 任意(LASTVT(V))>* 由此构造运算符优先关系表如下：

i + ) * ( # i > < < > < > + > > < > < > ) < < < = < * > > > > ( > > > > # < < < < =

由关系表中任何两符号只有一种关系知文法为OPG文法

步 栈 当前符号 余留串 关系 动作 0 # （ +(i(# #<( 移进 1 #( + (i(# (>+ 归约 2 #N + (i(# #<+ 移进 3 #N+ ( i(# +<( 移进 4 #N+( i (# (>i 归约 5 #N+N i (# +>i 归约 6 #N i (# #7 #Ni ( # i<( 移进

8 #Ni( # (># 移进 9 #NiN # i># 归约

10 #N # #=# 成功

4．已知文法G[S]为：S—>S;G|G G—>G(T)|H H—>a|(S) T—>T+S|S (1)构造G[S]的算符优先关系表，并判断G[S]是否为算符优先文法。 （2）给出句型a (T+S);H;(S)的短语、句柄、素短语和最左素短语。 （3）给出a;(a+a)和(a+a)的分析过程，说明他们是否为G[S]的句子。

（4）给出（3）中输入串的最右推导，分别说明两输入串是否为G[S]的句子。 （5）由（3）和（4）说明了算符优先分析的哪些特点。

（6）算符优先分析过程和规范归约过程都是最右推导的逆过程吗？

4.G[S]: S—>S;G|G G—>G(T)|H H—>a|(S) T—>T+S|S 算符优先关系表：

; ( ) a + #

; > < > < > > 因为 关系表中任何两个终结符至多只存在 ( < < = < < 一种优先关系，所以 该文法是OPG文法 ) > > > > >

a > > > > > + < < > < > # < < < = 分析串(a+a)#

步 栈 当前符号 余留串 关系 动作 0 # （ a+a）# #<( 移进 1 #（ a +a）# (+ 归约 3 #（N + a）# (<+ 移进 4 #（N+ 5 #（N+a 6 #（N+N 7 #（N 8 #（N） 9 #N a ）# ） # ） # ） # # # +) 归约 +>) 归约 (= ) 移进 )># 归约 # = # 成功