CPSC 411: Introduction to Compiler Construction

CPSC 411: Introduction to Compiler Construction

Languages and Compilers (SProg og Oversttere) Bent Thomsen Department of Computer Science Aalborg University With acknowledgement to Norm Hutchinson whos slides this lecture is based on. 1 Compilation So far we have treated language processors (including compilers) as black boxes Now we take a first look "inside the box": how are compilers built. And we take a look at the different phases and their relationships 2 The Phases of a Compiler Source Program Syntax Analysis

Error Reports Abstract Syntax Tree Contextual Analysis Error Reports Decorated Abstract Syntax Tree Code Generation Object Code 3 Different Phases of a Compiler The different phases can be seen as different transformation steps to transform source code into object code. The different phases correspond roughly to the different parts of the language specification: Syntax analysis <-> Syntax Contextual analysis <-> Contextual constraints Code generation <-> Semantics 4 Example Program

We now look at each of the three different phases in a little more detail. We look at each of the steps in transforming an example Triangle program into TAM code. !! This This program program is is useless useless except except for for !! illustration illustration let let var var n: n: integer; integer; var var c: c: char char in in begin begin cc :=

:= &; &; nn := := n+1 n+1 end end 5 1) Syntax Analysis Source Program Syntax Analysis Error Reports Abstract Syntax Tree Note: Note:Not Notall allcompilers compilersconstruct constructan an explicit explicitrepresentation

representationof ofan anAST. AST.(e.g. (e.g.on on aasingle singlepass passcompiler compilergenerally generallyno noneed need to toconstruct constructan anAST) AST) 6 1) Syntax Analysis -> AST Program LetCommand SequentialCommand

SequentialDeclaration AssignCommand AssignCommand VarDecl VarDecl SimpleT Ident n Ident Integer Char.Expr BinaryExpr VNameExp Int.Expr SimpleT SimpleV Ident

Ident c Char SimpleV Ident Char.Lit Ident c & n Ident Op Int.Lit n + 1 7

2) Contextual Analysis -> Decorated AST Abstract Syntax Tree Contextual Analysis Error Reports Decorated Abstract Syntax Tree Contextual analysis: Scope checking: verify that all applied occurrences of identifiers are declared Type checking: verify that all operations in the program are used according to their type rules. Annotate AST: Applied identifier occurrences => declaration Expressions => Type 8 2) Contextual Analysis -> Decorated AST Program LetCommand SequentialCommand SequentialDeclaration AssignCommand

BinaryExpr :int AssignCommand VarDecl VarDecl SimpleT Ident Ident n Integer Char.Expr :char VNameExp Int.Expr :int SimpleT SimpleV SimpleV

:char Ident Ident c Char :int Ident Char.Lit Ident c & :int n Ident Op Int.Lit n

+ 1 9 Contextual Analysis Finds scope and type errors. Example 1: AssignCommand :int ***TYPE ERROR (incompatible types in assigncommand) :char Example 2: foo not found SimpleV ***SCOPE ERROR: undeclared variable foo Ident foo 10

3) Code Generation Decorated Abstract Syntax Tree Code Generation Object Code Assumes that program has been thoroughly checked and is well formed (scope & type rules) Takes into account semantics of the source language as well as the target language. Transforms source program into target code. 11 3) Code Generation let var n: integer; var c: char in begin c := &; n := n+1 end VarDecl address = 0[SB] PUSH 2 LOADL 38

STORE 1[SB] LOAD 0 LOADL 1 CALL add STORE 0[SB] POP 2 HALT SimpleT Ident Ident n Integer 12 Compiler Passes A pass is a complete traversal of the source program, or a complete traversal of some internal representation of the source program. A pass can correspond to a phase but it does not have to! Sometimes a single pass corresponds to several phases that are interleaved in time. What and how many passes a compiler does over the

source program is an important design decision. 13 Single Pass Compiler A single pass compiler makes a single pass over the source text, parsing, analyzing and generating code all at once. Dependency diagram of a typical Single Pass Compiler: Compiler Driver calls Syntactic Analyzer calls Contextual Analyzer calls Code Generator 14 Multi Pass Compiler A multi pass compiler makes several passes over the program. The output of a preceding phase is stored in a data structure and used by subsequent phases. Dependency diagram of a typical Multi Pass Compiler: Compiler Driver calls

calls calls Syntactic Analyzer Contextual Analyzer Code Generator input output input output input output Source Text AST Decorated AST Object Code 15 Example: The Triangle Compiler Driver public public class class Compiler

Compiler {{ public public static static void void compileProgram(...) compileProgram(...) {{ Parser Parser parser parser = = new new Parser(...); Parser(...); Checker Checker checker checker = = new new Checker(...); Checker(...); Encoder Encoder generator generator = = new new Encoder(...); Encoder(...); Program

Program theAST theAST = = parser.parse(); parser.parse(); checker.check(theAST); checker.check(theAST); generator.encode(theAST); generator.encode(theAST); }} }} public public void void main(String[] main(String[] args) args) {{ ... ... compileProgram(...) compileProgram(...) ... ... }} 16 Compiler Design Issues

Single Pass Multi Pass Speed better worse Memory Modularity better for large programs worse (potentially) better for small programs better Flexibility worse

better Global optimization impossible possible Source Language single pass compilers are not possible for many programming languages 17 Language Issues Example Pascal: Pascal was explicitly designed to be easy to implement with a single pass compiler: Every identifier must be declared before it is first use. ? var n:integer; procedure inc; begin n:=n+1 end

procedure inc; begin n:=n+1 end; Undeclared Variable! var n:integer; 18 Language Issues Example Pascal: Every identifier must be declared before it is used. How to handle mutual recursion then? procedure ping(x:integer) begin ... pong(x-1); ... end; procedure pong(x:integer) begin ... ping(x); ... end; 19 Language Issues

Example Pascal: Every identifier must be declared before it is used. How to handle mutual recursion then? forward procedure pong(x:integer) procedure ping(x:integer) begin ... pong(x-1); ... end; OK! procedure pong(x:integer) begin ... ping(x); ... end; 20 Language Issues Example Java: identifiers can be declared before they are used. thus a Java compiler need at least two passes Class Example { void inc() { n = n + 1; } int n; void use() { n = 0 ; inc(); }

} 21 Keep in mind There are many issues influencing the design of a new programming language: Choice of paradigm Syntactic preferences Even the compiler implementation e.g no of passes available tools There are many issues influencing the design of new compiler: No of passes The source, target and implementation language Available tools 22

Recently Viewed Presentations

  • Rethinking Unemployment: The European Challenge

    Rethinking Unemployment: The European Challenge

    Estimates global income inequalities. Shows now inequality has risen under globalization. Is changing our understanding of the relationship of inequality to unemployment. Advantages Our method permits us to assess the value of inequality at each geographic level: Within provinces Within...
  • Design Project Management: Boeing Underwater Robotic Technologies [R13201]

    Design Project Management: Boeing Underwater Robotic Technologies [R13201]

    Much like ants, bees and birds. If one robot fails, others cover-up that lost robots tasks as well . 4 Projects to Visit at Imagine RIT. Autonomy Ideas. ... Design and development of a robotic arm with the dexterity of...
  • Tapping the Web and the New Media - College of Charleston

    Tapping the Web and the New Media - College of Charleston

    Tapping the Web and the New Media Chapter 12 Democratization of Information Internet is revolutionary in so many ways As a media form it is characterized by: Widespread broadband=high speed communication Wireless accessibility and "smart" mobile devices Free or inexpensive...
  • Copyright  2011 Pearson Education, Inc. Publishing as Longman

    Copyright 2011 Pearson Education, Inc. Publishing as Longman

    * Segregation was outlawed first in . A. education (LO 5.2) * LO 5.3: Relate civil rights principles to progress made by other ethnic groups in the United States. * Other minority
  • BMWs Hydrogen Powered Vehicles Tamer Hassanein ITMG 100

    BMWs Hydrogen Powered Vehicles Tamer Hassanein ITMG 100

    They make 15 of them which create the world's first fleet of hydrogen-powered cars and collectively travel a distance of 100,000 miles 2001 Create a redesigned 7 series, the sixth generation car: 745h 2004 BMWs H2R hydrogen-based racecar sets nine...
  • WintellectNOW

    WintellectNOW

    Displaying Form Validation InformationOverview. In previous videos of this series, Reactive Forms, Template Forms, Validators, Custom Validators and such have been explored, explained and demonstrated
  • Felak Suresi ve Nas Suresi (Felk Nas)  Felak

    Felak Suresi ve Nas Suresi (Felk Nas) Felak

    Felak Suresi ve Nas Suresi (Felâk Nas)
  • USA and CANADA

    USA and CANADA

    3rd largest country by size (after Russia and Canada) 3rd largest population (after China and India) = 310,232,863 (July 2010 est.) Constitution-based federal . ... Projected water shortages could turn into droughts that cause billions of dollars in crop and...