Compiler Design & Construction

Translator Software: A translator software is a type of system software

that converts programs written in one programming language (source code)
into another form, typically into machine code that the computer can directly
execute. It enables communication between humans, who write code in
high-level or assembly languages, and computers, which understand only
binary machine instructions. Types of Translator Software are given below -

1
1.​ Compiler: Translates the entire source program into machine code at
once. Generates an object file or executable file. Example: C, C++

-7
compilers like GCC, Turbo C.
2.​ Interpreter: Translates and executes the source program line by line.
No separate machine code file is produced. Example: Python Interpreter,
JavaScript Engine, Ruby Interpreter.
3.​ Assembler: Converts assembly language programs into machine code.
IM
Example: MASM (Microsoft Assembler), TASM, NASM.

Compiler: A compiler is a special program that translates source code

AM

written in a high-level programming language (like C, C++, or Java) into

machine code (binary form) that a computer’s processor can understand and
execute.
SH

Phases of Compiler: A compiler operates in several phases, and each

phase transforms the source program from one form of representation to
another. Every phase takes its input from the previous stage and passes its
output to the next phase. There are six phases in a compiler, each playing a
crucial role in converting high-level language code into machine code.
 1
-7
IM
1. Lexical Analysis (Scanning): Lexical Analysis is the first phase of the
compiler. It scans the source code and converts it into a sequence of tokens —
the smallest meaningful units such as keywords, identifiers, operators, etc.
AM
SH

2. Syntax Analysis (Parsing): Syntax Analysis is the second phase of

compilation. It checks whether the sequence of tokens follows the grammar
rules of the programming language and builds a parse tree representing the
syntactic structure. This phase verifies if the program syntax is valid or not.
3. Semantic Analysis: Semantic Analysis is the third phase of the compiler. It
checks whether the parse tree follows the semantic rules of the language, such
as type compatibility, scope resolution, and proper declaration usage. It also
stores identifier and expression information in a symbol table.
4. Intermediate Code Generation: It is the fourth phase of the compiler. It is

1
used to generate an intermediate code — a representation between high-level
and machine code. This code is independent of any specific machine and is

-7
easier to optimize later.

IM
5. Code Optimization: This is the fifth phase of the compiler and is
considered an optional phase. It improves the intermediate code to achieve
better performance and reduce memory usage. During this phase, the
AM

compiler removes redundant instructions, eliminates unused code, and

rearranges statements to ensure faster and more efficient execution without
changing its output.
SH

6. Code Generation: The final phase of the compiler translates optimized

intermediate code into machine code (or assembly code). It selects registers,
assigns memory locations, and produces the target program ready for
execution.
Compiler Compiler: A compiler-compiler, also known as a compiler
generator, is a specialized software tool used to automatically produce a
parser, interpreter, or even a full compiler from a formal description of a
programming language and its machine model. Instead of manually writing
the components of a compiler, developers provide the lexical rules, grammar
rules, and sometimes semantic rules, and the compiler-compiler generates the
required code. The most common type of compiler-compiler is the parser
generator.

1
Symbol Table: A Symbol Table is a key data structure used by a compiler to

-7
store information about identifiers, including variable names, function names,
objects, constants, and their attributes. It typically contains details such as the
identifier’s name, type, scope, memory location, and sometimes its value.

The symbol table interacts with all phases of the compiler as well as the error
handler, receiving updates whenever new identifiers are declared or
IM
referenced. It also plays a vital role in scope management, ensuring that
variables and functions are accessed correctly according to their visibility
within the program. The functions of a symbol table are written below.
AM

●​ Identifier Storage & Management: Stores all identifiers during

lexical/syntax analysis and keeps their attributes. Prevents duplicate
declarations within the same scope.
●​ Scope Management (Scope Resolution): Tracks global, local, and
block-level scopes. Ensures correct visibility, lifetime, and shadowing of
SH

identifiers.
●​ Type Checking (Semantic Verification): Holds data types for variables
and functions. Helps detect type mismatches during semantic analysis.
●​ Verification of Usage: Ensures identifiers are declared before use.
Validates function calls for correct argument number and types.
●​ Address Allocation: Provides memory addresses or offsets for
identifiers. Supports stack frame creation and machine code generation.

Parse Tree: A parse tree, also known as a derivation tree or concrete syntax
tree, is a hierarchical tree structure that represents the syntactic structure of a
string according to a given context-free grammar (CFG). It is widely used in
compiler design and automata theory to illustrate how a string is derived from
the start symbol of the grammar by sequentially applying production rules.

Key Features of a Parse Tree:

●​ Root Node: Represents the start symbol of the grammar.

●​ Internal Nodes: Represent non-terminal symbols.
●​ Leaf Nodes: Represent terminal symbols (actual tokens of the input

1
string).
●​ Edges: Represent the application of production rules.

-7
Front-End (Analysis Phase): The Front-End of a compiler is also known
as the Analysis Phase. It is responsible for analyzing the source code and
ensuring that it is syntactically and semantically correct. This phase is
machine-independent, meaning it does not depend on the target hardware. It
IM
reads the source program, breaks it down, and produces an intermediate
representation (IR) for further processing. Functions of the Front-End:

●​ Lexical Analysis: Converts code into tokens.

AM

●​ Syntax Analysis: Checks grammar, builds parse trees.

●​ Semantic Analysis: Ensures meaningfulness and type correctness.
●​ Intermediate Code Generation: Produces intermediate code.

Back-End (Synthesis Phase): The Back-End of a compiler is also known

SH

as the Synthesis Phase. It is responsible for transforming the intermediate

code into the target machine code. This phase is machine-dependent because
it involves direct interaction with registers, memory management, and CPU
instructions. Its main goal is to produce optimized and efficient executable
code. Functions of the Back-End:
●​ Code Optimization: Improves the intermediate code to enhance
performance and reduce resource usage.
●​ Code Generation: Converts the optimized intermediate code into target
machine code or assembly code.
 1
-7
Compiler Interpreter
Translates the entire program at Translates the program line by line.
once into machine code
IM
Errors are displayed after compiling Errors are shown immediately, one
the entire program. line at a time.
Execution is faster since the code is Execution is slower due to
AM

already compiled line-by-line translation at runtime

Produces an object/executable file. Does not produce an object or
executable file.
Requires more memory to store the Requires less memory since no
SH

object code. object code is stored.

All errors must be fixed before Execution stops as soon as an error is
execution. found.
Once compiled, the program can run Requires the interpreter every time it
without the compiler runs
Suitable for production-level Suitable for testing and debugging
deployment during development
Example: C compiler (GCC), C++ Example: Python interpreter,
compiler, Java compiler (javac). JavaScript interpreter, Ruby
interpreter.

Linker: A link editor, commonly known as a linker, is a program that

combines multiple object files into a single executable program. It resolves
external references (like function calls across files) and links library code if
needed.

Loader: Loads the executable file into main memory for execution. It

1
allocates memory, initializes required data, and transfers control to the

-7
program’s entry point (e.g., main() function).

Linker Loader
IM
A linker combines object files and A loader loads the executable into
resolves symbol references to create memory and prepares it for
a final executable. execution.
It operates during the compilation It operates during runtime,
AM

phase, linking object code and transferring the executable code

libraries into an executable. from disk to memory for execution.
The linker generates a file that can be The loader loads the executable into
run later. memory and starts execution when
the program is run.
SH

Linkers handle tasks such as symbol Loaders manage memory allocation,

resolution, address binding, and address mapping, and loading
combining multiple object files. dynamic libraries into memory.

Example: GNU ld linker used for Example: Operating system loaders

static linking. like the exec() function in Unix
systems.

Translating the statement position = initial + rate × 60 according to the six

phases of a compiler is as follows:
 1
-7
IM
Language Processing System: A language processing system is a
collection of programs or software tools that work together to translate,
analyze, and execute a program written in a high-level programming language
into a form that a computer’s hardware can understand and execute.
AM
SH
Preprocessor: A preprocessor is a program that processes the source code
before the compiler actually compiles it. It performs text replacement and
code manipulation based on special instructions called preprocessor
directives, which always start with the symbol #. A pre-processor can
implement the following functions −

●​ Macro Processing: Defines macros as short forms for complex code.

The preprocessor replaces each macro with its definition before
compilation.

1
●​ File Inclusion: Uses directives like #include to insert header files or
external code, improving modularity and reuse.

-7
●​ Rational Preprocessing: Adds additional control-flow and
data-structuring features to make the source code more organized.
●​ Language Extensions: Expands the language with new capabilities
using special macro constructs without modifying the compiler.
IM
Error in the phases of the compiler: A compiler detects different kinds
of errors at various stages of compilation. The three main types of errors
AM

detected during compile time are Lexical, Syntax, and Semantic.

1. Lexical Errors: Lexical errors are identified during the Lexical Analysis
phase. It occurs when the source program contains invalid characters or
tokens. Examples:
SH

●​ Illegal characters
●​ Invalid identifiers
●​ Unterminated strings
●​ Unknown symbols

2. Syntax Errors: Syntax errors are identified during the Syntax Analysis
(Parsing) phase. It happens when statements do not follow the language
grammar rules. Examples:

●​ Missing semicolon
 ●​ Unmatched parentheses
●​ Wrong statement structure
●​ Misplaced operators

3. Semantic Errors: Semantic errors are identified during the Semantic

Analysis phase. It occurs when statements are grammatically correct but
meaningfully incorrect. Examples:

●​ Type mismatches

1
●​ Using undeclared variables
●​ Incorrect number/type of function arguments

-7
●​ Assigning to a constant
●​ Incompatible return type
IM
Context-Free Grammar (CFG): A Context-Free Grammar (CFG) is a
formal grammar that describes the structure of strings in a context-free
AM

language. It consists of production rules that recursively generate valid

strings in the language. It can describe all regular languages and more, but it
cannot describe all possible languages. A context-free grammar has 4 tuples,
and it is denoted by G = (V, T, P, S). Where:

●​ V (Variables / Non-terminals): Symbols that can be replaced using

SH

production rules. Example: S, A, B

●​ T (Terminals): Actual alphabet symbols of the language. Example: a, b,
0, 1
●​ P (Productions): Set of rules for replacing variables with
variables/terminals. Example: S→aSb ∣ ε
●​ S (Start Symbol): A special variable from which the derivation begins

Parse tree: A parse tree is a hierarchical tree structure that shows how a
string of symbols is generated from a context-free grammar (CFG). In this tree,
each internal node represents a non-terminal symbol, while each leaf node
corresponds to a terminal symbol.

The parse tree plays a vital role in determining whether an input string
conforms to the rules of a grammar, thereby verifying its syntactic correctness.
During the parsing process, the input string is derived step by step from the
start symbol, which serves as the root of the tree.

1
-7
IM
Key Properties of a Parse Tree:
AM

●​ Root is the Start Symbol

●​ Internal Nodes Are Non-terminals
●​ Leaf Nodes Are Terminals or ε
●​ Children Represent the RHS of a Production Rule
SH

●​ Yield (Frontier) Forms the Derived String

●​ Structure Reflects Derivation Order
●​ Depth Represents Nested Structure
●​ Parse Tree Always Follows Grammar’s Hierarchy

Syntax Tree: A syntax tree, also called an abstract syntax tree (AST), is a
simplified, abstract representation of the syntactic structure of a program.
Unlike a parse tree, it does not show every grammar symbol. Instead, it
focuses on the essential hierarchical meaning of the program by removing
unnecessary syntactic details such as parentheses or extra non-terminals.
 Parse Tree Syntax Tree
Represents the complete derivation Represents the logical/abstract
based on grammar rules. structure of the program.
Includes all non-terminals and Omits unnecessary non-terminals;
terminals. focuses on essential constructs.
Very large and detailed More compact and simplified.
Shows the exact grammar hierarchy Shows the semantic structure used by

1
and order of derivations. compilers.
Derivation order and grammar Focuses on the meaning (semantics)

-7
hierarchy are clearly visible. rather than the derivation order.
Multiple parse trees may exist for Usually unique for a given expression.
ambiguous grammars.
Every production rule appears as a Combines or removes rules that do
separate node. not affect meaning.
IM
Lexical Analyzer as an Interface Between Input and Parser: The
AM

lexical analyzer (lexer) acts as a bridge between the source program (input)
and the syntax analyzer (parser). It converts the raw sequence of characters
(source code) into a stream of tokens, which the parser can easily understand
and process.
SH
 ●​ Input: The Input is the source program written in a high-level language
(like C, Java, etc.). It is provided to the lexical analyzer as a stream of
characters. Example: int x = 10;
●​ Lexical Analyzer (Scanner): The lexical analyzer reads the source code
character by character. It groups these characters into lexemes
(meaningful units like int, x, =, 10, ;). Then it converts each lexeme into a
token. The tokens are then sent to the syntax analyzer.
●​ Syntax Analyzer (Parser): The parser requests tokens from the lexical

1
analyzer. It uses these tokens to construct the parse tree or syntax tree
according to grammar rules. When the parser needs the next token, it

-7
asks for it again.

Reasons for separating the analysis phases of compiling into

lexical analysis and parsing: Separating the analysis phases of compiling
into lexical analysis and parsing provides clarity, efficiency, and modularity.
IM
The key reasons are:

●​ Simplifies parser design: Parsers work better with a clean stream of

tokens instead of raw characters.
●​ Improves efficiency: Tokenization is faster when handled separately
AM

using finite automata.

●​ Enhances modularity: Lexical rules and syntactic rules can be
designed, tested, and updated independently.
●​ Supports better error handling: Lexical errors (illegal characters,
malformed tokens) are caught early before parsing.
SH

●​ Allows use of specialized tools: Tools like lex for tokenizing and
yacc/bison for parsing work best with separated phases.
●​ Avoids grammar complexity: Without a separate lexer, grammar rules
become unnecessarily large and hard to manage.
Functions of a Lexical Analyzer: The primary role of a lexical analyzer is
to scan the source program and generate tokens, but it also performs several
additional important tasks in the compilation process:

●​ Tokenization: It groups characters into meaningful units called tokens

(identifiers, keywords, operators, literals, punctuation).
●​ Removal of Whitespaces and Comments: It eliminates spaces, tabs,
newlines, and comments that are not needed for syntax analysis.
●​ Lexical Error Handling: It detects invalid characters or malformed

1
tokens and reports lexical errors (e.g., illegal symbols).
●​ Symbol Table Management: It collects identifiers and inserts them into

-7
the symbol table, storing names and related attributes.
●​ Pattern Matching: It uses regular expressions or finite automata to
recognize lexical patterns in the input.
●​ Providing Tokens to the Parser: It acts as an interface between source
IM
code and the parser by delivering one token at a time on demand.
●​ Buffer Management: It efficiently reads input using buffers to handle
large files and ensures fast scanning.

Error Recovery Strategies in Lexical Analysis: In lexical analysis, the

AM

scanner may encounter invalid characters, incomplete tokens, or unknown

patterns. To continue scanning instead of stopping, the lexer uses error
recovery strategies. These strategies help the compiler proceed to the next
valid token and minimize disruption.
SH

●​ Panic-Mode Recovery: Skip characters until a valid token is found.

Ex: int x = 10 @ 20; @ is invalid, so the lexer skips everything from @
until it reaches a safe point (like ;).

●​ Skipping Erroneous Characters: Discard illegal or unexpected

characters and continue scanning.
Ex: int x = 5#; # is an illegal symbol so lexer removes only # and
continues scanning.
 ●​ Inserting Missing Characters: Add a likely missing character to
complete a token.
Ex: 3. → assume missing digit and treat as 3.0

●​ Deleting Extra Characters: Remove an unexpected character inside a

token.
Ex: int#x → delete # and proceed

●​ Replacing Characters: Replace an invalid character with the most likely

1
valid one.
Ex: 3,a → replace , with . and treat as a floating literal

-7
●​ Reporting and Continuing: Report the error but continue scanning
without stopping.

Token: A token is a collection of characters that represents a logical unit of

IM
information in the program. The program that performs lexical analysis is
called a scanner, tokenizer, or lexer.

Lexeme: A lexeme is a sequence of characters in the source program that

AM

matches the pattern of a token and is recognized by the lexical analyzer as an

instance of that token. Example: In the expression: X+5
●​ x → lexeme for the token IDENTIFIER
●​ + → lexeme for the token PLUS_OPERATOR
●​ 5 → lexeme for the token NUMBER
SH

Pattern: A pattern is the rule or regular expression used to describe how

valid lexemes for a token look. Example: Identifier pattern →
[A-Za-z][A-Za-z0-9_]*

Identifier: An identifier is a token type used for naming variables, functions,

classes, etc. Example lexemes: x, sum, totalMarks
Why a Lexical Analyzer Is Essential: A lexical analyzer is a crucial part
of a compiler because it performs the first step of processing the source code.
It transforms raw characters into meaningful tokens, making the next
compilation stages accurate and manageable.

●​ Breaks Input into Tokens: Converts long streams of characters into

structured tokens that the parser can understand.
●​ Simplifies Parsing: Removes complexities like whitespace, comments,

1
and irrelevant characters, allowing the parser to focus only on syntactic
structure.

-7
●​ Improves Accuracy: Ensures that tokens follow defined patterns
(keywords, identifiers, numbers, operators), reducing ambiguity.
●​ Handles Lexical Errors Early: Detects illegal characters or malformed
tokens before they affect the parser or later compilation phases.
●​ Manages Symbol Table Entries: Identifies and records identifiers for
IM
later semantic analysis.
●​ Increases Efficiency: Uses buffering and pattern-matching techniques
(like automata) to scan code faster and more consistently.
AM

Different Types of Tokens:

●​ Keywords: Predefined reserved words with fixed meaning. Ex: if, else,
while, return, int
●​ Identifiers: Names given by the programmer for variables, functions,
classes, etc. Ex: sum, totalMarks, x
SH

●​ Constants / Literals: Fixed values that appear directly in the program.

Ex: Integer: 10, 200 Float: 3.14
●​ Operators: Symbols that perform operations on operands. Examples: +,
-, *, /, =, ==, >
●​ Punctuation / Delimiters: Symbols used to separate program
elements. Ex: ;, ,, (), {}, []
●​ Special Tokens: Depending on the language, additional categories may
include: Comments, Whitespace, Preprocessor directives (e.g., #include)
Deterministic Finite Automaton (DFA): A Deterministic Finite
Automaton (DFA) is a special type of finite automaton in which for every state
and input symbol, there is exactly one transition to another state. In other
words, the machine has no ambiguity in choosing the next state. A DFA is
formally represented by a 5-tuple: M=(Q,Σ,δ,q0,F)

●​ Q is a finite set of states

●​ Σ is a finite set of input symbols (alphabet)
●​ δ is the transition function: δ: Q × Σ → Q

1
●​ q₀ is the initial state (q₀ ∈ Q)
●​ F is the set of accepting (final) states (F ⊆ Q)

-7
Nondeterministic Finite Automaton (NFA): A Nondeterministic Finite
Automaton (NFA) is a type of finite automaton where, for a given state and
input symbol, there may be multiple possible next states or even none. It may
also include ε-transitions, which allow the machine to change states without
IM
consuming any input symbol. An NFA is defined by a 5-tuple: M=(Q,Σ,δ,q0,F)

●​ Q is a finite set of states

●​ Σ is a finite input alphabet
AM

●​ δ is the transition function: δ: Q × Σ → 2Q

●​ q₀ is the initial state (q₀ ∈ Q)
●​ F is the set of accepting (final) states (F ⊆ Q)
SH

DFA NFA

Deterministic Finite Automaton Non-deterministic Finite Automaton

For each state and input symbol, For a state and input symbol, zero,
exactly one transition is defined. one, or more transitions may exist.

There is no ambiguity in the next The automaton may have multiple

state. possible paths for a single input.
No ε (epsilon) transitions are ε-transitions (move without input)
allowed. are allowed.

It is easier to implement in code Easier to design and construct

(used in real compilers). theoretically.

There is always only one May have multiple computation

computation path for an input string. paths for an input string.

1
Acceptance is based on a single path Acceptance of any path ends in a final
ending in a final state. state.

-7
DFA is less expressive to write but NFA is more flexible to define, but
equivalent in power. same computational power.

Require more space Require less space

DFA is difficult to design NFA is easier to design
IM
Input Buffering Technique (Double Buffering): Input buffering is
used in lexical analysis to read the source program faster. Reading characters
AM

one by one from the disk is slow, so compilers use two buffers of fixed size.
While the lexer processes one buffer, the compiler fills the other buffer with
the next part of the source file. This reduces I/O operations and makes
scanning efficient. Working procedure of input buffer technique:

●​ Two buffers: Buffer 1 and Buffer 2. Each buffer holds N−1 characters +
SH

1 sentinel (EOF marker)

●​ Two pointers:
○​ lexemeBegin → start of a token
○​ forward → scans characters

When forward reaches a sentinel, the lexer automatically switches to the other
buffer.

Simple Input-Buffer Technique Code (With Comments):

SH
AM
IM
-7
1