(Quetzalcoatl Home Page) (kdef.com) (sachiel.com) (VIC-20 Home) (Geek Home)
[History] [Things you to Do] [Future] [Design] [Development Guidelines] [Contact]

Quetzalcoatl
A Compiler Hackers' Guide
This Document: http://www.kdef.com/geek/vic/quetz/develop/chg.html Version 1.0.1
September 28, 1999 for Software Version 2.0a5
Brendan Jones

September 15, 1999: As time permits, I'll keep adding to this document. Check back regularly for updates.

Legals

Before viewing, using, modifying or copying the Quetzalcoatl Source Code be sure to read the legal note in legal.txt. If this is missing, contact me. You can send me email by clicking here.

What is Quetzalcoatl?

Queztalcoatl is a Cross Compiler for 6502 Processors. Queztalcoatl runs under Win32 and Linux. It can compile and link programs written in a subset of ANSI C, Assembler, the 1983 UPL language or any combination thereof. It is suitable for producing programs for the Commodore VIC-20 and Commodore 64. (You can run executables directly on emulators such as PCVIC or Free-64). With some minor modifications Queztalcoatl will also produce code for the Apple ][, old 6502 game consoles (such as the Nintendo Entertainment System) and 6502 embedded systems.

History

Quetzalcoatl's roots go back to 1983, when I wrote the UPL Compiler for the VIC-20 just for fun. In 1983 Development tools were in short supply, so I ended up writing UPL in BASIC. This meant some compromises, such as restricting UPL to byte variables and no advanced features, such as local storage, pointers or structures. Despite this, UPL did run and with inline assembler and the mem[] array you write programs that were almost useful. When the VIC-20 finally lost its crown to the Commodore 64 I put my UPL and my other VIC-20 programs into storage, and chalked up writing UPL as a good educational experience. (You can download the original UPL Compiler by clicking here).

In 1998, having purchased an old second-hand VIC-20 at a garage sale, and having discovered VIC-20 emulators on the Internet, my interest in the VIC-20 was renewed. I wondered, as a dare, if I could could write a 6502 Cross Compiler equivalent to UPL in a night? It ended up taking a few nights, but I soon had something that compiled UPL. Of course UPL was kind of useless. Would it be possible to modify the compiler to read Tiny C programs as well as UPL programs? Indeed it was. In a few nights I had that running too. But the Tiny C/UPL hybird wasn't particularly useful either, so I started adding features like subroutine parameters, arrays and pointers. I'd also spent some time adding optimisation so Quetzalcoatl (as the hybrid was now named) started producing some impressively tight code. Unable to find a decent 6502 assembler for the runtime library, I wrote one of those too and integrated it into the compiler.

I had originally developed Quetzalcoatl to satisfy my own curiosity. At Linus Åkerlund's suggestion I placed its binary up on the web site and have been amazed ever since at the number of people that have downloaded it. (I mean, it's a compiler for a museum-piece CPU! Like, why would anyone care!? J)

In September 1998 I was in the middle of adding proper C data types (pointers, structures and composite types) and improving the optimisation when the real-world beckoned. I figured I'd return to Quetzalcoatl and finish it when time permitted, but as of time of writing it's been 12 months and I'm still flat out.

I had been thinking about open sourcing Quetzalcoatl for some time, but the source lacks all but the most basic comments explaining how everything is strung together. The Netscape experience has taught the world it's not good enough just to slap an open source label on a piece of software, and expect the world to rush in to fix it up for you. It has to be maintainable. Plus I take pride in my code; I don't want a half-assed, second-rate product with my name on it floating around out there, periodically coming back to haunt me as an example of why someone shouldn't hire me. (For my commercial quality work I'm expected to use ISO.)

Rather than let Quetzalcoatl sit around and gather bit-rot, I've been documenting it when I get the chance. As of 15 September 1999 it's finally reached the stage where the basic structure is almost understanable. Thus I've decided to do a limited public release to people who have contacted me over the last year and expressed either a curiosity or an interest. Quetzalcoatl 2.0a5 is a limited source release to those people. (Accordingly, I'm asking those people not to redistribute the source.) If they're brave enough they are of course free to modify it, compile and distribute their own version of the compiler executables.

Future

When I've finished commenting Quetzalcoatl (or it is at least in a better state) I intend to open source it under GNU. If the right person comes along I'd be happy to hand it over to someone else with the time and the interest to take over lead development, cos for the forseeable future I'm going to be too busy.

I think Quetzalcoatl needs to reach a certain level of ANSI C functionality for it to be useful. Unless it does, you'll find it kept out of the realms of "real" programs. Given how far it has already come, it'd be a shame not to go than final mile.

But that said, I don't think it needs to be 100% ANSI C compliant. For one, Quetzalcoatl uses an LL parser, where as C is a LR grammar. For two, it isn't really necessary. Very few C programs need 100% compliance, and if you must compile one of these there are already perfectly good 6502 C Cross Compilers out there. No sense reinventing the wheel. But as an LL compiler Quetzalcoatl offers some interesting opportunities, because you can really get in there and fine-tune the mechanics. For example, you can add custom optimisers to squeeze every byte and cycle out of the machine. This fits well with Quetzalcoatl's orginal goal; to produce 6502 code for a VIC-20; a machine with a scant 3.5Kb of RAM(!) In such a constrained environment, you have to make every little bit count.

To Do

Goals can be divided into three broad categories:
  1. Improvements that bring Quetzalcoatl closer to ANSI C, so that it can compile "real" programs.
  2. Optimisation.
  3. Versatility.

Here are some ideas for Quetzalcoatl development:

Rationale

Here are some changes I don't see as necessary, and why.

Design

LL vs LR

There are two broad families of compilers; LL and LR. Quetzalcoatl is an LL compiler. These are easy to write and easy to understand. The catch is they can only parse certain types of grammars. (A grammar defines the rules of a language.) C is actually an LR grammar, so I had to bend it somewhat to get Quetzalcoatal, an LL compiler, to be able to be able to parse it. (The official response is that Queztalcoatl isn't C, even if it happens to look a lot like it.)

LR compilers are internally quite complicated. Compiler writers need to use a Compiler Compiler such as YACC or Bison to build them. They do the job beautifully, but internally they're extremely boring. Quetzalcoatl was written for fun, education and as a testbed for optimisation, which is why I chose to write it as an LL compiler. If 100% ANSI compliance was my goal, LR would have won, hands down.

Architecture

Here are the major objects within Queztalcoatl:

The upl.h file is a good place to look for more detail on many of these objects.

While Statement Example

The actual upl_Compiler parsing routines are contained in the file UPL_COMP.CPP. Here is a fragment from while_statement() illustrating the conceptual simplicity of an LL parser. For clarity, the address patching code is not shown in this example.


void upl_Compiler::while_statement(Flex& L, upl_Context& C)
{
  // ... patching declarations not shown

  upl_Expr_result       clause;
  upl_Expr		expr;

  L.check("while");
  if (L.matches("("))
    {
    expr(L, C, clause, 0);
    L.check(")");
    L.matches("do");
    }
  else
    {
    expr(L, C, clause, 0);
    L.check("do");
    }

  // ... statement parsing and patching code not shown
}

Development Guidelines

Until a suitable volunteer appears, I'm happy to act as a central point-of-contact for people wanting to modify or otherwise extend the code. I'll keep a list of active developers and what they are doing on the Queztalcoatl web site.

Source Guidelines

If you change the source code, and want to integrate those changes back into the Queztalcoatl primary distribution, please:

Contact

If you're thinking of changing the code and want to check in, or you're trying to understand what a particular piece of code does or why it was implemented that way, then please click here to send me email.

If you're using Quetzalcoatl for a 6502 programming project, I'm also interested to hear from you. To date there have been over 150 downloads of Quetzalcoatl and I'd love to know what on Earth it is that people are doing with it! J

Links


© Brendan Jones, 1999. All Rights Reserved. Quetzalcoatl and sachiel.com are trademarks of Brendan Jones. Kdef.com is a trademark of Kestrel Defence. Pussiesgalore.com.au is a trademark of Katina Balson. VIC-20 and C-64 are probably registered trademarks of someone.