# Cs419 lec10 left recursion and left factoring

50 %
50 %
Information about Cs419 lec10 left recursion and left factoring
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 LEFT RECURSION We have to eliminate left recursion because top down parsing methods can not handle left recursive grammars.  A grammar is left recursive if it has a nonterminal A such that there is a derivation A  Aα for some string α  Consider the left recursive grammar A  A α1 | A α2 | β1 | β2  +

Dr. Hussien M. Sharaf REMOVE LEFT RECURSION 1. 2. 3. Let A  other productions of A not starting with A (i.e. β1, β2), followed by A′ (A  β1A′| β2A′) Then let A′  postfix of the productions starting with A (α1, α2) followed by A′ (A′  α1A′|α2A′) Then add |ε to A′ (A′  α1A′|α2A′| ε) +

Dr. Hussien M. Sharaf ELIMINATION OF LEFT RECURSION EXAMPLE E  E+T|T T  T*F|F F  (E)|id  The equivalent non-left recursive grammar is: E  T E′ E′  +TE′|ε T  FT′ T′  *FT′|ε F  (E) | id

Dr. Hussien M. Sharaf LEFT FACTORING  In left factoring it is not clear which of two alternative productions to use to expand a nonterminal A. i.e. if A  αβ1 | αβ2 W e don’t know whether to expand A to αβ1 or to αβ2  To remove left factoring for this grammar replace all A productions containing α as prefix by A  αA′ then A′  β1 | β2

Dr. Hussien M. Sharaf ELIMINATION OF LEFT FACTORING EXAMPLE S  iEtS | iEtSeS | a Eb  The equivalent non-left factored grammar is: S  iEtSS′ | a S′ eS | ε Eb

Dr. Hussien M. Sharaf THANK YOU

 User name: Comment:

## Related pages

### Cs419 lec10 left recursion and left factoring - Education

3. Dr. Hussien M. SharafLL PARSING LL parsing is a technique of top-down parsing. Consists of: Parser stack: that holds grammar symbols: non-terminals and ...

### left - Documents

left. Heading of the PPT will come here. NexGen HR. October 11, 2010. Our Vision. To be a dedicated business partner to our clients To provide them with ...

### Left handedness - Health & Medicine - documents.mx

Cs419 lec10 left recursion and left factoring. Things Left Unshared. Left Out Of Linkedin. Ps348 Laponce Left. Nothing Left to Hold. Brahm, G.post Left ...

### Left facial numbness Ann Schmidt Oct 2005. Patient ...

Left facial numbness Ann Schmidt Oct 2005. Patient Presentation 54 yo female 54 yo female Left facial swelling, left leg swelling and left arm weakness.