Brainfuck Interpreter in C - second day
Hello everyone
Yesterday I made some magic in our code and today I want to show you this. The most important thing that I wrote is the implementation of the linked list which can store all instructions from the file. Let's see what we already have.
We have these functionalities:
- a file has to be read as an argument
- react if the file is not specified
- react if the file extension is not right
- react if the file is not found
Today we will add these to our interpreter:
- read brainfuck instructions from a file
- check if the char from the file is brainfuck instruction
- if it is brainfuck instruction then add it to the linked list
I assume that you already know what is linked list so now I am going to show you my implementation of this data structure. Let's have a look at this.
The linked list is a structure with some place in memory to store the data and another to store the pointer to the next element of the list. And that's why we have to implement the linked list using struct type. You have to know that this is the only declaration of our object which is not in the memory at least for now. The scope of this struct is global.
What about reading brainfuck instructions from a file and adding them to the list? This code should do this.
char_from_file is the int variable which will store ASCII value of the char from the file specified from an argument. *head_ptr is the pointer to the first element of the linked list which will be used to iterate over the list. *current_instr_ptr is the pointer to the current element of the list and each element of our structure will be the brainfuck instruction.
while loop is here because of reading chars from the file. if expression checks if this char is actually brainfuck instructions. If it is true than function adds it to the linked list. All libs included in this file are here:
Ok so let's go to the is_bf_instruction function.
This function simply declares const char array with the brainfuck instructions and returns the pointer to the found char or NULL if the char was not found. If the char was not found it means that this is not a brainfuck instruction and it will be not added to the list. This is the documentation of memchr function - https://www.tutorialspoint.com/c_standard_library/c_function_memchr.htm
Let's assume that checking char is the brainfuck instruction. When it is true than add_instruction_to_the_list function is called. Let's see what this method really does.
Look at the parameters of this function. Why we are going to pass pointer to pointer? That is a weird think at first glance. But this is smart solution at the end. Can we set the pointer to the another place in the memory when we copied its value to the function? Think about it for a while... The answer is NO. We can pass only the copy of something to the function or reference to something. If we operate at the copy we can't change the value of copied variable in the function. The scope of copied variable ends when the function ends. If we want to do something with the original variable we have to pass it by reference. And more precisely by the pointer to the cell in the memory which stores the value of the variable to change.
So it seems that we don't need to write *head_ptr in parameters because we don't want to copy the pointer. We have to write **head_ptr because we are going to set the head pointer in another place in the memory. But when you would like to change the value store in the memory cell where the pointer is pointing to, then you can simply copy this pointer to the function and write *<ptr> in the parameters.
The first instruction in this function is an if expression. What is FIRST_ELEMENT_NOT_EXISTS? This is basically *head_ptr == NULL.
We have to write the name of the pointer with the star at the left side because we pass the pointer to pointer to the function. So the value of the pointer passed in the function is the pointer to the first element to the list. Before creating this element, head_ptr is set to NULL and that's why our expression looks like.
ERROR!
This picture above which presents the whole function is correctly, but first I wrote the code with an issue. Look:
The block of code from first if expression is incorrect. The last instruction of this code sets current_instr_ptr to the address on which head_ptr is pointing to. But head_ptr is pointing to NULL. And that's the case. I had to change the first_element pointer to head_ptr because like I said - head_ptr is the pointer which points to the first element of our list.
The second error is that I didn't check if memory allocation was successful.
The third error is that my else was unreadable and too long so I decided to write a function which creates an element of the list and returns it.
CORRECT!
This is the correct function which adds the brainfuck instruction to the list:
exit(EXIT_FAILURE); is not such a great example how to handle an error with the memory allocation because some operating systems didn't clear the heap before exiting the process, but I didn't have an idea to handle this better - I'm sorry.
In else block of code we have assigns that member bf_instruction of our struct linked list is the char_from_file and we set the pointer next_element to the NULL. When next_element points to the NULL than we know that this is the last element of our linked list. The last instruction updates current_instr_ptr. Now, this pointer points to the same place as head_ptr. So for now on current_instr_ptr points to the first element of the linked list.
If it is not the first element of the list then call the function create_new_element and returns the address of the structure which is the new element of the list to the pointer new_element.
I'm sorry for the quality of this screen shot, but I had to hold this picture in the width of the place for the article.
First instruction set current_instr_ptr to the first element of the list. The while loop moves this pointer to the last element of the list. And after this operations malloc function from stdlib.h returns the pointer to the newly allocated memory on the heap and our function returns address of this memory. Basically address of our new element of the list.
After this, we set the member of the new element named bf_instruction to the char_from_file variable and next_element pointer is set to NULL. next_element pointer from the old element of the list is pointing to the new element for now on and current_instr_ptr is pointing to the new element.
And that's all. On the third day, I will describe my solution of print all of the brainfuck instructions and I am going to write a function that clears the memory after the list.
Here is the whole code of the program:
Yesterday I made some magic in our code and today I want to show you this. The most important thing that I wrote is the implementation of the linked list which can store all instructions from the file. Let's see what we already have.
We have these functionalities:
- a file has to be read as an argument
- react if the file is not specified
- react if the file extension is not right
- react if the file is not found
Today we will add these to our interpreter:
- read brainfuck instructions from a file
- check if the char from the file is brainfuck instruction
- if it is brainfuck instruction then add it to the linked list
I assume that you already know what is linked list so now I am going to show you my implementation of this data structure. Let's have a look at this.
The linked list is a structure with some place in memory to store the data and another to store the pointer to the next element of the list. And that's why we have to implement the linked list using struct type. You have to know that this is the only declaration of our object which is not in the memory at least for now. The scope of this struct is global.
What about reading brainfuck instructions from a file and adding them to the list? This code should do this.
char_from_file is the int variable which will store ASCII value of the char from the file specified from an argument. *head_ptr is the pointer to the first element of the linked list which will be used to iterate over the list. *current_instr_ptr is the pointer to the current element of the list and each element of our structure will be the brainfuck instruction.
while loop is here because of reading chars from the file. if expression checks if this char is actually brainfuck instructions. If it is true than function adds it to the linked list. All libs included in this file are here:
Ok so let's go to the is_bf_instruction function.
This function simply declares const char array with the brainfuck instructions and returns the pointer to the found char or NULL if the char was not found. If the char was not found it means that this is not a brainfuck instruction and it will be not added to the list. This is the documentation of memchr function - https://www.tutorialspoint.com/c_standard_library/c_function_memchr.htm
Let's assume that checking char is the brainfuck instruction. When it is true than add_instruction_to_the_list function is called. Let's see what this method really does.
Look at the parameters of this function. Why we are going to pass pointer to pointer? That is a weird think at first glance. But this is smart solution at the end. Can we set the pointer to the another place in the memory when we copied its value to the function? Think about it for a while... The answer is NO. We can pass only the copy of something to the function or reference to something. If we operate at the copy we can't change the value of copied variable in the function. The scope of copied variable ends when the function ends. If we want to do something with the original variable we have to pass it by reference. And more precisely by the pointer to the cell in the memory which stores the value of the variable to change.
So it seems that we don't need to write *head_ptr in parameters because we don't want to copy the pointer. We have to write **head_ptr because we are going to set the head pointer in another place in the memory. But when you would like to change the value store in the memory cell where the pointer is pointing to, then you can simply copy this pointer to the function and write *<ptr> in the parameters.
The first instruction in this function is an if expression. What is FIRST_ELEMENT_NOT_EXISTS? This is basically *head_ptr == NULL.
We have to write the name of the pointer with the star at the left side because we pass the pointer to pointer to the function. So the value of the pointer passed in the function is the pointer to the first element to the list. Before creating this element, head_ptr is set to NULL and that's why our expression looks like.
ERROR!
This picture above which presents the whole function is correctly, but first I wrote the code with an issue. Look:
The block of code from first if expression is incorrect. The last instruction of this code sets current_instr_ptr to the address on which head_ptr is pointing to. But head_ptr is pointing to NULL. And that's the case. I had to change the first_element pointer to head_ptr because like I said - head_ptr is the pointer which points to the first element of our list.
The second error is that I didn't check if memory allocation was successful.
The third error is that my else was unreadable and too long so I decided to write a function which creates an element of the list and returns it.
CORRECT!
This is the correct function which adds the brainfuck instruction to the list:
exit(EXIT_FAILURE); is not such a great example how to handle an error with the memory allocation because some operating systems didn't clear the heap before exiting the process, but I didn't have an idea to handle this better - I'm sorry.
In else block of code we have assigns that member bf_instruction of our struct linked list is the char_from_file and we set the pointer next_element to the NULL. When next_element points to the NULL than we know that this is the last element of our linked list. The last instruction updates current_instr_ptr. Now, this pointer points to the same place as head_ptr. So for now on current_instr_ptr points to the first element of the linked list.
If it is not the first element of the list then call the function create_new_element and returns the address of the structure which is the new element of the list to the pointer new_element.
I'm sorry for the quality of this screen shot, but I had to hold this picture in the width of the place for the article.
First instruction set current_instr_ptr to the first element of the list. The while loop moves this pointer to the last element of the list. And after this operations malloc function from stdlib.h returns the pointer to the newly allocated memory on the heap and our function returns address of this memory. Basically address of our new element of the list.
After this, we set the member of the new element named bf_instruction to the char_from_file variable and next_element pointer is set to NULL. next_element pointer from the old element of the list is pointing to the new element for now on and current_instr_ptr is pointing to the new element.
And that's all. On the third day, I will describe my solution of print all of the brainfuck instructions and I am going to write a function that clears the memory after the list.
Here is the whole code of the program:
Comments
Post a Comment