BisonC

The job of the compiler is to turn high level code into low level assembly language. This document discusses how this is done.

Translating simple instructions with a fixed set of opcodes such as

mov var,3

is relatively simple compared to translating high level expressions such as

x= cos(y) * sin (x)

The heart of the compiler and the main difference between compiling assembly and C rolves around parsing expression. There are two primary methods for high level language parsers, top-down and bottom-up

Top-Down

Because of the recursive nature of parsing this method is also known as recursive decent parsing.

Recursive descent parsing is best described with an example, consider the following.

for (int i=0i

At first glance we know we are dealing with a loop. This is due to the keyword for . If the for didn t exist we wouldn t know what we re dealing with. After recognising the initial keyword we can build upon what the next set of tokens should be.

Recursive decent parsing works in a similar fashion. It reads an initial token then has a set path for every keyword that can possibly exist in a given program. This method is pretty rigid, in order to add a new keyword you have to hard code a given validation path.

As described a recursive decent parser has a given code path for every language feature, once the parser reaches the opening brace it know leaves parsing the loop keyword then switches to parsing expressions. Once the closing brace is fond it switches back to parsing the loop.

Bottom-Up parsing

Bottom up parsers do not branch off to a specific parsing mechanism for a given token, rather it uses inductive reasoning to piece together a more refined picture of the source code.

Although more complex bottom up method is certainly a more flexible and efficient approach to parsing because it uses a single loop to parse the entire source file rather than branching off to specific method for specific circumstances. Rather parsing is handled through large procedurally generated lookup tables that helps detect patterns in the token stream.

Bottom-Up parsing is analogous to a state-machine methodology whilst top down is geared more towards a brute force approach.

Designing a Parsing strategy

I decided to use top down parsing method for the BisonC compiler. The main reason was that it was relatively simpler than that of its counterpart- bottom up parsing. This would allow me to complete and test the approach in the given time frame.

The second main design strategy was whether to use single or multiple pass compiler

A pass is defined as a complete scan over the source code regardless of what information is collected . Single pass compilers are faster (because they only make one pass).Multi pass compilers are easier to work with because you can gather information about variables and functions before processing the instructions that use them

I decided to go with multi pass approach because it allowed future extensibility to be implemented easier. If I decided to add such features as macros or dll support in the future having all function and variable information before hand will makes things a lot simpler to implement. Another driving factor was that most modern compilers are built around the two pass method, it seemed to be the given consensus in the compiler writing community.