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!