CPS 140 - Mathematical Foundationsof CSDr. S. Ro dgerSection: The Structure of a Compiler1.1 What is a Compiler?I. TranslatorDenition:program in translator program inlanguage!for!languageX X Y1Examples:Source Ob jectLanguage Language Name ExampleHigh High prepro c ratfor!f77m4, cppAssem. Mach. assemb asHigh Mach. compil g++, javacAny Level executes interp BASICimmed. c shellapl, lispjava2Prepro cessorfor i=1 to n do(stmts)end for#i = 1while (i<=n) do(stmts)i = i + 1end while3skeletal source program#prepro cessor#source program#compiler#target (ob ject) assembly program#assembler#4III. Compilerprogram in program inhigh level!compiler!machinelanguage X for X language Y51.2 STRUCTURE OF A COMPILERcodeintermediate codeintermediateparse treestokensGeneral OverviewHandlingErrorManagementSymbol TableObject ProgramGenerationCodeOptimizationCode Code GenerationIntermediateSyntax AnalysisLexical AnalysisSource Code61.3 PHASES OF COMPILATION1.3.1 Lexical Analysis (Scanner)a. Purp ose: Read the same programcharacter by character grouping theminto atomic units called \tokens."b. Tokens:dep end on language and compilerwriterExamples:reserved words if, forop erators+;; <;=constants 0, 4.89punctuation (,g, [identiers sb, chtreated as a pair: token.typ e andtoken.value7c. Exampleif (x<=0) x = y+zwhen put through lexical analyzerpro duces:token typ e valueif 25( 28id 23 \x"<=27int constant 22 0) 38id 23 \x"= assgnment 4id 23 \y"+34id 23 \z"8d. How do es one build a lexicalanalyzer?from scratchlexe. Preview of Lexidea: tokens describ ed by regularexpressionsbasic syntax:regular expression, actionbasic semantics:if match regular expression, thendo action.Example:%%\if " return(25);\(\ return(28);[0-9]+return(22);9f. RemarksBesides returning token typ es andvalues, the lexical analyzer mighta) print error messagesb) insert identiers in the symboltable1.3.2 Syntax Analysis (Parsing)a. Purp ose:b. Syntax:10c. Parse Treeif (x<=0) x = y+zididexpr+exprexpridrhs=lhsassg. stmtconstantidexpressionrelopexpression relationstatement)condition(if if-statementstatement<=d. How do es one build a parser?from scratchusing a parser generator such asyacc111.3.3 Intermediate Co de Generatora. Purp ose: Traverse the parse tree,pro ducing simple intermediate co de.b. Three-Address Co de:Instructions:1. id := id op id2. goto lab el3. if condition goto lab el12Example:if (x<=0) x = x+z#if (x<=0) goto L1goto L2L1: x := y + zL2:1.3.4 Intermediate Co de Generationa. Purp ose: Transform theintermediate co de into \b etter" co de.13b. Examples1) Rearrangement of Co deif (x<=0) goto L1 if (x>0 goto L2goto L2!x = y+zL1: x = y+z L2:L2:2) Redundancy Eliminationa = w+x+y T1 = x+y!a = w + T1b = x+y+z b = T1 + z143) Strength Reductionx2!x xexp ensive!cheapop erator op erator4) Frequency Reductionfor (i=1; i<n; i=i+1)fT1 = sqrt(26)x = sqrt(26)!for (i=1; i<n; i=i+1)gx = T1gc. Remarks:1) Main criteria for optimization issp eed.151.3.5 Co de Generationa. Purp ose: Transform intermediateco de to machine co de (assembler)b. Example: a = b + cmov b, R1add c, R1mov R1, ac. Remarks161.4 Symbol Tablea. Purp ose: record information ab outvarious ob jects in the source programb. Examplespro cedure - no. and typ e ofargumentssimple variable - typ earray - typ e, sizec. Use - information is requiredduringparsingco de generation171.5 Error Handlera. Errors - all errors should bedetecteddetected correctlydetected as so on as p ossiblerep orted at the appropriate placeand in a helpful mannerb. Purp oserep ort errors\error recovery" - pro ceed withpro cessing18c. Note: Errors can o ccur in eachphasemissp elled tokenwrong syntaximprop er pro cedure callstatements that cannot be