This post originated from an RSS feed registered with Scala Buzz
by Eric Torreborre.
Original Post: Mini-Parsers to the rescue
Feed Title: A++ [Eric Torreborre's Blog]
Feed URL: http://etorreborre.blogspot.com/feeds/posts/default/-/scala
Feed Description: This blog is "Software on my mind" and I try to write one post a month. As Scala is a lot on my mind recently, you can expect more Scala posts quite soon!
I'm implementing a reasonably complex algorithm at the moment with different transformation phases. One transformation is a "curryfication" of some terms to be able to transform some expressions like:
f(a, b, c)
to
.(.(.(f, a), b), c)
Being test-compulsive, I want to be able to test that my transformation works. Unfortunately the data structures I'm dealing with are pretty verbose in my tests.
One of my specs examples was this: "A composed expression, when curried" should { "be 2 successive applications of one parameter" + "when there are 2 parameters to the method expression" in { ComposedExp(MethodEx(method), const :: arb :: Nil).curryfy must_== Apply(Apply(Curry(method), Curry(const)), Curry(arb)) } }
But Apply(Apply(Curry(method), Curry(const)), Curry(arb))) is really less readable than .(.(method, const), arb).
With the help of a mini-parser
So I thought that I could just write a parser to recreate a "Curried" expression from a String.
A first look at the Scala 2.8.0 Scaladoc(filter with "parser") was a bit scary. Especially because my last parser exercise was really a long time ago now.
But no, parser combinators and especially small, specific parsers like the one I wrote are really straightforward: object CurriedParser extends JavaTokenParsers { val parser: Parser[Curried] = application | const val const = ident ^^ { s => Curry(s) } val application = (".(" ~> parser) ~ (", " ~> const <~ ")") ^^ { case a ~ b => Apply(a, b) } def fromString(s: String): Curried = parser.apply(new CharSequenceReader(s)).get }
In the snippet above I declare that:
my parser is returns a Curried object
my parser is either an application or a constant (with the | operator)
a constant is a Java identifier (because of the inheritance of the JavaTokenParsers trait)
a constant should be transformed to a Curry object
an application is composed of two parts (separated by ~). The first part is something that can be parsed with my parser (i.e. an application or a constant). The second part is a constant. And in each part I get rid of the syntactic elements (using a "discard" operator <~ or ~>)
once an application is parsed, part 1 and part 2 must be used to build an Apply object
the fromString method simply passes a String to the parser and gets the result
I have to say that this parser is really rudimentary. It doesn't handle errors in the input text, there needs to be a space after the comma, and so on.
Yet it really fits my testing purpose for a minimum amount of development time.
Open question (for later,...)
The only question that is open for me at the moment is this one: is there a way to define algebraic datatypes in Scala so that:
each class has a proper toString representation (as with case classes)
there is an implicit parser that is able to reconstruct the hierarchy of objects from the string representation of the tree
Previous Topic
