Cs419 lec11 bottom-up parsing

50 %
50 %
Information about Cs419 lec11 bottom-up parsing
Education

Published on February 20, 2014

Author: hussiensharaf

Source: slideshare.net

WELCOME TO A JOURNEY TO CS419 Dr. Hussien Sharaf Computer Science Department dr.sharaf@from-masr.com

Dr. Hussien M. Sharaf LR PARSING  LR(1) parsing is a technique of bottom-up parsing.     L: scan input string from left to right. R: uses right most derivation. 1: uses one token ahead to decide which rule to use for reduction. Consists of:    Parser stack: that holds grammar symbols: non-terminals and tokens. Parsing table: that specifies the parser actions (Shift, Reduce, Accept, Error). Driver function: that interacts with parser stack, parsing table, and scanner. Output Scanner Next token Parser driver Parsing table Parsing stack

Dr. Hussien M. Sharaf BOTTOM-UP PARSER ACTIONS     Shift: parser shifts the next token on the parser stack. Reduce: parser reduces the RHS of a production to its LHS. Accept: parsed successfully. Error: failure.

Dr. Hussien M. Sharaf BOTTOM-UP PARSING A parser is a bottom-up if it traverse a parse tree bottom up.  A right most derivation is applied to each step.  Bottom-up parsers are preferred in practice.  They do not need left factoring.  It reduces the input string to the starting symbol by using the reverse of production rules. 

Dr. Hussien M. Sharaf BOTTOM-UP (CONT.) Consider the following grammar: E→T+E|T T → id * T | id | (E) ; Input string: id + id * id  Input string id * id + id id * T + id T + id T+T T+E E Rules T → id T → id * T T → id E→T E→T+E Is there another parsing for the same input string using bottom up algorithm?

Dr. Hussien M. Sharaf BOTTOM-UP (CONT.) Input string id * id + id id * id + T id * T + T T+T T+E E   Rules T → id T → id T → id * T E→T E→T+E Is there another parsing for the same input string using bottom up algorithm? What happens if “T + T” was reduced to “E + T”? Would the parsing still continue?

Dr. Hussien M. Sharaf PARSING TREE E Input string id * id + id id * id + T id * T + T T+T T+E E E T T T i d * i d + i d

Dr. Hussien M. Sharaf PARSING TREE Consider the following grammar: E→T+E|T T → id * T | id | (E) ; Input string: id + id * id  But what if we start with reducing the first id to T as follows: Input string id * id + id T * id + id  Rules T → id We would be stuck with “T * id” or “T * T” or “T * E”

Dr. Hussien M. Sharaf CONFUSING POINTS  How does the parser choose whether to shift or reduce?  General strategy is to reduce whenever it is possible otherwise shift.  How does the parser handles the situations when there is more than one choice for reducing?  Even non-ambigious grammars can cause this situation. The parser uses back-tracking to decide which choice is correct.

Dr. Hussien M. Sharaf Example 1 Consider the following grammar…. A(A) | a Stack Input Action $ ((a))$ Shift $( (a))$ Shift $(( a))$ Shift $((a ))$ Reduce A a $((A ))$ Shift $((A) )$ Reduce A (A) $(A )$ Shift $(A) $ Reduce A (A) $A $ Accept

Dr. Hussien M. Sharaf LR Parsing Example 2 Stack Input Action $ $ id $T $E $E+ $E+( $ E + ( id $E+(T $E+(E $E+(E+ $ E + ( E + id $E+(E+T $E+(E $E+(E) $E+T $E id + ( id + id ) $ + ( id + id ) $ + ( id + id ) $ + ( id + id ) $ ( id + id ) $ id + id ) $ + id ) $ + id ) $ + id ) $ id ) $ )$ )$ )$ $ $ $ S R, G3 R, G2 S S S R, G3 R, G2 S S R, G3 R, G1 S R, G4 R, G1 A G1: G2: G3: G4: E E T T     E+T T id (E)

Dr. Hussien M. Sharaf Example 3

Dr. Hussien M. Sharaf THANK YOU

Add a comment

Related presentations

Related pages

Cs419 lec11 bottom-up parsing - Education

Cs419 lec11 bottom-up parsing. by arab-open-university-and-cairo-university
Read more

Cs419 lec11 bottom-up parsing - Education - documents

4. Dr. Hussien M. SharafBOTTOM-UP PARSING A parser is a bottom-up if it traverse a parse tree bottom up. A right most derivation is applied to each step ...
Read more

Parsing - Education - documents.mx

Cs419 lec11 bottom-up parsing Comments. RECOMMENDED. Parsing. Kuligowski Parsing. Palindrome Parsing. Parsing Table.c. essential parsing. Parsing SWIFT.
Read more