# Shortest parser for a left-recursive grammar

Write the shortest parser for the grammar:

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

• Would this question make more sense to me if I had ever taken any CS classes? ;-). Perhaps you can give a couple if input/output examples for the rest of us – Digital Trauma Sep 19 '14 at 15:19
• @DigitalTrauma I have edited my answer. – thwd Sep 20 '14 at 9:33

## Ruby, 51 bytes

f=->s{s.split(/(\+)(?=n$)/).map{|t|t['+n']?f[t]:t}}  This seems weirdly cumbersome. It can be called like f['n+n+n']. # CJam, 13 15 If I have understood what did you mean by "the code to validate input is not necessary" correctly: {'+/{[\"+"@]}*}  ### Example {'+/{[\"+"@]}*}:T; "n+n+n" T N "n+n+n+n" T  Output: [["n" "+" "n"] "+" "n"] [[["n" "+" "n"] "+" "n"] "+" "n"]  Or if I have to check the grammar: # CJam, 24 {'+/_"n"a-L@{[\"+"@]}*?}  • Am I doing something wrong? The Code only prints itself on cjam.aditsu.net – Falco Sep 19 '14 at 14:17 • @Falco I have changed the code to a function (or block) but forgot to change the "from stdin to stdout" line... Now added some examples. – jimmy23013 Sep 19 '14 at 15:20 • What was wrong with the 13-char version? It seemed to work. – flornquake Sep 19 '14 at 23:16 • @MartinBüttner said it should be a function... – jimmy23013 Sep 19 '14 at 23:32 # Augeas, 42 module A=let rec l=[key"n".(del"+""+".l)?]  Example usage, by adding: test l get "n+n+n" = ?  and launching: $ augparse a.aug
Test result: a.aug:2.0-.22:
{ "n"
{ "n"
{ "n" }
}
}


Due to the bidirectional nature of Augeas lenses, the provided code also manages the reverse transformation, e.g. by using:

test l put "n" after clear "n/n/n" = ?


then launch augparse:

\$ augparse a.aug
Test result: a.aug:2.0-.38:
"n+n+n"


# Pyth, 20 13 bytes

L.U[b\+Z)cz\+


Took me forever to shorten it, but I did! I changed pretty much the entire algorithm. Defines a function y that takes one string argument.

Live demo with 3-byte test harness and test cases.

## Original

?tJu?qH\n+GH,GHzkJ]J


Live demo and test cases.

• For those (like me) that don't grok Pyth, how exactly does it create a function called y? – Jerry Jeremiah Sep 2 '15 at 22:29
• @JerryJeremiah The L creates a function named y that takes an argument b. If you want, I'll add an explanation in a few. :) – kirbyfan64sos Sep 2 '15 at 22:32
• Thanks so much. I really want to learn one of these golfing languages. I am just not competitive at all with the languages I am good at... – Jerry Jeremiah Sep 2 '15 at 22:49
• @JerryJeremiah Just remember that algorithms beat languages. I've been beated by Python because the other person had a better method of solving the problem than I did. :) – kirbyfan64sos Sep 2 '15 at 23:27