Shortest parser for a left-recursive grammar Write the shortest parser for the grammar:

M -&gt; M + n | n



Output must be some representation of a structured value representing the concrete syntax tree produced by the input n+n+n.
The code to produce the textual output from the structured value is not necessary.
The code to read/validate input is not necessary.
Solution is anything that can somehow be called; a function, an object, doesn't matter.
How your solution receives input (currying character-by-character, whole-string, some kind of input reader) does not matter.


For example a bottom-up parser (Javascript, 284 characters):

function M(d){function c(a){throw"unexpected "+a;}function f(a){if("+"==a)return b.push(a),e;if(null==a)return b;c(a)}function e(a){if("n"==a)return b.push(a),b=[b],g;c(a)}function g(a){if("+"==a)return b.push(a),e;if(null==a)return b;c(a)}var b=[];if("n"==d)return b.push(d),f;c(d)};


When called:

 M('n')('+')('n')('+')('n')(null)


will return an array that in JSON-notation looks like this:

[["n", "+", "n"], "+", "n"]




Edit for the uninitiated in parsing: This is one of those questions where making a program produce the correct output is easy but the form of the program is essential for up-boats.

M -&gt; M + n | n


Means that M consists of a previous M, a plus sign and a literal "n". Or good M is a single "n" literal character.

There are several way of approaching this challenge, I'll describe my own solution, which is called bottom-up parsing. Character by character:

 Stack               Incoming Character         Action on stack
                     n                          
 n                   +                          reduce "n" to M
 M+                  n
 M+n                 +                          reduce "M + n" to M
 M+                  n                          
 M+n                 EOF                        reduce "M + n" to M
 M


The twist in this question is that the simplest form of parsers called "recursive-descent" parsers won't work because the grammar is left-recursive and that throws a recursive-descent parser into an infinite loop.
Ruby, 51 bytes

f=-&gt;s{s.split(/(\+)(?=n$)/).map{|t|t['+n']?f[t]:t}}


This seems weirdly cumbersome. It can be called like f['n+n+n'].