Role of Lexical Analyzer

Definition

A Lexical Analyzer (also called a Scanner) is the first phase of the compiler.
Its main role is to read the source code character by character, group those characters
into meaningful sequences called lexemes, and convert them into tokens which are
sent to the next phase (Syntax Analysis).

Main Tasks / Functions

1. Reading Input Characters

• The lexical analyzer reads the entire source code character by character and
symbol by symbol using an input buffer.

• It identifies where each word or symbol begins and ends.

2. Forming Lexemes

• Consecutive characters that form a meaningful unit are grouped together into
lexemes.

• A lexeme is the actual text found in the source program that matches a language
pattern (e.g., int, a, 5, +).

3. Generating Tokens

• Each lexeme is converted into a token that represents its category.

• A token is a structure like (token_name, attribute)

Example: (KEYWORD, "int"), (IDENTIFIER, "a"), (NUMBER, "5")

• These tokens are sent to the parser for syntactic analysis.

4. Ignoring Unnecessary Elements

• The lexical analyzer skips parts of the source code that have no effect on the
program’s logic:

o Whitespace (spaces, tabs, newlines)

o Comments (//, /* ... */)

o Line breaks

• This keeps only the meaningful content.

5. Reporting Lexical Errors

 • It detects and reports invalid tokens or illegal sequences of characters such as:

o Invalid symbols (@x = 5;)

o Unclosed string literals ("Hello)

o Malformed numbers (12.3.4)

• It reports the line number and position of the error.

Example

Source Code:

int age = 20;

Lexical Analyzer Output:

Lexeme Token Type

int KEYWORD

age IDENTIFIER

= ASSIGNMENT_OPERATOR

20 NUMBER

; DELIMITER

Token Stream:

(KEYWORD, int)

(IDENTIFIER, age)

(ASSIGNMENT_OPERATOR, =)

(NUMBER, 20)

(DELIMITER, ;)

Error Example

int @age = 10;

Here, the character @ is invalid → the lexical analyzer raises a lexical error at that
position.
Real-World Analogy

Think of the lexical analyzer like your brain reading a sentence:

When you read “I love coding”, you first recognize the individual words (tokens) before
checking grammar or meaning.
Similarly, the lexical analyzer splits the source code into tokens before any further
analysis.

Summary Table

Function Description

Input Source code (characters)

Output Stream of tokens

Removes Whitespaces, comments, line breaks

Reports Lexical errors

Tool Lex / Flex

Final Answer (short form for exam use):

The lexical analyzer reads the source code character by character using input buffering,
groups characters into meaningful sequences called lexemes, and produces tokens
representing their types. It removes comments, spaces, and line breaks, and reports
lexical errors. The output of this phase is a stream of tokens that are passed to the
syntax analyzer for further processing.
INPUT BUFFERING TYPES

When the compiler (specifically, the lexical analyzer) reads your source code, it
doesn’t read one character at a time — that would be way too slow.

So it uses buffers — small memory areas that temporarily hold a block of characters
from your program.

There are two types of buffering systems:

1. Single Buffer System

2. Double Buffer System

Let’s break each one down simply

SINGLE BUFFER SYSTEM (One Buffer)

Simple Idea:

• There’s only one buffer.

• The compiler fills it with a block of characters (e.g., 10 or 20) from your source
program.

• The lexical analyzer reads from this buffer to form tokens.

Example:

Program:

int age = 20;

Buffer (size = 10):

|i|n|t| |a|g|e| |=| |

The compiler can now read these characters one by one from this buffer instead of
calling the operating system each time.

Problem:

What if your program is longer than 10 characters?

Let’s say your code is:

int age = 20; float x;

→ That’s 21 characters, but the buffer holds only 10.

Once the buffer is full, new data will start overwriting the old data.

So while the compiler is still processing "int age =",

the new characters (2, 0, ;, f, etc.) overwrite it.

Result:
Tokens get broken,
Some characters are lost,
Lexemes become incomplete.

Why it Fails:

The compiler might be halfway reading "float" when the buffer overwrites part of it.
It has no backup area to store the rest of the input.

Hence — data loss, errors, and incomplete tokens.

In Short:

Concept Explanation

Buffer Count 1

Advantage Faster than reading character-by-character

Problem Overwriting old data when buffer fills up

Result Data loss, incomplete lexemes

DOUBLE BUFFER SYSTEM (Two Buffers)

Simple Idea:

To fix overwriting problems, we use two buffers —

one to read from, and one to fill next.

So when one buffer finishes, the compiler switches to the other.

This way, there’s always one buffer ready to read — continuous flow, no waiting.
 Example:

Let’s use the same program:

int age = 20; float x;

and assume each buffer can hold 10 characters.

Step 1: Fill Buffer 1

Buffer 1: | i | n | t | | a | g | e | | = | |

Buffer 2: (empty)

The lexical analyzer starts scanning from Buffer 1.

Step 2: While Buffer 1 is being read, fill Buffer 2

Buffer 1: (being read)

Buffer 2: | 2 | 0 | ; | | f | l | o | a | t | |

When FP (Forward Pointer) reaches the end of Buffer 1,

it automatically jumps to Buffer 2 and continues scanning there.

Step 3: When Buffer 2 ends

Buffer 1: (refilled) | x | ; | EOF | ... |

Buffer 2: (being read)

Now Buffer 1 is refilled with the next characters while Buffer 2 is being read.

This alternating process continues until the end of the source file.

No overwriting
No waiting
Continuous scanning

Sentinel / EOF Marker

At the end of each buffer, a special symbol (EOF or sentinel) is added to mark where the
buffer ends.

When FP sees this marker, it knows it’s time to switch buffers.

 Advantages of Two Buffer System

Advantage Explanation

No Data Loss Old data is safe while new data is loaded

Continuous Reading When one buffer ends, the next is ready

Less System Calls Reads big blocks at once instead of single characters

Efficient Speeds up lexical analysis

Easy Analogy

Think of two buffers like two buckets being filled with water (characters):

• You pour from Bucket A while Bucket B is being refilled.

• When Bucket A empties, you swap — start pouring from Bucket B while refilling
Bucket A.

You’ll never run out of water (data) — smooth, non-stop flow.

In Short:

Concept Explanation

Buffer Count 2

Working While one buffer is read, the other is refilled

Marker EOF (sentinel) used at end

Result Continuous, efficient, and loss-free reading

Final Summary

Single Buffer → Simple but causes overwriting when input > buffer size.
Double Buffer → Uses two buffers alternately so that one is filled while the other is
read — no data loss, smooth scanning, and very efficient.
Intermediate Code Generation (ICG)

(The Fourth Phase of the Compiler)

1. Definition and Role in Compiler Architecture

The Intermediate Code Generator (ICG) is the fourth phase of a compiler.

It serves as a bridge between the front end (analysis) and back end (synthesis) of the
compilation process.

Input and Output

• Input: Semantically verified syntax tree (from the Semantic Analyzer)

• Output: Intermediate Code (machine-independent representation)

Compiler Structure Overview

Part Phases Included Dependency

Front Lexical Analyzer, Syntax Analyzer, Semantic Analyzer, Machine-

End Intermediate Code Generator Independent

Back Machine-
Code Optimizer, Code Generator
End Dependent

Thus, the output of the front end (Intermediate Code) becomes the input to the back
end.

2. Purpose and Necessity of Intermediate Code

The Intermediate Code Generation phase exists mainly to achieve:

1. Machine Independence (Retargeting)

2. Ease of Code Optimization

🅐 Machine Independence (Retargeting)

• The front end of the compiler (up to ICG) is machine-independent, meaning it

does not rely on any specific hardware or OS.

• The back end is machine-dependent because it must generate code for a

particular CPU or system.
 • The ICG converts high-level source code into a machine-independent
intermediate representation (IR).

• Once the IR is available, the same front end can be reused for multiple target
machines.
Only the back end (optimizer and code generator) needs adjustment.

Example:
If a C compiler works on Windows, the same front end can be reused for Linux or
Android — only the code generator (back end) must change.

Result:
This property is called retargeting — the ability to reuse the same compiler front end for
multiple platforms.

🅑 Enabling Optimization

• The Intermediate Code makes it easier to apply machine-independent

optimization techniques before generating final code.

• Optimizations such as constant folding, dead code elimination, and strength

reduction are simpler at this stage.

• Using a structured format like Three-Address Code (TAC) allows easy

manipulation during optimization.

Result:
Optimized intermediate code leads to faster and smaller target code.

3. Types of Intermediate Code Representations

Intermediate code can be represented in four main forms, classified into two
categories:

Category Representations

Linear Form Postfix (Reverse Polish) Notation, Three-Address Code (TAC)

Tree Form Syntax Tree, DAG (Directed Acyclic Graph)

Among all, Three-Address Code (TAC) is the most widely used, as it provides the best
balance between readability, optimization, and code generation.
 4. Detailed Overview of Each Representation

1. Three-Address Code (TAC)

Definition:
A sequence of simple instructions, each having at most three addresses:

x = y op z

where x = result, y and z = operands, and op = operator.

If an expression contains more than three addresses, it’s broken down using
temporary variables.

Example:
Expression: a = b + c * d

TAC form:

t1 = c * d

t2 = b + t1

a = t2

Features:

• Each statement has ≤ 3 operands.

• Uses temporary variables (t1, t2, …) for intermediate results.

• Simplifies later phases like optimization and code generation.

2. Postfix Notation (Reverse Polish Notation)

Definition:
An expression form where operators come after operands — no parentheses are
needed.

Example:
a + b * c → Postfix: a b c * +

Advantages:

• No need for operator precedence or associativity rules.

• Easy to evaluate using a stack (used in interpreters or calculators).

 3. Syntax Tree

Definition:
A tree representation where:

• Leaf nodes represent operands (variables or constants).

• Internal nodes represent operators.

Example for a + b * c:

(+)

/ \

(a) (*)

/ \

(b) (c)

Usage:

• Directly used in semantic analysis and as the basis for generating TAC.

4. Directed Acyclic Graph (DAG)

Definition:
A DAG is an optimized version of a syntax tree that eliminates duplicate
subexpressions.

Purpose:
To save memory and computation time by reusing previously computed results.

Example:

Expression:

t1 = a + b

t2 = a + b

t3 = t1 + c

In a DAG, both t1 and t2 share the same (a + b) node instead of creating two separate
ones.

5. Role of ICG in Compiler Flow

Phase Input Output

Lexical Analyzer Source Code Tokens

Syntax Analyzer Tokens Parse Tree

Semantic Analyzer Parse Tree Annotated (Verified) Tree

Intermediate Code Generator Annotated Tree Intermediate Code (IR)

Code Optimizer Intermediate Code Optimized Intermediate Code

Code Generator Optimized Code Target Machine Code

6. Summary — Why Intermediate Code Generation Matters

Purpose Explanation

Connects machine-independent analysis phases to machine-

Acts as a bridge
dependent synthesis phases

Improves portability Same front end can be reused for multiple platforms

Supports
Easier to apply transformations on intermediate form
optimization

Simplifies code
Structured and standardized form for backend phases
generation

7. Metaphor (Simple Understanding)

Think of ICG as a universal blueprint designer:

When you design a building (program), you don’t create unique blueprints for each type
of land (Windows, Linux, Android).
Instead, you create one universal blueprint (Intermediate Code) that fits everywhere.
Later, each construction crew (Back End for each platform) adjusts it slightly to fit their
land.

Result:
One common front end for all systems, only the final stage (Back End) changes.

In Short
The Intermediate Code Generator is the fourth compiler phase that translates the
semantically verified parse tree into a machine-independent intermediate
representation (like Three-Address Code).
It enables portability, optimization, and simplifies code generation, forming the
bridge between the compiler’s front end and back end.

Bh