List the different conflicts that occur in bottom-up parsing and give examples for that

Shift-Reduce Parser-

It takes the given input string and builds a parse tree-

• Starting from the bottom at the leaves.
• And growing the tree towards the top to the root.

Data Structures-

Two data structures are required to implement a shift-reduce parser-

• A Stack is required to hold the grammar symbols.
• An Input buffer is required to hold the string to be parsed.

Working-

Initially, shift-reduce parser is present in the following configuration where-

• Stack contains only the $ symbol.
• Input buffer contains the input string with $ at its end.

The parser works by-

• Moving the input symbols on the top of the stack.
• Until a handle β appears on the top of the stack.

The parser keeps on repeating this cycle until-

• An error is detected.
• Or stack is left with only the start symbol and the input buffer becomes empty.

After achieving this configuration,

• The parser stops / halts.
• It reports the successful completion of parsing.

Possible Actions-

A shift-reduce parser can possibly make the following four actions-

1. Shift-

In a shift action,

• The next symbol is shifted onto the top of the stack.

2. Reduce-

In a reduce action,

• The handle appearing on the stack top is replaced with the appropriate non-terminal symbol.

3. Accept-

In an accept action,

• The parser reports the successful completion of parsing.

4. Error-

In this state,

• The parser becomes confused and is not able to make any decision.
• It can neither perform shift action nor reduce action nor accept action.

PRACTICE PROBLEMS BASED ON SHIFT-REDUCE PARSING-

Problem-01:

Consider the following grammar-

E E E

E E x E

E id

Parse the input string id id x id using a shift-reduce parser.

Solution-

The priority order is: id > x >

Problem-02:

Consider the following grammar-

S [ L ] | a

L L , S | S

Parse the input string [ a , [ a , a ] ] using a shift-reduce parser.

Solution-

Problem-03:

Consider the following grammar-

S T L

T int | float

L L , id | id

Parse the input string int id , id ; using a shift-reduce parser.

Solution-

Problem-04:

Considering the string 10201, design a shift-reduce parser for the following grammar-

S 0S0 | 1S1 | 2

Solution-

To gain better understanding about Shift-Reduce Parsing,

Watch this Video Lecture

Download Handwritten Notes Here-

Next Article- Operator Precedence Parsing

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.