Courses

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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!