Cs419 lec10 left recursion and left factoring

1. Compilers Welcome to a journey to CS419 Lecture 10 Left recursion and left factoring Cairo University FCI Dr. Hussien Sharaf Computer Science Department [email protected]

2. 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 S d c A b a

3. 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. Dr. Hussien M. Sharaf Scanner Parser driver Parsing table Output Next token Parsing stack

4. Problems facing LL(1) parsers Left recursion. Left factoring. Both problems prevents any LL parser from deciding deterministically which rule should be fired. Dr. Hussien M. Sharaf

5. 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 +

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

7. 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 ′  +T E ′| ε T  FT′ T ′  *FT′| ε F  (E) | id Dr. Hussien M. Sharaf

8. 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

9. Elimination of Left factoring Example S  iEtS | iEtS eS | a E  b The equivalent non-left factored grammar is: S  iEtS S ′ | a S′ eS | ε E  b Dr. Hussien M. Sharaf

10. Thank you Dr. Hussien M. Sharaf