所以文法是LL(1)的。

预测分析表（Predicting Analysis Table）

也可由预测分析表中无多重入口判定文法是LL(1)的。 第2 种改写：

用S 的产生式右部代替A 的产生式右部的S 得：

S→Aa|b A→AaB|bB B→ab

消除左递归后文法变为： 0) S→A a 1) S→b 2) A→b B N 3) N→a B N 4) N→ε 5) B→a b

非终结符 FIRST 集 FOLLOW 集 S {b} {#} A {b} {a} B {a} {a} N {a,ε} {a}

对相同左部的产生式可知：

SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠ SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠ 所以文法不是LL(1)的。 预测分析表：

也可由预测分析表中含有多重入口判定文法不是LL(1)的。

第6 章 自底向上优先分析

第1 题已知文法G[S]为：S→a|∧|(T)

T→T,S|S

(1) 计算G[S]的FIRSTVT 和LASTVT。

(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。 (3) 计算G[S]的优先函数。

(4) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。 答案：

文法展开为： S→a S→∧ S→(T) T→T,S T→S

(1) FIRSTVT - LASTVT 表：

(2) 算符优先关系表：

(3)对应的算符优先函数为：

（4）对输入串（a,a）#的算符优先分析过程为

Success!

对输入串（a,(a,a)）# 的算符优先分析过程为：

Success!

第2 题已知文法G[S]为：S→a|∧|(T) T→T,S|S

(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。

(2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。 答案：（１）(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,(T,a)) => (T,(S,a)) => (T,(a,a)) => (S,(a,a)) => (a,(a,a))

(a,(a,a))的规范归约过程：

(a,a)的规范归约过程：

(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与 非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名

字是什么，因此去掉了单非终结符的归约。

规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。 第３题：有文法G[S]： S->V V->T|ViT T->F|T+F F->)V*|(

(1) 给出(+(i(的规范推导。

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

(3) G[S]是否为OPG？若是，给出(1)中句子的分析过程。 答案：

(1)S=>V=>ViT=>ViF=>Vi(=>T i(=>T+F i(=>T+( i(=>F+( i(=>(+( i( (2)句型F+Fi(的语法树：

短语：F，F+F，(，F+Fi( 句柄：F 素短语：( (3)FIRSTVT 和LASTVT

算符优先关系

因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。 (+(i(的分析过程

第４题文法G［S］为： S→S;G｜G G→G(T)｜H H→a｜(S)