Adventures in Language Design

Some time back, I ran across this really nice set of tutorials by Dr. Jack Crenshaw on how to build a compiler. He basically introduces top-down recursive descent with the idea that a separate assembler will handle the grubby parts of object code file formats. It's cool and inspiring and all, but it gets rather irritating that we're constantly using single-letter words. About half-way through, there's a bit of a treatise on why people shouldn't have to mess with bottom-up parsing methods. He says they're too complicated, and anyway, recursive descent code is almost free. This is especially true if you're generating code for a stack machine, or something with few enough registers as to seem like a stack machine. His original target was actually the Motorola 68000 series, which has eight data registers and eight address registers--enough for most purposes--but his goal did not (seem to) include teaching people how to perform intelligent register allocation.

I am personally interested in designing a programming language for the express purpose of scratching some itches. It's one thing to have a definition for the language, but it's something else to have something you can play around with and test your theories about what language constructs are preferable. I'll confess now that I'm mainly interested in reducing the brainpower spent on getting good code while making it laborious to produce nonsense. I also want to try to apply some ideas from the field of linguistics.

This means I have some theories about what syntax should be available as primitive language, and also what kinds of things we should be able to give names to for later reference. I also believe that most common programming errors are caused by oversights which the language makes easy, so I'll try to prevent oversights like uninitialized variables by demanding that they be initialized at the point of introduction. Failure to return a value from a function can be prevented by guaranteeing that all paths through the function set the return value, and preferably only once. Case fall-though shall not be the default, but will require special syntax. (Indeed, it need not be present in the initial version.) Algorithms involving repetition don't always fit the standard molds, especially when there are two or more termination conditions. I want to give the vocabulary surrounding repetition a more complete set of operational semantics, but without opening Pandora's Goto Box. Also, there are some ideas I have about how programming constructs are frequently misused. As far as possible, I want to make such behavior into an error.

So here's where I stand: I have a working lexical analyzer with one flaw: it doesn't recognize reserved words yet. I don't particularly relish writing a reserved-word recognizer. I'd rather let the computer do it. I'm willing to teach it how. I have already taught it how to write the operator scanner so that I can scan for new multi-character operators without writing any new code.

I was influenced by the observation that words and operators can be thought of as individual glyphs at a slightly higher level, so it made sense to isolate the concern of scanning them into a module. Having that, I know I can build with all the same recursive-descent ideas, except that instead of descending all the way down to the individual character as a distributed feature of the parser, I simply ask to get the next token. This way, my lexical analyser can be designed and maintained in isolation from the rest of the language.

For the moment, let's assume that the reserved-word recognition problem is solved. Then the next part is making actual programs. I've seen from Dr. Crenshaw's work that we don't have to worry about very big programs at any given time. We can focus on toy problems and work our way up. Eventually, we have a complete, functioning programming language.

The basic plan seems to be to codify and then program one production rule at a time. That means having some rules in mind. Like Dr. Crenshaw, it might be nice to start with algebraic expressions on the integers, then add variables and assignment.

One of the real issues is output. I would tend toward generating code for NASM. This at least is usable for actual execution. However, I'm a stickler for trying to get something out of the compiled code. I want to see progress. So before I start down the garden path, I want to make sure I can get something displayed. In the very short term, I can hard-code a call to "printf" in the C library. Longer-term, I have other plans. For now, this will work.

I'll post more when I get more working.