2
  • 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.

Nick Powers
  • 127
  • 8
  • 2
    Who says right recursive grammars are not appropriate for LR(k) parsing? They work fine. – rici Mar 03 '16 at 03:18
  • @rici My professor apparently. I am completing a test review and that is one of the questions. I was a bit confused because it has never been mentioned in class before and I found nothing concerning it in my textbook or powerpoints. – Nick Powers Mar 03 '16 at 03:39
  • 1
    You can use left- or right- recursive rules with any LR(k) parsing algorithm. Right recursive has a funny property 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 a left recursive rule, you reduce after each step and the stack can be essentially unit depth. So, you can use either kind of rule. The right recursive one may go deep; people with fixed sized stacks sometimes run out as a consequence. – Ira Baxter Mar 03 '16 at 04:04
  • ... so your professor may be telling you something deep, or it may be just silly. Hard to tell without the rationale. – Ira Baxter Mar 03 '16 at 04:10
  • @IraBaxter I emailed him and he confirmed basically what you said. That you can in fact use a right- recursive grammar with a LR(k) parsing algorithm but that the answer he was looking for was the stack depth part. He basically reiterated what you said about having to build a stack as deep as the right recursion and that this could theoretically be infinite. Thanks for the input, much appreciated. – Nick Powers Mar 03 '16 at 08:13

1 Answers1

4

[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.

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341