Compiler Design - Tutorialspoint

Compiler Designi

Compiler DesignAbout the TutorialA compiler translates the codes written in one language to some other language withoutchanging the meaning of the program. It is also expected that a compiler should make thetarget code efficient and optimized in terms of time and space.Compiler design principles provide an in-depth view of translation and optimization process.Compiler design covers basic translation mechanisms and error detection & recovery. Itincludes lexical, syntax, and semantic analysis as front end, and code generation andoptimization as back-end.AudienceThis tutorial is designed for students interested in learning the basic principles of compilers.Enthusiastic readers who would like to know more about compilers and those who wish todesign a compiler themselves may start from here.PrerequisitesThis tutorial requires no prior knowledge of compiler design but requires a basic understandingof at least one programming language such as C, Java, etc. It would be an additionaladvantage if you have had prior exposure to Assembly Programming.Copyright & Disclaimer Copyright 2014 by Tutorials Point (I) Pvt. Ltd.All the content and graphics published in this e-book are the property of Tutorials Point (I)Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republishany contents or a part of contents of this e-book in any manner without written consent ofthe publisher.We strive to update the contents of our website and tutorials as timely and as precisely aspossible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt.Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of our websiteor its contents including this tutorial. If you discover any errors on our website or in thistutorial, please notify us at contact@tutorialspoint.comi

Compiler DesignTable of ContentsAbout the Tutorial ··········· iAudience ························· iPrerequisites ··················· iCopyright & Disclaimer ···· iTable of Contents ··········· ii1.COMPILER DESIGN – OVERVIEW ······················· 1Language Processing System ··················· 1Preprocessor ···················2Interpreter bler ker ·····2Loader ····3Cross-compiler ················3Source-to-source Compiler PILER DESIGN –ARCHITECTURE ················· 4Analysis Phase ·················4Synthesis �·················43.COMPILER DESIGN – PHASES OF COMPILER ······ 5Lexical Analysis ···············6Syntax ····················6Semantic Analysis ···········6Intermediate Code Generation ················6Code Optimization ··········6Code Generation ·············6Symbol ILER DESIGN – LEXICAL ANALYSIS ············ 8Tokens ··· 8Specifications of Tokens · 9Alphabets trings ····9Special Symbols ··············9Language COMPILER DESIGN – REGULAR EXPRESSIONS ·· 11ii

Compiler DesignOperations s edence and Associativity ················126.COMPILER DESIGN – FINITE AUTOMATA ········· 13Finite Automata Construction ··············· 13Longest Match Rule ······ 147.COMPILER DESIGN – SYNTAX ANALYSIS ··········· 15Context-Free Grammar · 15Syntax Analyzers ·········· 16Derivation ···················· 17Left-most Derivation ·····17Right-most Derivation ···17Parse Tree ···················· 18Ambiguity ciativity ··················21Precedence ···················22Left Recursion ···············22Left Factoring ················24First and Follow Sets ····· 25First Set 25Follow Set tions of Syntax Analyzers ············· 268.COMPILER DESIGN – TYPES OF PARSING ········· 27Top-down Parsing ········· 27Bottom-up �··········· 279.COMPILER DESIGN – TOP-DOWN PARSING ····· 29Recursive Descent Parsing racking ················30Predictive Parser ···········30LL Parser LL Parsing Algorithm ·····3210.COMPILER DESIGN – BOTTOM-UP PARSING ···· 34Shift-Reduce Parsing ·····34iii

Compiler DesignLR Parser ·······················34LL vs. LR ························ 3611.COMPILER DESIGN – ERROR RECOVERY ·········· 37Panic Mode ···················37Statement Mode ···········37Error Productions ··········37Global Correction ··········37Abstract Syntax Trees ···3812.COMPILER DESIGN – SEMANTIC ANALYSIS ······ 40Semantics ····················· 40Semantic Errors ············ 41Attribute Grammar ······· 41Synthesized Attributes ··41Inherited Attributes ······42S-attributed SDT ··········· 43L-attributed SDT ··········· 4313.COMPILER DESIGN – RUNTIME ENVIRONMENT ······················· 45Activation �·············· 45Storage Allocation ········ 47Static Allocation ··········· 47Stack Allocation ············ 48Heap Allocation ············ 48Parameter Passing ········ 49r-value ··49l-value ··49Formal Parameters ·······49Actual Parameters ········50Pass by �·················· 50Pass by Reference ········· 50Pass by Copy-restore ···· 50iv

Compiler DesignPass by Name ··············· 5114.COMPILER DESIGN – SYMBOL TABLE ··············· ···················· 52Operations ··················· 53insert() ······53Scope Management ······ 5415.COMPILER DESIGN – INTERMEDIATE CODE GENERATION ······· 56Intermediate Representation ················ 56Three-Address Code ····· 57Declarations ················· 5816.COMPILER DESIGN – CODE GENERATION ········ 60Directed Acyclic Graph · 60Peephole Optimization · 61Redundant Instruction Elimination ········61Unreachable Code ········62Flow of Control gebraic Expression Simplification ·······63Strength Reduction ·······63Accessing Machine Instructions ·············63Code Generator ····················

Compiler Design 10 A compiler can broadly be divided into two phases based on the way they compile. Analysis Phase Known as the front-end of the compiler, the analysis phase of the compiler reads the source program, divides it into core parts,