Compiler Design (MCA554) Unit 1: Introduction to Compilers & Lexical Analysis

-

Unit 1: Introduction to Compilers & Lexical Analysis

From your MCA Semester III syllabus. 

---


What is a Compiler?

A Compiler is a software that translates a program written in a high-level language into machine language.

Example:

printf("Hello");

Compiler converts it into machine code that the computer understands.

---

Language Translators

1. Compiler

Converts the entire program at once.

Source Program

      ↓

   Compiler

      ↓

Object Code

Advantages:

Faster execution

Errors shown after compilation

Examples:

C

C++

Go

---

2. Interpreter

Translates line by line.

Source Program

      ↓

 Interpreter

      ↓

 Execute Line by Line


Advantages:

Easy debugging

Disadvantages:

Slower execution

Examples:

Python

JavaScript

---

3. Assembler

Converts Assembly Language to Machine Language.

Assembly Code

      ↓

   Assembler

      ↓

Machine Code

---


Difference Between Compiler and Interpreter

Compiler Interpreter

Entire program compiled Line by line

Faster execution Slower

Generates object code No object code

Errors after compilation Errors immediately

---

Structure of a Compiler

A compiler consists of several phases.

Source Program

      ↓

Lexical Analysis

      ↓

Syntax Analysis

      ↓

Semantic Analysis

      ↓

Intermediate Code Generation

      ↓

Code Optimization

      ↓

Code Generation

      ↓

Target Program

---


Phases of Compiler

1. Lexical Analysis

First phase.

Tasks:

Read source code

Remove spaces/comments

Generate tokens

Example:

int a=10;

Tokens:

int

a=10;

---

2. Syntax Analysis

Checks grammatical correctness.

Uses:

Parse Trees

Context Free Grammar

Example:

a = + 5

Syntax Error

---

3. Semantic Analysis

Checks meaning.

Example:

int x;

x = "Hello";

Semantic Error

---

4. Intermediate Code Generation

Creates intermediate representation.

Example:

a = b + c

becomes

t1 = b + c

a = t1

---

5. Code Optimization

Improves efficiency.

Example:

a = 5 + 3

Optimized to:

a = 8

---


6. Code Generation

Produces machine code.

---


Front End and Back End of Compiler

Front End

Handles:

Lexical Analysis

Syntax Analysis

Semantic Analysis

Purpose:

Understand source code

---


Back End

Handles:

Optimization

Code Generation

Purpose:

Produce efficient machine code

-----

Linker

Combines object files.

Example:

main.obj

math.obj

file.obj

    ↓

  Linker

    ↓

program.exe

---


Loader

Loads executable program into memory.

Program.exe

     ↓

   Loader

     ↓

 Memory

---

Types of Compiler

Single Pass Compiler

Only one scan.

Advantage:

Fast

---

Multi Pass Compiler

Multiple scans.

Advantage:

Better optimization

---

Cross Compiler

Runs on one machine but generates code for another.

Example:

Windows → ARM Processor

---

Lexical Analyzer

Also called:

Scanner

First phase of compiler.


Responsibilities:

Read characters

Form tokens

Remove comments

Ignore spaces

---

Token

Smallest meaningful unit.

Example:

int age=20;

Tokens:

int age = 20;

---


Lexeme

Actual sequence of characters.

Example:

count

Here:

Lexeme = count

---

Pattern

Rule describing a token.

Example:

[a-zA-Z][a-zA-Z0-9]*

Represents identifiers.


---

Recognition of Tokens

Lexical Analyzer identifies:

Keywords

Identifiers

Operators

Constants

Delimiters

---


Examples

Keywords

int

float

while

if

return

---

Identifiers

count

salary

marks

---

Operators

+

-

*

/

=

---

Delimiters

;

,

()

{}


---

Input Buffering

Improves reading efficiency.

Without buffering:

Character by character reading

With buffering:

Reads blocks of data

Benefits:

Faster compilation

---

Issues in Lexical Analysis

1. Removing comments

2. Handling white spaces

3. Detecting invalid tokens

4. Efficient scanning


---

Lexical Analyzer Generator

Tool used to generate lexical analyzers automatically.

Example:

LEX

Input:

Token Rules

Output:

Lexical Analyzer Program

---

Important Exam Questions

Short Questions

1. Define Compiler.

2. Define Token.

3. Define Lexeme.

4. What is a Loader?

5. What is a Linker?

6. What is Input Buffering?

7. What is Lexical Analysis?

8. What is LEX?

---------------

Long Questions

1. Explain structure and phases of a compiler.

2. Differentiate Compiler and Interpreter.

3. Explain Lexical Analysis with examples.

4. Explain Front End and Back End of Compiler.

5. Discuss Tokens, Lexemes and Patterns.

6. Explain Linker and Loader.

--------------

Quick Revision

Compiler = High-level → Machine code.

Interpreter = Line-by-line translation.

Assembler = Assembly → Machine code.

Lexical Analysis = First phase.

Token = Smallest meaningful unit.

Lexeme = Actual text.

Pattern = Rule for token.

Linker = Combines object files.

Loader = Loads program into memory.

LEX = Lexical analyzer generator.



Comments

Post a Comment

Popular posts from this blog

Raster scan Vs Vector Scan

-
1. Raster Scan Display   How It Works : A raster scan display works by painting an image on the screen pixel by pixel, row by row. It follows a systematic pattern where the electron beam (in CRT monitors ) or the display elements (in modern LCD/LED screens ) sweep across the screen from left to right, top to bottom, in a series of horizontal lines ( scan lines ). This process is akin to how a traditional TV screen works.   Process : The display draws the image starting from the top-left corner, moving to the right, then moves to the next row below, and repeats this process until the entire screen is filled. This pattern creates a grid of pixels, where each pixel can have a color and brightness level.   Characteristics : Pixel-based : The screen consists of a grid of pixels, and each pixel can have a distinct color and intensity. Continuous Image : Raster scan displays are capable of displaying detailed and complex images, including photographs and videos, because they br...
Read more

MCA SYLLABUS ALLAHABAD UNIVERSITY 2025

-
 PAPER 1: PROGRAMMING IN ‘C’ WITH DATA STRUCTURES (MCA540)  Unit 1 : Algorithm development and C language Programming: Structure and properties of algorithm,   Flowchart, Introduction to C, Compilation & execution of C programs, , Data types & sizes, Declaration of variables, Modifiers, Identifiers & keywords, Symbolic constants, Operators: Unary operators, Arithmetic & Logical operators, Bit-wise operators, Assignment operators and expressions, Conditional expressions, Precedence & associativity, order of evaluation. Control statements: If-else, Switch, Break, Continue, Go-to statement; Loops: For, While, Do-while.  Unit 2: Functions and Arrays: Functions: Built-in & User-defined, Function declaration, Definition &function call, Parameter passing: Call by value, Call by reference, Recursive functions. Linear arrays, Multi-dimensional arrays, passing arrays to functions, Arrays & Strings; Storage classes: Automatic, External, Regi...
Read more

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 1 – INTRODUCTION & SORTING TECHNIQUES ) university of allahabad

-
cx  📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS 🔴 UNIT 1 – INTRODUCTION & SORTING TECHNIQUES 1️⃣ Introduction to Algorithms ✅ What is an Algorithm? An algorithm is a finite set of well-defined steps used to solve a problem. ✅ Characteristics of Algorithm ✔ Input ✔ Output ✔ Finiteness ✔ Definiteness ✔ Effectiveness 2️⃣ Analysis of Algorithms Algorithm analysis means measuring performance in terms of: 🔹 Time Complexity Time taken by an algorithm to run. 🔹 Space Complexity Memory used by the algorithm. 3️⃣ Growth of Functions Used to compare algorithm efficiency. Common Growth Rates: Notation Name O(1) Constant O(log n) Logarithmic O(n) Linear O(n log n) Linear-log O(n²) Quadratic O(2ⁿ) Exponential 4️⃣ Asymptotic Notations 🔹 Big-O Notation – Worst Case O (n) 🔹 Omega (Ω) – Best Case Ω(n) 🔹 Theta (Θ) – Average Case Θ(n) 5️⃣ Recurrence Relations A recurrence relation defines a function in terms of itself. Example: T ( n ) = T ( n / ...
Read more