Cs419 lec8 top-down parsing

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

Dr. Hussien M. Sharaf TOP-DOWN PARSING A parser is a top-down if it discovers a parse tree top to bottom.  A top-down parse corresponds to a preorder traversal of the parse tree.  A left most derivation is applied to each step. 

Dr. Hussien M. Sharaf LL PARSING LL parsing is a technique of top-down parsing.  Consists of:     Parser stack: that holds grammar symbols: non-terminals and tokens. Parsing table: that specifies the parser actions (Match, Predict, Accept, Error). Driver function: that interacts with parser stack, parsing table, and scanner. Scanner Next token Parser driver Parsing table Output Parsing stack

Dr. Hussien M. Sharaf PROBLEMS FACING LL(1) PARSERS 1. 2. Left recursion. Left factoring. Both problems prevents any LL parser from deciding deterministically which rule should be fired.

Dr. Hussien M. Sharaf TOP-DOWN PARSER ACTIONS     Match: to match top of parser stack with next input token. Predict: to predict a production and apply it in a derivation step. Accept: parsed successfully. Error: failure.

Dr. Hussien M. Sharaf EXAMPLE 1 Consider the following grammar: S  ( S ) | to parse (()), we follow these steps: Parser stack Input Parser action S (())$ Predict S (S) (S) (())$ Match ( S) ())$ Predict S (S) (S)) ())$ Match ( S)) ))$ Predict S )) ))$ Match ) ) )$ Match ) Empty $ Accept

Dr. Hussien M. Sharaf EXAMPLE 2 Consider the following grammar: 1.E 2.Q 3.Q 4.Q 5.T TQ +TQ -TQ FR 6.R 7.R 8.R 9.F 10.F *FR /FR (E) id

Dr. Hussien M. Sharaf EXAMPLE 2 (CONT.) The parsing table for id*(id+id)$ is: + E Q T R F - 2 * / ( 1 3 ) 4 5 8 8 id 1 6 7 4 5 8 9 $ 8 10

Dr. Hussien M. Sharaf EXAMPLE 2 Consider the following grammar: 1.E 2.Q 3.Q 4.Q 5.T TQ +TQ -TQ FR 6.R 7.R 8.R 9.F 10.F *FR /FR (E) id

Dr. Hussien M. Sharaf EXAMPLE 2 (CONT.) To parse id*(id+id)$, we follow these steps: stack Input Parser action id RQ)RQ id+id)$ E id*(id+id)$ Predict E TQ RQ)RQ +id)$ Predict R TQ id*(id+id)$ Predict T FR Q)RQ +id)$ Predict Q +TQ FRQ id*(id+id)$ Predict F id +TQ)RQ +id)$ Match + id RQ id*(id+id)$ Match id TQ)RQ id)$ Predict T FR RQ *(id+id)$ Predict R*FR FRQ)RQ id)$ Predict Fid *FRQ *(id+id)$ Match * id RQ)RQ id)$ Match id FRQ (id+id)$ Predict F(E) RQ)RQ )$ Predict R (E)RQ (id+id)$ Match ( Q)RQ )$ Predict Q E)RQ id+id)$ Predict ETQ )RQ )$ Match ) TQ)RQ id+id)$ Predict T FR RQ $ Predict R FRQ)RQ id+id)$ Predict F id Q $ Predict Q id RQ)RQ id+id)$ Match id Empty $ Accept Match id

Dr. Hussien M. Sharaf THANK YOU