[Custom Thumbnail]

All the Code of the series can be found at the Github repository:

https://github.com/drifter1/compiler

Introduction

Hello it's a me again @drifter1! I was in vacation for one week, but am now back at home to post yet another article! Today we continue with my Compiler Series, a series where we implement a complete compiler for a simple C-like language by using the C-tools Flex and Bison. In this article we will generate code for Simple Statements (Break, Continue, Increment, Decrement).

Requirements:

Actually you need to read and understand all the topics that I covered in the series as a whole, as these articles will give you access to knowledge about:

What Compiler Design is (mainly the steps)
For which exact Language the Compiler is build for (Tokens and Grammar)
How to use Flex and Bison
How to implement a lexer and parser for the language using those tools
What the Symbol Table is and how we implement it
How we combine Flex and Bison together
How we can pass information from the Lexer to the Parser
How we define operator priorities, precedencies and associativity
What Semantic Analysis is (Attributes, SDT etc.)
How we do the so called "Scope Resolution"
How we declare types and check the type inter-compatibility for different cases that include function parameters and assignments
How we check function calls later on using a "Revisit queue", as function declarations mostly happen after functions get used (in our Language)
Intermediate Code Representations, including AST's
How we implement an AST (structure and management)
Action Rules for AST nodes and more
The target system's architecture and its assembly language (MIPS)
Register Allocation & Assignment and how we implement it
How we generate Assembly code for various cases

Difficulty:

Talking about the series in general this series can be rated:

Intermediate to Advanced

Today's topic(s) can be rated:

Easy

So, without further ado, let's now finally start with the actual Tutorial...

Actual Tutorial Content

Increment & Decrement Statements

An increment or decrement statement is basically the same as the arithmetic expression one. The only difference between those two is that the result of the statement "version" is not directly used inside of an expression that contains other variables. This all means that the increment/decrement statement is basically not included in our adjacency Graph, as there is no adjacency relationship between the variable that gets incremented/decremented and another variable.

Thinking about integer incrementation/decrementation we have:

For Floating-point Incrementations and Decrementations we will have to store the immediate '1.0' inside of $f28 and apply ADD.D and SUB.D correspondingly.

In Code all this looks like this:

code_generation.h:

...

void generate_incr_decr(FILE *fp, AST_Node_Incr *node);

...

code_generation.c:

...

void generate_incr_decr(FILE *fp, AST_Node_Incr *node){
    switch(node->incr_type){
        case 0: // increment
            if(node->entry->st_type == REAL_TYPE){
                fprintf(fp, "LI.D $28, 1.0\n");
                fprintf(fp, "ADD.D %s, %s, $28\n",
                    GetRegisterName(node->entry->g_index, 1),
                    GetRegisterName(node->entry->g_index, 1));
            }
            else{
                fprintf(fp, "ADDI %s, %s, 1\n",
                    GetRegisterName(node->entry->g_index, 0),
                    GetRegisterName(node->entry->g_index, 0));
            }
            break;
        case 1: // decrement
            if(node->entry->st_type == REAL_TYPE){
                fprintf(fp, "LI.D $28, 1.0\n");
                fprintf(fp, "SUB.D %s, %s, $28\n",
                    GetRegisterName(node->entry->g_index, 1),
                    GetRegisterName(node->entry->g_index, 1));
            }
            else{
                fprintf(fp, "SUBI %s, %s, 1\n",
                    GetRegisterName(node->entry->g_index, 0),
                    GetRegisterName(node->entry->g_index, 0));
            }
            break;
        default:
            fprintf(stderr, "Error in Incr_Type selection!\n");
            exit(1);
    }
}

...

By the end of this article, we will see what gets generated for the file: "full_example.c".

Break & Continue Statements

In the context of Loops (for loop in the diagram), we can visualize the break and continue statements as following:

    As you can see the break statement immediately stops the loop (while or for) from executing, "jumping us out" of the loops body. On the other hand, the continue statement skips the current iteration's code, making sure to increment the loop counter and also checking the loop condition.

    Implementing the break-statement is quite simple as we will just have to jump to a label right that will be generated right after the Loops-Code. For now we will only include a temporary label.

    Implementing the continue-statement is more tricky. In for-loops we can easily include a Label right before the incrementation/decrementation of the loop counter (i++/i--) and jump there. In while-loops things are more difficult. In a quite older article of the series, we wrote some code that finds out which variable is the loop counter, but still how exactly all this gets implemented will be covered in the corresponding article of While Loop Generation.

So, what is the code for a break or continue statement? Well, it's simply:

J Label

In other words, the code for generating any of those two simple statements is:

code_generation.h:

...

void generate_simple(FILE *fp, char* Label);

...

code_generation.h:

...

void generate_simple(FILE *fp, char* Label){
    fprintf(fp, "J %s\n", Label);
}

...

main_func_traversal() Function

The two functions that we wrote in this article have to be included inside of the main function's traversal. This basically means, that we write the following Code for the cases "SIMPLE_NODE" and "INCR_NODE":

...

/* simple case */
case SIMPLE_NODE:
    generate_simple(fp, "Temp_Label");  

    break;
/* increment statement */
case INCR_NODE:
    temp_incr = (AST_Node_Incr*) node;

    generate_incr_decr(fp, temp_incr);
    break;

...

Compiler Output for full_example.c

Running our compiler we get the following output file:

.data
# variables
c: .byte 'c'
i: .word 0
p: .word 0
val: .double 2.500000
res: .double 0.500000, 1.500000, 2.500000, 3.500000, 4.500000, 5.500000
# messages
msg1: .asciiz "\n"
msg2: .asciiz "\n"
msg3: .asciiz "iteration: 3\n"
msg4: .asciiz " "
msg5: .asciiz "\n"

.text
main:
LA $s3, res($0)
LW $s0, i($0)
BGE $s0, 10, Temp_Label
LW $s0, i($0)
BGT $s0, 5, Temp_Label
J Temp_Label
LW $s0, i($0)
BNE $s0, 5, Temp_Label
LW $s0, i($0)
MULI $s5, $s0, 2
LI $s6, 0
L.D $f4, val
LW $s0, i($0)
LI.D $f14, 0.0
LW $s3, res($0)
J Temp_Label
L.D $f4, val
LW $s0, i($0)
LI.D $f16, 0.0
LW $s3, res($0)
LW $s3, res($0)
LW $s4, p($0)
ADDI $t1, $s4, 1
LW $s0, i($0)
BNE $s0, 2, Temp_Label
L.D $f4, val
LI.D $f28, 4.50
C.EQ.D $f4 $f28 
BC1F Temp_Label
AND $s0, $s0, $s0
ADDI $s0, $s0, 1
LW $s0, i($0)
BGE $s0, 12, Temp_Label
LW $s0, i($0)
LW $s1, c($0)
ADDI $s0, $s0, 1

The two "bold" Jumps correspond to the:

break statement at line 12
continue statement at line 20

The two "emphasised" incrementations correspond to the:

for loop counter incrementation of line 10, that gets executed after the for loop's body and before the next incrementation
while loop counter incrementation of line 39

The rest of the output is basically the same as before...

RESOURCES

References:

No references, just using code that I implemented in my previous articles.

Images:

All of the images are custom-made!

Previous parts of the series

General Knowledge and Lexical Analysis

Syntax Analysis

Syntax Analysis Theory
Bison basics
Creating a grammar for our Language
Combine Flex and Bison
Passing information from Lexer to Parser
Finishing Off The Grammar/Parser: [part 1] [part 2]

Semantic Analysis (1)

Final words | Next up on the project

And this is actually it for today's post! In the next article we will generate the machine code for Assignments.

Next up on this series, in general, are:

Machine Code generation (MIPS Assembly)
Various Optimizations in the Compiler's Code

Which are all topics for which we will need more than one article to complete them. Also, note that we might also get into AST Code Optimizations later on, or that we could even extend the Language by adding complex datatypes (structs and unions), more rules etc.

So, see ya next time!

GitHub Account:

https://github.com/drifter1

Keep on drifting! ;)

Writing a simple Compiler on my own - Generating Code for Simple Statements