# Why does bottom-up parsing of right-recursive grammars require unbounded O(n) stack space?

I keep reading that while bottom-up parsing of a left-recursive grammar can be done in constant O(1) stack space, for a right-recursive grammar, we have to push the entire input stream onto the stack before popping any of them off. Why is this?

Let's say that I consider a simple right-recursive grammar List -> elt List | elt , and I consider the string elt elt elt. When the parser pushes the first elt onto the stack, why doesn't it just immediately reduce it to List and then continue parsing?

• When you say bottom-up parsing, do you mean LR parsing? The answer to your question depends on the parsing algorithm you use. Also, the LR(k) parsing algorithm does not apply to all context free grammars.
– Bob
Sep 28 at 20:09
• Yep, I am indeed referring to LR parsers in this case. The book I’m using (Cooper, Torczon - Engineering a Compiler) refers to LR parsers as shift-reduce machines, which I’m familiar-ish with. Sep 28 at 21:40

The question is: given the grammar \begin{align}\textit{List}&\to \textbf{elt}\ \textit{List}\\ \textit{List}&\to \textbf{elt} \end{align} and the input $$\textbf{elt elt elt}$$ Why doesn't the parser immediately reduce $$\textit{List}\to \textbf{elt}$$ Suppose that it did. You would then have $$\textit{List}\textbf{ elt elt}$$ Now what? No production starts with $$\textit{List}$$ so the parser is stuck.
The only way the parser can parse the entire input is to assume that the $$\mathbf{elt}$$ is the first symbol in $$\textit{List}\to\textbf{elt}\textit{ List}$$ and proceed from there, but that necessarily uses a stack slot to record the incomplete production.
To put it another way, if you use right-recursion, the unit production $$\textit{List}\to\textbf{elt}$$ applies to the last $$\mathbf{elt}$$ in the $$\textit{List}$$. In contrast, in a left-recursive grammar for the same language, the unit production would apply to the first $$\mathbf{elt}$$. Whether or not there is a semantic difference depends on your attribute actions; if there is no semantic difference, the left-recursive grammar will normally be prefered.
However, in many languages, there are also syntactic constraints which might suggest using a right-recursive grammar even though it uses up stack space. For example, the simplified grammar for a parameter list with optional unnamed trailing arguments (C99 varargs macros, for example): \begin{align}\textit{Parameters}&\to \textbf{ID , }\ \textit{Parameters}\\ \textit{Parameters}&\to \textbf{ID}\\ \textit{Parameters}&\to \textbf{. . .}\\ \end{align} Since the $$\textbf{. . .}$$ can only be at the end of the parameter-list, it's easiest to write the grammar as right-recursive.