如何判断1个文法是LL文法.ppt

LL的含义 －自左向右扫描分析输入符号串 －从识别符号开始生成句子的最左推导 LL(1):向前看一个输入符号，便能唯一确定当前应选择的规则 LL(k):向前看k个输入符号，才能唯一确定当前应选择的规则;同一非终结符有多个候选式时 ;1. FIRST集 ;（1）若α=aα′，且a∈VT ，则a∈FIRST(α)； 例： FIRST(i)={i} FIRST(+TE)={+};① 将FIRST(X1)中的一切非ε的终结符加进FIRST(α)； ② 若ε∈FIRST(X1),则将FIRST(X2)中的一切非ε的终结符加进FIRST(α)； ③ 若ε∈FIRST(X1)且ε∈FIRST(X2),则将FIRST(X3)中的一切非ε的终结符加进FIRST(α)； ④ 依此类推，若对于一切1≤i≤n,ε∈FIRST(Xi)，则将ε加进FIRST(α)。;FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T)=FIRST(F)-{ε}={(,i} FIRST(E’)={+,ε} FIRST(E)= FIRST(T)-{ε}={(,i} FIRST(TE’)=FIRST(T)-{ε}={(,i} FIRST(+TE’)={+} FIRST(ε)={ε} FIRST(FT’)= FIRST(F)-{ε}={(,i} FIRST(*FT’) ={*} FIRST(（E）)={(} FIRST(i)={i};2. FOLLOW集 ;构造集合FOLLOW的算法;【例4.10】 G[E] E→TE E→+TE|? T→FT T→*FT|? F→(E)|i;若一个文法满足以下条件，则称该文法G为LL(1)文法：;【例4.11】 G[E]： E→TE E→+TE|? T→FT T→*FT|? F→(E)|i 判别该文法是否为LL(1)文法。