Parser Combinators are the shit!

The name is daunting, but parser combinators are actually pretty straightforward once you get the hang of it (as is the case with most programming :P). Scala has a parser combinator library built right in; I myself followed the chapter on Parser Combinators in Programming in Scala 2nd Edition (PiS2E). I won’t go into details about how such combinators work or write a tutorial; there are enough of them out there. It is sufficient to say that you can build a basic arithmetic calculator (with +, -, *, /, and parentheses) using THREE LINES (ok, six counting declarations). If that doesn’t whet your appetite, then your stomach is probably made of rubber… There’s probably a better pun in there somewhere, but I’ll leave that as an exercise for the reader :P The following code is taken directly from PiS2E:

import scala.util.parsing.combinator._
class Arith extends JavaTokenParsers {
def expr: Parser[Any] = term~rep("+"~term | ""~term)
def term: Parser[Any] = factor~rep("*"~factor | "/"~factor)
def factor: Parser[Any] = floatingPointNumber | "("~expr~")"
}

All you need aside from that is to actually call the “parseAll” method with input, and then magic happens:

println(parseAll(expr, args(0)))
input: 2 * (3 + 7)
[1.12] parsed: ((2~List((*~(((~((3~List())~List((+
~(7~List())))))~)))))~List())

The formatting isn’t particularly pleasing to look at but it’s apparent that the structure is in there. It’s not much more complicated to adapt the code to actually spit out a number, add in constants, or parse variables. It’s the shit.

I used parser combinators on a sketch about a week ago to let users type in linear transformations. I’ve been on a fractal binge lately, and I was reading about IFSes and decided to implement a simple IFS drawer for a sketch. The algorithm is pretty straightforward:

  /*
  a) you have a set of geometric objects (points, lines, polygons, curves, etc) (named S)
  b) you have a set of transformations (rotate, translate, scale, shear, etc) (named T)
  c) you apply each transformation to each object in that set, which gives you the set of transformed objects S' (giving you num(S)*num(T) new objects)
  d) Use S' as the set S in a)
  */
  def iterated(): Set[Geometry] = {
    var Sprime: Set[Geometry] = Set()
    S.foreach(g => T.foreach(t => Sprime += g.transformed(t)))
    return Sprime;
  }

  def iterate() { //Move the iteration along.
    S = iterated();
  }

Writing a combinator to parse matrix inputs is pretty straightforward: you have basic transformations (translate, scale, rotate, etc.), and then you may combine them, usually with matrix multiplication (although I also implemented by-element summation to see what would happen). After some wiring and judicious ^^ usage (the ^^ method transforms raw combinator output types into types you want), some nice looking figures start popping up:

The shit!

At this point the only shape you start off with is a square; originally I was going to leave it at that but coming back to the sketch yesterday, I decided to add drawing capabilities. You can see the sketch here.

You can draw stuff!

I’m using controlP5 for the GUI, which works great for Processing but doesn’t have a comprehensive focus system so one has to write methods checking whether the user wants to draw things or if they’re just working the controls. controlP5 is also finnicky with regards to Proguard since the font it uses is stored in a couple of gif files within the “controlp5” package, so I decided to skip obfuscation for this jar; the resulting file is ~550kb, which still isn’t bad.

I wanted to create a three-dimensional view that kept track of the “age” of shapes and placed them on the Z axis according to age; that might be a future feature. All in all, I’m very pleased with how easy and quick it was to do what I was looking for in Scala, especially in regards to writing a grammar for linear transformations. It’s one of the reasons why I love Scala as a language; it’s like everything you ever wanted but didn’t have in Java. And so. Much. Less. Boilerplate. I’m not sure if I even USE plates anymore!

Advertisements

One Comment on “Parser Combinators are the shit!”

  1. […] first example pertains to the FunctionN implementations. For the linear transformation drawer, I tried writing a DSL with some sort of function application syntax that maps to underlying Scala […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s