Building a Lexical Analyzer - Compiler Frontend I

Hey guys, today I'll be building a fully functional Lexical Analyzer that detects unrecognized tokens in C++!

Beginning:

The foundation of this program is derived from another program that counts different tokens in a C/C++ program. While I will try to explain all the basics of Lex here, if you find yourself stranded, you can refer the above link too. Once you understand the method of identifying tokens, the following program is just the converse of it!
Here's a basic overview of what happens in a Lex Program:

Some basics about a Lex Program

Lex (FLEX) basically iterates through your entire input string, trying to match everything it finds in the rules section. Once it finds the pattern, it executes the set of lines listed within the {} brackets.

So you can consider the "rules" an informal way of function declaration.

Rule Section in a Lex Program:                         Rule Section in a C/C++ Program:

It is important to note that Flex does not scan the input character-by-character. Remember, the rules section is just like declaring a regular expression. 

And if you have completed your Second Year, you might know the answer to What identifies a Regular Expression? 

A DFA.  

So the input string is validated as long as the character sequence that are coming in, satisfy the rule. That is why, the rule [0-9] is different from [0-9]+ 

For a more comprehensive information about the rules section, I would direct you to refer GFG's page on FLEX.

If you want to further understand the inner workings of a Lex Program, refer the 'Lex - Theory' Section of this PDF

The Code:

The Explanation:

So now that I've shown you the code, let's walk through the process of building a Lexical Analyzer. 

When should we output an error?

As soon as we see any non-keyword string. Like, 

fore(int i = 0....

Yes, that should give an output as an unrecognized token, while all the other keywords, operators, seperators should be accepted as perfectly valid tokens.

Yet, we are forgetting something incredibly important: identifiers.

Ofcourse! Right when you would write int a, it would return an unrecognized token. That shouldn't happen.

So now we need to make sure that as soon as the 'int', 'float', 'double', etc keywords are encountered, the subsequent strings are passed/accepted until the ';' is encountered.

int a, b, c;

To do that, I added an int variable in the Definitions Section which I'm using as a boolean value to toggle the acceptance of identifiers. You can see that in the rules section of "int" & "float", I'm setting the identify variable and in the ";" section, I'm resetting the variable again.

If the lex program encounters anything other than keywords, operators & seperators, it will now check if it is accepting identifiers through the identify variable.

Great, problem solved. Or is it?
We've solved the integer declaration problem, but what if someone tries to initialize the variable after declaring it? No answers for that!

a = 5;

So we need to save the declared variables, like a...(yes, you guessed it right!) Symbol Table. The main crux of the Compiler and we've finally realized its importance through our implementation failures!

Ideally, to construct the Symbol Table we should build a map. But since the code sections should be in C, I went ahead with using a 2D Character Array in the program, just to store the string values of the identifiers. This can be further improvised to build a Hash Table, but for now, let's just focus on accepting the right tokens.

So when we're deciding if the token is an identifier, all we need to do is just add the identifier if the identify variable is set, or else,
check the 2D Char Array for the occurence of the String in it. If it is present there, accept it as an identifier.
If all this fails, its an invalid token. You're free to output the most savage errors you can imagine.

Note:
If you look at the program, you might still not find all the keywords in it. You are free to add all the tokens in the "while"|"if".... section. It's a child's play now that you've understood the working of a Lexical Analyzer, the first part of the Compiler FrontEnd