LL(1)文法的定义
(2012-05-22 20:54:58)
标签:
it |
分类: 编译原理 |
S->C$
C->bA|aB
A->a|aC|bAA
B->b|bC|aBB
构造一个等价的LL(1)文法!!!!!
-----------------------------------------------------------------------------------
LL(1)文法表示是有限的,有的文法是无法用LL(1)文法表示的.
LL(1)文法的条件有板有3:
1:无左递归
2:无左公因子
3:如果 ε∈first(A),A∈非终结符,
首先你给的文法很容易看出没有直接或间接左递归.
其次你的算法中含有左公共因子,则需要消除左公共因子. 所以消除左公共因子后文法是:
S->C$
C->bA |aB
A->aP |bAA
B->bP|aBB
P->C |ε
然后检测改算法是否是LL(1)文法的第三个条件.
对于你这个文法很容易看出只有first(p) 含有ε,那么只需检测first(P)∩follow(P)
容易看出 : first(P) = {ε}∪first(C) = {ε} ∪ {a,b} = {a,b,ε}
first(P)∩follow(P)= φ
满足第三个条件 .所以上改造后的文法是LL(1).
--------------------------------------------------
注意:如果第三步检测不通过,那么文法是无法用LL(1)表示的.