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.


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!


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

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

"Hey Google" get me a new T-shirt

Everyone loves Google for its amazing technology and creative workspaces! Guess what? Google loves its developers as much as the world loves it too! And yeah, you don't need to be an amazing programmer to be a developer in Google's community. All you need to do is to spare 30 minutes, just once, and maybe have some creativity! That's it! Oh, and you should be really checking your mails periodically, although if you don't currently have this habit, your excitement would develop that for you. What do we want? So you arrived here to know about getting a T-shirt. Would you also like having a Google Home ? Yup, that is also something you could get through this. And of course, as I mentioned earlier, an entry to Google's Developers Community Program! There're a lot of perks for it but let's first talk business. What do we have to do? In a nutshell: Make an Action for Google Assistant .  But what's an Action ? Action is a feature, or a sub-applicat