In this class, we are going to discuss about Handle and Handle Pruning. Handle is a substring which matches with right side of the production. If the handle matches with right side of the production, then it is replaced with the corresponding left hand side non-terminal. so with the help of an example we will discuss handy and handle pruning in detail so let us write the grammar let the first production is s implies a a b small e a implies a b c r b b implies d Let the input string is ABBCDE. So hand is during passing of input string.
What is the input string? ABBCDE is the input string. So here we have three columns.
The first column is write sentential form. Second column is handy and the next column is reducing production. so first we have to consider the input string so what is the input string here abb cde is the input string now we have to take a substring and check whether the substring is available in right side of the projection or not? Only A. This A is not available. Why?
Because we have A, A, B, E but we don't have A. A, B is also not available but we have B available in the right side of the projection. So, this B is called as a handle. So, handle is a substring which matches with right side of the production.
If the handle matches with right side of the production, then it is replaced with the corresponding left hand side non-terminal. This replacement is called as reduction. So, reduction is a process of replacing the right hand side substring with the left hand side non-terminal. the left hand side non-terminal. So here what is the hand A?
B is the hand A. And what is the reducing production? A implies B is the reducing production. So now B is reduced with A.
So B, so this B is reduced with A. And what is the remaining input string? So BC, DE is the remaining input string. Now we have to consider one more input string. We don't have A, but here we have B.
We can take B as capital A. If you take B as capital A, if you replace B with capital A, then we get A A C D E. But A, double A. Double A is not available in right side of the production.
So this replacement is not correct one. So we have to choose one more substrate. So here we have A B C which is available in right side of the production. So let us consider the handy as A B C. So handy is a substrate.
So, what is the corresponding production for AVC? A implies AVC. So, now we have to reduce this AVC to A.
So, this AVC is reduced to A. Next, the remaining input string is AA. DE is the remaining input string.
Next, we do not have AA in the right hand side. Here we have D. We can reduce D with B.
So, now let us see. consider d as the handling so d as the handle the corresponding production for d is b implies d so now this d is reduced to b so reduce d to b so the remaining input string is a a b e So what is A A B E? A A B E is nothing but the start symbol of the grammar.
So let us consider A A B E as the start symbol. A A B E as the ending. So for A A B E, what is the corresponding prediction? S implies A A B E. so this a a b is reduced to yes so this is nothing but start symbol of the grammar so this is nothing but bottom of passing in bottom of passing we will construct the passing starting from bottom so bottom means input string and continue use two words the star symbol of the grammar if you consider these reductions then we can say that bottom of parser generates rightmost derivation in reverse order rightmost derivation in reverse order why because here what is the last prediction we are taking So, S for S what is the production?
S implies AAB is the production. So, this is nothing but rightmost derivation. In rightmost derivation we have to consider rightmost non-terminal. So, capital B.
So, capital B is replaced with D. So, A A D E. Next, this is the rightmost non-terminal. So, A is replaced with A A B C D E. So, what is this A? So, this A is nothing but B B C D E. So, we can say that bottom of parser is nothing but it produces the rightmost derivation in reverse order. So, this process is known as handle pruning.
So, handle pruning is obtained by producing the rightmost derivation in reverse order. So, we can say that the rightmost derivation in reverse order can be obtained by handle pruning. So, handle means a substance which matches with right side of the production. Whereas, handle pruning means the rightmost derivation in reverse order.
The rightmost derivation in reverse order. Thank you. is obtained by handle proving so this process is known as handle proving now let's see why we are taking here as right sentential form we have two types of sentential forms are available left sentential form right sentential form left sentential form means leftmost non-terminal is expanded whereas right sentential form means rightmost non-terminal is expanded here every time we are expanding left hand side not terminal only but it is producing rightmost derivation in reverse order it is producing rightmost derivation in reverse order so here we have to scan the input from left to right only left to right is nothing but leftmost derivation leftmost sentential form only but here what it is producing it is producing bottom of passing is producing rightmost derivation in reverse order order.
So that's why we have taken this as right sentential form. Now let us take an example. With the help of that example also we will discuss handle and handle pruning.
So that example is nothing but expression grammar. The basic example. So the first production is E implies this. E implies, E produces, E plus T R T. Second prediction is, T produces, T star F R F. Third prediction is, F produces, left parenthesis E, right parenthesis R I D. So let the input string here is I D star I D. So we have to write handles for this input string. So here we have three columns.
The first column is right sentiential form. Why? Because bottom of parcel produces rightmost derivation in reverse order. So that's why we have taken right sentiential form. And the next one is handy.
So handy is a substance which matches with right side of the projection. If handy matches with right side of the projection, then it is reduced to corresponding non-territorial. So that is nothing but reducing projection. So this is the first column. with which production we are reducing.
So for potamo parser the input is input string. So ID star ID. Where as the output is star symbol of the grammar.
So initially we have to take a handle. So handle means a sub string. So here ID matches with right side of the production.
So we can take ID as a handle. so what is the corresponding prediction for id f implies id so this id is reduced to f0 so reduce id to f so f star id next f so we have f which is available in right hand side. So, we can take f as a hand a.
So, what is the corresponding production for f? So, here f is nothing but hand a. The corresponding production is t implies f.
So, this f is reduced to t now. So, t star id. So, now we have t as well as id so if we take t then we will get e star id so what is id id means f so e star f but e star f is not available in the right side of the projection so now it is better to take id as the handy id as the handy so for id the corresponding projection is f implies id so now reduce this id to f so d star f so t star f is available in right side of the projection why because here we have to scan the input from left to right only so t star f so replace t star f with d so what is the handle of t star f is the handle so for t star f the associated production is t implies t star f so this t star f is reduced to t now so t is available in the right side of the projection So, we can take t as the handle.
So, what is the corresponding production here? e implies t. So, now this t is reducible to e.
So, e is nothing but star symbol of the grammar. So, what is a handle? Handle means a subset.
string which matches with right side of the projection. If the handle matches with right side of the projection, then it is reduced to the corresponding left hand side non-derivative. Handle pruning means the rightmost derivation. So, this is nothing but the rightmost derivation in reverse order. The rightmost derivation in reverse order.
The rightmost derivation in reverse order can be obtained by handle pruning. So, this process is known as handle pruning. So, why we have written right center? because bottom of passing is producing rightmost derivation in reverse order.
So, rightmost derivation it is producing. So, that is why we have taken right sentential form. So, this is about Handel and Handel's derivative.