Bottom Up Parsing Handle and Reduction
In this class, We discuss Bottom-Up Parsing Handle and Reduction.
For Complete YouTube Video: Click Here
The reader should have a prior understanding of top-down parsing techniques. Click Here.
Top-Down Parsing
The below diagram shows the top-down parsing example grammar and derivation tree.
The top-down parsing reads input from left to right.
The grammar expands from the starting non-terminal.
The grammar generates the leftmost derivation tree.
Bottom-Up Parsing:
The bottom-up parsing reads the input left to right.
The bottom-up parser generates the rightmost derivation tree in reverse.
The below example shows the grammar and derivation tree step by step.
Example: id * id
We reduce the first ‘id’ to F.
In bottom-up parsing, we reduce the productions.
The above example shows the step-by-step reduction of the input id * id.
Finally, We reduce the input to the starting non-terminal symbol.
Handle:
The handle is the substring that matches the body of the production.
The below table shows the example handles during the reduction of id * id.
The first id in the input string id * id matched the production body F – id.
We do the reduced action when the matching body is identified.
Important: In the above table, in the third line, we have the symbol, T.
But T is not considered as a handle to reduce to E.
In the fifth line, we considered T to reduce to E.
When to consider T to reduce to E? The next classes will deal with when to consider the handle for reduction.