论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2008-02-20 14:45 |只看该作者 |倒序浏览

这个问题原来觉得想明白了，现在又糊涂了
如文法：
A ==> AR | B
现在觉得：只要FIRST(A)与FIRST(B)无交集，则对于无回溯的递归下降分析或LL(1)，无需消除左递归。因为递归下降会将超前扫描Token与FIRST(A)与FIRST(B)，以此决定到底用那个推导，这样就不会导致无穷循环。

所以核心问题是FIRST(A)与FIRST(B)是否有交集，而不是左递归。只有对于带回溯的自顶向下分析，才必须消除左递归

我的想法问题在哪儿？望达人指点

文库|博客

Wind-Son

丰衣足食

论坛徽章:: 0

2楼 [报告]

发表于 2008-02-20 18:44 |只看该作者

转过弯来了
超前搜索与FIRST(A)一致时,进入A,但此事超前搜索符号尚未被消耗掉,始终为FIRST(A),从而不断进入A

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

3楼 [报告]

发表于 2008-02-20 22:43 |只看该作者

FIRST(A)和FIRST(B)必然有交集

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

Wind-Son

丰衣足食

论坛徽章:: 0

4楼 [报告]

发表于 2008-02-20 23:45 |只看该作者

回复 #3 cjaizss 的帖子

是
转过弯了谢指点

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

prolj

荣誉版主

论坛徽章:: 0

5楼 [报告]

发表于 2008-03-03 21:27 |只看该作者

LL（1）为什么要消除左递归？怎么消除的？形式上还是实际上？
递归下降为什么叫递归下降？

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

6楼 [报告]

发表于 2008-03-03 22:08 |只看该作者

回复 #5 prolj 的帖子

因为要从左向右检索，所以要消除左递归（因为左递归无法规约），同理，从右往左检索要消除右递归。
可以通过重写规则消除左递归
比方如果A->A B
         A->C
那么A为CB*
那么重写：
   D->B
      D->BD
      A->CD
“形式上”还是“实际上”，这个不好说，因为如果一种语言是由一组语法规则诱导来的，只要是可以源源不断生成的语言，那么递归是一定存在的，你所能做的只是消除左递归。
至于递归下降为什么叫递归下降：因为它是一直递归的找到语法树的叶子