Hello all, in this video we will see the bottom up evaluation of S-attributed definitions. So this is an example that we have discussed in a couple of previous videos. As an example for S-attributed definition because it only has synthesized attributes in it.
That is all the grammar symbols are deriving its attribute values from its children. The arrows always goes the purchase and reticence. So, we will see how this is evaluated. Actually, the parser is maintaining a stack which is actually a pair of two arrays. That is, it will be having two arrays like this.
In the first array, the grammar symbols will be stored. For example, if it is e, the grammar symbol e will be stored. Here, e dot value, the value will be stored.
That is, here it is simple and the other part will have attribute value. So, like this a tier of arrays is maintained in the form of a stack that is the last and first two data structure and this is how it process or evaluate this data. So, we will see when as it is a stack whenever for example if there is a prediction A gives X, Y, Z when this right side is reduced to the left hand side the top is updated.
accordingly that is the three symbols here will be replaced with the one symbol on the left hand side isn't it when xyz is reduced to a three symbols here is replaced with a single symbol which is appearing on the left hand side so the toe will be decremented by two this is how it works that is like the usual step whenever reduction happens the right hand side will be replaced by the left hand side and the toe pointer will be incremented or decremented accordingly in case of prediction now it will be a recommendation for sure and i will see an example using this particular input the very same input we will take the very same input we will put an n also because this grammar contain an n for new line which indicates the end of the string is in red so we will have input We will have the stack which is a pair of two arrays as I have told you and we will have the reducing productions. Productions used for reducing. So these are the three columns that we will have. So initially the input is 3 plus 4 into 5n.
Isn't it? See initially the stack is empty. now prediction has been used next time we will move the very first simple in the input to this stack so it will be plus 4 into 5 n and on this stack it will be simply 3 on this stack it will be 3 and uh i mean The symbol is appearing as 3. If the symbol do not have any attribute value, doesn't have any attribute value, we can simply put a minus. Now, the prediction used is nothing.
Now, next time, see we can reduce this 3 to f. isn't it? Next time we will use the we will reduce this 3 to f in that case f will be the simple and 3 will be its attribute value.
So the prediction used is on this tag this is the grammar simple and the second array is the attribute value. So the prediction used is f gives digit. see f is giving digit if you want to see the exact grammar uh i'll yeah i'll write the grammar at the end of this video or you can refer to the previous video now i'll write the grammar towards the end of this uh video so that you can refer that grammar so first giving digits now we can see next is the simple plus so if you want to give plus You have to somehow turn this into E, isn't it?
Because only E is deriving plus. E plus T something like that. So you have to keep on converting this F into E. Then only this plus can be introduced. Otherwise there is no point in having plus.
So we will keep on reducing F until it becomes E. So F becomes T. Value is 3. The prediction used is T gives F.
Now plus 4. into 5n and the t becomes e because e gives t. So it becomes e and the value is 3. The production used is E gives T. See now we got E.
Now there is a prediction like E gives E plus T. Now we can consider the plus. That is whenever we are reducing we just have to consider the remaining symbols in the input.
Okay that is when we are reducing when we are attempt to reduce we should always look at the rest of the input. So here we have plus. So we will move that plus to this tag.
So 4 into 5n. So we have e with value 3 plus with value nil. Plus do not have any attribute value as you know. We didn't use any predictions.
Now we can move 4 to this tag. So it becomes star 5n. When you move 4 you will get e with the value 3. plus with no attribute value and 4 with no attribute value.
Next, we have to reduce 4 till it becomes t. Then only we can reduce it to e, isn't it? No, you have to reduce it to t.
Then only you can have the star here. So, you have to keep on reducing 4 until it becomes t. So we are reducing, we are trying to reduce the 4 to t.
So it becomes f first, the value 4. So the prediction used is f gives digit. Now again we are reducing, e gives t plus nothing. F is reduced to t.
So t giving 4. t with the value 4. So the production used is t gives f. Now that we have t we can introduce that star. So I am pushing star onto this tag.
So I will get 5n here. and the stack is growing, e is having value 3, now plus is having no value, so plus and minus, this means that no attribute value, now it is t with value 4, and next it is star with value 3, now you can move the next symbol to this stack, that is this becomes n, and you can move e with value 3, plus, S with value nothing, H with value nothing, T with value 4 and star with value nothing. Sorry. E with value 3, plus with no value, T with value 4. Start with no value and 5 onto the start with no value. Now if you want to reduce 5, 5 should be reduced to 2. Then only you can apply t star represented.
So in the next step, we will reduce e with value 3, less with no value. t with value 4, star with value nothing and sorry on the next step we will have e with value 3, plus with no value, t with value 4 Star with no value and 5 is replaced to f. f with value 5. Isn't it?
See the next step this is f and star and t. t star. of can be that the production reduction used at this stage is f gives digit that is fire has been replaced by f see um rubbing from the bottom see now uh now um See T star f can be replaced by T because there is a prediction T giving T star f isn't it?
So T star f the top three positions can be replaced by T star f that is you will have n itself. That is, I am continuing on the top. See, you will have N itself here but on this stack you are having the T star f can be replaced by T. So, you have E with value 3 plus with value nothing then T star f has been replaced by T with the value T star f 5 into 4 20. T star f with value 20. Prediction used is t giving t star f.
Sorry, t star. Now, see this is e plus t. e plus t can be replaced by e. You know, that is it.
e plus t is equal to e. So, this is e. The prediction used is e gives e plus t.
Now, you can shift this n also onto this with e plus t. The value is 23. Now you can shift n also into this tag. Then you will get nothing here.
And this is e with value 23 followed by n. When this n and all appears you can replace it by l gives en. Now the value will be printed which is 23. So this is how we evaluate. This is how we perform the bottom up evaluation of s-attributed definitions we have.
a stack which is implemented using two pair of arrays first array is used to hold the grammar symbol second array is used to hold the attribute values whenever a reduction can be made we will perform the appropriate reduction and when we keep on reducing grammar symbols we just have to consider the remaining symbols in the input to make the to take the correct reduction decision So, we will go to the output 23 here and that is the output. So, this is how we evaluate the S-articulated definition is bottom up using stat. And then as it is a stat, whenever you are performing an evaluation, that is whenever you are reducing x, y, z into a, the top should be decremented accordingly. That is the only thing. So, that is all about bottom up evaluation of S-articulated definitions.
Thank you. So this was the grammar used. Thank you.