CODEWITHSUNDEEP
parsingrecursioncontext-free-grammar
Nick Powers
Nick Powers

Reputation: 127

Why right-recursive grammar is not appropriate for Bottom-Up LR(k) parsing?

I know Bottom-Up parsing starts at leaves and builds up to the root node whereas Top-Down starts at the root and makes it's way down, did a little research regarding these questions and got how they could be modified but couldn't get a direct answer as to why this doesn't work. Any help is appreciated.

Upvotes: 2

Views: 2656

Answers (1)

Ira Baxter
Ira Baxter

Reputation: 95402

[OP changed question title from "why can't ... be used" to "why isn't appropriate ..." That in turn changes my comment into an answer, so I am posting it as one.]

You can use left- or right- recursive rules with any LR(k) parsing algorithm.

Right recursive rules cause a funny property of the parsing process, if you are going to build trees: you have to keep a stack as deep as the right recursion to track the collected nodes.

People will give you source files containing a million items in a list so your stack must be that deep. With right recursive rules this may be deep enough so that you run out of space if you have a fixed sized stack.

Often a parser stack is implemented using the processor's natural push down stack. Our common OSes (Windows, Linux) and their common compilers happen to offer you exactly such fixed size pushdown stacks so in some sense they aggravate this problem.

With a left recursive rule, you reduce after each list item so the stack can be essentially unit depth. That's a lot friendlier: doesn't crash, and uses the cache well.

Upvotes: 4

Related Questions