Making a programming language Part 2 - something that kinda works

Posted on August 30, 2012

Table of contents, Whole project on github, relevant version on github

In the Part 1 I posted a working repl(read-eval-print-loop) for simple math expressions but I kinda cheated and only explained how I built the AST.

AST elements

Just scala case classes

Parser combinators revisited

I use power of scala library to cheat a bit and do lexing and parsing in one step.Basic parser combinators from scala api documentation, everything you need to define productions in your grammar.

However, to transform the matched string to an AST you need something more

Firstly, in the RegexParser class is an implicit conversion from Regex to Parser. So I could write

Notice the type annotation. Inferred type would be Regex, since this function is private I can still have implicit conversion, but I rather have all parsers be of type Parser[_].The ^^ part is an action combinator - a map function. But as ^^ is only available on Parser instances my regex has already been implicitly converted. So in my lambda I already know(scala can infer) the type of s to be String. One last example

Function rep is also from Parsers class matches any number of repetitions(including 0). Here’s the type signature

The catch here is that ~ returns a single parser that matches both sides, but fortunately it can be pattern matched to extract both sides. And I can even use meaningful names since I am in fact matching a head with an optional tail. Inside the case statement I used more imperative style to build a tree, nothing fancy here. Folding was a bit awkward in this case for me(maybe I’m just incompetent) so I went with a for each loop.Apply the same pattern to +/- part and you have yourself a tree.Oh, yeah…and the top parser function. A bit changed from last time, to yield useful error messages


Now what I promised in previous post - evaluation. At first I planned on compiling the code for JVM but I just wanted to see some results first so I decided to do a simple interpreter, no compiling whatsoever - for now. My first approach was to modify the Expression

and implement this on all case classes hardcoding the double type and coupling AST representation and evaluation together. Yikes. Granted, it worked, but what an ugly way to do it. So I did a hard reset(always use git folks! or something similar) and went about doing a standalone evaluator. Since scala’s pattern matching skills are awesome and I’m already using case classes why not just do that.

This is all the code. Just pattern matching and recursion. But yes, still hardcoded double as the data-type. Looking back, not a great decision…but hey I got something working and this is fun.

next time: Adding features(contants, exponents, function calls)

Facebook Twitter Google Digg Reddit LinkedIn StumbleUpon Email
comments powered by Disqus