Top Down Parsing CS164 Lecture 8 Prof Fateman CS 164 Lecture 8 1 Announcements Programming Assignment 2 due Thurs Sept 22 Midterm Exam 1 on Thursday Sept 29 In Class ONE handwritten page 2 sides Your handwriting No computer printouts no calculators or cellphones Bring a pencil Prof Fateman CS 164 Lecture 8 2 Review We can specify language syntax using CFG A parser will answer whether L G and will build a parse tree which is essentially an AST and pass on to the rest of the compiler Next few lectures How do we answer L G and build a parse tree After that from AST to assembly language Prof Fateman CS 164 Lecture 8 3 Lecture Outline Implementation of parsers Two approaches Top down Bottom up Today Top Down Easier to understand and program manually Next Bottom Up More powerful and used by most parser generators Prof Fateman CS 164 Lecture 8 4 Intro to Top Down Parsing Terminals are seen in order of appearance in the token stream t2 t5 t6 t8 t9 1 t2 3 4 t9 7 The parse tree is constructed From the top From left to right Prof Fateman CS 164 Lecture 8 t5 t6 t8 5 Recursive Descent Parsing Consider the grammar 3 10 in text S if E then S else S S begin S L S print E L end L S L E num num Prof Fateman CS 164 Lecture 8 6 Recursive Descent Parsing Parsing S defun s case car tokens S if E then S else S S begin S L S print E L end L S L E num num if eat if e eat then s eat else s begin eat begin s l print eat print e otherwise eat if cheap error can t match if Prof Fateman CS 164 Lecture 8 7 Recursive Descent Parsing Parsing L defun l case car tokens S if E then S else S S begin S L S print E L end L S L E num num end eat end eat s l otherwise eat end Prof Fateman CS 164 Lecture 8 8 Recursive Descent Parsing parsing E S if E then S else S S begin S L defun S print E L end L S L E num num e eat num eat eat num Prof Fateman CS 164 Lecture 8 9 Recursive Descent Parsing utilities Get token pop Parse checks for empty token list defun eat h cond equal h car tokens pop tokens pop x means setf x cdr x t error stuck at s tokens defun parse tokens s if null tokens It is a sentence Prof Fateman CS 164 Lecture 8 10 Recursive Descent Parsing tests defparameter test begin print num num if num num then print num num else print num num end parse test It is a sentence parse if num then num Error stuck at then num Prof Fateman CS 164 Lecture 8 11 This grammar is very easy Why S if E then S else S S begin S L S print E L end L S L E num num We can always tell from the first symbol which rule to use if begin print end Prof Fateman CS 164 Lecture 8 num 12 Recursive Descent Parsing backtracking Example 2 Consider another grammar E T E T T int int T E Token stream is int5 int2 Start with top level non terminal E Try the rules for E in order Prof Fateman CS 164 Lecture 8 13 Recursive Descent Parsing Backtracking Try E0 T1 E2 Then try a rule for T1 E3 E T E T T int int T E But does not match input token int5 int5 int2 Try T1 int Token matches But after T1 does not match input token Try T1 int T2 This will match int but after T1 will be unmatched Parser has exhausted the choices for T1 Backtrack to choice for E0 Prof Fateman CS 164 Lecture 8 14 Recursive Descent Parsing Backtracking Try E0 T1 Follow same steps as before for T1 And succeed with T1 int T2 and T2 int With the following parse tree E0 T1 int5 T2 int2 Prof Fateman CS 164 Lecture 8 15 Recursive Descent Parsing Backtracking Do we have to backtrack Trick is to look ahead to find the first terminal symbol to figure out for sure which rule to try Indeed backtracking is not needed if the grammar is suitable This grammar is suitable for prediction Sometimes you can come up with a better grammar for the same exact language Prof Fateman CS 164 Lecture 8 16 Lookahead makes backtracking unnecessary defun E T case car tokens eat E otherwise nil E T E defun T Lookahead resolves rule choice case car tokens eat E eat T E int eat int T int int T case car tokens look beyond int eat T T int T otherwise nil T int otherwise eat end Prof Fateman CS 164 Lecture 8 17 When Recursive Descent Does Not Work Consider a production S S a suggests a program something like defun S S eat a S will get into an infinite loop A left recursive grammar has a non terminal S S S for some Recursive descent does not work in such cases Prof Fateman CS 164 Lecture 8 18 Elimination of Left Recursion Consider the left recursive grammar S S S generates all strings starting with a and followed by a number of are strings of terminals in these examples Can rewrite using right recursion S S S S Prof Fateman CS 164 Lecture 8 19 More Elimination of Left Recursion In general S S 1 S n 1 m All strings derived from S start with one of 1 m and continue with several instances of 1 n Rewrite as S 1 S m S S 1 S n S Prof Fateman CS 164 Lecture 8 20 General Left Recursion The grammar S A A S is also left recursive even without a leftrecursive RULE because S S This left recursion can also be eliminated Prof Fateman CS 164 Lecture 8 21 Summary of Recursive Descent Simple and general parsing strategy Left recursion must be eliminated first but that can be done automatically Not so popular because common parser generator tools allow more freedom in making up grammars False reputation of inefficiency If hand written powerful error correction and considerable flexibility Sometimes Rec Des is used for lexical analysis Balanced comment delimiters e g In practice backtracking does not happen ever Prof Fateman CS 164 Lecture 8 22 Predictive Parsers generalizing lookahead Like recursive descent but parser can predict which production to use By looking at the next few tokens No backtracking Predictive parsers accept LL k grammars L means left to right scan of input L means leftmost derivation k means predict based on k tokens of lookahead In practice LL 1 is used Prof Fateman CS 164 Lecture 8 23 LL 1 Languages In recursive descent for each non terminal and input token there may be a choice of production LL 1 means that for each non …
View Full Document
Unlocking...