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?

  • $\begingroup$ 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. $\endgroup$
    – Bob
    Sep 28 '21 at 20:09
  • $\begingroup$ 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. $\endgroup$
    – user49404
    Sep 28 '21 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.