Word

Compilers
Bottom-Up Parsing

Alex Aiken

Bottom-Up Parsing

• Bottom-up parsing is more general than (deterministic) top-down parsing – And just as efficient – Builds on ideas in top-downparsing • Bottom-up is the preferred method

Alex Aiken

Bottom-Up Parsing

• Bottom-up parsers don’t need left-factored grammars • Revert to the “natural” grammar for our example:
ET+E|T T int * T | int | (E)

• Consider the string: int * int + int
Alex Aiken

Bottom-Up Parsing

Bottom-up parsing reduces a string to the start symbol by inverting productions
int * int + int int *T + int T + int T+T T+E E T  int T  int * T T  int ET ET+E

Alex Aiken

Bottom-Up Parsing

Note the productions, read backwards, trace a rightmost derivation
T  int T  int * T T  intET
ET+E

int * int + int int * T + int T + int T+T
T+E E

Alex Aiken

Bottom-Up Parsing

Important Fact #1 about bottom-up parsing: A bottom-up parser traces a rightmost derivation inreverse

Alex Aiken

Bottom-Up Parsing E T E

int * int + int int * T + int

T + int
T+T

T+E
E

T
int * int +

T
int
Alex Aiken

Bottom-Up Parsing

int * int + int

int

*int

+

int
Alex Aiken

Bottom-Up Parsing

int * int + int int * T + int

T
int * int + int
Alex Aiken

Bottom-Up Parsing

int * int + int int * T + int

T + int

T

T
int *int + int
Alex Aiken

Bottom-Up Parsing

int * int + int int * T + int

T + int
T+T

T

T
int * int +

T
int
Alex Aiken

Bottom-Up Parsing

int * int + int int * T + int

T +int
T+T

T

E

T+E

T
int * int +

T
int
Alex Aiken

Bottom-Up Parsing E T E

int * int + int int * T + int

T + int
T+T

T+E
E

T
int * int +

T
int
Alex Aiken

Forthe given grammar, what is the correct series of reductions for the string: -(id + id) + id
-(id + id) + id -(id + E’) + id -(id + E) + id -(E’ + E) + id -(E) + id -E’ + id E’ + id E’ + E’ E’ + E...