Introduction to Compiler Construction

​

​

Compiler

• A given source language is either compiled or interpreted for execution
• compiler is a program that translates a source program (HLL; C, Java) into target code; machine re-locatable code or assembly code.
• The generated machine code can be later executed many times against different data each time.
• The code generated is not portable to other systems.

​

Interpreter

• In an interpreted language, implementations execute instructions directly and freely without previously compiling a program into machine code instructions.
• Translation occurs at the same time as the program is being executed.
• An interpreter reads an executable source program written in HLL as well as data for this program, and it runs the program against the data to produce some results.

Interpreter

• Common interpreters include Perl, Python, and Ruby interpreters, which execute Perl, Python, and Ruby code respectively.
• Others include Unix shell interpreter, which runs operating system commands interactively.
• Source program is interpreted every time it is executed (less efficient).

​

Interpreter

• Interpreted languages are portable since they are not machine dependent. They can run on different operating systems and platforms.
• They are translated on the spot and thus optimized for the system on which they’re being run.

​

Compilers and Interpreters

• “Compilation”
• Translation of a program written in a source language into a semantically equivalent program written in a target language

Compiler

Error messages

Source

Program

Target

Program

Input

Output

Compilers and Interpreters (cont’d)

Interpreter

Source

Program

Input

Output

Error messages

• “Interpretation”
• Performing the operations implied by the source program

The Analysis-Synthesis Model of Compilation

• There are two parts to compilation:
• Analysis Phase

This is also known as the front-end of the compiler. It reads the source program, divides it into core parts and then checks for lexical, grammar and syntax errors. The analysis phase generates an intermediate representation of the source program and symbol table, which should be fed to the Synthesis phase as input

• Synthesis Phase

Its also known as the back-end of the compiler.

It generates the target program with the help of intermediate source code representation and symbol table.

Other Tools that Use the Analysis-Synthesis Model

• Editors (syntax highlighting)
• Pretty printers (e.g. Doxygen)
• Static checkers (e.g. Lint and Splint)
• Interpreters
• Text formatters (e.g. TeX and LaTeX)
• Silicon compilers (e.g. VHDL)
• Query interpreters/compilers (Databases)

Preprocessors, Compilers, Assemblers and Linkers

• A preprocessor considered as part of compiler, is a tool that produces input for compilers. It deals with macro-processing, file inclusion, language extension, etc.

​

• Assembler

An assembler translates assembly language programs into machine code. The output of an assembler is called an object file, which contains a combination of machine instructions as well as the data required to place these instructions in memory.

Preprocessors, Compilers, Assemblers and Linkers

• Linker

A computer program that links and merges various object files together in order to make an executable file.

​

• All these files might have been compiled by separate assemblers. The major task of a linker is to search and locate referenced module/routines in a program and to determine the memory location where these codes will be loaded, making the program instruction to have absolute references.

Compiler Design - Architecture of a Compiler

• A compiler can have many phases and passes.
• Pass : A pass refers to the traversal of a compiler through the entire program.

​

• Phase : A phase of a compiler is a distinguishable stage, which takes input from the previous stage, processes and yields output that can be used as input for the next stage. A pass can have more than one phase.

Phases of a Compiler

• The compilation process is a sequence of various phases.
• Each phase takes input from its previous stage and has its own representation of source program, and feeds its output to the next phase of the compiler.

​

Traditional three pass compiler

Front end

Source

code

Machine

code

errors

IR

Back end

Middle

end

IR

​

Phases of a Compiler - Front end

​

​

• The front end analyzes the source code to build an internal representation of the program, called the intermediate representation (IR).
• It also manages the symbol table, a data structure mapping each symbol in the source code to associated information such as location, type and scope.

​

​

Phases of a Compiler - Front end cont’d

The front end includes all analysis phases and the intermediate code generator.

​

• Lexical analysis is the first phase of compiler which is also termed as scanning.
• During this phase, Source program is scanned to read the stream of characters and those characters are grouped to form a sequence called lexemes which produces token as output. Tokens are defined by regular expressions which are understood by the lexical analyzer.

​

Lexical Analysis

• lexical analysis: The process of converting a sequence of characters (such as in a computer program) into a sequence of tokens (strings with an identified "meaning")
• Lexical analysis takes the modified source code from language preprocessors that are written in the form of sentences.
• The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.

​

Lexical Analysis

• The lexical analyzer (either generated automatically by a tool like lex, or hand-crafted) reads in a stream of characters, identifies the lexemes in the stream, and categorizes them into tokens.

​

• This is called "tokenizing". If the lexer finds an invalid token, it will report an error.

​

Front end: Terminologies

• Token: Token is a sequence of characters that represent lexical unit, which matches with the pattern, such as keywords, operators, identifiers etc.
• Lexeme: Lexeme is instance of a token i.e., group of characters forming a token.
• Pattern: Pattern describes the rule that the lexemes of a token takes. It is the structure that must be matched by strings.

​

​

Token and Lexeme

• Once a token is generated the corresponding entry is made in the symbol table.

​

At lexical analysis phase,

Input: stream of characters

Output: Token

Token Template:

<token-name, attribute-value>

• For example, for c=a+b*5;

Hence,

<id, 1><=>< id, 2>< +><id, 3 >< * >< 5>

​

Token and Lexeme Cont’d

​

​

​

​

​

​

​

​

​

​

​

​

Syntax Analysis

​

• Syntax Analyze is sometimes called as parser. It constructs the parse tree. It takes all the tokens one by one and uses Context Free Grammar to construct the parse tree.

​

Why Grammar ?

• The rules of programming can be entirely represented in some few productions. Using these productions we can represent what the program actually is. The input has to be checked whether it is in the desired format or not.

Syntax Analysis cont’d

​

• Syntax error can be detected at this level if the input is not in accordance with the grammar.

Syntactic Analysis

​

• Parsing or syntactic analysis is the process of analyzing a string of symbols, either in natural language or in computer languages, conforming to the rules of a formal grammar

​

• Parse: analyze (a string or text) into logical syntactic components, typically in order to test conformability to a logical grammar.

​

Syntactic Analysis cont’d

​

• If the lexical analyzer finds a token invalid, it generates an error.
• The lexical analyzer works closely with the syntax analyzer. It reads character streams from the source code, checks for legal tokens, and passes the data to the syntax analyzer when it demands.

​

​

Semantic Analysis

• Semantic analyzer takes the output of syntax analyzer and produces another tree.

​

• Similarly, intermediate code generator takes a tree as an input produced by semantic analyzer and produces intermediate code.

​

Semantic Analyzer

​

​

​

​

​

​

​

​

​

​

​

​

Semantic Analysis cont’d

Syntax tree is a compressed representation of the parse tree (a hierarchical structure that represents the derivation of the grammar to obtain input strings) in which the operators appear as interior nodes and the operands of the operator are the children of the node for that operator.

• Example of syntax tree

​

Semantic Analyzer

Semantic analysis is the third phase of compiler.

• It checks for the semantic consistency.
• Type information is gathered and stored in symbol table or in syntax tree.
• Performs type checking.
• It verifies the parse tree, whether it’s meaningful or not. It furthermore produces a verified parse tree.

​

Semantic Analyzer

Front-end, Back-end division

• Front end maps legal code into IR
• Back end maps IR onto target machine
• Allows multiple front ends
• Multiple passes -> better code

Front end

Source

code

Machine

code

errors

IR

Back end

Front end

• Recognize legal code
• Report errors
• Produce IR
• Preliminary storage maps

Scanner

Source

code

IR

errors

tokens

Parser

Front end

• Scanner:
• Maps characters into tokens – the basic unit of syntax
• x = x + y becomes <id, x> = <id, x> + <id, y>
• Typical tokens: number, id, +, -, *, /, do, end
• Eliminate white space (tabs, blanks, comments)
• A key issue is speed so instead of using a tool like LEX it sometimes needed to write your own scanner

Scanner

Source

code

IR

errors

tokens

Parser

Front end

• Parser:
• Recognize context-free syntax
• Guide context-sensitive analysis
• Construct IR
• Produce meaningful error messages
• Attempt error correction
• There are parser generators like YACC which automates much of the work

Scanner

Source

code

IR

errors

tokens

Parser

​

Phases of a Compiler cont’d

Middle End – The Optimizer

​

​

• The middle end performs optimizations on the intermediate representation in order to improve the performance and the quality of the produced machine code.
• The middle end contains those optimizations that are independent of the CPU architecture being targeted.
• Effort to realize efficiency
• Can be very computationally intensive

​

Middle end (optimizer)

• Modern optimizers are usually built as a set of passes
• Typical passes
• Constant propagation
• Common sub-expression elimination
• Redundant store elimination
• Dead code elimination

​

Back end

• Translate IR into target machine code
• Choose instructions for each IR operation
• Decide what to keep in registers at each point
• Ensure conformance with system interfaces

Instruction

selection

IR

Machine code

errors

Register

Allocation

Phases of a Compiler

• Back End – This is responsible for the CPU architecture specific optimizations and for code generation.
• Machine dependent optimizations: optimizations that depend on the details of the CPU architecture that the compiler targets
• Code generation. The transformed intermediate language is translated into the output language, usually the native machine language of the system.

​

Phases of a Compiler

• It also involves resource and storage decisions, such as; deciding which variables to fit into registers and memory and the selection and scheduling of appropriate machine instructions along with their associated addressing modes
• Processor (target) Dependant optimization

Phases of a Compiler - Instruction selection

• Instruction selection is the stage of a compiler back-end that transforms its middle-level intermediate representation (IR) into a low-level IR where each operation directly corresponds to an instruction available on the target machine.

​

• In a typical compiler, instruction selection precedes both instruction scheduling and register allocation; hence its output IR has an infinite set of pseudo-registers

​

Back end

• Have a value in a register when used
• Limited resources
• Optimal allocation is difficult

Instruction

selection

IR

Machine code

errors

Register

Allocation

Intermediate Code Generation

After semantic analysis the compiler generates an intermediate code of the source code for the target machine.

• It represents a program for some abstract machine.
• It is in between the high-level language and the machine language.
• This intermediate code should be generated in such a way that it makes it easier to be translated into the target machine code.

Code Optimization

• Optimization can be assumed as something that removes unnecessary code lines, and arranges the sequence of statements in order to speed up the program execution without wasting resources (CPU, memory).

Code Generation

• In this phase, the code generator takes the optimized representation of the intermediate code and maps it to the target machine language.

​

• The code generator translates the intermediate code into a sequence of (generally) re-locatable machine code. Sequence of instructions of machine code performs the task as the intermediate code would do.

Symbol Table

• It is a data-structure maintained throughout all the phases of a compiler.
• All the identifier's names along with their types are stored here.
• The symbol table makes it easier for the compiler to quickly search the identifier record and retrieve it. The symbol table is also used for scope management.

​

Compiler-Construction Tools

• Software development tools are available to implement one or more compiler phases
• Scanner generators
• Parser generators
• Syntax-directed translation engines
• Automatic code generators
• Data-flow engines