Hello everyone and welcome back. We are already in the journey of learning about LL1 parsers. In this session, we are going to observe the LL1 parsing table.
So without any further ado, let's get to learning. Coming to the outcome of today's session, today we are going to observe the construction of LL1 parsing table. Now during the session, top-down parsers, LL1 parsers, we already observed the organization of the LL1 parsers, didn't we?
Now during that session, I told you the LL1 parsers, they need the LL1 parsing table and the stack for the generation of the parse tree. Now before the LL1 parser generates the parse tree, it needs to construct the LL1 parsing table. And for the construction of that, we needed to understand the functions first and follow. And that is exactly why we have been practicing FORCE AND FOLLOW till the last session.
Now let's dive into the construction of LL1 parsing table. So what we are going to do, we are going to take this grammar and I hope you remember this grammar from the session FORCE AND FOLLOW. There we achieved the firsts and follows of all the non-terminals involved this grammar one by one. Now this is the table that we are going to need in order to construct the parsing table.
Now, coming to LL1 parsing table, it has got some rows and some columns. Now, basically, all the non-terminals involved in the grammar will be enlisted as rows, and the columns will be dedicated for the terminal symbols. Now, look at this grammar.
What are the terminal symbols? First, we have id, then we have open parenthesis. Here, the close parenthesis is also a terminal symbol.
Thereafter, we have this asterisk. Then we have this addition symbol. And alongside all these, we are also going to consider the dollar symbol as a terminal symbol. Now before we get into the construction of this entire parsing table, let's try to understand the idea why we are creating it on the first place.
Now if you remember, L1 parsers are actually predictive parsers. So basically, whenever any of these symbols are in the stack, we are going to take this one lookahead symbol That is, the parser will look ahead any of these terminal symbols from the input stream and then predict which of the production rules to follow in order to generate the parse tree. Basically, for a particular terminal symbol, considering a particular non-terminal, the parser is going to predict which of the production rules to use. And there, the firsts and follow are going to help us determine which of the production rules to place under which column of a specific row.
So, let's begin with the non-terminal symbol E. Now, as you can notice, in the first of non-terminal symbol E, we have ID and this open parenthesis. And also, E is involved in only this particular production rule. So, we are going to take this production rule E can be rewritten as capital T followed by E dash in the places of ID and open parenthesis. So, let's place them.
Now, apart from these two terminal symbols, the non-terminal E cannot really generate any of these. So, let's proceed to the next one, that is E'. Now, if you observe E', in the first of E', we have plus and epsilon.
And E'is involved in two different production rules. That is, E'can be rewritten as plus followed by capital T capital E', or E'can be rewritten as epsilon. Now, coming to first, plus is a terminal symbol, isn't it?
So, we are going to place this particular production rule in the section of plus. So, let's do that. Now, e dash has got another production rule that it can also be rewritten as epsilon.
So, in case e dash produces epsilon, the terminal symbols it is going to generate is this dollar symbol and this close parenthesis. Isn't it? So, we are going to place the production rule e dash can be rewritten as epsilon in the columns of dollar and close parenthesis. So, let's do that. I hope you are getting the interpretation.
When we have e dash in the stack and in the input stream if we see plus, we are going to use this particular production rule. And in case the parser sees either the dollar symbol or the close parenthesis, in that particular instance it is going to use these production rules. Let's move on to the next non-terminal, that is t. Now, in the first of t, we have two terminal symbols id and open parenthesis. And T is involved in only one production rule.
So following the drill, we are going to place the production rule in the column of ID and the open parenthesis. Moving ahead to the next non-terminal that is T'. Now, in the first of T', we have the terminal symbol star.
So, the production rule T'can be rewritten as star followed by F followed by T'. This particular production rule is going to be placed in the column of star. Now, just like E', T'is also having another production rule where T'can be rewritten as epsilon.
And following the drill that we followed for E', we are going to fill the columns of plus dollar and close parenthesis for t dash with the production rule, t dash can be written as epsilon. Because those are the terminal symbols which t dash will generate in case t dash ever produces epsilon. Let's move on to the next terminal symbol, that is f. Now, in the first of f, we have the symbols id and open parenthesis. However, f is involved in two different production rules.
Now, in order to generate id, F is definitely going to use this production rule, that is F can be written as ID. So, this particular production rule we will place under the column of ID. Now, coming to the next production rule, that is F can be written as open parenthesis followed by E followed by close parenthesis. Using this one, we can actually generate this open parenthesis.
Therefore, we are going to keep that production rule in the column of open parenthesis. So, this is how the LL1 parsing table is constructed. Basically, there are two rules to follow.
the first one, all the epsilon productions are placed under the follow sets. Notice this, there were only two non-terminal symbols which were involved in the production of epsilons. And in the follow sets of those, we placed all the epsilon productions, didn't we? Now coming to the second rule, the remaining productions are to be placed under the firsts.
And this is the reason why we are very much interested in finding the firsts and the follow of all the non-terminals involved in the grammar so that we can construct the LL1 parsing table. So, in this session, we observed the construction of LL1 parsing table. Alright people, that will be all for this session. In the next session, we are going to observe the LL1 parsing technique. So, I hope to see you in the next one.
Thank you all for watching.