3
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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 \$\endgroup\$ – Digital Trauma Sep 19 '14 at 15:19
  • \$\begingroup\$ @DigitalTrauma I have edited my answer. \$\endgroup\$ – thwd Sep 20 '14 at 9:33
2
\$\begingroup\$

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'].

\$\endgroup\$
2
\$\begingroup\$

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@{[\"+"@]}*?}
\$\endgroup\$
  • \$\begingroup\$ Am I doing something wrong? The Code only prints itself on cjam.aditsu.net \$\endgroup\$ – Falco Sep 19 '14 at 14:17
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – jimmy23013 Sep 19 '14 at 15:20
  • \$\begingroup\$ What was wrong with the 13-char version? It seemed to work. \$\endgroup\$ – flornquake Sep 19 '14 at 23:16
  • \$\begingroup\$ @MartinBüttner said it should be a function... \$\endgroup\$ – jimmy23013 Sep 19 '14 at 23:32
2
\$\begingroup\$

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"
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For those (like me) that don't grok Pyth, how exactly does it create a function called y? \$\endgroup\$ – Jerry Jeremiah Sep 2 '15 at 22:29
  • \$\begingroup\$ @JerryJeremiah The L creates a function named y that takes an argument b. If you want, I'll add an explanation in a few. :) \$\endgroup\$ – kirbyfan64sos Sep 2 '15 at 22:32
  • \$\begingroup\$ 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... \$\endgroup\$ – Jerry Jeremiah Sep 2 '15 at 22:49
  • \$\begingroup\$ @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. :) \$\endgroup\$ – kirbyfan64sos Sep 2 '15 at 23:27

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.