<html>
https://i.postimg.cc/mDyhfZmp/if-else-thumb.jpg
<br>
[Custom Thumbnail]<br>
All the Code of the series can be found at the <strong>Github repository</strong>:
https://github.com/drifter1/compiler
<hr>
<h1>Introduction</h1> Hello it's a me again @drifter1! Today we continue with my <strong>Compiler Series</strong>, 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 Action Rules for If-Else Statements.
<h2>More specifically, the topics that we will cover today are:</h2>
<ol>
<li>The need of a Statements-node</li>
<li>Action rules for "simple" if-else statements</li>
<li>Action rules for if-else statements that contains else if's</li>
<li>Running the compiler for "full_example.c"</li>
</ol>
<h2>Requirements:</h2> Actually <strong>you need to read and understand all the topics that I covered in the series as a whole</strong>, as these articles will give you access to knowledge about:<ul>
<li>What Compiler Design is (mainly the steps)</li>
<li>For which exact Language the Compiler is build for (Tokens and Grammar)</li>
<li>How to use Flex and Bison</li>
<li>How to implement a lexer and parser for the language using those tools</li>
<li>What the Symbol Table is and how we implement it</li>
<li>How we combine Flex and Bison together</li>
<li>How we can pass information from the Lexer to the Parser</li>
<li>How we define operator priorities, precedencies and associativity</li>
<li>What Semantic Analysis is (Attributes, SDT etc.)</li>
<li>How we do the so called "Scope Resolution"</li>
<li>How we declare types and check the type inter-compatibility for different cases, including function parameters</li>
<li>How we check function calls later on using a "Revisit queue", as function declarations mostly happen after functions get used (in our Language)</li>
<li>Intermediate Code Representations, including AST's</li>
<li>How we implement an AST (structure and management)</li>
<li>Action Rules for other cases</li>
</ul>
<h2>Difficulty:</h2>Talking about the <strong>series in general</strong> this series can be rated:
<ul><li>Intermediate to Advanced</li></ul>
<strong>Today's topic(s)</strong> can be rated:
<ul><li>Medium</li></ul>
So, without further ado, let's now finally start with the actual Tutorial...
<hr>
<h1>Actual Tutorial Content</h1>
<h2>The need of a Statements-Node</h2> If-else statements, for statements, while statements, optional functions and even the "main" function, all mostly <strong> contain more than one statements</strong> in their "body" or "tail" as I call it sometimes in the grammar. So, there is the need of <strong>creating a new node that will store many "statement" nodes</strong>, to be able to access them later on. Knowing that <strong>statements are described recursively</strong> in our grammar, we can visualize it as follows:<br>
https://i.postimg.cc/DwzXFGsV/statements.png
<br><br>
-||- means that the second "Statements" does the same as the first one.<br><br>
So, let's create such a structure!
<h3>The Statements AST Node</h3> This node will store an dynamic pointer array to AST_Node structures, where each of them will of course be a "statement". To know the amount of statements that are stored in this structure, we have to also define a variable to store the statement count. The whole structure will be of a new Node-type "STATEMENTS" and will have the name "AST_Node_Statements". So, let's define an array "statements" and the integer variable "statement_count" as entries of this structure.<br><br>
In <strong>code</strong> this looks as following:<br>
<pre><code>typedef enum Node_Type {<br>
...<br>
STATEMENTS, // statements<br>
...<br>
}Node_Type;<br>
...<br>
typedef struct AST_Node_Statements{
enum Node_Type type; // node type<br>
// statements
struct AST_Node **statements;
int statement_count;<br>
}AST_Node_Statements;<br>
...</code></pre><br>
Of course this code is inside of "ast.h".
<h3>Creation Function</h3> The way with which the rule "statements" is build up makes it easy for us to use the creation function to add new statements to the "statements"-parent rule. So, the creation function, let's say "new_statements_node", will have 3 parameters which are:<br>
<ul>
<li>The statements array of the previous "statements"-rule</li>
<li>The statement_count value of the previous "statements"-rule</li>
<li>The "statement" to be added</li>
</ul>
Knowing that the "statements"-rule looks as following:<br>
<code>statements -> statements statement | statement ;</code><br>
we understand that the first two parameters are useless for the second sub-rule of "statements". For this rule we will just pass NULL and 0 as parameters!<br><br>
The function declaration in "ast.h" and actual code of "ast.c" are:<br>
<pre><code><strong>ast.h</strong>:<br>
AST_Node *new_statements_node(AST_Node **statements,<br>
int statement_count, AST_Node *statement);<br>
-----------------------------------------------------------------<br>
<strong>ast.c</strong>:<br>
AST_Node *new_statements_node(AST_Node **statements,<br>
int statement_count, AST_Node *statement){<br>
// allocate memory
AST_Node_Statements *v = malloc (sizeof (AST_Node_Statements));<br>
// set node type
v->type = STATEMENTS;<br>
// first statement
if(statements == NULL){
statements = (AST_Node**) malloc (sizeof (AST_Node*));
statements[0] = statement;
statement_count = 1;
}
// add new statement
else{
statements = (AST_Node**) realloc (statements,
(statement_count + 1) * sizeof (AST_Node*));
statements[statement_count] = statement;
statement_count++;
}<br>
// set entries
v->statements = statements;
v->statement_count = statement_count;<br>
// return type-casted result
return (struct AST_Node *) v;
}
</code></pre>
<br>
You can see that there are two cases, which correspond to the second and first sub-rule of "statements". Of course I also did some changes in the traversal and print functions of the nodes. To see these changes go to GitHub, where I always upload the code of the series.
<h3>Integrate with the "statements"-rule</h3> In the second sub-rule we just create a new node with parameter NULL, 0 and the already created node stored in "statement". Knowing that all nodes are type-casted to "AST_Node", the second sub-rule will need to type-cast the already created "statements" node of the "statements"-part and give the statements-array and statement_count of this node as a parameter of the creation function, together with the "statement" node.<br><br>
So, the new <strong>rule</strong> now becomes:<br>
<pre><code>statements:
statements statement
{
AST_Node_Statements *temp = (AST_Node_Statements*) $1;
$$ = new_statements_node(temp->statements, temp->statement_count, $2);
}
| statement
{
$$ = new_statements_node(NULL, 0, $1);
}
;</code></pre>
<br>
Also don't forget to include the token definition of "statements":<br>
<code>%type <node> statements</code>
<br><br>
<em>The same stuff will have to be done for "declarations" as well, but I will leave it for when we get to function declarations!</em>
<hr>
<h2>Action Rules for "Simple" If-Else Statements</h2> The if statement is a somewhat complicated statement as it can include a dynamic amount of else if's and an optional else part. So, we will have to use concepts we already used in previous topics like "declarations", to <strong>take all the needed information/attributes and pass them over to the actual If-node</strong>! To solve a conflict with the else ifs and else, I had to split the "if_statement" rule into two parts: one with else if's and one without. So, the whole problem can be visualized as following:<br>
https://i.postimg.cc/q73HCmn8/if-statement.png
<br><br>
Let's first get into the "simple" case that does not require the complicated passing of Else-If nodes. Visualizing this simple case we see that:<br>
https://i.postimg.cc/fRFhy43z/if-with-optional-else.png
<br><br>
(as you can see I put lots of visualizations today!)<br><br>
So, what do we understand? Well, the condition is pretty simple as we already have the information stored in the expression. The actual if_branch is represented by the "tail"-rule, which will have to store the "statements"-node that it get's from the "statements"-rule inside of the bracelets. This tells us that the "tail" also has to be of type "node" and so we add it alongside "statements". In the same way the if_statement, optional_else and else_if rule are also of type node. And so we can already write the following <strong>non-terminal type-definitions</strong>:<br>
<pre><code>%type <node> statements tail
%type <node> if_statement else_if optional_else</code></pre>
<br>
The "tail"-rule becomes:<br>
<pre><code>tail: LBRACE statements RBRACE
{
$$ = $2; /* just pass information */
ast_traversal($2);
}
;</code></pre><br>
So, what remains now is the optional else. For the optional else we will just return the "statements"-node stored in the "tail"-part (else exists) or NULL (no else). The rule becomes:<br>
<pre><code>optional_else:
ELSE tail
{
/* else exists */
$$ = $2;
}
| /* empty */
{
/* no else */
$$ = NULL;
}
;</code></pre><br>
Knowing what we store in each of these non-terminals, the action rule for this simple if statement looks as following:<br>
<pre><code>if_statement:
IF LPAREN expression RPAREN tail else_if optional_else
{
/* later */
}
| IF LPAREN expression RPAREN tail optional_else
{
$$ = new_ast_if_node($3, $5, NULL, 0, $6);
}
;</code></pre><br>
You can see that we pass NULL and 0 for the else ifs. For the rest we just find the correct number to put after '$'. All the parameters have the correct type already and so there is no need of type-casting or creating temporary nodes..
<hr>
<h2>Action Rules for If-Else Statements that contains Else If's</h2> So, now for the more complicated case! We will be using the same idea that we used for declarations and initialization, where we had <strong>global variables</strong> to store the newly found names and values for the array initialization. In this case we will have a <strong>AST_Node pointer array to store the else-if branches</strong> (elsifs) and a <strong>counter variable for the number of else ifs</strong> (elseif_count). To add a new entry we will define a <strong>new function "add_elseif"</strong> that takes the newly found Else-if node as a parameter and adds it to the global array. We of course have two cases for that:<br>
<ol>
<li>First entry of the array, where we will have to allocate the array for the first time</li>
<li>General case, where we allocate memory for the new entry and add the entry to the end of the array</li>
</ol>
So, with all that in mind the parser now contains:<br>
<pre><code>%{<br>
...<br>
// for else ifs
void add_elseif(AST_Node *elsif);
AST_Node **elsifs;
int elseif_count = 0;
%}<br>
...<br>
void add_elseif(AST_Node *elsif){
// first entry
if(elseif_count == 0){
elseif_count = 1;
elsifs = (AST_Node **) malloc(1 * sizeof(AST_Node));
elsifs[0] = elsif;
}
// general case
else{
elseif_count++;
elsifs = (AST_Node **) realloc(elsifs, elseif_count * sizeof(AST_Node));
elsifs[elseif_count - 1] = elsif;
}
}<br>
...</code></pre><br>
All that we said until now, can be visualized as following<br>
https://i.postimg.cc/DyxhV4nb/if-with-else-ifs.png
<br><br>
Using the function "add_elseif", the "else_if"-rule is pretty easy to write now! Both sub-rules do the same thing, but will have a different numeration for the non-terminals that are passed as parameters. The <strong>"else_if"-rule</strong> looks as following:<br>
<pre><code>else_if:
else_if ELSE IF LPAREN expression RPAREN tail
{
AST_Node *temp = new_ast_elsif_node($5, $7);
add_elseif(temp);
}
| ELSE IF LPAREN expression RPAREN tail
{
AST_Node *temp = new_ast_elsif_node($4, $6);
add_elseif(temp);
}
;</code></pre>
<br>
Thinking about the "if_statement"-rule now, the only thing that changes is that we will use these global variables as parameters, by also re-initializing them back to 0 and NULL. So, with all that in mind <strong>the final "if_statement" rule becomes</strong>:<br>
<pre><code>if_statement:
IF LPAREN expression RPAREN tail else_if optional_else
{
$$ = new_ast_if_node($3, $5, elsifs, elseif_count, $7);
elseif_count = 0;
elsifs = NULL;
}
| IF LPAREN expression RPAREN tail optional_else
{
$$ = new_ast_if_node($3, $5, NULL, 0, $6);
}
;</code></pre>
<br>
And this is it actually! Wasn't that bad right?
<hr>
<h2>Running the Compiler for "full_example.c"</h2> Before running the compiler I would like to point out that I removed many "ast_traversal" functions from the action rules, as they would just produce duplicate messages. We will only put "ast_traversal" functions for the declarations and statements rules now. Later on there will be only one traversal of the whole AST, that will be found in the "program"-rule. Of course this will be used for the machine code generation :)<br><br>
So, let's run the compiler:<br>
https://i.postimg.cc/nVYZkwW2/console.jpg
<br><br>
You can see that we get new messages in the console! I also included some explanations for what got printed out. The main outer statements of the "full_example.c" file are of course only 4! The other statement node messages correspond to the for and while statements and more specifically to the "tail" of them. In the beginning we can also see the statements node of the last if-node that appears in the for statement. Nice huh? Next time we will get into Loops ;)
<hr>
<h2>RESOURCES</h2>
<h3>References:</h3>
No references, just using code that I implemented in my previous articles.
<h3>Images:</h3>
All of the images are custom-made!
<hr>
<h2>Previous parts of the series</h2>
<ul >
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-introduction">Introduction</a> -> What is a compiler, what you have to know and what you will learn</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-a-simple-c-language">A simple C Language</a> -> Simplified C, comparison with C, tokens, basic structure</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-lexical-analysis-using-flex">Lexical Analysis using Flex</a> -> Theory, Regular Expressions, Flex, Lexer</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-symbol-table-basic-structure">Symbol Table (basic structure)</a> ->Why Symbol Tables, Basic Implementation</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-using-symbol-tables-in-the-lexer">Using Symbol Table in the Lexer</a> -> Flex and Symbol Table combination</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-syntax-analysis-theory">Syntax Analysis Theory</a> -> Syntax Analysis, grammar types and parsing</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-bison-basics">Bison basics</a> -> Bison tutorial actually</li>
<li><a href="https://steemit.com/programming/@drifter1/writing-a-simple-compiler-on-my-own-creating-a-grammar-for-our-language">Creating a grammar for our Language</a> -> Grammar and first Parser</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-combine-flex-and-bison">Combine Flex and Bison</a> -> lexer and parser combined</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-passing-information-from-lexer-to-parser">Passing information from Lexer to Parser</a> -> Bug Fix, yylval variable, YYSTYPE union, Setting up the Parser, Passing information "directly" and through the symbol table (special case) with examples.</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-finishing-off-the-grammer-parser-part-1">Finishing Off The Grammar/Parser (part 1)</a> -> Adding the missing grammar rules, small fixes</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-finishing-off-the-grammar-parser-part-2-c-flex-bison">Finishing Off The Grammar/Parser (part 2)</a> -> Operator priorities, precedencies and associativity, complete example file (for testing), grammar rule visualization, finish off grammar/parser</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-semantic-analysis-theory-c-flex-bison">Semantic Analysis Theory</a> -> What is Semantic Analysis about, CSG and CSL, Attribute Grammars, Syntax Directed Translations (SDT)</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-semantics-examples-c-flex-bison">Semantics Examples</a> -> Visualization of Semantics for different rules/cases, needed attributes, what we have to implement from now on</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own---scope-resolution-using-the-symbol-table-cflexbison">Scope Resolution using the Symbol Table</a> -> What we have now, scope resolution, integration, compiler output </li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-type-declaration-and-checking-c-flex-bison">Type Declaration and Checking</a> -> Type declaration and type checking code, "simple" code integration</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-function-semantics-part-1-c-flex-bison">Function Semantics (part 1)</a> -> Code for parameter definitions, function declarations and parameter compatibility checking</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-function-semantics-part-2-c-flex-bison">Function Semantics (part 2)</a> -> Revisit queue concept, basic implementation, inserting undeclared identifiers</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-abstract-syntax-tree-principle-c-flex-bison">Abstract Syntax Tree Principle</a> -> Intermediate code generation and representations, how to design an AST</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-abstract-syntax-tree-structure-c-flex-bison">Abstract Syntax Tree Structure</a> -> Node, operator and value types, AST node structures, some management functions, integration with the rest of the compiler</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-abstract-syntax-tree-management-c-flex-bison">Abstract Syntax Tree Management</a> -> Tweaking Nodes, Node creation and AST traversal functions, "manual" testing of the AST</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-action-rules-for-declarations-and-initializations-c-flex-bison">Action Rules for Declarations and Initializations</a> -> Replacing many values with a Value union, Other smaller changes, Action rules for declarations, Action rules for initializations</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-action-rules-for-expressions-c-flex-bison">Action Rules for Expressions</a> -> Separating operator tokens, Action rules for expressions, running the compiler</li>
<li><a href="https://steemit.com/utopian-io/@drifter1/writing-a-simple-compiler-on-my-own-action-rules-for-assignments-and-simple-statements-c-flex-bison">Action Rules for Assignments and Simple Statements</a> -> Action rules for simple statements, Action rules for assignments, running the compiler</li>
</ul>
<hr>
<h2>Final words | Next up on the project</h2> And this is actually it for today's post! I hope that I explained everything well.<br>
Next up on this series are:
<ul>
<li>Semantic analysis (using more action rules in Bison)</li>
<li>Intermediate Code generation (using the AST structure for more cases)</li>
<li>Machine Code generation (MIPS Assembly)</li>
</ul>
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.<br>
So, see ya next time!
<hr>
<h2>GitHub Account:</h2>
https://github.com/drifter1<br>
https://steemitimages.com/0x0/https://media.giphy.com/media/ybITzMzIyabIs/giphy.gif
<br>
Keep on drifting! ;)
</html>
hiveblocks