Skip to main content

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 

Comments

Popular posts from this blog

Namaste JavaScript Quick Notes

Note:  Akshay Saini's Namaste JavaScript is probably the best course for JavaScript developers out there. These are my personal notes that I made while watching the course; they serve more of as an online quick reference for my understanding and revision, and I hope it benefits anyone reading it too! Everything in JS happens inside an Execution Context. Before a JS code is run, memory is allocated and variables are set as undefined   , and functions are set as their exact code in the scope within the Execution Context. The global execution context hosts all the global variables and function definitions. An Execution Context has 2 components: Memory, that stores variables and functions; and Code, that reads and executes the code. Call Stack maintains the order of execution contexts. Since JS is single threaded and asynchronous, at one point of time, only one function is executed which is at the top of the call stack. For each function, an execution context is created before executi

An introduction to APIs

API is an acronym for Application Programming Interface. Let's start with first defining some basic terms: Browser: These are browsers. To visit any website on the internet, you need a browser. Server: Hmm, this is tough. In simple words, server is a computer. Yes, just like the laptop, or PC at your home. The only difference is that it does not have a screen. Of course, there are other differences in technical specifications, but at its core, the server is just, simply, a computer. That's it. So why is it called a server? Because it serves . When you go to a website like google.com , your computer connects to the internet and gets you your search result. But your computer's internet connection has to get that result from somewhere, right? If the google search result is giving you some answers, the answers have to come from somewhere. What is that place? The answer to that some place is: a server. When you click on the search button on google, or hit enter after typing, &q

i3wm essentials - I (Brightness)

So you have started using i3 and somehow managed to open your browser and almost resumed your normal work.  But wait, the brightness is too much isn't it? Or is it too low? The mousepad used to work fine, but now all of a sudden tapping does not equal click?!  Don't worry.  This blog series will tell you all about the essential setup commands and common shortcuts that I use to navigate my work in i3, and how you can too. Changing the brightness So you just started i3 and you just can't take this brightness setting. You go for your function keys, and damn! They aren't working. Quick fix: Run the following command if you need to change the brightness ASAP. xrandr -q | grep ' connected' | head -n 1 | cut -d ' ' -f1 This will give an ouput that's the name of your monitor.  Use that monitor name here and change the values of brightness to suit your needs. xrandr --output <monitor-name> --brightness 0.7 Now that your eyes are comfortable, let me show