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.