Introduction to Compiling

What is a compiler?
Programming problems are easier to solve in high-level languages
Languages closer to the level of the problem domain, e.g., SmallTalk: OO programming JavaScript: Web pages

Solutions are usually more efficient (faster, smaller) when written in machine language
Language that reflects to the cycle-by-cycle working of a processor

Compilers are the bridges:

Tools to translate programs written in high-level languages to efficient executable code

What is a compiler? A program that reads a program written in one language and translates it into another language. As an important part of this translation process, the compiler reports to its user the presence of errors in the source program.

Source language

Compiler

Target language

Error messages

Traditionally, compilers go from high-level languages to low-level languages.

Compilation task is full of variety?? Thousands of source languages

Fortran, Pascal, C, C++, Java,

Thousands of target languages

Some other lower level language (assembly language), machine language

Compilation process has similar variety

Single pass, multi-pass, load-and-go, debugging, optimizing.

Variety is overwhelming Good news is:

Few basic techniques is sufficient to cover all variety Many efficient tools are available

Requirement In order to translate statements in a language, one needs to understand both

the structure of the language: the way sentences" are constructed in the language, and the meaning of the language: what each sentence" stands for.

Terminology: Structure Syntax Meaning Semantics

Analysis-Synthesis model of compilation

Two parts
Analysis Breaks up the source program into constituents and creates an intermediate representation of the source program Synthesis Constructs the target program from the intermediate representation
Intermediate Language Source Language Front End language specific Back End machine specific

Target Language

Compilation Steps/Phases
Source Program 1

Lexical Analyzer

Syntax Analyzer

3 Symbol-table Manager

Semantic Analyzer Error Handler

Intermediate Code Generator

Code Optimizer

Code Generator

Target Program

Compilation Steps/Phases
Lexical Analysis Phase: Generates the tokens in the source program

Syntax Analysis Phase: Recognizes sentences" in the program using the syntax of the language
Semantic Analysis Phase: Infers information about the program using the semantics of the language Intermediate Code Generation Phase: Generates abstract code based on the syntactic structure of the program and the semantic information Optimization Phase: Refines the generated code using a series of optimizing transformations Final Code Generation Phase: Translates the abstract intermediate code into specific machine instructions

Lexical Analysis Convert the stream of characters representing input program into a sequence of tokens Tokens are the words" of the programming language Lexeme
The characters comprising a token

For instance, the sequence of characters static int" is recognized as two tokens, representing the two words static" and int" The sequence of characters *x++" is recognized as three tokens, representing *", x" and ++ Removes the white spaces Removes the comments

Lexical Analysis

Input: result = a + b * 10
Tokens:

result, =, a, +, b, *, 10

identifiers

operators

Syntax Analysis (Parsing)

Uncover the structure of a sentence in the program from a stream of tokens. For instance, the phrase x = +y", which is recognized as four tokens, representing x", = and +" and y", has the structure =(x,+(y)), i.e., an assignment expression, that operates on x" and the expression +(y)". Build a tree called a parse tree that reflects the structure of the input sentence.

Syntax Analysis: Grammars Expression grammar

Exp

| | |

Exp + Exp Exp * Exp ID NUMBER

Syntax Tree
Input: result = a + b * 10
Assign

result

a
b

*
10

Semantic Analysis Check the source program for semantic errors

It uses the hierarchical structure determined by the syntax-analysis phase to identify the operators and operands of expressions and statements
Performs type checking
Operator operand compatibility

Intermediate Code Generation Translate each hierarchical structure decorated as tree into intermediate code A program translated for an abstract machine Properties of intermediate codes
Should be easy to produce Should be easy to translate into the target program

Intermediate code hides many machine-level details, but has instruction-level mapping to many assembly languages Main motivation: portability One commonly used form is Three-address Code

Code Optimization Apply a series of transformations to improve the time and space efficiency of the generated code. Peephole optimizations: generate new instructions by combining/expanding on a small number of consecutive instructions. Global optimizations: reorder, remove or add instructions to change the structure of generated code Consumes a significant fraction of the compilation time Optimization capability varies widely Simple optimization techniques can be vary valuable

Code Generation Map instructions in the intermediate code to specific machine instructions. Memory management, register allocation, instruction selection, instruction scheduling, Generates sufficient information to enable symbolic debugging.

Symbol Table Records the identifiers used in the source program

Collect information about various attributes of each identifier
Variables: type, scope, storage allocation Procedure: number and types of arguments, method of argument passing

Its a data structure containing a record for each identifier

Different fields are collected and used at different phases of compilation

When an identifier in the source program is detected by the lexical analyzer, the identifier is entered into the symbol table

Error Detection, Recovery and Reporting Each phase can encounter error Specific types of error can be detected by specific phases
Lexical Error: int abc, 1num; Syntax Error: total = capital + rate year; Semantic Error: value = myarray [realIndex];

Should be able to proceed and process the rest of the program after an error detected Should be able to link the error with the source program

Reviewing the Entire Process

position := initial + rate *10 lexical analyzer id1 := id2 + id3 * 10 syntax analyzer

:= id1 id2 + *

id3
semantic analyzer

10

:=
Symbol Table position .... initial . rate. intermediate code generator

id1 id2l

+ *

id3

inttoreal
10

E r r o r s

Reviewing the Entire Process

Symbol Table

position ....
initial . rate. intermediate code generator temp1 := inttoreal(10) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3 code optimizer temp1 := id3 * 10.0 id1 := id2 + temp1

E r r o r s

3 address code

final code generator MOVF id3, R2 MULF #10.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

Syntax Analyzer versus Lexical Analyzer

Which constructs of a program should be recognized by the lexical analyzer, and which ones by the syntax analyzer?
Both of them do similar things; But the lexical analyzer deals with simple non-recursive constructs of the language. The syntax analyzer deals with recursive constructs of the language. The lexical analyzer simplifies the job of the syntax analyzer. The lexical analyzer recognizes the smallest meaningful units (tokens) in a source program. The syntax analyzer works on the smallest meaningful units (tokens) in a source program to recognize meaningful structures in our programming language.

Cousins of the Compiler Preprocessor

Macro preprocessing
Define and use shorthand for longer constructs

File inclusion
Include header files

Rational Preprocessors
Augment older languages with modern flow-of-control or data-structures

Language Extension
Add capabilities to a language Equel: query language embedded in C

Assemblers
Source program

Compiler

Assembly program

Assembler

Relocatable machine code

Loader/link-editor

Absolute machine code

Two-Pass Assembly Simplest form of assembler First pass

All the identifiers are stored in a symbol table Storage is allocated

Second pass
Translates each operand code in the machine language
Instruction Register code Addressing Mode Address Relocation bit

MOV a, R1 ADD #2, R1 MOV R1, b

Source

Identifier Address a 0 b 4 After First Pass

0001 01 00 00000000 * 0011 01 10 00000010 0010 01 00 00000100 * After 2nd Pass

Loaders and Link-Editors Convert the relocatable machine code into absolute machine code
Map the relocatable address

Place altered instructions and data in memory

0001 01 00 00000000 * 0011 01 10 00000010 0010 01 00 00000100 * Address space of data to be loaded starting at location L=00001111 0001 01 00 00001111 0011 01 10 00000010 0010 01 00 00010011

Make a single program from several files of relocatable machine code

Several files of relocatable codes Library files