https://i.postimg.cc/fbw0xvTT/compiler-series.jpg

[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! 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 write the needed code for type checking and type declarations, without actually integrating it into the compiler (bison parser) completely!

The topics that we will cover today are:

Type declaration code
Type checking code
"Simple" code integration with Symbol Table, Lexer and Parser

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"

Difficulty:

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

Intermediate to Advanced

Today's topic(s) can be rated:

Medium

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

Actual Tutorial Content

Type Declaration Code

First up, now that we start implementing semantics, it might be a good idea to put this code into a new header and code file. Let's call them "semantics.h" and "semantics.c".
The new header file should contain the data (or token) types that our language has, meaning that we should remove them from the symbol table header "symtab.h" and include this new header there and whenever we want to access types and semantics in general. Doing that I also saw that I defined more types than I should and that the character type was called string type, which might be a little confusing. So, in the end, the header file will now contain the following type definitions:

#define UNDEF 0
#define INT_TYPE 1
#define REAL_TYPE 2
#define CHAR_TYPE 3
#define ARRAY_TYPE 4
#define POINTER_TYPE 5
#define FUNCTION_TYPE 6

That's because, right now, our simple C language only has:

Integers
Floats and Doubles (Real type)
Characters (including Strings)
Arrays and pointers of the previous types
Functions returning the previous types

In the same notion I also found out that I defined string arrays or strings instead of characters in some places of the symbol table entry struct "list_t". So, now the "new" struct is:

typedef struct list_t{
    // name, size of name, scope and occurrences (lines)
    char st_name[MAXTOKENLEN];
    int st_size;
    int scope;
    RefList *lines;

    // to store value and sometimes more information
    int st_ival; double st_fval; char st_sval;

    // "main" type
    int st_type;

    // for arrays (info type), for pointers (pointing type)
    // and for functions (return type)
    int inf_type;

    // array stuff
    int *i_vals; double *f_vals; char *s_vals;
    int array_size;

    // function parameters
    Param *parameters;
    int num_of_pars;

    // pointer to next item in the list
    struct list_t *next;
}list_t;

When declaring a variable we have to be able to set the type of the identifier afterwards, using the type-information stored in the "type"-rule for example (something that I will not do today, but later on). So, we need some kind of "set type" function that let's us actually declare a variable or an identifier, by now setting the "undefined" type of the identifier to the correct type that was used in the declaration. Such a function will call lookup() to find the corresponding entry of the needed identifier to then access the entries st_type and inf_type, so that we can store the "main" type and info/data, pointing or return type when talking about pointers, arrays or functions.
The code for such a function looks as following:

void set_type(char *name, int st_type, int inf_type){
    /* lookup entry */
    list_t *l = lookup(name);

    /* set "main" type */
    l->st_type = st_type;

    /* if array, pointer or function */
    if(inf_type != UNDEF){
        l->inf_type = inf_type;
    }   
}

Of course we could also do this by hand every time, but I think a function that does it for us is much better in the circumstance! In the same way, we should also be able to get the type of the identifier using some "get type" function that gives us the "actual" type of the entry. For "simple" variables we just have to return the value from "st_type", but for the others (array, pointer or function) we have to return the info, pointing or return type, which is stored in "inf_type".
In code this looks as following:

int get_type(char *name){
    /* lookup entry */
    list_t *l = lookup(name);

    /* if "simple" type */
    if(l->st_type == INT_TYPE || l->st_type == REAL_TYPE || l->st_type == CHAR_TYPE){
        return l->st_type;
    }
    /* if array, pointer or function */
    else{
        return l->inf_type;
    }
}

And the "set_type" function is actually all that we have to call in the actual parser when setting or better said declaring the type of an identifier. The other function will be used, so that we are able to access the type of an identifier when "type checking".

Type Checking Code

Depending on the type of operator, different types are inter-compatible or not. This means that we will have to define the operator types, in the same way that we defined the data types. The following operators can occur when type checking:

None -> When assigning or when checking parameter inter-compatibility
Arithmetic -> When adding/subtracting, multiplying and dividing
Increment -> When incrementing/decrementing numeric values
Boolean -> In Boolean OR or AND operations
Not -> The Boolean NOT operator
Relational -> The operators: '>', '=' and '<='</li> <li>Equality -> The operators: "==" and "!="</li> </ul> Note that the increment operator is still an arithmetic operator, but just a special case. The same way the Not operator is a special case of Boolean operator. Both of these operators have only one parameter. In actual "definition" code, this looks as following: <pre><code>#define NONE 0 // to check types only - assignment, parameter #define ARITHM_OP 1 // ADDOP, MULOP, DIVOP (+, -, *, /) #define INCR_OP 2 // INCR (++, --) #define BOOL_OP 3 // OROP, ANDOP (||, &&) #define NOT_OP 4 // NOTOP (!) #define REL_OP 5 // RELOP (>, <, >=, <=) #define EQU_OP 6 // EQUOP (==, !=)</code></pre> Of course this code is inside of the "semantics.h" file. The actual type checking will be implemented using a function that checks the types depending on the operator and returns if they are compatible by maybe even returning the result type of the operation. Knowing that the actual types are: Integer, Real or Char, we can easily write the code needed. So, let's get into each case after covering the main function declaration!
The function declaration looks as following:
int get_result_type(int type_1, int type_2, int op_type);

No operator
When having no operator only "equal" types can be assigned to each other (or used in parameters). This means that an integer or character can only be assigned to an integer or character, cause these types are actually the same. The ASCII representation of a char is actually an int! The value of a float or double, and so real in general, can be any of the others (including the same type). This might change in the future if we define a separate float and double type! From all that we understand that the code needs to be:
```
switch(op_type){
case NONE: /* type compatibility only, '1': compatible */
 // first type INT
 if(type_1 == INT_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return 1;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type REAL
 else if(type_1 == REAL_TYPE){
 // second type INT, REAL or CHAR
 if(type_2 == INT_TYPE || type_2 == REAL_TYPE || type_2 == CHAR_TYPE){
 return 1;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type CHAR
 else if(type_1 == CHAR_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return 1;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 break;
...code continues...
```
You can see that we have a switch case with the operator type "op_type" and than the current case of "NONE" operator (no operator). That way depending on the first type we see if the second type is compatible with it or not. When they are compatible we return '1'. When not, well, then we call a new function called "type_error". This function just prints out that the two types are incompatible when using this operator type.
More specifically, the code of this function is:
```
void type_error(int type_1, int type_2, int op_type){ 
 fprintf(stderr, "Type conflict between %d and %d using op type %d\n",
 type_1, type_2, op_type);
 exit(1);
}
```
You can see that we just print out that a type conflict occurred and then end the program with return code '1', meaning error! Pretty easy I guess!
In the same notion we also have cases for the rest of the operators...
Arithmetic operators
Again real is compatible with everything, but, the same also happens with the rest of the types. In general, arithmetic operators are compatible with everything. But now we should also see what kind of result we get in each of these calculations! In general, whenever real is one of the types, the result will be real. In the same way, having int and char the result will be int. Only when we have char as the first type we will get a type of char in the result!
So, the code is:
```
...
case ARITHM_OP: /* arithmetic operator */
 // first type INT
 if(type_1 == INT_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 // second type REAL
 else if(type_2 == REAL_TYPE){
 return REAL_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type REAL
 else if(type_1 == REAL_TYPE){
 // second type INT, REAL or CHAR
 if(type_2 == INT_TYPE || type_2 == REAL_TYPE || type_2 == CHAR_TYPE){
 return REAL_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type CHAR
 else if(type_1 == CHAR_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return CHAR_TYPE;
 }
 // second type REAL
 else if(type_2 == REAL_TYPE){
 return REAL_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
...
```
The special case of INCR operator is very simple. We just return the type of the first parameter. The second type is non-existent and mostly UNDEF. That way we just have to write:
```
...
case INCR_OP: /* special case of INCR */
 // type INT
 if(type_1 == INT_TYPE){
 return INT_TYPE;
 }
 // type REAL
 else if(type_1 == REAL_TYPE){
 return REAL_TYPE;
 }
 // type CHAR
 else if(type_1 == CHAR_TYPE){
 return CHAR_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
...
```
Boolean operators
As a Boolean value we can only use integers and characters. This means that only these two types are inter-compatible and usable with Boolean operators. To make our life even simpler we will return the type of the first parameter! In code this looks as following:
```
...
case BOOL_OP: /* Boolean operator */
 // first type INT
 if(type_1 == INT_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type CHAR
 else if(type_1 == CHAR_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return CHAR_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
...
```
The special case of NOT is similar to INCR. We just return the type of the first parameter. This means that the code is:
```
...
case NOT_OP: /* special case of NOTOP */
 // type INT
 if(type_1 == INT_TYPE){
 return INT_TYPE;
 }
 // type CHAR
 else if(type_1 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
...
```
Relational operators
In relational operators the types need to be comparable. So when talking about integers or characters, those can be compared with each other, but also with the type real. For example we can have: "5 >= 5.5", which means that an integer is greater than a real. So, in the same way as with arithmetic operators all of the types are inter-compatible or better said inter-comparable in this case! But, there is one BIG difference now! The result type is a Boolean value, which in C is represented with an integer value.
So, knowing all that the code is:
```
...
case REL_OP: /* Relational operator */
 // first type INT
 if(type_1 == INT_TYPE){
 // second type INT, REAL or CHAR
 if(type_2 == INT_TYPE || type_2 == REAL_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else if(type_1 == REAL_TYPE){
 // second type INT, REAL or CHAR
 if(type_2 == INT_TYPE || type_2 == REAL_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type CHAR
 else if(type_1 == CHAR_TYPE){
 // second type INT, REAL or CHAR
 if(type_2 == INT_TYPE || type_2 == REAL_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
...
```
Equality operator
Only Integer and characters can be inter-compatible in the equality and in-equality checks. Reals can only be compared with themselves. The result of such a comparison is again a Boolean value that we will represent using an integer. So, in the end, the code, including the default case and end of the switch-case statement, is:
```
...
case EQU_OP: /* Equality operator */
 // first type INT
 if(type_1 == INT_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else if(type_1 == REAL_TYPE){
 // second type REAL
 if(type_2 == REAL_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 // first type CHAR
 else if(type_1 == CHAR_TYPE){
 // second type INT or CHAR
 if(type_2 == INT_TYPE || type_2 == CHAR_TYPE){
 return INT_TYPE;
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 }
 else{
 type_error(type_1, type_2, op_type);
 }
 break;
/* ---------------------------------------------------------- */
default: /* wrong choice case */
 fprintf(stderr, "Error in operator selection!\n");
 exit(1);
}
```
 I would like to note that this type checking is of course not final at all! We just got into the general structure of "Type checking" and created the rules for most of the types! Of course Pointers need a special handling, that we will get into some articles later on. In arrays and functions we just use the info/data or return value, meaning that we use the types that we already covered!

"Simple" Integration
 Of course the "semantics.h" and "semantics.c" files have to be included in our previous code. More specifically, the "semantics.c" file has to include it's corresponding header file "semantics.h". Both the "symtab.c" and the "symtab.h" files, which contain the symbol table, have to include the "semantics.h" library. That's because we now defined the (token) types in there!
 To compile and use them in the actual final compiler we of course also have to include these files in the lexer and parser! In the lexer we have to include the header file "semantics.h", to be able to use the token type "UNDEF" when inserting an ID into the symbol table. That's because the insert() function of course also take a type as a parameter. In the same way, to be able to use the new functions in the parser we will have to include the "semantics.c" file there. This will also make sure that this new code will be compiled and included in the final compiler executable!
 And this is actually all that I wanted to do today! So, go take a look at the code on GitHub to understand how everything gets bind together! Of course the compiler right now, has the same features that it had in the previous article. But, we made a first step in the declaration and type checking procedures, which just need an "actual" integration now. To do this we will have to store information/attributes in the actual rules and so non-terminals, which is something that we will do in an article that follows. So, what remains now is writing some more code that will be used for semantics checks, by also creating the actual Attribute Grammar...

RESOURCES

References:
 The following helped me refresh my knowledge about C-datatypes, their inter-compatibility and semantics:
1. http://www.cs.sfu.ca/~msiahban/personal/teaching/CMPT-379-Spring-2016/typecheck.pdf
2. http://www.cse.chalmers.se/edu/year/2015/course/DAT150/lectures/proglang-07.html
3. https://pebble.gitbooks.io/learning-c-with-pebble/content/chapter03.html
4. https://pebble.gitbooks.io/learning-c-with-pebble/content/appendixa.html
5. https://engineering.purdue.edu/~milind/ece468/2014fall/lecture-04.pdf
Images:
All of the images are custom-made!

Previous parts of the series
- Introduction -> What is a compiler, what you have to know and what you will learn
- A simple C Language -> Simplified C, comparison with C, tokens, basic structure
- Lexical Analysis using Flex -> Theory, Regular Expressions, Flex, Lexer
- Symbol Table (basic structure) ->Why Symbol Tables, Basic Implementation
- Using Symbol Table in the Lexer -> Flex and Symbol Table combination
- Syntax Analysis Theory -> Syntax Analysis, grammar types and parsing
- Bison basics -> Bison tutorial actually
- Creating a grammar for our Language -> Grammar and first Parser
- Combine Flex and Bison -> lexer and parser combined
- Passing information from Lexer to Parser -> Bug Fix, yylval variable, YYSTYPE union, Setting up the Parser, Passing information "directly" and through the symbol table (special case) with examples.
- Finishing Off The Grammar/Parser (part 1) -> Adding the missing grammar rules, small fixes
- Finishing Off The Grammar/Parser (part 2) -> Operator priorities, precedencies and associativity, complete example file (for testing), grammar rule visualization, finish off grammar/parser
- Semantic Analysis Theory -> What is Semantic Analysis about, CSG and CSL, Attribute Grammars, Syntax Directed Translations (SDT)
- Semantics Examples -> Visualization of Semantics for different rules/cases, needed attributes, what we have to implement from now on
- Scope Resolution using the Symbol Table -> What we have now, scope resolution, integration, compiler output
Final words | Next up on the project
And this is actually it for today's post! I hope that I explained everything as much as I needed to, meaning that you learned something out of it.
Next up on this series are:
- Semantic analysis (creating and using even more semantic rules in bison, attribute grammar)
- Intermediate Code generation (Abstract Syntax Tree)
- Machine Code generation (MIPS Assembly)
Which are all topics that will need more than one article to complete. Also, note that we might also get into Optimizations later on, or 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
https://steemitimages.com/0x0/https://media.giphy.com/media/ybITzMzIyabIs/giphy.gif
Keep on drifting! ;)