CFG 文法中的递归问题

[ibudao]

小白问题。CFG文法的产生式中通常在Rhs中包含Lhs来表达递归，例如：
Sums → Sums + Products

这里我想问的是为什么Rhs中的Sums要在第一个位置呢，为什么不能这么写：
Sums → Products + Sums

[akfish]

这样就形成左递归了，会导致递归下降分析器无限递归。

[cocorosiekz]

LL(1)的不能解析这种语法，SLR的就无所谓了

[ibudao]

@cocorosiekz 那为什么LR的文法我看到的都是用这种左递归呢，还是说写成有递归也是可以的？

[ibudao]

@cocorosiekz 那为什么LR的文法我看到的都是用这种左递归呢，还是说写成右递归也是可以的？

[cocorosiekz]

@ibudao 我觉得LR文法可以处理左递归，是因为本身是bottom-up的，shift\reduce的方式本身不存在这个问题

[ibudao]

@cocorosiekz 在维基上找到答案了。A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form. In contrast, left recursion is preferred for LALR parsers because it results in lower stack usage than right recursion.

[cocorosiekz]

@ibudao 恩，这里没有解释为什么左递归和右递归的gammar可以用到bottom-up中，可能比较直白了吧，关于左递归和右递归对栈的消耗高低是对的，这个具体写一下就可以明白

[chengluyu]

因为加号是一个左结合的操作符，就是说1+1+1+1=(((1+1)+1)+1)。
结合性的重要性在加号上体现的不明显，因为加法无论怎么结合答案都一样，但是如果是减法就不一样了：
1-1-1-1-1-1=(((((1-1)-1)-1)-1)-1)，但是不等于((1-1)-(1-1)-(1-1))。
所以把product放在左边就是为了符合操作符的左结合性。

顺便一提，如果你熟悉Haskell这样的函数式语言，你会发现这个和foldl和foldr很像。

[chengluyu]

至于左递归，只要用消除左递归的法则消除就可以使用递归下降的方法进行语法分析了。

[ibudao]

@chengluyu 对的，我是erlang程序员，在erlang中也有foldl和foldr。但是，如果左递归是为了表达操作符的左结合性，右递归是为了表达右结合行，我好奇的是LL(k)解析器是如何消除左递归，而又能表达操作符的左结合性的？

[Golevka]

chengluyu关于结合性的说明是正确的，虽然不同的CFG能产生同样的集合但是对应的parse tree不同，于是解析出的AST是不一样的，比如1 - 2 + 3这个case就能放倒一大片结合性做杯具了的parser:

correct: (+ (- 1 2) 3)
incorrect: (- 1 (+ 2 3))

[Golevka]

@ibudao LL(k)是干不掉左递归的，你只能通过left-factoring之类的手段重写CFG再交给LL(k)去处理；LR parser就无所谓了，要是遇见shift-reduce conflict八成是你产生式写错了或者predicate/precedence没加上。