Bottom-Up Parsing A bottom-up parser creates the parse tree of the given input starting from leaves towards the root. A bottom-up parser tries to find the right-most derivation of the given input in the reverse order. S→..→o(the right--most derivation of) (the bottom-up parser finds the right-most derivation in the reverse order) Bottom-up parsing is also known as shift-reduce parsing because its two main actions are shift and reduce. -At each shift action,the current symbol in the input string is pushed to a stack. At each reduction step,the symbols at the top of the stack(this symbol sequence is the right side of a production)will replaced by the non-terminal at the left side of that production. There are also two more actions:accept and error. CS308 Compiler Theory 2Bottom-Up Parsing • A bottom-up parser creates the parse tree of the given input starting f l dh rom leaves towar ds t he root. • A bottom-up parser tries to find the right-most derivation of the given i t i th d inpu t in the reverse or der. S ⇒ ... ⇒ ω (the right-most derivation of ω ) ← (the bottom-upp g arser finds the ri ght-most derivation in the reverse order ) • Bottom-up parsing is also known as shift-reduce parsing because its two main actions are shift and reduce. – At each shift action, the current symbol in the input string is pushed to a stack. – At each reduction step, the symbols at the top of the stack (this symbol sequence is the right side of a production) roductio n ) will replaced eplaced by the non-terminal at the left side of that production. roductio n. – There are also two more actions: accept and error. CS308 Compiler Theory 2