Bottom-Up Parsing CS308 Compiler Theory
Bottom-Up Parsing CS308 Compiler Theory 1
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 2
Bottom-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
Shift-Reduce Parsing A shift-reduce parser tries to reduce the given input string into the starting symbol. a string>the starting symbol reduced to 。 At each reduction step,a substring of the input matching to the right side of a production rule is replaced by the non-terminal at the left side of that production rule. If the substring is chosen correctly,the right most derivation of that string is created in the reverse order. Rightmost Derivation: Shift-Reduce Parser finds: CS308 Compiler Theory 3
Shift-Reduce Parsing • A shift-reduce parser tries to reduce the given input string into the starting symbol. a string Î the starting symbol reduced to • At each reduction step, a substring of the input matching to the right side of a production rule is replaced by the non production rule is replaced by the non -terminal at the left side of that production rule. terminal at the left side of that production rule. • If the substring is chosen correctly, the right most derivation of that string is created in the reverse order. Rightmost Derivation: S ⇒ ω *rm Shift-Reduce Parser finds: ω ⇐ ... ⇐ S rm rm CS308 Compiler Theory 3
Shift-Reduce Parsing--Example S→aABb input string:aaabb A->aA a aaAbb B→bBIb aAbb reduction aABb S SaaBb aAbb aaAbb aaabb Right Sentential Forms How do we know which substring to be replaced at each reduction step? CS308 Compiler Theory
Shift-Reduce Parsing -- Example S → aABb input string: aa abb A → aA | a aaAbb B → bB | b aA b b ⇓ reduction aABb S S ⇒ aABb ⇒ aA bb ⇒ aaAbb ⇒ aa abb rm rm rm rm Right Sentential Forms • How do we know which substring to be replaced at each reduction step? CS308 Compiler Theory 4
Handle Informally,a handle of a string is a substring that matches the right side of a production rule. But not every substring matches the right side of a production rule is handle A handle of a right sentential form y (=aBo)is a production rule a-→βand a position ofy where the string B may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation ofy. S台0A0三0β0 rm rm If the grammar is unambiguous,then every right-sentential form of the grammar has exactly one handle. We will see that o is a string of terminals. CS308 Compiler Theory 5
Handle • Informally, a handle of a string is a substring that matches the right side of a prod ction r le of a production rule. – But not every substring matches the right side of a production rule is handle • A h dl an e of i h i lf f a right sentential form γ (≡ αβω) is a production rule A → β and a position of γ where the string where the string β may be found and replaced by A to produce may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ. S ⇒ αAω ⇒ αβω If th i bi th i ht t ti l f f th rm rm * • If the grammar is unambiguous, then every right-sentential form of the grammar has exactly one handle. • We will see that ω is a string of terminals CS308 Compiler Theory 5 We will see that ω is a string of terminals