Jolly Good Software

Working through ‘WACC’ – Chapter 1, A minimal compiler

—

by

paulmoore100
in

Ok, some real meat now.

The compiler we are building (I will call it ‘mycc’ from now on) works like this

The flow is:

  • launch (and wait for completion of) the installed c preprocessor, writing to a temporary file
  • mycc then reads that temporay file and compiles it to assembly code and writes that to a temporary file
  • it then launches the installed assembler and linker

The book , being Linux and mac oriented, requires gcc (or clang impersonating gcc) and instructs you to use them as the preprocessor and the assembler / linker.

The program (mycc) is also required to accept various command line options so that the test harness can run only certain phases , such as just the lexer.

Rust Implementation

First added for error handlinig :-

Command line parsing : clap – Rust pretty much the standard for cli handling

Launching the compilers needs two things, finding the compiler and then running it. I found this crate cpreprocess – Rust . This uses rusts standard cc – Rust to find the platform’s c toolchain and then launches it, a perfect starting point. It is in my cpp.rs file (reminder to myself, acknowledge it since I take and modify the source)

Finally I added pest. The Elegant Parser the commonly used parser toolkit. I have used it several times before, so its a no brainer (or not, see later)

Making it work with Windows

(You can obviously skip all this is you are using Linux or Mac)

The book shows the command lines for invoking gcc

  • gcc -E -P INPUT_FILE -o PREPROCESSED_FILE
  • gcc ASSEMBLY_FILE -o OUTPUT_FILE

To use the Microsoft tool chain – hereafter referred to as MSVC – we need

  • cl /EP /E /FiPREPROCESSED_FILE
  • ml64 /FeOUTPUT_FILE

Easy, and all done! Sadly no. gcc uses AT&T assembler syntax, ml64 uses intel (MASM) syntax. This is a big difference. Using the first program in the book.

int main(void) {
    return 2;
}

The gcc compatible code looks like this (the output from gcc)

        .file   "test.c"
        .text
        .globl  main
        .type   main, @function
main:
        movl    $2, %eax
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
        .section        .note.GNU-stack,"",@progbits

mycc generates

INCLUDELIB LIBCMT
_TEXT   SEGMENT
PUBLIC main
main PROC
        push rbp
        mov rbp, rsp
        sub rsp, 0
        mov eax, 2
        mov rsp, rbp
        pop rbp
        ret
        mov eax, 0
        mov rsp, rbp
        pop rbp
        ret
main ENDP
_TEXT   ENDS
END

There are a couple of major differences

  • in gcc format the arguments are source, dest. In masm its dest source. Look at the instruction to put 2 into the eax register. gcc is “move 2 to eax”, masm is “let eax = 2”
  • operand length (8, 16, 32, 64 bits) is specified in the opcode in gcc but is inferred from the operand in masm. gcc is ‘movl $2,%eax’ the ‘l’ says ‘long’ which means 32 bits. In masm its ‘mov eax,2’ , eax is 32 bits so this is a 32 bit move.

The last difference is more pronounce when we reference memory (chapter 1 doesnt get that far). But to demonstarte here is a snippet of the code generated for 

....
   int x = 1;
   return 1;
...

gcc

        movl    $1, -4(%rbp)
        movl    -4(%rbp), %eax
        ret

masm / mycc

        mov DWORD PTR[rbp-4], 1
        mov eax, DWORD PTR[rbp-4]
        ret

Notice that the length in masm is determined by the memory address specification; ‘DWORD PTR’ means this is a pointer to a 32 bit value. This makes for more fiddly assembler generation in later chapters.

The other changes are largely boiler plate.

Structure of the compiler

The compiler phase (the part that reads the expanded c code and creates the assembly) looks like this.

The boxes are code, the ovals are in memory structures. I will not go into detail of what these phases do since they are obviously well covered in the book.

The two step assembly generation needs a little explanation. The first phase reads the C AST and generates a new in memory representation the logical instructions needed to execute it, this first pass understands the underlying capabilities of the target instruction set. This new representation allows several passes to be made over it fixing things up before the actual assembler is generated.

I dont agree that this is an AST of the generated assembler code, which is what the book calls it. However, that is the term used throughout the book

Testing under windows

The test suite needs a few tweaks to work under windows. These changes are in my fork of Nora’s testsuite repo pm100/writing-a-c-compiler-tests: Test cases for Writing a C Compiler . The changed suite works with the original platforms too

Summary

  • The executable name to run after the compile is generated by converting <testcase>.c to <testcase> . This needs to be changed <testcase>.exe
  • The exit code of the executable is the main way that the test programs report their results to the test harness. On linux and Mac this is truncated to one byte, on Windows it is not. In a couple of tests this matters so I simply added an & 0xFF
  • The test suite has a database of expected results, this is looked up via file name. The slashes are the wrong way round (thank you Billg!) so it needed a name.replace("\\", "/")
  • One test consists of a single backslash character. The gcc preprocessor passes this through as a single backslash and so the lexer fails because that’s not valid c. This test is supposed to fail. The msvc preprocessor however sees this as an escaped new line and produced an empty file, which is valid c and so the lexer does not complain. Fixed by converting adding a space after the backslash in the test c source file

The command to launch the test suite under Windows is 

python .\test_compiler ........

because Windows does not support shebang scripts

Abandoning pest

I started out using pest, but gave up for various reasons

  • Nora said so
  • I could not easily work out how to do a few things in pest even though I had used it several times before. In all previous cases the compilers or interpreters I was creating were for languages specifically design for teaching purposes and so were easy to parse. Not so with C
  • I found that they are not that hard to do
  • C is not a context free grammar which definitely complicates things see ‘the trouble with typedefs’ page 108.
  • Nora said so

So I created my own lex and parse code.

Comments

Leave a comment