Compiler Design Slides for Third Year Computer Science and Engineering

Power Point Slides of Compiler Design

1. Compiler Construction 1 Compiler Design

2. DR. BABASAHEB AMBEDKAR TECHNOLOGICAL UNIVERSITY, LONERE BTCOC601: Compiler Design [Unit 1] Introduction to Compiling [7 Hours] Definition, analysis of the source program, the phases of a compiler, the grouping of phases, Compiler Construction tools, A simple one-pass compiler, [Unit 2] Lexical Analysis [7 Hours] The role of the Lexical analyzer, Input buffering, Specification of Tokens, A Language for Specifying Lexical Analyzers, Design of a Lexical Analyzer generator. [Unit 3] Syntax Analysis [7 Hours] The role of the Parser, Context-free grammars, Writing a Grammar, Top-Down Parsing, Bottom-Up Parsing, Operator-precedence Parsing, LR Parsers, Using Ambiguous Grammars, Parser Generators. [Unit 4] Syntax-Directed Translation [7 Hours] Definitions, Construction of Syntax Trees, Bottom-Up Evaluation of S- Attributed definitions, Top-Down Translation, Bottom-Up Evaluation of Inherited attributes. Intermediate Languages, Declarations, Assignment Statements, Boolean Expressions, Case Statements, Back patching, Procedure Calls. Compiler Construction 2

3. [Unit 5] Code Generation [7 Hours] Issues in the Design of a Code Generator, The target Machine, Run-Time Storage Management, Basic Blocks and Flow Graphs, Next-Use Information, Simple Code Generator, Register allocation and Assignment, The DAG Representation of Basic Blocks, Generating Code from DAGs, Dynamic Programming, Code- Generation Algorithm, Code-Generators. Text Book: Aho , Sethi , Ullman, Compilers Principles, Techniques and Tools, Pearson Education India, 2nd Edition, 2013 Reference Books: 1. Hopcroft , Motwani and Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Publication, 2nd Edition, 2001. 2. Dick Grune , Kees van Reeuwijk , Henri E. Bal , Ceriel J. H. Jacobs and Koen Langendoen , Modern Compiler Design, Springer, 2nd Edition, 2012. Compiler Construction 3

4. Compiler Construction 4 The Goal of Chapter 1 Introduce different forms of language translators Give a high level overview of the structure of a typical compiler Discuss trends in programming languages and machine architecture that are shaping compilers. Introduction Chapter 1

5. Introduction Language Processors Compilation Compiler is a program that can read a program in one language- the source language – and translate it into equivalent of a program written in another language – the target language Ignore machine-dependen t details for programmer Compiler Construction 5 Chapter 1

6. If the target program is an executable machine-language program, it can then be called by the user to process inputs and produce outputs Compiler Construction 6 Ta rget Program input output

7. Chapter 1 - Introduction 7 What is a Compiler? Def : Compiler -- a program that translates a program written in a language like Pascal, C, PL/I, FORTRAN, or COBOL into another language. An important role of the compiler is to report any errors that it detects.

8. Chapter 1 - Introduction 8 What is an Interpreter? Def : Interpreter -- Instead of producing a target program at translation, it appears to directly execute the operations specified in the source program on the inputs specified by the user.

9. Interpreter Performing the operations implied by the source program Instead of generating code from the syntax tree, the syntax tree is directly processed to evaluate expressions and statements Interpretation is slower than compilation but, writing an interpreter is simpler than compiler Compiler Construction 9

10. Interpreter gives better error diagnosis than the compiler, because it executes the source program statement by statement Java language processor combines compilation and interpretation Java source program is first compiled in to intermediate form called bytecodes The bytecodes are then interpreted by a virtual machine. The benefit is bytecodes compiled on one machine can be interpreted on another machine. Compiler Construction 10

11. Some Java compilers (Just-in-time) translates the bytcodes into machine language immediately Compiler Construction 11 Translator Source Program Intermediate Program Virtual Machine Input Output A Hybrid Compiler

12. Compilers may generate three types of code: Pure Machine Code Machine instruction set without assuming the existence of any operating system or library. Mostly being OS or embedded applications . Augmented Machine Code Code with OS routines and runtime support routines. More often Virtual Machine Code Virtual instructions, can be run on any architecture with a virtual machine interpreter or a just-in-time compiler Ex. Java Compiler Construction 12

13. Why study compilers? Application of a wide range of theoretical techniques Data Structures Theory of Computation Algorithms Computer Architecture Good SW engineering experience Better understanding of programming languages Compiler Construction 13

14. Cause Software for early computers was written in assembly language The benefits of reusing software on different CPUs started to become significantly greater than the cost of writing a compiler The first real compiler FORTRAN compilers of the late 1950s 18 person-years to build Compiler Construction 14

15. Features of compilers Correctness Preserve the meaning of the code Speed of target code Speed of compilation Good error reporting/handling Cooperation with the debugger Support for separate compilation Compiler Construction 15

16. A Language Processing System Compiler Construction 16

17. A source program may be divided into modules stored in different files. The task of collecting the source program is given to a separate program, called a preprocessor. It may expand macros. The modified source program is then fed to a compiler The compiler may produce an assembly language program as its output It is then processed by assembler that produces relocatable machine code as its output. Compiler Construction 17

18. Linker then links together relocatable machine code with other object files and library files into the code that actually runs on the machine The loader then puts together all of the executable object files into memory for execution. Compiler Construction 18

19. The Analysis-Synthesis Model of Compilation There are two parts to compilation: Analysis determines the operations implied by the source program which are recorded in a tree structure Analysis of the source program S ynthesis takes the tree structure and translates the operations therein into the target program Synthesis of a machine-language program Compiler Construction 19

20. Compiler structure Compiler Construction 20 source code target code Front End Back End IR Use intermediate representation Why?

21. Compiler Construction 21 Front end Recognize legal/illegal programs report/handle errors Generate IR The process can be automated Back end Translate IR into target code instruction selection register allocation instruction scheduling Compiler structure

22. Compiler Construction 22 Optimization goals improve running time of generated code improve space, power consumption, etc. how? perform a number of transformations on the IR multiple passes important: preserve meaning of code Compiler structure

23. Scanning (lexical analysis) recognize "words" (tokens) Parsing (syntax analysis) check syntax Semantic analysis examine meaning (e.g. type checking) Other issues: symbol table (to keep track of identifiers) error detection/reporting/recovery Compiler Construction 23 The Front End

24. Compiler Construction 24 The Structure of a Compiler

25. Compiler Construction 25 The Lexical Analyzer reads the stream of characters and groups them into meaningful sequences called lexemes. Scanner The scanner begins the analysis of the source program by reading the input, character by character, and grouping characters into individual words and symbols ( tokens ) RE ( Regular expression ) NFA ( Non-deterministic Finite Automata ) DFA ( Deterministic Finite Automata ) LEX

26. 2.The Syntax Analyzer depicts the grammatical structure of the lexemes in a syntax tree Compiler Construction 26 Parser Given a formal syntax specification (typically as a context-free grammar [CFG] ), the parse reads tokens and groups them into units as specified by the productions of the CFG being used. As syntactic structure is recognized, the parser either calls corresponding semantic routines directly or builds a syntax tree . CFG ( Context-Free Grammar ) BNF ( Backus-Naur Form ) GAA ( Grammar Analysis Algorithms ) LL, LR, SLR, LALR Parsers YACC

27. 3.The Semantic Analyzer checks the tree for semantic consistency (type checking) 4. Intermediate Code Generation – produces assembly like instructions (three address code) Compiler Construction 27 Semantic Routines Perform two functions Check the static semantics of each construct Do the actual translation The heart of a compiler Syntax Directed Translation Semantic Processing Techniques IR (Intermediate Representation)

28. 5. Code Optimization – seeks to improve intermediate code so better target code can be generated Compiler Construction 28 Optimizer The IR code generated by the semantic routines is analyzed and transformed into functionally equivalent but improved IR code This phase can be very complex and slow Peephole optimization loop optimization, register allocation, code scheduling Register and Temporary Management Peephole Optimization

29. 6.Code Generation – takes the intermediate code and maps to the target code 7.Symbol Table Management - An essential function of the compiler is to record the variable names used in the source program and collect attributes of each name. (type, scope,…) Compiler Construction 29 Code Generator Interpretive Code Generation Generating Code from Tree/Dag Grammar-Based Code Generator

30. Compiler Construction 30 The Structure of a Compiler Scanner [Lexical Analyzer] Parser [Syntax Analyzer] Semantic Process [Semantic analyzer] Code Generator [Intermediate Code Generator] Code Optimizer Tokens Parse tree Non-optimized Intermediate Code Code Optimizer Target machine code

31. Chapter 1 - Introduction 31 The Grouping of the Phases into Passes Pass – several phases may be grouped together into a pass that reads an input file and writes an output file. Front End Lexical Analysis, Syntax Analysis, Semantic Analysis, and Intermediate Code Generation Code Optimization Might be an optional pass. Back End Code Generation for a specific target machine.

32. The Grouping of Phases Compiler front and back ends : Front end: analysis ( machine independent ) Back end: synthesis ( machine dependent ) Compiler passes: A collection of phases is done only once ( single pass ) or multiple times ( multi pass ) Single pass: usually requires everything to be defined before being used in source program Multi pass: compiler may have to keep entire program representation in memory Compiler Construction 32

33. Single-Pass Compilers Compiler Construction 33 Phases work in an interleaved way scan token parse token check token generate code for token eof? n y The target program is already generated while the source program is read.

34. Compiler Construction 34 Multi-Pass Compilers Phases are separate "programs", which run sequentially Each phase reads from a file and writes to a new file characters scanner tokens parser tree sem. analysis ... code Why multi-pass? if memory is scarce (irrelevant today) if the language is complex if portability is important

35. Short History of Compiler Construction Compiler Construction 35 Formerly "a mystery", today one of the best-known areas of computing 1957 Fortran first compilers (arithmetic expressions, statements, procedures) 1970 Pascal user-defined types, virtual machines (P-code) 1985 C++ object-orientation, exceptions, templates 1995 Java just-in-time compilation We only look at imperative languages Functional languages (e.g. Lisp) and logical languages (e.g. Prolog) require different techniques. 1960 Algol first formal language definition (grammars in Backus-Naur form, block structure, recursion, ...)

36. Compiler-Construction Tools Software development tools are available to implement one or more compiler phases Scanner generators - Produce lexical analyzers from a regular expression description of the token of a language Parser generators – Automatically produce syntax analyzers from a grammatical description of a programming language Syntax-directed translation engines - Produce collection of routines for walking a parse tree and generating intermediate code Compiler Construction 36

37. Code-generator code generators – Produce code generator from a collection of rules for translating each operation of the intermediate language into the machine language for a target machine. Data-flow analysis engines – It is a key part of code optimization. It gathers information about how values are transmitted from one part of program to each other part. Compiler-construction toolkits- Provide an integrated set of routines for constructing various phases of a compiler. Compiler Construction 37