Shift: Reduce Parsing

SHIFT- REDUCE PARSING:
Shift Reduce Parsing uses a stuck to hold grammar symbols and input buffer to hold string to be parsed, because handles always appear at the top of the stack i.e., there's no need to look deeper into 
the state.

A shift-reduce parser has just four actions: 
1. Shift-next word is shifted onto the stack (input symbols) until a handle is formed.
2. Reduce - right end of handle is at top of stack, locate left end of handle within the stack. Pop handle off stack and push appropriate LHS.
3. Accept - stop parsing on successful completion of parse and report success.
4. Error - call an error reporting/recovery routine.

3.1 Possible Conflicts: Ambiguous grammars lead to parsing conflicts.
1. Shift-reduce: Both a shift action and a reduce action are possible in the same state (should we shift or reduce)

Example: dangling-else problem

2. Reduce-reduce: Two or more distinct reduce actions are possible in the same state. (Which production should we reduce with 2). 
 

Example:

Stmt →id (param) (a(i) is procedure call)

Param→ id Expr → id

(expr) /id (a(i) is array subscript)

Stack input buffer action

$&aa (i ) &.$ Reduce by ?

Should we reduce to param or to expr? Need to know the type of a: is it an array or a function. This information must flow from declaration of a to this use, typically via a symbol table.
 

Shift - reduce parsing example: (Stack implementation)

Grammar: E→E+E/E*E/(E)/id Input: id1+id2+id3
 

One Scheme to implement a handle-pruning, bottom-up parser is called a shift-reduce parser. Shift

reduce parsers use stack and an input buffer.

The sequence of steps is as follows:
1. initialize stack with $.
2. Repeat until the top of the stack is the goal symbol and the input token is "end of life". a. Find the handle 
If we don't have a handle on top of stack, shift an input symbol onto the stack.

b.  Prune the handle

if we have a handle (A→b) on the stack, reduce (i) pop /b/ symbols off the stack (ii)push A onto the stack.
 

Example 2:
Goal à Expr
Expr à Expr + term | Expr - Term | Term
Term à Tem & Factor | Term | factor | Factor
Factor à number | id | (Expr) The expression grammar : x - z * y
 

1. shift until the top of the stack is the right end of a handle
2. Find the left end of the handle & reduce.
 

Procedure:
1. Shift until top of stack is the right end of a handle.
2. Find the left end of the handle and reduce.
* Dangling-else problem: 

stmt→if expr then stmt/if expr then stmt/other then example string is: if E1 then if E2 then S1 else S2 has two parse trees (ambiguity) and so this grammar is not of LR(k) type.