Computer Science Canada

Writing a parser in C++

Author:  md [ Sat Oct 10, 2009 12:21 am ]
Post subject:  Writing a parser in C++

As part of a project I've got going right now I've written a scanner/parser for the RedCode assembly language ( And as I have it working (after very very preliminary testing...) I figured I would share it with as an example, and possibly inspire others to do something similar.

The code is available from my mercurial server ( as a C++ eclipse project, and as a tarball at Unfortunately I haven't bothered to write a makefile for it, so if you don't use eclipse you'll have to write your own or use an automake tool. For those who just want to look at the code it is also available through your web browser at I've made a branch, so the code will remain stable for a while as I continue to work on the Trunk.

The code consists of 5 major parts: a set of tokens, a scanner to read a file and return tokens, a finite state machine (FSM) to match some of the tokens, a parser to build a RedCode program construct, and the RedCode program construct itself. If there are questiosn about the code (which is not well documented yet...) post 'em here and I'll do my best to answer; right now I'm a wee bit tired to explain it in any more detail then that Razz

[edit] Fixed broken links which a surprising number of people are following to point to the correct place

Author:  Clayton [ Sun Oct 11, 2009 8:40 pm ]
Post subject:  RE:Writing a parser in C++

Your states! They make my eyes bleed. Is there really no better way of handling them?

Author:  apomb [ Tue Oct 13, 2009 9:27 am ]
Post subject:  RE:Writing a parser in C++

Is this a project for school? or work? or just a personal project? I don't know enough about parsers to ask specific questions, but that's very impressive work indeed.

Author:  Tony [ Tue Oct 13, 2009 9:38 am ]
Post subject:  RE:Writing a parser in C++


Redcode is the name of the programming language used in the game Core War.

Author:  md [ Wed Oct 14, 2009 8:17 pm ]
Post subject:  RE:Writing a parser in C++

For fun, and there are a couple of bugs in it currently - a memory leak for one (see if you can find it!)

The FSM could probably be done better (as in more readable) but certainly not as efficiently. It's only unreasonable because I chose to recognise alll the operator and operator modifiers with the FSM instead of a seperate table lookup after the fact. The later aproach is shorter line-wise, but makes slightly more complicated code. The finite state machine is actually absurdly simple to debug.

Author:  mirhagk [ Mon Feb 08, 2010 2:23 pm ]
Post subject:  RE:Writing a parser in C++

i would just like to say thank you. I know that this is kinda a necro but i actually am currently working on a parser for school so now i have something to kinda see how a parser actually works.

Author:  md [ Mon Feb 08, 2010 4:53 pm ]
Post subject:  RE:Writing a parser in C++

You're most welcome.

Unfortunately I haven't done much more work on that particular project due to time constraints; however I am reasonably sure that what I have already written is at least free of bugs.

You might find to be a better reference, as there were a couple of bug fixes after the version.

[edit] Fixed broken link (see above and below!)

Author:  md [ Sat Feb 12, 2011 12:10 am ]
Post subject:  RE:Writing a parser in C++

As it seems that people still find this interesting and are looking for the code, I've re-hosted it as a mercurial repository here:

Author:  QuantumPhysics [ Thu Aug 30, 2012 12:44 pm ]
Post subject:  RE:Writing a parser in C++

The black mage has casted an evil Resurrection spell on this post.

I'm sorry but, would you happen to tell me where exactly the link is for the download? For some reason i cannot see it. I am really interested in see'ing the source code.

Author:  md [ Thu Aug 30, 2012 9:18 pm ]
Post subject:  Re: Writing a parser in C++

Seems that on one of my re-installs I disabled the non-passworded access to my repos and removed this one anyway.

Here's an archive of the source, untouched since I last looked at it.

Note that as compsci limits file name extensions it's not actually a ZIP file, but a bz2'd tar archive. either rename to tar.bz2 or use a sane tool that doesn't care about file names.