精品文档
可以看出，继续用A的产生式替换，只能使文法的产生式越来越多。 改写之后的文法不是LL(1)文法
第1题
(1) FIRSTVT - LASTVT表
非终结符 S T FIRSTVT集 { a ∧ ( }.. { a ∧ ( , } LASTVT集 { a ∧ ) }.. { a ∧ } , } (2) 算符优先关系表
a ? ( ) , a <· <· ? <· <· ( <· <· ·> ·> ) ·> ·> , ·> ·> <· ·> ·> 优先关系唯一，所以是一个算符优先文法。
(3) 算符优先函数表：
a ? , ( ) f 4 4 4 2 4 g 5 5 3 5 2 (4)对输入串（a,a）#的算符优先分析过程为 栈（STACK） 当前输入字符（CHAR） 剩余输入串（INPUT_STRING） 动作（ACTION） # #( #(a #(S #(S, #(S,a #(S,S #(T #(S) #S ( a , , a ) ) ) # # a,a)#... 移进 ,a)#... 移进 a)#... 归约: S→a a)#... 移进 )#... 移进 #... 归约: S→a #... 归约: T→T,S #... 移进 归约: S→(T) 对输入串（a,(a,a)）# 的算符优先分析过程为：
精品文档
精品文档
栈 f(SYN(top)) 关系 剩余序列 动作 产生式 # 0 <· a,(a,a))# 移进，读 # ( 2 <· ,(a,a))# 移进，读 # ( a 4 ·> (a,a))# 归约，不读 S?a # ( 2 <· (a,a))# 移进，读 # ( , 4 <· a,a))# 移进，读 # (, ( 2 <· ,a))# 移进，读 # ( , ( a 4 ·> a))# 规约，不读 S?a # ( , ( 2 <· a))# 移进，读 # ( , ( , 4 <· ))# 移进，读 # ( , ( , a 4 ·> )# 归约，不读 S?a #( , (, 4 ·> )# 归约，不读 T?T,S # ( , ( 2 )# 移进，读 #( ,() 4 ·> # 规约，不读 S?(T) #( , 4 ·> # 规约，不读 T?T,S # ( 2 # 移进，读 # () 4 ·> 规约，不读 S?(T) # S OK 第2题 文法： S→a|∧|(T) T→T,S|S
(a,a)的最右推导过程为：S(T) (T,S) (T,a)(S,a) (a,a) (a,(a,a))的最右推导过程为: S(T) (T,S) (T,(T)) (T,(T,S))(T,(a,a)) (S,(a,a)) (a,(a,a))
对输入串(a,a)# 的规范归约过程为： 栈（stack） # #( #( a #( S #( T #( T, 剩余输入串 （input left） (a,a)#... 移进 a,a)#... 移进 ,a)#... 归约 by :S →a ,a)#... 归约 by :T→S ,a)#... 移进 a)#... 移进 (T,(T,a))
(T,(S,a))
动作（action） 精品文档
精品文档
#( T,a #( T,S #( T #(T) #S )#... 归约 by :S →a )#... 归约 by :T →T,S )#... 移进 #... 归约 by :S →(T) #... 对输入串（a,(a,a)）# 的规范归约过程为：
栈 # #( #( a #( S #( T #( T, #( T,( #( T,(a #( T,(S #( T,(T #( T,(T, #( T,(T,a #( T,(T,S #( T,(T #( T,(T) #( T,(S #( T #( T) #S 剩余输入串 (a,(a,a))#... 移进 a,(a,a))#... 移进 ,(a,a))#... 归约 by :S →a ,(a,a))#... 归约 by :T→S ,(a,a))#... 移进 (a,a))#... 移进 a,a))#... 移进 ,a))#... 归约 by :S →a ,a))#... 归约 by :T →S ,a))#... 移进 a))#... 移进 ))#... 归约 by :S →a ))#... 归约 by :T →TS ))#... 移进 )#... 归约 by :S →(T) )#... 归约 by :T →T,S )#... 移进 #... 归约 by :S →(T) #... 动作
规范归约是最左归约过程，首先确定符号（包括终结符及非终结符）之间优先关系，建立优先关系表，在归约过程中根据各符号之间的优先关系决定是移进还是归约，当出现句柄时进行归约; 算符优先归约方法不是规范的归约过程，首先确定终结符之间优先关系，在归约过程中根据最左素短语进行归约。
1、(1) a*(-b+c) ：ab-c+* (3) abcde/+*+ (4) AB∧C?D∨∨ (7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算） 2、
三元式 (1) (+ a, b) 间接三元式序列 间接码表 四元式 (2) (+ c, d) (1) (+ a, b) (1) (1) (+, a, b, t1) 精品文档
(2) (+ c, d) (2)
(3) (* (1), (2)) (3) (4) (- (3), /) (4) (5) (- (4), (1)) (1)
(2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5)
精品文档
(3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b) (6) (- (4), (5))
4、(0) S′→E { if error≠1 then print E.VAL}
(1) E→E1+E2 { if E1.TYPE=int AND E2.TYPE=int then begin
E.VAL:=E1.VAL + E2.VAL; E.YTPE:=int; end
else if E1.TYPE=real AND E2.TYPE=real then begin
E.VAL:=E1.VAL + E2.VAL; E.YTPE:=real; end else error=1 }
(2) E→E1*E2 { if E1.TYPE=int AND E2.TYPE=int then begin
E.VAL:=E1.VAL * E2.VAL;; E.YTPE:=int; end
else if E1.TYPE=real AND E2.TYPE=real then begin
E.VAL:=E1.VAL * E2.VAL;; E.YTPE:=real; end else error=1 }
(3) E→(E1) { E.VAL:=E1.VAL;
E.TYPE:=E1.TYPE } (4) E→n { E.VAL:=n.LEXVAL;
E.TYPE:=n.LEXTYPE } 5、
产生式 S?L1.L2 S?L L?L1B 语义规则 S.val:?L1.val?L2.val/2L2.length S.val:=L.val L.val:=L1.val*2+B.val L.length:=L1.length+1 精品文档