Chapter 4: Syntax Analysis Part 1: Grammar ConceptsSyntax Analysis - ParsingAn Overview of ParsingParsing During CompilationParsing ResponsibilitiesKey issues in Error HandlingWhat are some Typical Errors ?Error Recovery StrategiesError Recovery Strategies – (2)Motivating GrammarsContext Free LanguagesContext Free Grammars : Concepts & TerminologyContext Free Grammars : A First LookHow is Grammar Used ?Derivation and Parse TreeDerivation ExampleExample GrammarExample Grammar - TerminologyGrammar ConceptsHow does this relate to Languages?Leftmost and Rightmost DerivationsExamples of LM / RM DerivationsDerivations & Parse TreeParse Trees and DerivationsParse Tree & Derivations - continuedAlternative Parse Tree & DerivationExample Pascal Grammar in YaccSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33Resolving Grammar Problems/DifficultiesResolving Problems/Difficulties – (2)Resolving Problems/Difficulties – (3)How Does This CFG Derive Strings ?Regular Expressions vs. CFGsResolving Grammar Difficulties : MotivationResolving Problems: Ambiguous GrammarsResulting Parse TreeExample : What Happens with this string?Parse Trees for ExampleRemoving AmbiguityResolving Difficulties : Left RecursionWhy is Left Recursion a Problem ?Resolving Difficulties : Left Recursion (2)Resolving Difficulties : Left Recursion (3)Using the AlgorithmUsing the Algorithm (2)Removing Difficulties : -MovesRemoving Difficulties : CyclesRemoving Difficulties : Left FactoringResolving Grammar Problems : Another LookResolving Grammar Problems : Another Look (2)Resolving Grammar Problems : Another Look (3)Resolving Grammar Problems : Another Look (4)Resolving Grammar ProblemsContext-Sensitive Languages - ExamplesHow do you show a Language is a CFL?SolutionsCH4p1.1CSE4100Chapter 4: Syntax AnalysisChapter 4: Syntax AnalysisPart 1: Grammar ConceptsPart 1: Grammar ConceptsProf. Steven A. DemurjianComputer Science & Engineering DepartmentThe University of Connecticut371 Fairfield Way, Unit 2155Storrs, CT [email protected]://www.engr.uconn.edu/~steve(860) 486 - 4818Material for course thanks to:Laurent MichelAggelos KiayiasRobert LeBarreCH4p1.2CSE4100Syntax Analysis - ParsingSyntax Analysis - Parsing An overview of parsing : Functions & An overview of parsing : Functions & ResponsibilitiesResponsibilities Context Free Grammars: Concepts & TerminologyContext Free Grammars: Concepts & Terminology Writing and Designing GrammarsWriting and Designing Grammars Resolving Grammar Problems / DifficultiesResolving Grammar Problems / Difficulties Top-Down Parsing Top-Down Parsing Recursive Descent & Predictive LL Bottom-Up ParsingBottom-Up Parsing LR & LALR Key Issues in Error HandlingKey Issues in Error HandlingConcluding Remarks/Looking AheadConcluding Remarks/Looking AheadCH4p1.3CSE4100An Overview of ParsingAn Overview of ParsingWhy are Grammars to formally describe Languages Important ?1. Precise, easy-to-understand representations2. Compiler-writing tools can take grammar and generate a compiler3. allow language to be evolved (new statements, changes to statements, etc.) Languages are not static, but are constantly upgraded to add new features or fix “old” onesADA  ADA9x, C++ Adds: Templates, exceptions,How do grammars relate to parsing process ?CH4p1.4CSE4100Parsing During CompilationParsing During Compilationinterm represerrorslexical analyzerparserrest of front endsymbol tablesource programparse treeget next tokentokenregular expressions• also technically part or parsing• includes augmenting info on tokens in source, type checking, semantic analysis• uses a grammar to check structure of tokens• produces a parse tree• syntactic errors and recovery• recognize correct syntax• report errorsCH4p1.5CSE4100Parsing ResponsibilitiesParsing ResponsibilitiesSyntax Error Identification / HandlingRecall typical error types:Lexical : MisspellingsSyntactic : Omission, wrong order of tokensSemantic : Incompatible typesLogical : Infinite loop / recursive callMajority of error processing occurs during syntax analysisNOTE: Not all errors are identifiable !! Which ones?CH4p1.6CSE4100Key issues in Error HandlingKey issues in Error HandlingDetectionDetectionActual DetectionFinding position at which they occurReportingReportingClear / accurate presentationRecoveryRecoveryHow to skip over to continue and find later errorsCannot impact compilation of correct programsCH4p1.7CSE4100What are some Typical Errors ?What are some Typical Errors ?#include<stdio.h>int f1(int v){ int i,j=0; for (i=1;i<5;i++) { j=v+f2(i) } return j; }int f2(int u){ int j; j=u+f1(u*u) return j; }int main(){ int i,j=0;for (i=1;i<10;i++) { j=j+i*I; printf(“%d\n”,i); printf("%d\n",f1(j)); return 0;}Which are “easy” to recover from? Which are “hard” ?As reported by MS VC++'f2' undefined; assuming extern returning intsyntax error : missing ';' before ‘}‘syntax error : missing ';' before ‘return‘fatal error : unexpected end of file foundCH4p1.8CSE4100Error Recovery StrategiesError Recovery StrategiesPanic Mode – Discard tokens until a “synchro” token is found ( end, “;”, “}”, etc. ) -- Decision of designer -- Problems: skip input miss declaration – causing more errors miss errors in skipped material -- Advantages: simple suited to 1 error per statementPhase Level – Local correction on input -- “,” ”;” – Delete “,” – insert “;” -- Also decision of designer -- Not suited to all situations -- Used in conjunction with panic mode to allow less input to be skippedCH4p1.9CSE4100Error Recovery Strategies – (2)Error Recovery Strategies – (2)Error Productions: -- Augment grammar with rules -- Augment grammar used for parser construction / generation -- Add a rule for := in C assignment statements Report error but continue compile -- Self correction + diagnostic messages -- What are other rules ? (supported by yacc)Global Correction: -- Adding / deleting / replacing symbols is chancy – may do many changes ! -- Algorithms available