Skip to main content

Find First and Follow for Syntactical Parsing - Compiler Frontend II

Hey! In my last post, I talked about the implementation of the Lexical Analyzer that would detect errors in the program originating from the use of invalid tokens. If you want to read more about it, you can start here.

In this blog, we will write a very short program to find the First & Follow of a set of productions in a Grammar. I'm hoping you have a basic understanding of Productions, and deriving First & Follow manually.

Why?

When I tried to understand the code to find the First & Follow from the internet, namely on sites like GeeksForGeeks, the code was too long, and sometimes I'm just too lazy to read code :). As it turns out, I was recently in a situation where I had no option than to write the code myself. Surprisingly, that turned out to be a blessing in disguise, as I developed a much shorter code for it using Hash Tables.  (Yeah, 82 lines is a much shorter code for this program!)

Here's the link for the gist.


Please note the conditions for the input in the last commented lines of code.

The Explanation

I have created three Hash Tables: one ordered map to store the productions - a char key with string as values, two unordered_maps to store First and Follow - a char key with a vector of characters as the value.

The input is given in string, so I will convert all the grammar into an ordered map. The first loop is all about that.

The next for loop finds the first of all the variables.
If you look at the manual way of solving, it is more feasible to find the First where the variable is directly defining a terminal. 
For example, F->id. 
You can easily say that the First is {id}.
But if the production is S->AS. 
We will need to find the First of A, and then we can add those characters to the First of S.

This is where the property of 'maps' comes in. Based on your chronological input, the traversal of maps would start from the alphebetical order, where the beginning alphabets hold the terminal values. As we progress to higher variables, we would already have the Firsts of the simpler variables. Thus, finding the First became really simple by trading some input constraints. 

Finding the Follow

This is a little complicated. Finding the Follow has some more rules. 
To find a Follow of a variable:
  • We need to scan the occurence of the variable in the RHS of all the productions.
  • When we find the next character, if it is a Terminal, we will add it as the Follow of the Variable and move on. BUT, if it's a Variable, things are different.
  • All the Firsts of that next Variable are added to the Follow of the scanned Variable.
  • In addition to this, if the First contains '(', we will need to look further at the subsequent Variable, and as long as we keep finding an Epsilon. 
So a 'found' boolean variable was created, where as long as its value true, all the above actions would be looked after, and it is continuously toggled based on the occurence of the scanned variable in the production.

I'm sorry if the above explanation was difficult to understand. But if you're confused even after re-reading it 5 times, then I would suggest some practice on finding the First & Follow of a Grammar. Once you get enough practice, you'll automatically start seeing a pattern, or specifically, an Algorithm that you are following. 

Feel free to modify the code and improve the above code as much as possible!

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