Compiler-Design Notes | EduRev

: Compiler-Design Notes | EduRev

 Page 1


Compiler Design 
 
11. Table-Driven Bottom-Up Parsing: LALR  
More Examples for LR(0), SLR, LR(1), LALR 
Kanat Bolazar 
February 23, 2010 
Page 2


Compiler Design 
 
11. Table-Driven Bottom-Up Parsing: LALR  
More Examples for LR(0), SLR, LR(1), LALR 
Kanat Bolazar 
February 23, 2010 
2 
Bottom-Up Parsers 
• We have been looking at bottom-up parsers. 
• They are also called shift-reduce parsers 
– shift: Put next token in the stack, move on 
– reduce: Tokens combine to RHS of a rule; reduce this to the 
nonterminal on the left. 
• Scan the input from Left to Right 
• Produce a Rightmost derivation from the grammar 
• Not all context free languages have LR grammars 
 
Page 3


Compiler Design 
 
11. Table-Driven Bottom-Up Parsing: LALR  
More Examples for LR(0), SLR, LR(1), LALR 
Kanat Bolazar 
February 23, 2010 
2 
Bottom-Up Parsers 
• We have been looking at bottom-up parsers. 
• They are also called shift-reduce parsers 
– shift: Put next token in the stack, move on 
– reduce: Tokens combine to RHS of a rule; reduce this to the 
nonterminal on the left. 
• Scan the input from Left to Right 
• Produce a Rightmost derivation from the grammar 
• Not all context free languages have LR grammars 
 
3 
Shift-Reduce Parsing 
• Example: 
• Grammar: 
E -> 1 | E - 1                (rules 1 and 2) 
• Input: 
1 - 1 $       ($ : End of file / tape) 
• Steps: 
1            shift 
E            reduce by rule 1 
E -         shift 
E - 1      shift 
E - E     reduce by rule 1 
E            reduce by rule 2 
E $         accept 
Page 4


Compiler Design 
 
11. Table-Driven Bottom-Up Parsing: LALR  
More Examples for LR(0), SLR, LR(1), LALR 
Kanat Bolazar 
February 23, 2010 
2 
Bottom-Up Parsers 
• We have been looking at bottom-up parsers. 
• They are also called shift-reduce parsers 
– shift: Put next token in the stack, move on 
– reduce: Tokens combine to RHS of a rule; reduce this to the 
nonterminal on the left. 
• Scan the input from Left to Right 
• Produce a Rightmost derivation from the grammar 
• Not all context free languages have LR grammars 
 
3 
Shift-Reduce Parsing 
• Example: 
• Grammar: 
E -> 1 | E - 1                (rules 1 and 2) 
• Input: 
1 - 1 $       ($ : End of file / tape) 
• Steps: 
1            shift 
E            reduce by rule 1 
E -         shift 
E - 1      shift 
E - E     reduce by rule 1 
E            reduce by rule 2 
E $         accept 
4 
LR(0) Table: Reduce on Any Token 
s1:   S ? •E   ,   E ? •E - 1  ,   E ? •1 
        action(s1, '1') = shift2         goto(s1, E) = s3 
s2:   E ? 1•      action(s2, on any token) = reduce by rule2 
s3:   S ? E•  ,   E ? E• - 1 act(s3, EOT)=accept   act(s3, '-')=s4 
s4:   E ? E - •1 action(s4, '1') = shift5 
s5:   E ? E - 1•  action(s5, on any token) = reduce by rule1 
 
LR(0) Action Goto 
State - 1 EOT E 
s1 s2 s3 
s2 r2 r2 r2 
s3 s4 accept 
s4 s5 
s5 r1 r1 r1 
Page 5


Compiler Design 
 
11. Table-Driven Bottom-Up Parsing: LALR  
More Examples for LR(0), SLR, LR(1), LALR 
Kanat Bolazar 
February 23, 2010 
2 
Bottom-Up Parsers 
• We have been looking at bottom-up parsers. 
• They are also called shift-reduce parsers 
– shift: Put next token in the stack, move on 
– reduce: Tokens combine to RHS of a rule; reduce this to the 
nonterminal on the left. 
• Scan the input from Left to Right 
• Produce a Rightmost derivation from the grammar 
• Not all context free languages have LR grammars 
 
3 
Shift-Reduce Parsing 
• Example: 
• Grammar: 
E -> 1 | E - 1                (rules 1 and 2) 
• Input: 
1 - 1 $       ($ : End of file / tape) 
• Steps: 
1            shift 
E            reduce by rule 1 
E -         shift 
E - 1      shift 
E - E     reduce by rule 1 
E            reduce by rule 2 
E $         accept 
4 
LR(0) Table: Reduce on Any Token 
s1:   S ? •E   ,   E ? •E - 1  ,   E ? •1 
        action(s1, '1') = shift2         goto(s1, E) = s3 
s2:   E ? 1•      action(s2, on any token) = reduce by rule2 
s3:   S ? E•  ,   E ? E• - 1 act(s3, EOT)=accept   act(s3, '-')=s4 
s4:   E ? E - •1 action(s4, '1') = shift5 
s5:   E ? E - 1•  action(s5, on any token) = reduce by rule1 
 
LR(0) Action Goto 
State - 1 EOT E 
s1 s2 s3 
s2 r2 r2 r2 
s3 s4 accept 
s4 s5 
s5 r1 r1 r1 
5 
SLR(1) Table: Reduce Depends on Token 
s1:   S ? •E   ,   E ? •E - 1  ,   E ? •1 
        action(s1, '1') = shift2         goto(s1, E) = s3 
s2:   E ? 1•      action(s2, {-, EOT}) = reduce by rule2 
s3:   S ? E•  ,   E ? E• - 1 act(s3, EOT)=accept   act(s3, '-')=s4 
s4:   E ? E - •1 action(s4, '1') = shift5 
s5:   E ? E - 1• action(s5, {-, EOT}) = reduce by rule1 
 
SLR(1) Action Goto 
State - 1 EOT E 
s1 s2 s3 
s2 r2 r2 
s3 s4 accept 
s4 s5 
s5 r1 r1 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!