Error RecoveryPreviouslySlide 3Local Error RecoveryCaution…Global Error RepairBurke-Fisher Error RepairYacc Support for Error CorrectionError RecoveryCS 671February 5, 20082CS 671 – Spring 2008PreviouslyTop-Down Parsing, e.g. LL(1)Bottom-Up Parsing, e.g. LR(1)Next Question: What if the compiler finds a syntactic error?3CS 671 – Spring 2008Error RecoveryWhat if the compiler finds a syntactic error?•Ideally, report all errors, not just firstApproaches:• Local error recovery – Find synch point, resume• Global error recovery – Change input, resume4CS 671 – Spring 2008Local Error Recovery•Informally, skip to next synchronizing token•Exampleexp  IDexp  exp + expexp  ( exps )exps  expexps  exps ; exp1.Skip to next SEMICOLON or RPAREN2.Resume parsingHow? Introduce new terminal symbols and rules:exp  ( error )exps  error ; exp5CS 671 – Spring 2008Caution…Unfortunately, error states can cause problems when semantic actions are attached (unless we’re careful). Consider:statements : statements exp SEMICOLON| statements error SEMICOLON| /* empty */exp : increment exp decrement | IDincrement: LPAREN {nest=nest+1;}increment: RPAREN{nest=nest-1;}6CS 671 – Spring 2008Global Error RepairAnother way to recover: insert/delete tokens before the point of the error let type a := intArray [ 10 ] of 0 in … ^(real error: type should be var)Global repair: Find smallest set of insertions or deletions that would convert string to a syntactically correct string (not always at error point)Outcome: type  var (1 replacement)7CS 671 – Spring 2008Burke-Fisher Error Repair•Tries every possible single-token insertion, deletion, replacement up to K tokens before error.• Chooses: Whichever replacement, etc. allows it to progress farthest after error• Realistic limit: 4 tokens beyond error is “good enough”Kerror8CS 671 – Spring 2008Yacc Support for Error Correction• The %value directive (used during insertions)%value ID (“bogus”)%value INT (1)%value STRING (“”)• Programmer specified substitutions%change EQ -> ASSIGN | ASSIGN -> EQ | SEMICOLON ELSE -> ELSE | -> RBRACEScope