LR(0) Parser

Creator
Creator
Alan JoAlan Jo
Created
Created
2022 Oct 26 5:40
Editor
Editor
Alan JoAlan Jo
Edited
Edited
2022 Oct 26 23:37
Refs
Refs
R means rightmost derivation in reverse
Task in LR parsing: determining the handle, thus the next RSF
LR(0) means no need to look ahead to determine the handle
 
Item: a state representing the status of RHS recognition
  • use a dot “.” to separate the recognized part and the rest
 

item

a state representing the status of RHS recognition

initial items

 
 
 

complete items

handle candidates
 
 
Action: shift or reduce (using which rule) based on state
 
 
table header is
  • State
  • Action
    • shift
    • accept
    • reduce
  • Rule if action is reduce
 
 

LR(0) Conflicts

Action (shift/reduce) at a state is unclear
  • Shift-reduce conflict : one item can shift, another can reduce
  • Reduce-reduce conflict : two (or more) items that can reduce
If no state has conflicts, the grammar is LR(0) grammar
 
 
 
 

Recommendations