Search code examples
recursioncompiler-construction

which type of recursion should we use? (discussion)

i was studing topic about "left and right recursion in compiler " where i get confused in statement

Any kind of sequence can be defined using either left recursion or right recursion, but you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space.

but isn't it right that

When a production starts with a self reference then predictive parser stuck in a loop forever

M stuck there make me clear that would be grateful

Solution

  • The statement about always preferring left recursion comes from a discussion about bottom-up parsers. The statement about left recursion leading to endless loops comes from a discussion about top-down (predictive) parsers.

    Both statements are correct, because there is a difference between the two parsing algorithms.

    Bottom-up parsers can handle either left or right recursion, but left recursion is slightly more efficient because it doesn't require stack space. By contrast, top-down parsers can only handle right recursion.

    Any grammar which can be parsed with a top-down parser can be parsed bottom-up, but the reverse is not true: many grammars can only be parsed bottom-up. (Unless you allow unlimited lookahead or, equivalently, backtracking, in which case you can no longer guarantee to parse in linear time.)