加载中…
个人资料
等待
等待
  • 博客等级:
  • 博客积分:0
  • 博客访问:787
  • 关注人气:26
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

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∈非终结符,
  那么必须满足:
  first(A)∩follow(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,ε}
  follow(P) = follow(A)∪follow(B) = follow(C)∪follow(C) = follow(C) = {$}
first(P)∩follow(P)= φ
满足第三个条件 .所以上改造后的文法是LL(1).
--------------------------------------------------
注意:如果第三步检测不通过,那么文法是无法用LL(1)表示的.

 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有