Compiler Design

Compiler Design covers the principles and techniques used to translate a source program into target code. This syllabus starts with the basic role of compilers, interpreters, lexical analysis, regular expressions, finite automata, and parsing methods.

Unit I: Compilers and Top-Down Parsing

Introduction to Language Processing

Computers have become an unavoidable and essential part of human life. As programming languages evolved with more advanced and user-friendly features, the need for translator or mediator software became very important.

Humans usually write programs in high-level languages because they are easier to read, write, and understand. Machines, however, understand low-level instructions such as machine code. This creates a gap between human understanding and machine understanding.

Language processing is the process of bridging this gap. It converts a program written in one language into another form that a computer can understand and execute.

To understand language processing properly, we first need to understand some important terms such as language translator, compiler, interpreter, source language, and target language.

Language Translators

A language translator is a computer program that translates a program written in one language into an equivalent program in another language.

The original program is called the source program, and the language in which it is written is called the source language. The translated program is called the target program, and the language into which it is translated is called the target language.

The source language is usually a high-level programming language. The target language may be machine language for a specific machine, such as a microprocessor or supercomputer, or it may be another high-level language.

Two commonly used language translators are:

• Compiler
• Interpreter

Key Definitions Visual

Definitions overview: compiler, interpreter, phase, and pass.

Language Processing System

Based on the input a translator takes and the output it produces, a language translator can be classified into different components of a language processing system.

The main components are:

• Preprocessor
• Compiler
• Assembler
• Loader
• Linker

Preprocessor

A preprocessor takes a skeletal source program as input and produces an extended version of it.

This extended source program is produced by:

• Expanding macros
• Expanding manifest constants
• Including header files
• Collecting modules or files if the source program is divided into multiple files
• Expanding shorthand notations into source language statements

For example, the C preprocessor is a macro processor that is automatically used by the C compiler to transform the source program before actual compilation.

Compiler in Language Processing

A compiler is a translator that takes a source program written in a high-level language and converts it into an equivalent target program in machine language.

In addition to translation, the compiler also:

• Reports errors present in the source program
• Helps the user identify and correct errors
• Produces code that can be executed after successful compilation

Assembler

An assembler is a program that takes an assembly language program as input and converts it into equivalent machine language code.

Assembly language is closer to machine language than high-level languages, but it still uses symbolic instructions. The assembler converts these symbolic instructions into binary machine instructions.

Loader and Linker

A loader/linker takes relocatable code as input, collects library functions and relocatable object files, and produces equivalent absolute machine code.

Loading means taking relocatable machine code, modifying relocatable addresses, and placing the changed instructions and data into memory at proper locations.

Linking means combining several files of relocatable machine code into a single program. These files may come from different compilations, and some may be library routines provided by the system for use by any program that needs them.

In addition to these translators, programs such as interpreters, text formatters, and other support tools may also be used in a language processing system.

To translate a high-level language program into an executable program, the compiler often performs compilation and linking functions by default.

Normally, the steps in a language processing system begin with preprocessing the skeletal source program. This produces an extended or expanded source program, also called a ready-to-compile source unit. The expanded source program is then compiled, linked, loaded, and finally converted into equivalent executable code.

All of these steps are not mandatory in every system. In some cases, the compiler performs linking and loading functions implicitly.

The steps involved in a typical language processing system can be understood with the following flow:

Context of a compiler in a language processing system.

This diagram shows the context of a compiler in a complete language processing system. The compiler is one important part of the system, but preprocessing, assembling, loading, and linking may also be needed to produce the final executable machine code.

Compiler

A compiler is a program that reads a program written in one language, called the source language, and translates it into an equivalent program in another language, called the target language.

Along with translation, the compiler also detects errors in the source program and presents error information to the user.

Interpreter

An interpreter is another commonly used language processor. Instead of producing a target program as a single translation unit, an interpreter appears to directly execute the operations specified in the source program on the inputs supplied by the user.

In simple words, an interpreter translates and executes the source program step by step, usually line by line, rather than generating a separate target program first.

Interpreter flow: source program and input are directly processed to produce output.

This shows that an interpreter takes both the source program and input, then directly produces the output without first creating a separate target program.

Compiler Overview

The compiler works as a translator between the source program and the target program.

Compiler overview: source program is translated into target program and errors are reported.

The source program is usually written in a high-level language such as C, C++, Java, or Python-like syntax. The compiler analyzes this source program and produces an equivalent program in another language.

The target program may be:

• Machine code
• Relocatable object code
• Another high-level language program
• Any equivalent target representation

If the target program is an executable machine-language program, users can run it directly to process input data and produce output.

Running the target program: input is processed to produce output.

This represents the running stage of the target program after successful compilation.

During compilation, the compiler may also produce error information. These errors help the programmer correct the source program before successful execution.

Common errors reported by a compiler include:

• Syntax errors
• Semantic errors
• Type mismatch errors
• Undeclared variable errors
• Invalid expression errors

Types of Compilers

Based on the specific input a compiler takes and the output it produces, compilers can be classified into the following types.

Type of Compiler	Description	Examples
Traditional Compiler	Converts a source program written in a high-level language into native machine code or object code.	C, C++, Pascal
Interpreter-Based Compiler	First converts source code into intermediate code, then interprets or emulates it to produce equivalent machine behavior.	LISP, SNOBOL, Java 1.0
Cross-Compiler	Runs on one machine but produces code for another machine.	Compiler on Windows generating ARM code
Incremental Compiler	Separates the source program into user-defined steps and compiles or recompiles step by step. It may interpret steps in a given order.	Interactive development systems
Converter	Translates one high-level language into another high-level language.	COBOL to C++ converter
Just-In-Time Compiler	Converts intermediate language, such as bytecode or MSIL, into executable native machine code at runtime. It may also perform type-based verification to make executable code more trustworthy.	Java JIT, Microsoft .NET JIT
Ahead-of-Time Compiler	Pre-compiles code into native code before runtime.	.NET NGen, AOT for Java/.NET
Binary Compiler	Converts object code of one platform into object code of another platform.	Binary translation tools

Phases of a Compiler

Phases of a compiler with symbol-table manager and error handler.

Compilation is a complex task, so a compiler usually works through a sequence of compilation phases. Each phase performs a specific subtask and passes its output to the next phase.

The phases communicate with each other through clearly defined interfaces. An interface may contain:

• A data structure, such as a tree or intermediate representation
• A set of exported functions
• Intermediate information needed by the next phase

Except for the first phase, most compiler phases do not work directly on the original source program text. Instead, they work on an abstract intermediate representation of the source program.

Compiler phases are individual modules that are executed in chronological order. Each module performs its own sub-activity, and the combined result of all phases is the final target code.

It is usually desirable to have relatively few phases because reading and writing intermediate files can take extra time.

A typical compiler has the following major phases:

1. Lexical Analyzer, also called Scanner
2. Syntax Analyzer, also called Parser
3. Semantic Analyzer
4. Intermediate Code Generator, or ICG
5. Code Optimizer, or CO
6. Code Generator, or CG

In addition to these major phases, a compiler also uses:

• Symbol table management
• Error handler

Not every compiler must include every phase. For example, the code optimizer phase may be optional in some compilers.

Analysis and Synthesis Parts

The phases of a compiler are commonly divided into two major parts.

Part	Phases	Main Work
Analysis Part	Lexical analysis, syntax analysis, semantic analysis	Breaks the source program into meaningful components and checks correctness.
Synthesis Part	Intermediate code generation, code optimization, code generation	Builds the target program from the analyzed representation.

PHASE, PASSES OF A COMPILER:

In some application we can have a compiler that is organized into what is called passes. Where a pass is a collection of phases that convert the input from one representation to a completely deferent representation. Each pass makes a complete scan of the input and produces its output to be processed by the subsequent pass. For example a two pass Assembler.

THE FRONT-END & BACK-END OF A COMPILER

All of these phases of a general Compiler are conceptually divided into The Front-end, and The Back-end. This division is due to their dependence on either the Source Language or the Target machine. This model is called an Analysis & Synthesis model of a compiler. The Front-end is the part of the compiler that analyzes the source language and produces an abstract syntax tree (AST). The Back-end is the part of the compiler that takes the AST and generates the target language. The Front-end of the compiler consists of phases that depend primarily on the Source language and are largely independent on the target machine. For example, front-end of the compiler includes Scanner, Parser, Creation of Symbol table, Semantic Analyzer, and the Intermediate Code Generator.

The Back-end of the compiler consists of phases that depend on the target machine, and those portions don't dependent on the Source language, just the Intermediate language. In this we have different aspects of Code Optimization phase, code generation along with the necessary Error handling, and Symbol table operations.

LEXICAL ANALYZER (SCANNER):

The Scanner is the first phase that works as interface between the compiler and the Source language program and performs the following functions:

Reads the characters in the Source program and groups them into a stream of tokens in which each token specifies a logically cohesive sequence of characters, such as an identifier , a Keyword , a punctuation mark, a multi character operator like := . The character sequence forming a token is called a lexeme of the token. The Scanner generates a token-id, and also enters that identifiers name in the Symbol table if it doesn't exist. Also removes the Comments, and unnecessary spaces. The format of the token is < Token name, Attribute value >

SYNTAX ANALYZER (PARSER):

The Parser interacts with the Scanner, and its subsequent phase Semantic Analyzer and performs the following functions: Groups the above received, and recorded token stream into syntactic structures, usually into a structure called Parse Tree whose leaves are tokens. The interior node of this tree represents the stream of tokens that logically belongs together. It means it checks the syntax of program elements.

SEMANTIC ANALYZER:

This phase receives the syntax tree as input, and checks the semantically correctness of the program. Though the tokens are valid and syntactically correct, it may happen that they are not correct semantically. Therefore the semantic analyzer checks the semantics (meaning) of the statements formed.

The Syntactically and Semantically correct structures are produced here in the form of a Syntax tree or DAG or some other sequential representation like matrix.

INTERMEDIATE CODE GENERATOR(ICG):

This phase takes the syntactically and semantically correct structure as input, and produces its equivalent intermediate notation of the source program. The Intermediate Code should have two important properties specified below:

It should be easy to produce,and Easy to translate into the target program. Example

intermediate code forms are:

Three address codes,

Polish notations, etc.

CODE OPTIMIZER:

This phase is optional in some Compilers, but so useful and beneficial in terms of saving development time, effort, and cost. This phase performs the following specific functions:

Attempts to improve the IC so as to have a faster machine code. Typical functions include –Loop Optimization, Removal of redundant computations, Strength reduction, Frequency reductions etc.

Sometimes the data structures used in representing the intermediate forms may also be changed.

CODE GENERATOR:

This is the final phase of the compiler and generates the target code, normally consisting of the relocatable machine code or Assembly code or absolute machine code.

Memory locations are selected for each variable used, and assignment of variables to registers is done.

Intermediate instructions are translated into a sequence of machine instructions.

The Compiler also performs the Symbol table management and Error handling throughout the compilation process. Symbol table is nothing but a data structure that stores different source language constructs, and tokens generated during the compilation. These two interact with all phases of the Compiler.

For example the source program is an assignment statement; the following figure shows how the phases of compiler will process the program.

The input source program is Position=initial+rate*60

Translation of an assignment statement through compiler phases.

LEXICAL ANALYSIS:

As the first phase of a compiler, the main task of the lexical analyzer is to read the input characters of the source program, group them into lexemes, and produce as output tokens for each lexeme in the source program. This stream of tokens is sent to the parser for syntax analysis. It is common for the lexical analyzer to interact with the symbol table as well. When the lexical analyzer discovers a lexeme constituting an identifier, it needs to enter that lexeme into the symbol table. This process is shown in the following figure.


When lexical analyzer identifies the first token it will send it to the parser, the parser receives the token and calls the lexical analyzer to send next token by issuing the getNextToken() command. This Process continues until the lexical analyzer identifies all the tokens. During this process the lexical analyzer will neglect or discard the white spaces and comment lines. The lexical analyzer is responsible for the following tasks:

Reading the input characters of the source program. Grouping them into lexemes. Producing tokens for each lexeme. Sending tokens to the parser. Interacting with the symbol table.

TOKENS, PATTERNS AND LEXEMES:

A token is a pair consisting of a token name and an optional attribute value. The token name is an abstract symbol representing a kind of lexical unit, e.g., a particular keyword, or a sequence of input characters denoting an identifier. The token names are the input symbols that the parser processes. In what follows, we shall generally write the name of a token in boldface. We will often refer to a token by its token name.

A pattern is a description of the form that the lexemes of a token may take [ or match]. In the case of a keyword as a token, the pattern is just the sequence of characters that form the keyword. For identifiers and some other tokens, the pattern is a more complex structure that is matched by many strings.

A lexeme is a sequence of characters in the source program that matches the pattern for a token and is identified by the lexical analyzer as an instance of that token.

Example: In the following C language statement , printf ("Total = %d\n", score) ;

both printf and score are lexemes matching the pattern for token id, and "Total = %d\n" is a lexeme matching literal [or string].


LEXICAL ANALYSIS Vs PARSING:

There are a number of reasons why the analysis portion of a compiler is normally separated into lexical analysis and parsing (syntax analysis) phases.

1. Simplicity of design is the most important consideration.

The separation of Lexical and Syntactic analysis often allows us to simplify at least one of these tasks. For example, a parser that had to deal with comments and whitespace as syntactic units would be considerably more complex than one that can assume comments and whitespace have already been removed by the lexical analyzer.

2. Compiler efficiency is improved.

A separate lexical analyzer allows us to apply specialized techniques that serve only the lexical task, not the job of parsing. In addition, specialized buffering techniques for reading input characters can speed up the compiler significantly.

3. Compiler portability is enhanced:

Input-device-specific peculiarities can be restricted to the lexical analyzer.

INPUT BUFFERING:

Before discussing the problem of recognizing lexemes in the input, let us examine some ways that the simple but important task of reading the source program can be speeded. This task is made difficult by the fact that we often have to look one or more characters beyond the next lexeme before we can be sure we have the right lexeme. There are many situations where we need to look at least one additional character ahead. For instance, we cannot be sure we've seen the end of an identifier until we see a character that is not a letter or digit, and therefore is not part of the lexeme for id. In C, single-character operators like -, =, or < could also be the beginning of a two-character operator like ->, ==, or <=. Thus, we shall introduce a two-buffer scheme that handles large look aheads safely. We then consider an improvement involving "sentinels" that saves time checking for the ends of buffers.

Buffer Pairs

Because of the amount of time taken to process characters and the large number of characters that must be processed during the compilation of a large source program, specialized buffering techniques have been developed to reduce the amount of overhead required to process a single input character. An important scheme involves two buffers that are alternately reloaded.


Each buffer is of the same size N, and N is usually the size of a disk block, e.g., 4096 bytes. Using one system read command we can read N characters in to a buffer, rather than using one system call per character. If fewer than N characters remain in the input file, then a special character, represented by eof, marks the end of the source file and is different from any possible character of the source program.

Two pointers to the input are maintained:

The Pointer lexemeBegin, marks the beginning of the current lexeme, whose extent we are attempting to determine. Pointer forward scans ahead until a pattern match is found; the exact strategy whereby this determination is made will be covered in the balance of this chapter.

Once the next lexeme is determined, forward is set to the character at its right end. Then, after the lexeme is recorded as an attribute value of a token returned to the parser, 1exemeBegin is set to the character immediately after the lexeme just found. In Fig, we see forward has passed the end of the next lexeme, ** (the FORTRAN exponentiation operator), and must be retracted one position to its left.

Advancing forward requires that we first test whether we have reached the end of one of the buffers, and if so, we must reload the other buffer from the input, and move forward to the beginning of the newly loaded buffer. As long as we never need to look so far ahead of the actual lexeme that the sum of the lexeme's length plus the distance we look ahead is greater than N, we shall never overwrite the lexeme in its buffer before determining it.

Sentinels To Improve Scanners Performance:

If we use the above scheme as described, we must check, each time we advance forward, that we have not moved off one of the buffers; if we do, then we must also reload the other buffer. Thus, for each character read, we make two tests: one for the end of the buffer, and one to determine what character is read (the latter may be a multi way branch). We can combine the buffer-end test with the test for the current character if we extend each buffer to hold a sentinel character at the end. The sentinel is a special character that cannot be part of the source program, and a natural choice is the character eof.