July 9th, 2008
The second part of my Scala compiler construction tutorial has been a long time coming. This post is, unfortunately, not the second part of the article — although that is coming soon. Honest.
Since part 1 was published, Scala 2.7 has been released which — among other things — introduced changes to the parser combinator library. Changes that meant the source code from part 1 will not compile in Scala 2.7. Sorry about that. Updated, working code can be found at the end of this post.
So what exactly has changed? Well, let’s see …
keyword() no longer discards its result
A bit of a refresher first:
In both Scala 2.6 and 2.7, the keyword implicit is called whenever you use a string in your “grammar rules”. For example:
def sum = expr ~ "+" ~ expr
Is the equivalent of:
def sum = expr.~(keyword("+").expr)
In Scala 2.6’s parser combinator library, the result of the keyword() call was actually the UnitParser — that is, a parser that would discard its result. At the time, that meant we could use the tilde operator (”~”) to create a sequenced parser and everything was fine:
def sum = expr ~ "+" ~ expr ^^
((left : Expr, right : Expr) => Sum(left, right))
In 2.7, the keyword() implicit returns a Parser[String] rather than a UnitParser. This means we have to either deal with the newly introduced tokens as follows:
def sum = expr ~ "+" ~ expr ^^
((left : Expr, op : String, right : Expr) => Sum(left, right))
Or alternatively …
Use <~ and ~> to indicate the important parts of a parse rule
Let’s start with something simple based on the 2.6 combinators:
def bracketExpr = "(" ~ expr ~ ")" ^^ ((e : Expr) => e)
Again, in 2.7 we know that keyword() is no longer a UnitParser, so we have to deal with it like so:
def bracketExpr = "(" ~ expr ~ ")" ^^
((l : String, e : Expr, r : String) => e)
Alright, this compiles and does what we expect. But why should we keep those strings around if we don’t need them? They sure do clutter up the code a whole bunch.
<~ and ~> can be used to include or discard the result of a given parser. <~ builds a parser that takes the result of two parsers (the parsers to its left and right) and builds a parser that takes the result of both and discards the result of the one on the right. Conversely, ~> yields a parser that takes the result of both parsers and discards the result on the left.
So, using these two operators we can rewrite bracketExpr as follows:
def bracketExpr = "(" ~> expr <~ ")" ^^
((e : Expr) => e)
Ah. Much better. 
The ^^^ operator
I had to go digging in the Scala source code to work out what exactly this one does.
First, let’s take a look at some 2.6 code:
def simpleExpr = term * (
"+" ^^ ((x : Expr, y : Expr) => Add(x, y)) |
"-" ^^ ((x : Expr, y : Expr) => Sub(x, y))
)
In 2.6, this can parse zero or more repetitions of “term” interleaved by “+” and “-” (check out part 1 if you need a refresher on how the * combinator works). In 2.7 it’s a compile-time error because of the fact keyword() is no longer a UnitParser (are you seeing a pattern here? ), and ^^ is trying to pass the resulting String on to the anonymous method in each case.
If we use the ^^^ operator here, we can effectively discard the result of the keyword parse, and build a parser that uses a simple anonymous method to parse the current pair of terms:
def simpleExpr = term * (
"+" ^^^ ((x : Expr, y : Expr) => Add(x, y)) |
"-" ^^^ ((x : Expr, y : Expr) => Sub(x, y))
)
Exactly what we’re after. This compiles and behaves as expected.
What else?
There may be more changes to the parser combinator library which I haven’t covered here, but I’m not going to go looking for any more changes since the updated code seems to work just fine. This should be enough to at least understand the updated code for the compiler described in part 1 without needing to deal with any cryptic compiler errors.
Finally, the new code!
Special thanks to Harshad for sending through working code for 2.7 ages ago which I never got around to posting here. This code, along with the Scala API docs, was used to figure out just what had changed since 2.6. The code below is derived from some code he sent to me a few months back.
I’m really sorry this has been so long in the making. I’ll try to get around to writing the “real” part two of this article. In the meantime, here’s the updated code. Thanks! Please post or email any comments or questions.
Categories: Compiler Construction with Scala and BCEL, Compilers, Functional Programming, Scala, Software Development |
3 Comments
April 14th, 2008
This was originally planned as a response to this post by Paul Bonser, but grew a little unwieldy (and his comment submission form seems to be broken?).
Effectively, Paul was (somewhat sleepily) mulling over the workings of the IMPORT_NAME bytecode. This bytecode is generated in response to Python code like the following:
import sys
And also for:
from foo import bar, baz
You’ll have to see the original post for the actual bytecode generated for this code, but Paul was asking why the latter syntax generates an IMPORT_NAME bytecode instruction which seems to do nothing at all with the fromlist, then generates additional IMPORT_FROM bytecodes that fetch the fromlist attributes from the parent module.
The documentation for __import__ somewhat solves this mystery:
Note that even though locals() and ['eggs'] are passed in as arguments, the __import__() function does not set the local variable named eggs; this is done by subsequent code that is generated for the import statement. (In fact, the standard implementation does not use its locals argument at all, and uses its globals only to determine the package context of the import statement.)
Essentially, when the IMPORT_NAME is executed for ‘from foo import bar, baz’, the __import__ builtin is called with the fromlist and a few other arguments (namely the globals() and locals() from the current frame of execution) to provide custom import handling for your Python programs. For example, you may want to prevent users of your program from writing scripts that import certain modules. I imagine Google’s App Engine might be using something like this to prevent access to certain evil or unavailable modules (but that’s just a wild, unfounded guess).
The code in Python/ceval.c for IMPORT_NAME seems to back this up (I’ve annotated the code with a few comments):
case IMPORT_NAME:
w = GETITEM(names, oparg);
/* 1. LOCATE THE __import__ BUILTIN */
x = PyDict_GetItemString(f->f_builtins, "__import__");
if (x == NULL) {
PyErr_SetString(PyExc_ImportError,
"__import__ not found");
break;
}
Py_INCREF(x);
v = POP();
u = TOP();
/* 2. BUILD THE LIST OF ARGUMENTS FOR __import__ USING THE fromlist, globals() AND locals() */
if (PyInt_AsLong(u) != -1 || PyErr_Occurred())
w = PyTuple_Pack(5,
w,
f->f_globals,
f->f_locals == NULL ?
Py_None : f->f_locals,
v,
u);
else
w = PyTuple_Pack(4,
w,
f->f_globals,
f->f_locals == NULL ?
Py_None : f->f_locals,
v);
Py_DECREF(v);
Py_DECREF(u);
if (w == NULL) {
u = POP();
Py_DECREF(x);
x = NULL;
break;
}
READ_TIMESTAMP(intr0);
v = x;
/* 3. CALL __import__ WITH THE module name, fromlist, globals() AND locals() */
x = PyEval_CallObject(v, w);
Py_DECREF(v);
READ_TIMESTAMP(intr1);
Py_DECREF(w);
SET_TOP(x);
if (x != NULL) continue;
break;
So this answers the question of why IMPORT_NAME needs the fromlist in the first place: it is merely passed along to __import__ to make it available to custom import handling code. But why aren’t the fromlist attributes added to the namespace inside IMPORT_NAME? I’m guessing it was a design decision: we already have an opcode for adding elements to the namespace, so why have a special case for imports? Of course the details may be more involved than that, but it’s the most obvious explanation I can think of.
In any case, thanks for the thought-provoking post, Paul!
UPDATE: Seems my comment made it through to his blog after all. Sorry for the double-up!
Categories: Compilers, Python, Software Development |
2 Comments
November 11th, 2007
I just read Hans-Eric Gronlund’s post on the pending extinction of programmers. The sky is falling in Software Development Land, it would seem: we’re all to be replaced by the very programs we’re writing. My natural reaction to his post is outright rejection. To my mind, there are too many fringe cases to account for, too many semantic nuances in spoken and written language to possibly pretend – even for a moment – that we’re just an academic paper or two away from being able to produce truly useful software from a high level specification. I wager that we’ll never see such a silver bullet come to fruition any time in the foreseeable future.
The Devil in the Details
Software development is not easy. You can trivialize it away all you want, and pretend that somehow the computer is going to know what you mean when you say “generate a report based on the data in the products table”. The devil is, and always will be, in the details. Simply put, you cannot abstract away details. Combine this with the fact that programming languages are constantly being born, evolved and killed. Ideas in languages decades old are being reimplemented in modern languages with a twist. We’re in an endless spiral of self-destruction: the software we write to day will be out of date – technologically speaking – by tomorrow because language X is no longer popular, or framework Y is now unsupported, or platform Z has crap support for multiple cores and so our software simply cannot scale. Our tools are constantly improving, but as developers we’re forever reinventing the software wheel – and that’s a problem caused by the overzealous nature of the software market.
The VM Wars
For example, the arrival of feasible byte-code-driven virtual machines is a wonderful thing: so what if language X is out of date? We can start using language W on Monday because it compiles down to the same bytecode. Platform Z has crap support for multiple cores? Hey, that’s cool: the VM we target also runs on another platform with better support for multi-core hardware. Sure, we’re still stuck with a shit framework, but hey: gift, horse, mouth. Virtual machines, while not fixing The Semantic Problem discussed by Gronlund, are a big step forward on other fronts.
How could the industry possibly screw such a theoretically wonderful idea up? Enter Sun and Microsoft with the JVM and .NET, respectively. Two entirely incompatible virtual machines with separate bytecode instructions and standard libraries. Brilliant. So now we all have to make a choice and hope that it’s the right one or we’re back to inventing wheels when the JVM is no longer supported by Sun, or .NET is superseded by an instruction set only feasibly implemented on specific hardware configurations. Even if both continue to exist forever and a day, the choice is still largely mutually exclusive: if you pick Java, your options for reuse are limited to Java solutions. If you pick .NET, you’re in the same boat in a different creek with the familiar uneasiness one feels in the absence of paddles in such a situation.
I wouldn’t for a second advocate blind homogeneity, but the two virtual machines are so god damn similar at a semantic level, they might as well be the same platform. It’s for entirely avoidable reasons like this VM divide that we’re doomed to the software development dark ages – and all that without even mentioning the words “software patent”. My prediction is that there will never be a magical breakthrough while we’re throwing away everything we produce every few years. We’ll be too busy fixing yesterday’s problem with today’s technology to ever think about a better way to approach the process as a whole. Even if we improve the process, we’re still doomed to the details, because – again – you can’t abstract away details.
No “Super Compiler”
Clearly, I’m a sceptic of the super compiler that Gronlund predicts (even when looking far, far into the future as he does), but I do see highly configurable software systems filling specific niches: systems like Drupal and Joomla are already filling this niche on the web development front. For bog-standard content-managed web sites, you can hand Drupal off to a half-trained monkey, slap a pretty theme on it, and you really can’t go wrong. However, even with such systems you are limited to the constraints of the systems themselves: the moment you want your site to do something unsupported out-of-the-box, the moment you want a certain feature to behave slightly differently, you’re back in the land of programmers. Further, what happens should PHP (the technology on which Drupal is built) disappear? Is Drupal then to be simply rebuilt in another language on another platform? Even if this is unlikely to happen in the real world: on a hypothetical level, why the hell should we need to do this?
Commercialization, Legislation and a Dull Sense of Deja VuÂ
To make matters worse, software development is outrageously commercialized. Even if we assume that a massive breakthrough in the software development tool set will eventually surface, you can bet it will be so riddled with patents that nobody will be able to legally use it anyway. It’s sad, but it’s the brutal truth. I don’t mean to be overly gloomy with this post: I love software development, and the possibilities for our profession are simply endless. It’s because I love my job that I look to the future with such pessimism: it’s unrealistic to think that – with the industry’s current approach to software development – we are going to see anything more than incremental improvement.
The more you try something new to the software development scene, the more it feels like we’re all doing a slightly different dance to the same bad song. I guess all we can do for now is keep on trying new things and hope somebody, somewhere stumbles upon Brooks’ silver bullet in the process …
Categories: Compilers, Languages, Software Development |
4 Comments
November 3rd, 2007
Writing a compiler is no simple undertaking. I’ve spent a few years on and off (mostly with the Python source code) trying to understand compiler internals on a practical level, and I’m only really only just beginning to learn enough to be able to manage some of the basics. So, in this article I present a detailed discussion of a simple compiler implementation that targets the Java Virtual Machine. I’ve been wanting to write a tutorial like this for a few months, because it’s exactly the sort of thing I wish I could have read a two or three years ago. So this is my little gift to all the other aspiring compiler nerds out there struggling (like me!) with the learning curve of compiler construction
Prerequisites
You’ll probably need at least a fundamental understanding of Scala and/or Java to be able to follow the code samples in this article, but I promise to try and keep the code as simple as possible. I’d also recommend that you have at least a high-level understanding of how compilers tend to be structured internally i.e. if you don’t know what a “scanner” or a “parser” is, you’re going to get lost very quickly.
Obviously, you’ll want Scala installed if you plan to run the code. You’ll also want some sort of *nix toolchain available if you plan on using the simple build scripts I’ve provided. It’s not that hard to compile it by hand if you’re stuck on Windows or something like that.
Scala, the language
I haven’t covered Scala a whole lot on this blog. To be honest, I only started using Scala about two weeks ago. I’m already falling in love with it – you can think of it as a more expressive Java that straddles the fence the computing industry seems to have erected between functional and object-oriented languages. Yes, yes, there’s classes in Ocaml, the other functional/OO language you’ll hear me ranting about on this blog – but even in Ocaml, OOP is generally shunned in favour of a functional approach. Scala, on the other hand, is a beautiful blend of the two. I won’t go into the details of some of the more elegant aspects of Scala, but here’s just a few little things about Scala that I find especially nice:
- Scala is statically typed, but the excessive verbosity of Java is a thing of the past thanks to Scala’s type inferencing
- Scala has closures and anonymous methods
- Scala has what I can only describe as anonymous types: Neil Bartlett called this statically-checked duck typing
- Scala types can be aliased
- Scala code can use any Java class
- If some care is taken, Java code can easily use Scala classes.
Scala, the standard library
Scala comes with its own standard library (on top of the standard Java library) containing a slew of useful components. The Scala standard library comes with its own unit testing toolkit called SUnit, a database abstraction layer (think Scalafied JDBC), syntactic sugar wrappers around well-known Java collection classes, concurrent programming utilities and – the bit we’re interested in – a bunch of stuff useful to compiler construction.
For more information about the Scala standard library, please check out the Scala API documentation.
Our programming language
The source language will effectively be a glorified calculator with variables. The result of the final expression evaluated is to be printed to the screen. For example, something like this:
v = 5;
t = 10;
v + 6 * t;
Would output “65″.
High-level overview of a compiler
Irrespective of what language you write it in, the structure of a compiler tends to look something like this:
- Lexical analysis or Scanning - scan the source document to produce a stream of interesting tokens
- Syntax analysis or Parsing - transform the token stream produced by the previous phase into an abstract representation of the program structure
- Semantic analysis or Type Checking - analyse the in-memory representation of the compiled program to ensure it “makes sense”
- Code generation – generate the executable code from the type-checked representation of the program
The compiler presented by this tutorial won’t have an explicit “step 3″ – the language is simple enough that it should be impossible to write a syntactically correct, semantically invalid program.
Our abstract syntax tree
Our parser will be transforming the token sequence generated by the scanner in phase 1 to produce what’s called an Abstract Syntax Tree – a representation of the program as a structured tree. There’s plenty of literature available on ASTs out in the wild, so I’ll gloss over the details and provide you with the relevant Scala code for declaring the nodes in our tree:
abstract class Expr
case class Add(l: Expr, r: Expr) extends Expr
case class Sub(l: Expr, r: Expr) extends Expr
case class Mul(l: Expr, r: Expr) extends Expr
case class Div(l: Expr, r: Expr) extends Expr
case class Num(value: int) extends Expr
case class Store(id: String, r: Expr) extends Expr
case class Load(id: String) extends Expr
case class Program(body: List[Expr]) extends Expr
So for a simple example, imagine we have a simple program in our language that looks something like this:
3 + 5; 4 * 6 - 2;
We could manually express this as an AST using the above classes as follows:
Program(
List(
Add(Num(3), Num(5)),
Sub(
Mul(Num(4), Num(6)),
Num(2)
)
)
)
Of course, building ASTs like this isn’t quite what we’re after. In practice, we break AST construction down into a set of simple rules using Scala’s parser combinators. But more on that later.
Finally, you will want to note that the concrete elements of the AST are implemented as Scala case classes. Case classes will allow us to use Scala’s pattern matching features to inspect the AST in the code generation phase. This makes it really, really easy conceptually to see how the code should be generated.
The standard lexer
Scala comes with a standard lexical analysis class (StdLexical) which is capable of producing tokens for a simple Scala-like language. More than enough for our particular needs here. StdLexical knows how to parse numeric values, so all we need to do is tell the scanner which delimiters are important (i.e. a few simple arithmetic operators):
type Tokens = StdLexical
val lexical = new StdLexical
lexical.delimiters ++= Set("(", ")", "+", "-", "*", "/", ";")
That’s all the Scala code we need to write to configure our lexical analyser! Assuming your language doesn’t do anything too weird, StdLexical will likely be able to take care of the rest of the scanning process for you.
Pseudo-EBNF using parser combinators
EBNF is the notation de rigeur for describing programming language syntax in the compiler construction world. In theory, once you have written an EBNF description of your programming language syntax, writing a parser for it should be reasonably simple: you simply transcribe the EBNF into your language of choice and away you go. Unfortunately it’s not always that simple in practice, so people resort to using tools like yacc or bison to generate their parsers using EBNF-esque pattern-matching. The downside to these tools is that most have a fairly big learning curve.
Along comes parser combinators. Using combinators, it suddenly becomes possible to use EBNF-like rules in the compiler implementation language – a sort of DSL for parsers, if you like. Combinators appear to be especially popular in functional languages like Haskell (via Parsec) – although I’m still not sure what’s intrinsically special about functional languages that would make them more appropriate for combinators. If anybody could clear that up for more it would be much appreciated. In any case, Scala provides a parser combinator library as part of its standard API. Here’s the Scala code describing our simple little language, which also acts as the parser for our language:
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))def expr = assign | simpleExpr
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
def term = factor * (
"*" ^^ ((x: Expr, y: Expr) => Mul(x, y))
| "/" ^^ ((x: Expr, y: Expr) => Div(x, y))
)
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
Please note that, although I haven’t been explicit about return types for all of these methods they all return a Parser[Expr] – that is, a parser for an element of our AST. In fact, pretty much every method call you see here (including the operators!) is returning a Parser of some sort. If it’s not obvious, parser combinators – despite the scary name – have a very simple task: that of chaining simple parsers together to form a slightly more complex parser. These slightly more complex parsers can then be combined together as well, to form a slightly more complex parser again. Eventually you wind up with a tree of parsers that match one-to-one with the rules you provide in your combinator “grammar”.
It’s also interesting to note here that precedence is actually being enforced using the nested parsing rules: a factor will be parsed before any other rules because the factor rule is nested deeper in the parsing hierarchy than any of the others.
Now it probably goes without saying, but there’s a lot going on under the hood here. I’ll spend the next few sections trying to explain just exactly what all this actually means, but before we start it’s important that you understand …
Scala operators are just method calls
Many of the operators you see in the above source code listing are actually method calls on the objects preceding them. For example:
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
Could actually be rewritten thus:
def assign = ident.~(keyword("=").~(expr.^^(flatten2(Store))))
Obviously the first example is much more readable, but knowing this will make understanding what’s going on in the above code examples just that little bit easier.
Another bit of Scala magic: the parser combinators know to implicitly convert String arguments into a UnitParser using the keyword method. keyword accepts a string argument – the token it “expects” – and then discards the result.
As a side note, methods with more traditional names can be used as operators too:
import java.util.ArrayList
val list = new ArrayList
list add "Test" // the same as list.add("Test")
Finally, Scala operators – being methods – can be trivially overridden:
class Monkey {
var numBananas = 0
def +=(numBananas: int): unit = this.numBananas += numBananas
}
val m = new Monkey
Console.println(m.numBananas)
m += 5
Console.println(m.numBananas)
The “sequence”, “one-or-more” and “apply” combinators
Let’s take a look at the first rule in our program.
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))
The parser for this rule is expressed by this fragment:
def program = ((expr ~ ";")+)
Which, in plain old English, means: “a program consists of one or more sequences of expr and a semi-colon.”. Those of you familiar with regular expressions will probably have already guessed that the + combinator means “one or more”. The ~ combinator has a slightly more subtle meaning: it’s used to combine parsers together in a sequence. That is, within the context of this rule, once we have finished parsing an expr we would expect to find a literal semi-colon. If we do not, it’s a syntax error.
The final operator we’re covering here is the ^^ operator, which takes the result of the previous parser, applies a function to it, and returns the result (which should be an element of our AST) . Let’s take a look at the whole rule again:
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))
So the result of the one-or-more combinator is a list of expressions (List[Expr]). If parsing of the one-or-many rule succeeds, the ^^ takes the result (the said list of expressions) and passes it to the function passed as the operand on the right. In this case, we’re wrapping the list of expressions in a Program AST element.
So that should really be all you need to know about the ~, + and ^^ combinators. Please note that the annoying excess of brackets I use here is more for clarity than anything else – you could rewrite this as:
def program = (expr ~ ";" +) ^^ ((e: List[Expr]) => Program(e))
The “alternative” combinator
Take the next rule in our parser:
def expr = assign | simpleExpr
A relatively simple rule compared to the previous one. The only thing of note here, really, is the | operator, which creates a parser that can parse either of its operands: in this case, an assign or a simpleExpr. You can specify as many alternatives as you want. e.g.
def expr = assign | simpleExpr | ifExpr | functionDef | classDef | lambda
The way it works is by simply attempting to parse the leftmost rule. If that fails, it tries the next rule along. If that fails, it tries the next one along again and so on and so forth, until there are no more alternatives (in which case we have a syntax error) or one of the rules are successfully parsed. The net effect is similar to a logical “or”.
Something else of note is that we’re not using the apply combinator here. We simply don’t need to in this case, since both assign and simpleExpr both return a Parser[Expr], so there’s no need to convert the result of the parse into an AST element.
Simplifying your code with flatten[2-5]
The next rule – the “variable assignment” rule – appears to be pretty straightforward:
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
You’ve seen ~ and ^^ before – we’re just parsing a sequence and applying a function. But what’s flatten2?
The Scala parser combinator library includes a utility class called ImplicitConversions. This includes a couple of functions useful for writing cleaner combinators, including flatten2. Calling flatten2 here returns a function that takes the two arguments resulting from the sequence (the ident String and the expr Expr) and passes them to our AST Store constructor. Rewriting this using typical anonymous methods isn’t quite so clean:
def assign = ident ~ "=" ~ expr ^^ ((id: String, e: Expr) => Store(id, e))
It’s still readable, but still obviously much cleaner in the first example. Feel free to use either approach.
If you need to use flatten with more than two arguments, the library also provides flatten3, flatten4 and flatten5.
(Note: It should also be possible to have the flatten* calls happening implicitly, but I haven’t quite worked out how yet)
The “zero-or-more with separator” combinator
The next combinator we’re going to cover is similar to the one-or-more combinator, with a slight twist. First, let’s take a look at the next parsing rule:
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
Let’s get rid of the application combinators and look at the core rule to simplify things:
term * ("+" | "-")
That should be much easier to read. Now, you might initially think that this rule can be described as “a simpleExpr is zero or more terms followed by a plus or minus”. However, that’s not the case. In actual fact, it means: “a simpleExpr is zero or more terms interleaved by a plus or minus”. In order to parse the former, it would need to be expressed as something like:
(term*) ~ ("+" | "-")
But you probably don’t want that, and I digress
Let’s take another look at the original rule:
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
If there is a single term, it will be returned as the result for simpleExpr. If there are multiple terms, separated by “+” or “-” literals, they will be folded into a single Expr by recursively parsing the terms into Add or Sub AST nodes depending on which separator is encountered at each step. For example, given this source code:
5 + 3 - 2;
First, the parser will see a term, which evaluates a Num:
Num(5)
Next, the parser will see the literal “+”, and wraps the Num we just parsed in an Add with the next evaluated term (another Num):
Add(Num(5), Num(3))
Finally, the parser will see the literal “-” before wrapping the previous Add in a Sub with the next evaluated term (again, another Num):
Sub(Add(Num(5), Num(3)), Num(2))
I hope this clears up a potentially hairy construct. It’s really pretty simple once you get used to it, just keep at it.
More of the same
The next rule is exactly the same as the previous rule, except it expects factors (instead of terms) interleaved by either “*” or “/” (instead of “+” and “-”), and returns Mul and Div AST nodes (instead of Add and Sub nodes).
def term = factor * (
"*" ^^ ((x: Expr, y: Expr) => Mul(x, y))
| "/" ^^ ((x: Expr, y: Expr) => Div(x, y))
)
No further explanation should be necessary, but feel free to query it in the comments if you have any problems.
Parsing numbers and variable identifiers
Earlier I discussed the fact that parser combinators (and, indeed, parsers in general) simply take rules for simple parsers and combine them together to make more complex parsers. The factor rule is the simplest of all the parsers in terms of complexity, although the syntax expressing it is a little daunting:
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
The first thing to note is that I’ve explicitly stated the return type: because our parser is recursive, we must explicitly tell the compiler what our return type is going to be in the most fundamental element of our compiler. Now let’s break that rule down into more manageable chunks for discussion:
"(" ~ expr ~ ")"
This parser forces expressions in brackets to be parsed before anything else. As soon as a factor starting with a bracket is found, parsing starts near the top level again at the expr rule. Once the inner expr has been parsed, we expect a closing bracket. Easy.
ident ^^ ((s: String) => Load(s))
The ident method is provided by the Scala parser combinator library, which can handle typical variable names. If you need to handle any weird and wonderful characters, you may need to write your own.
Anyway, this simple rule parses a variable identifier (expressed as a String) and wraps it in an AST Load node. The only time that identifiers are not wrapped in an AST Load is when we’re doing assignment (see assign), where we use a Store node instead. The difference between Load and Store is semantically important to the code generator. I’ll discuss that more in the next part of this tutorial.
numericLit ^^ ((s: String) => Num(s.toInt))
As above, numericLit is provided by the Scala parser combinator library. It can parse simple numeric values (including floating point numbers, I believe). It returns a string expression of the number, which we then convert to an int and pass to the Num constructor. All numeric literals in our program will be wrapped in Num AST nodes.
Looking at the original factor rule again:
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
It doesn’t look so daunting any more. In simple terms, a factor is any expression wrapped in brackets, a variable name, or a number.
Code generation
Just to get something on-screen, let’s generate some simple bytecode:
def generateCode(e: Expr): String = e match {
case Num(v) => "push " + v + "n"
case Ident(id) => pushString(id) + "derefn"
case Mul(l, r) => generateCode(r) + generateCode(l) + "muln"
case Div(l, r) => generateCode(r) + generateCode(l) + "divn"
case Add(l, r) => generateCode(r) + generateCode(l) + "addn"
case Sub(l, r) => generateCode(r) + generateCode(l) + "subn"
case Assign(id, e) => generateCode(e) + pushString(id) + "bindn"
case Program(body) => body map(generateCode(_)) mkString ""
}
def pushString(s: String): String = "push '" + s + "'n"
The code generation method accepts an AST node (an Expr) and uses pattern matching to determine what code should be generated. This pseudo-bytecode is for a stack-based virtual machine, similar to the JVM. I’m not going to go into the details of how it works, because it’s quite self explanatory: effectively we walk the AST generated in the parse phase and generate simple pseudo-bytecode instructions depending on the type of the AST node. Arguments to operations like add, sub, mul & div are passed in reverse order. When the node we’re processing contains child nodes, we generate code for them through simple recursion.
Hooking the lexer up to the parser and starting compilation
Finally, to kick of the compilation process we use the following code:
program(new lexical.Scanner(Console.readLine())) match {
case Success(e, _) => Console.println(generateCode(e))
case Failure(msg, _) => Console.println("[FAILURE] " + msg)
case Error(msg, _) => Console.println("[ERROR] " + msg)
}
Here we simply instantiate a new lexical.Scanner instance (recall that lexical is an instance of StdLexical from the Scala standard library). Our call to program here actually returns the Parser[Expr] combinator constructed from our set of parsing rules, which then has its apply method called with the scanner as its one and only argument. It is the apply() call which starts the actual parsing of the input. This is possible thanks to functor-like syntatic sugar made possible by Scala conventions.
Once the Parser object has finished the parsing process, a ParseResult case class is returned. We use pattern matching to determine the outcome of the parsing process: ParseResult can be an instance of any one of Success, Failure or Error. Success obviously means that parsing completed successfully. The other two obviously indicate parsing failures and other problems in the combinators. Assuming parsing completes successfully, the root node of the AST (a Program instance in our parser) is provided as part of the Success case class. We then simply generate code for the AST and print it to the screen.
Click here to download the source code for part 1. Just for kicks, I’ve included a simple Python “virtual machine” in the download below which takes the pseudo-bytecode generated by this compiler and “executes” it in case you want to test it out. You can run the compile/execute toolchain using the following command:
script/build; script/run "v = 1; n = 2; v + n * 5;"
Thanks
This massive post was in no small part inspired by this document, written by Adriaan Moors. I strongly recommend you give it a read for a more formal introduction to Scala’s parser combinators by somebody who’s probably been doing it a lot longer than I have.
Part 2
Thanks for taking the time to read this tutorial. If you enjoyed it, drop me a line with some suggestions and/or improvements. I’m always open to input. In part 2 I’ll be discussing code generation with BCEL and providing the source code to the final, JVM-targetted compiler discussed in both tutorials. See you next time!
UPDATE: No part 2 yet, but part 1.5 is here!
Categories: Compiler Construction with Scala and BCEL, Compilers, Scala, Software Development |
6 Comments
June 15th, 2007
My Introduction to Haskell
A few years ago when I was studying for my degree at university, I took a class on functional programming using the Haskell programming language. It was very instructional, if a little abrupt. I struggled with the language initially, despite being very comfortable with a number of other (imperative) languages. Once it started to click, however, I started to get a glimpse of the power must inevitably draw many toward the functional paradigm.
The project we were given was to build on an existing compiler (written in Haskell) for a simple, strictly-typed programming language devised by the lecturer. Once the lexer & parser had been extended with the new features, we also had to generate custom bytecode for the new features. Finally, we had to write an interpreter for the bytecode in C or Java. Compiler development was something I had always felt was out of my reach but the more I toyed with the code, the more comfortable I became with Haskell’s fairly alien syntax and – in turn – with extending the compiler itself.
The Joy of the Functional Paradigm
Within an hour or two, my extensions to the mini-language meant that I could now assign values to variables. Another few hours, and I had a for loop. Another, and I had enumerations and constants. The byte code generator, however, required me to step out of the mindset I had been in for half of the day: How do I now turn the AST generated by the parser into bytecode?
By this stage I was becoming comfortable enough with Haskell that I was able to work out the basics from the code used for the original language constructs. I was beginning to get a rough idea by the end of the first day and another day or two later, the project was finished. Thinking about it now, this was perhaps the only university unit that I really, really enjoyed. It was fun. Haskell and the constructs of the parser framework we were using were powerful tools. I had achieved something completely new and exciting using a language I was almost totally unfamiliar with.
The Return to Functional Languages: Ocaml
Fast forward maybe three years. I haven’t really touched Haskell since. Sure, I tried – but without a practical application for it there was no real drive. The passion I that had grown for compilers led me to the Python source code and, eventually, to PEP 341 where I was able to scratch a long-standing itch in the form of the try/except, try/finally statements. Due to the recent introduction of an AST, the changes were generally limited to the grammar and the AST and – although satisfying – were relatively trivial to implement.
As far as code contributions for Python go, I’m sure that I just need more practice and experience with the source. However, I still long to test the waters with functional languages again. Haskell, while it proved to be powerful and fun, lacks the supporting libraries to make useful (in the short term, anyway) only to academics and those willing to slog it out writing their own support code. Scheme was intriguing, but I’m still not sure which implementation I should be using nor did it have a useful library. Then I started hearing about Ocaml. A powerful functional programming language with support for imperative and/or object-oriented programming, Ocaml also sports a decent (if a little bare and disorganized) framework for all the basics.
A Lack of Tutorials
Documentation for Ocaml’s libraries exist, but tutorials for learning Ocaml properly are few and far between. http://www.ocaml-tutorial.org offers lots of information for those patient enough to read it, but I found it a little hard going.Further, there was little in the way of web, network/socket, graphics and UI programming.
The Big Tutorial Idea
I’m going to try and learn Ocaml myself using whatever resources I can find and hopefully distill the information and knowledge I come across in an easy-to-follow manner. Obviously I’ll be learning as I go, so the more jaded Ocaml and functional programmers should certainly point out the foolish errors of my ways.
Eventually I’d like to compile these posts into a proper tutorial for newcomers to Ocaml – although not necessarily newcomers to programming. From my limited experience with Ocaml, I can already see it’s a powerful language with much to offer. Keep an eye out for part 1 of TMHO later next week! Any suggestions/comments?
Categories: Compilers, Ocaml, Software Development, TMHOO |
5 Comments
