自顶向下与左递归问题

Wind-Son 发表于 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 发表于 2008-02-20 18:44

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

cjaizss 发表于 2008-02-20 22:43

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

Wind-Son 发表于 2008-02-20 23:45

回复 #3 cjaizss 的帖子

是
转过弯了谢指点

prolj 发表于 2008-03-03 21:27

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

cjaizss 发表于 2008-03-03 22:08

回复 #5 prolj 的帖子

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

prolj 发表于 2008-03-04 19:24

LL(1)消除左递归仅仅是形式上转化成了右递归，为了避免无限递归。
LL和递归下降还是有些区别的，实践中我是递归下降的坚实支持者。当然，LZ搞某理论的话就另当别论了。
语法这么成熟了，如果能搞出点名堂来也许会是图灵奖。类型检查和制导翻译虽然不太理想，实际上还过得去。LTO好象是当前的热点。

freearth 发表于 2008-04-07 17:41

回复 #3 cjaizss 的帖子

FIRST(A)和FIRST(B)必然有交集
支持这个答案

modoke 发表于 2008-04-08 23:25

上周写的LL1程序自动生成FIRST FOLLOW集合
对于左递归理解进了一步

modoke 发表于 2008-04-08 23:27

在生成FIRST集是如果不消左递归会进入无限递归溢出
总之呢一定要确定起点

页: [1]

Chinaunix's Archiver