短语：aTSHS句柄是a
6．已知文法GS为：
S→ABbC
A→bλ
B→aDλ
C→ADb
D→aSc
对其每一个非终级符求First集和Follow集。
FirstSbaλ
FirstAbλ
FirstBaλ
FirstCbac
FirstDac
FollowS
FollowAac
FollowB
FollowC
FollowD
二、（10分）设有文法GAAiBe
BSB
SeCi
CeC
判定该文法是否为LL1文法？若是则给出它的LL1分析表，否则说明理由。
先计算各个产生式的Predict集：
PredictAiBei
PredictBSB
PredictB
精品文档
f精品文档
PredictSeCPredictSiPredictCeCePredictC因为Predict集没有冲突，所以是LL1文法。LL1分析表如下：
i

e


A
iBe

B
SB
S
eC
C
eC

1、证明下面文法是LL1的但不是SLR1文法
S→AaAbBbBa
A→ε
B→ε
解：对于产生式S→AaAbBbBa来说FIRSTAaAb∩FIRSTBbBaa∩bΦ而A，B∈VN仅有一条候选式。因此，这个文法是LL1的。下面构造这个文法的识别活前缀的DFA。
I0S→SS→AaAbS→BbBaA→B→I1S→SI2S→AaAbI3S→BbBaI4S→AaAbA→I5S→BbBaB→I6S→AaAbI7S→BbBaI8S→AaAbI9S→BbBa

SBi
由于FOLLOWAFOLLOWBab
因此项目集I0中存在归约－归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→ε还是B→ε进行归约。故此文法不是SLR1的。但是，此文法是LR1的。
五、已知文法GS，其产生式如下：S→La
L→L，SS
精品文档
f精品文档从GS中消除左递归，并为之构造一个非递归预测分析器LL1分析表。请说明在句子a，a，a上的分析器的动作。（20分）解：将所给文法消除左递归得G：S→LaL→SLL→，SLε
实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G有FIRSTsaFOLLOWSFIRSTLaFOLLOWLFIRSTL’FOLLOWL’按以上结果，构造预测分析表M如下：
文法G’是LL1的，因为它的LL1分析表不含多重定义入口。预测分析器对输入符号串aaa做出的分析动作如下：
例53的文法G3S为：S→aAS→dA→bASA→ε不难看出由定义53可得：精品文档
f精品文档
SELECTS→aAaSELECTS→ddSELECTA→bASbSELECTA→εad所以SELECTS→aA∩SELECTS→da∩d
SELECTA→bAS∩SELECTA→εb∩ad由r