Compiler Part 3 - Compiler Design Overview

Part 1: Introduction

Part 2: Compilers, Transpilers and Interpreters

What Are We Writing?

A calculator. Sort of. A compiler for a super simple mathematical language.

We are, at least for now, going to avoid the complications of dealing with strings and characters and focus on numbers. Not just numbers, whole numbers. Integers to be specific. This is the only “type” we’ll have in our system, for now.

Adding new types isn't exactly hard, and indeed is desirable, but makes our design much more complicated than need-be at this stage in the game.

Stages of Compilation

Whether you are building an interpreter or a compiler most of the steps remain the same. The most common, basic steps are:

1. Lexical Analysis
2. Parsing
3. Semantic Analysis
4. Optimization
5. Code Generation

We’ll attack each of these steps one at a time.

Overview: Lexical Analysis

We've all written code before. It’s a “human readable” representation of what we want our programs to do. We need to take something that is human readable and make it something a computer can understand. The first step, is lexical analysis.

The short of it is, we have to scan through the text and report what was found. That is, we have to pick out all the different unique parts of our language and assign an identifier to them called a token. Each token is associated with a lexeme, the literal string of characters, for handling in the next stage. Literals (numbers, strings, etc), keywords and operators are examples of the kind of things we identify in this step.

For error reporting, we should also provide the position at which the token was found.

Overview: Parsing

In this stage, also called syntactic analysis, we start to give meaning to the tokens we’ve found. Each token is represented by an object and placed into a tree data structure.

The language syntax is verified at this stage. We want to ensure that the order of what we’ve received is correct. In LISP, an expression takes the form of an opening bracket, an operator or function, followed by any number of arguments and a closing bracket. Parsing ensures that these requirements are met.

Overview: Semantic Analysis

Next, we check to ensure the semantics of our language are met. If a variable has been declared as an integer but assigned a string, we have a problem. The number of arguments of a function call not matching the number of parameters of the function signature is another semantic error.

Semantic Analysis is a;sp concerned with things like variable scope and generates errors if a variable is used that hasn't been declared.

Overview: Optimization

This stage does what it says. It optimizes the output, usually for speed or size (memory consumption). I won’t be covering much of this in this series but an easy example would be assigning a variable the result of an expression rather than the expression itself.

For example, what if we assign the variable A the statement ‘2 + 3’. Adding two static numbers could require several steps in code generation. This can be optimized by pre-calculating the result and assigning it in the generated code, simplifying the statement to ‘A = 5’.

Overview: Code Generation

This is the final stage. It outputs the lower level code we want to emit. A Java compiler would output Java bytecode. A C compiler might output assembly. An assembler outputs machine code.

Moving On...

Bear in mind that there can be more or less steps in your compiler. A C compiler, for example, also has a pre-processing step. Some steps, like parsing and semantic analysis, can be wrapped together into a single step. There is a lot to compiler design. For a broader overview, check out this Wikipedia page: Compilers.

It would be great if we could dive into writing a compiler now. Unfortunately, that would be folly. Without knowing what our language requires we’d be at a loss as to what to actually write. Without a set of rules to follow we’d have no direction.

Next up: the language specification!

Compiler Part 2: Compiling, Transpiling and Interpreting

Part 1 served as an introduction to this series.

In this second post, I want to do an overview of some definitions before we dive in to the actual steps of compiling.

Compiling

Compiling is the act of taking code written in one language and translating it into a lower level language. A C compiler doesn't usually output machine code directly. Instead, it translates the C source code into assembly. The assembler takes that output and compiles it into machine code. C# and Java are translated into bytecode. Bytecode isn't transformed into machine code until it is executed by the virtual machine.

It’s important to understand this distinction.

Compiling often consists of using an intermediate representation (IR) or intermediate language. Assembly is a common intermediate language. LLVM has an IR imaginatively called LLVM IR. C can also act as an intermediate language.

Transpiling

Transpiling, by contrast, is transforming code from one language to another language of equal or higher level. Translating Go to Javascript is an example of this.

Do not confuse this with what languages like Scala or Clojure do. Both of these languages are compiled directly to Java bytecode and use the JVM to execute their code. Neither are considered to be transpiled because Java bytecode is a lower level of abstraction. Were they translated into Java first prior to being compile to bytecode then they might be considered transpiled languages.

Translating Go or Lisp to C isn't really transpiling either, though it rides a fine line. C is a lower level language although it is certainly a higher level language than assembly.

Interpreting

Interpreters are usually associated with scripting. Rather than translating a language into another language or IR the language is, typically, interpreted directly.

In some cases this means, quite literally, scanning the code and interpreting it on the fly and halting the moment something isn't right. In other cases, it means scanning through the entire code, validating it and then executing it from the internal tree data structure holding all the information.

In a sense, an interpreter of this kind must “compile” the script or source code each time it is run, making it much slower. This is because it needs to do all the steps a compiler does each time the script is executed rather than doing that process only once.

Many modern interpreters don’t typically do this, however. You may want to investigate Just In Time (JIT) compiling if you’re interested in the details. The short and simple version is that the script is interpreted only once, just like a compiler, and is stored in some kind of intermediate form so it can be loaded faster. This process also allows the designers to incorporate optimizations to further speed up code.

Binaries, Compiling

The objective of compilers is often to create an executable binary, or at least some kind of object  the machine can read and execute.

It’s not so simple to just create machine code. Compiling is actually just the first step.

Here are the basic steps that GCC and Go might use to compile their source code:

C using GCC:

1. Translate C into assembly via GNU C Compiler (gcc);
2. Translate assembly into machine code via GNU Assembler (gas);
3. Link machine code with standard library and produce an architecture specific binary via the GNU Linker (ld).

Go using Go Compiler on x86-32:

1. Translate Go into assembly via Go compiler (8g);
2. Translate assembly into machine code via Plan 9 Assembler (8a);
3. Link machine code with standard library and produce an architecture specific binary via the Plan 9 Linker (8l).

As you can see, the compiler is just one step of the process. In these articles we’ll only be dealing with step 1. Assembling and linking are well beyond the purpose of these articles.

Don’t fret though! Our compiler will produce an executable binary!

Next

Now that we've taken care of some definitions and understand the process to making executable code we can look at a compiler in a little more detail in Part 3.

Compiler Part 1: Introduction to Writing a Compiler in Pure Go

Introduction

I've long been interested in learning how a compiler works. Cryptic compiler messages and odd behaviours have always baffled me. I’ve never quite understood how optimizations are done or how it is a compiler knows what I've done wrong.

When I first decided it was time to learn how to write a compiler I found out that there are a lot of terms and acronyms not often used outside of the discipline. What was an SLR or LALR parser? What in the heck is a lexeme or finite automata? What is recursive-descent parsing? What is an AST?

It can be pretty overwhelming at first.

The largest hurdle I found was that most online courses, tutorials and other learning materials on the Internet don’t teach you how to write a compiler or interpreter. Correction; they don’t teach you how to build one from scratch but provide you an overarching, top-down approach, relying on existing tools to help you do the job. This is because building a compiler is a pretty big job and it would be nigh impossible to cover everything in a single semester. I can’t fault anyone for that.

That said, I felt these tools skipped over what I think are valuable lessons and information. I wanted more.

So, I want to take you on a tour of my personal journey through learning how to write a compiler.

Bare in mind, I’m not a professional programmer nor am I finished figuring everything out. That said, I've discovered so many wonderful things that I can’t help but want to share them in the hopes they’ll help you discover your own path. After all, it’s why you’re here, isn't it?

Credit Where Credit is Due

Calc is an original work and while all the code for this project has been hand written there can be no denying parallels and similarities to Go and Go parser package in the standard library. In learning to write a compiler I have often referenced those works when I got stuck. Any and all credit must go to the Go developers for any code that resembles any of their collective works. You can find the source code for the Go compiler at golang.org.

Prerequisites

As much as I’d like it to be, this series is not really intended for novice programmers. It assumes you have some programming experience and are already familiar with the Go programming language. Therefore, it is targeted at more of an intermediate programmer.

While I think a more novice programmer might be able to follow the articles I will make no attempt to explain Go or any code not directly related to compiling. There are several utility functions which I will point out but since they aren't explicitly about compiling I won’t explain them.

Tools

Compiler design is a component, or perhaps companion, to language design. It’s a massive topic and each step of the compiler is a lesson in of itself.

There are a couple tools out there that people use to simplify or expedite the process of building a compiler. Each tool tends to focus on one particular step of the process. I am telling you about these tools so that you know that they exist but they are not relevant to this blog series. There are, however, many articles and classes that will teach you compiler design by using these tools.

Flex and Bison are probably the most common open source options available. Flex is based on a program called Lex, short for Lexical analysis, which is the first step of compiling. Bison is based on a program called YACC, an acronym for Yet Another Compiler Compiler, which does parsing and builds something called an abstract syntax tree.

I don't expect you to understand any of that, so don't worry. I will caution you that trying to use either of those tools without comprehending how a compiler works will be difficult in the extreme. You should prepare for some hurt.

I have actually found it more useful to skip these tools and learn the basics, first. I think building the entire compiler stack by hand provides a better solution in the long term anyway but that’s just my opinion. Take it for what you will.

The problem, for me, is that there ends up being a very serious disconnect and loss of control between each stage of compiling. It also begs the question of: “how does it actually work?”

The Solution

That’s why in this series I’m going to cover each individual component and we’re going to write code from scratch. It might take longer but I think you’ll have a stronger understanding in the end. If, after we’re done, you decide you want to use the aforementioned tools you’ll be able to do so much easier and make a more informed decision.

Stay tuned for Part 2 to start getting our feet wet!

[Edit: Updated the tools section to be more clear in its intent]

A Quick Interlude

I have vowed to be a more prolific writer this year. Indeed, I have been but not that anyone reading this blog would be able to tell!

I am currently in the midst of writing a multi-part series of articles on writing compilers. I can't really say how complete this work is because I'm honestly not sure how long it will take. I have gone back and refined what I've done so far and would say I have the first four posts in good shape. Those four posts barely crack the surface of the drafts being worked on and I have some attending code to write for the articles, too.

Regardless, good progress is being made!

I also have a much shorter series in the works on memory. In them, I talk about stack and heap memory and how they're used in Go. The ultimate purpose is to help new programmers understand how the garbage collector works and how they could possibly improve their own code to maximize efficiency.

There are a few other pieces in the works in varying degrees of completeness. It's likely I'll release one or more of them sooner rather than later since they're much smaller works.

Thanks for reading and all the shares and likes you guys have given over the years!

Changes Coming in Goncurses 0.3

*Updated  for more content*

I've been doing some more work in the month since I tagged 0.2 that, unfortunately, will introduce more breakage. I really hate to continue changing the API in backwards incompatible ways but I feel these changes are pretty necessary.

Before I get into that, though, let me introduce the most exciting change to Goncurses. So, without further adieu!

Windows Support!

 Yes, you read correctly. PDCurses support! Windows users may rejoice! ;)

I had a lot of reservations about adding PDCurses support since there seemed to be some surprisingly major incompatibilities with ncurses. I had attempted to add support almost a year ago but quickly became frustrated and decided to discard my efforts to focus on ncurses support alone. However, due to a personal need, I decided to revisit integrating PDCurses and finally met with success.

By default Goncurses will always use ncurses on Linux and MacOS X but I imagine you could also use PDCurses on those platforms as well with minimal changes. Built-in support for doing so will likely never be introduced into the library.

A New Demo/Game

I also have added a new, fun example program which features a much more complete working example of using Goncurses. It is a side-scrolling shoot-em-up called Starfield where you blast asteroids. Rather than use Go's concurrency model to handle input and drawing separately I instead used Go's time library to simulate "heartbeats" using Tickers for different timings. Updating of the background, user input (ship position) and active sprites all happen at different intervals which I can finely control. In order to achieve this I used a select statement to poll whether a 'tick' or 'heartbeat' has happened and, if not, handle any input. It was pretty fun to whip together but don't expect anything magical!

I am also in the progress of writing a feature demo but it's in a poor state right now and I don't recommend using it, yet.

Breaking Changes

• Changed NapMilliseconds to simply Nap
• Changed NL to NewLines for clarity
• Changed Getyx to CursorYX to make it clear exactly what you were getting; see below for the new YX function
• Changed Maxyx to MaxYX to match YX and CursorYX
•  DelChar was split into DelChar and MoveDelChar to make the interface more idiomatic Go and inline with the rest of the library.
• (Update) Window creation functions like Init, NewWindow, Sub and Duplicate now return pointers. Any functions which take pointers like Sub does you no longer need to take the address of the Window you are passing which may break some code. Thankfully it's a simple, if not annoying, fix.
• (Update) GetMouse now returns a MouseEvent to make it more idiomatic and sane.
• (Update) Mouse has been renamed to MouseOk
• (Update) Form and Menu functions now take the Char type as parameters to match the rest of the library.

Other Changes

• NewPad now returns a pointer and all pad related methods use a pointer receiver. This should not break/change existing code unless you needed to address a pad for some reason.
• Several Window methods had their godoc strings improved.
• The Parent Window method was fixed to work properly. Previously it always returned a Window object whether it was valid or not. Now it correctly returns nil if the window has no parent.
• (Update) Made fixes to almost all examples including: a vastly improved Window example, and the Mouse example much improved and should now work properly on all platforms.

Pending Changes

• Finish the feature demo
• (Update) Change functions/methods that return a Window to return pointers. This will help with several functions which expect to receive a Window pointer and other implementation difficulties when writing Goncurses apps. In most cases old code should not need to be updated but there will be some exceptions to that rule.

Upcoming Changes in Goncurses 0.2

I wrote and maintain an ncurses wrapper library for the Go programming language. Much like this blog, it went through a long dormancy with a few minor spurts of action while I was wrapped up in my regular job and my family. Back in June I finally tagged version 0.1.

Since that time I've implemented a fair number of changes and, as I warned at the time, a couple are somewhat breaking. The library is quite young as far as implementation goes and I want to avoid any API breaking changes if I can but I felt these were necessary.

Here is a list of changes coming up in 0.2:

Breaking Changes

• As I announced in the 0.1 release, the Print statement has now been broken up into separate Print and MovePrint functions to be more ncurses-like and each has been further separated to be more Go-like: Print,  Println, Printf, MovePrint, MovePrintln, and MovePrintf. A regex replacement ought to fix most instances but some manual editing will probably be required.
• The Character type has been changed to the shorter Char type. A simple gofmt or sed regex will easily fix any existing code.
• Several functions now use the Char type like: AttrOn, AttrOff, Box, Border,ColorPair,  etc
• Color related functions now take an int16 rather than an int (32bit) type. This is to mirror the C short type to protect against any type conversion errors.

Non-Breaking Changes

• Implemented the slk soft-keys functions.
• Added screen functions (newterm, set_term, etc).
• Implemented a StdScr function which returns the underlying stdscr window object. This was mainly a requirement to using the screen functions because there was no other way to get the stdscr but it may be useful for other situations.
• Implemented AttrSet, Standend and Standout text attribute functions.
• Implemented Timeout for input on Windows

Version Control for Go

When I first heard of version control, the most popular ones at the time were probably CVS and subversion. It seemed like every open source project used one. I understood their value for collaboration but not as a sole developer so I steered clear of them for a long while. However, they kept coming up and eventually there were some new kids on the block which were vying for attention: Git, Mercurial and Bazaar. Now, this isn't a history lesson of any kind or some kind of detailed comparison of them all. There’s plenty of that already out there. Instead, this is a short explanation of which one I chose to use when programming in Go and why.

I recall reading a book on C programming which had a section on Subversion. I tried it out. I didn't understand it. There were a lot of do’s and don’ts and I found it very intimidating. I understood the value but hated using it. Why did I have to keep track of changes anyway if I wasn't sharing the code? As time went on and I wanted to finally work on my first major project, however, I knew I was going to need a method of tracking my changes even if I didn't share my code. Too many times I'd get part way through working through a feature, realize I didn't like it or it didn't work, and realize it was too late to go back (or would take a lot to revert the changes. This left me little choice but to look at version control, again.

Fast forward a few years and I finally installed a GNU/Linux distribution that really clicked with me: Ubuntu. Long story short, I discovered Ubuntu used a version control system called Bazaar and after reading a few articles telling me how easy it was to use I decided to give it a try. A lot of mistakes later I finally figured out how to use it and I loved it. Bazaar was simple and easy to use. I really liked that the commands were clear in their purpose and the defaults felt natural. I could clone a repository into a new directory with a specific name, make changes (like a hot-fix or new feature), then merge that directory back into the main repo. and the name stuck with it! Forever I would know that a series of commits belonged to a fix or feature with that name. Loved it!

As time went on, I began to discover that Bazaar was the least favoured of the 'big three' distributed version control systems. At first this didn't matter to me but it started to make me wonder if I'd made the right choice. Indeed, Git and Mercurial both had much larger share of the market, as it were. But, Git scared the hell out of me. It had so many commands and features that it still made me feel truly lost, even after using Bazaar for close to a year.

I had just discovered Go and, perhaps naively, I thought that if I were to create a Go library I should use Google Code hosting, just like Go did! The problem being: no support for Bazaar. This was a problem I found everywhere except Launchpad and Sourceforge. No other popular code hosting site supported Bazaar. But, many of them did support Mercurial and guess what? Mercurial was just like Bazaar but, perhaps, even better.

Mercurial welcomed me with open arms! It supported the same workflow and the commands were all almost identical. Now I had a wider choice in code hosting too.

Again, as I stated already, I was discovering Go. And one thing that Go doesn't like is when sub-directories change. Let me give an example. Lets say you’re using Google Code to host your project. Let’s call the project an imaginative name. Let’s call it: foo. So you’d import that library from “code.google.com/p/foo”. Maybe I want to make a fix. What I would typically do is clone my project into a new directory called foo-name-of-fix. Now, let’s say I want to run the test framework to make sure it passes and I didn't mess something up. If I just run ‘go test’ it will import from “code.google.com/p/foo” NOT from the repo. I just created, which would be “code.google.com/p/foo-name-of-fix”. That meant, every time I made a new directory I’d need to change everything. And, make sure you change it all back before merging! A headache to be sure!

Now, this isn't the only way to do it in Mercurial. You can used named branches or tags. There are ways to overcome this problem. But again, these were workarounds and it was like “a splinter in my mind” driving me crazy. I was also aware that the most popular version control was Git.

So, I tried it. And this time I’d accumulated enough experience that I wasn't completely overwhelmed. Yes, Git has a shit-ton of features. But, you don’t need to use them. You don’t even have to know they’re there. You just need to know the basic commands and ask questions (most questions have already been asked on Stack Overflow so a quick search is usually the best thing to do) when you get stuck or if something bothers you. Because in Git, there’s almost always an answer.

I didn't immediately like Git but one thing I really liked was that named, in-directory branches were the natural way to do things. It made working with Go brutally easy. I didn't like that the name is discarded once you merge and delete said branch. I really liked that Git doesn't assume that just because you made a change to a file you want to commit it. This is a feature I didn't like at first but that I've grown to like. You can use a shortcut when committing to get the same behaviour as Mercurial and Bazaar but otherwise it will force you to manually add those files you want to commit. Very nice for cherry picking changes.

There are things I don’t like about Git. Many of it's features are reserved for corner cases and it’s still a bit overwhelming at first even though the Git community has done a tremendous job alleviating that particular problem. There are a million and one ways to do the same thing with their own pros and cons making it sometimes difficult to know which is the right solution for you. I’m not overly fond that branch names aren't attached to a commit series after merging, either.

Conclusion

I don’t want to mislead you. I still like, and use, Mercurial. As a matter of fact, my main project goncurses uses it still and I have no plans to change that. The Go project itself also uses it. I do, though, find myself missing Git sometimes and the reverse is not true when using other version control systems. I can’t really say why I find myself liking Git better but its just a feeling I get that I can’t put my finger on. Were I to make a recommendation it would be Git because it plays nicely with Go within its 'default' workflow but to be perfectly honest very similar behaviour can be done in Mercurial so you can't really go wrong with it either. It's a very close second. You just need to be aware about the issue with using cloned branches.

Depending on your workflow and habits, you may need to be flexible when using a VCS like Mercurial with Go. My needs are simple and the adjustment wasn't hard. Depending on what you’re used to, no adjustment at all may be necessary.