Cs419 lec8 top-down parsing

67 %
33 %
Information about Cs419 lec8 top-down 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 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

Add a comment

Related presentations

Related pages

Cs419 lec8 top-down parsing - Education - docslide.us

Cs419 lec8 top-down parsing. by arab-open-university-and-cairo-university
Read more

Cs419 lec8 top-down parsing - Education - documents

The document was removed. Please view another documents 1 × Close Share Cs419 lec8 top-down parsing
Read more

Cs419 lec11 bottom-up parsing - Education - documents

Cs419 lec11 bottom-up parsing; Cs419 lec11 bottom-up parsing Nov 20, 2014 Education arab-open-university-and-cairo-university. of 13
Read more

Cs419 lec11 bottom-up parsing - Education

Cs419 lec11 bottom-up parsing. by arab-open-university-and-cairo-university. on Nov 20, 2014. Report Category: Education. Download: 0 Comment: 0. 543.
Read more

Principle of Complier Design Prof. Y. N. Srikant ...

So, let us move on to recursive descent parsing. Recursive descent parsing is a top down parsing strategy and basically instead of a table driven, ...
Read more