# 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

 User name: Comment:

## Related presentations

#### Filosof_Skovoroda

November 22, 2017

#### Caroline Clausen PPT Proposal_5

November 22, 2017

#### «Внимание дети»

November 22, 2017

#### Get Full Furnished And Safe Paying Guest For Girl

November 18, 2017

#### Study in Canada and have a high-quality life

November 22, 2017

#### Tvori_Skovoroda

November 22, 2017

## Related pages

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

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

### Cs419 lec8 top-down parsing - Education - documents

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

### 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