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

Review: Nestjs - Finally a scalable way to build APIs

I have been thinking about this for a long time. There HAS to be a defined way to build APIs in a scalable way.  If you have used Node, Express, etc in your side projects, you might have felt that after a point in development, debugging truly becomes a pain. Sure, enterprise-level API codes are great. But a lot of times, these configurations are too much, and probably not even needed in other projects. To be honest, I haven't seen a lot of Open-Source API codes either to make a judgement on how experienced developers build their APIs. Anyway, I came across an amazing framework recently, and I think if you are coding a complex API, this should be your way to go. Nest.js Nest.js is a framework for building efficient, reliable and scalable server-side applications.  You essentially break your APIs into controllers, services, and modules, which allow you to modularize the smallest of functionalities in your endpoints or the API as a whole. Why is modularizing important? As I have talk