SYSTEM PROGRAMMING

Complete Study Notes

Q1. Intermediate Code Representation

Q2. Dynamic Linking Loader

Q3. Pass-I of Two Pass Assembler

Q4. Design of Two Pass Assembler

Q5. Single Pass Macro Processor

Q6. Forward Reference Problem & TII

Q7. Code Optimization Techniques

Q8. Absolute Loader

Q9. Types of Assembler Statements

Q10. Direct Linking Loader

Q11. Phases of Compiler

Q12. Relocation and Linking in Loaders

Q13. Three Address Code (TAC)

Q14. Features of Macro

Q15. Issues in Code Generation

Q16. Context Free Grammar (CFG)

Q17. System Programming & System Programs

 What are the different ways of Intermediate Code
Q1.
Representation? Explain with example.

Intermediate Code Representation

Intermediate Code (IC) is a machine-independent code generated by the compiler after source code
analysis and before target machine code generation. It helps in optimization and makes compiler design
easier.

The commonly used intermediate code representations are:

• Syntax Tree
• Directed Acyclic Graph (DAG)
• Postfix Notation
• Three Address Code (TAC)

1) Syntax Tree
A Syntax Tree is a hierarchical tree structure in which:
• Leaf nodes contain operands (variables/constants)
• Internal nodes contain operators
It represents the grammatical structure of an expression.
Example — Expression: a + b * c
+ / \ a * / \ b c

Explanation: Multiplication is performed first because * has higher precedence, then addition is
performed.
Advantages:
• Easy to understand expression hierarchy
• Useful in semantic analysis

2) Directed Acyclic Graph (DAG)

DAG is similar to a syntax tree but avoids repeated computation by sharing common subexpressions.
Example — Expression: (a+b) + (a+b) * c
+ / \ (a+b) * / \ (a+b) c

Here, (a+b) is stored once and reused.

Explanation:
• Reduces repeated calculations
• Helps in code optimization
Advantages:
• Saves memory and execution time
• Detects common subexpressions

3) Postfix Notation
In postfix notation, operators are written after operands.
Example — Expression: a + b * c
Postfix Form: abc*+
Explanation:
• b*c becomes bc*
 • Then a + (bc*) becomes abc*+
Advantages:
• No need for parentheses
• Easy stack implementation

4) Three Address Code (TAC)

Three Address Code uses instructions having at most three addresses. General form: x = y op z
Example — Expression: a + b * c
t1 = b * c t2 = a + t1

Explanation:
• Temporary variables are used
• Complex expressions are broken into simpler statements
Advantages:
• Easy optimization
• Easy target code generation

Conclusion: Intermediate code representation provides a machine-independent way to represent

programs. Different representations like Syntax Tree, DAG, Postfix Notation, and Three Address Code
help the compiler perform optimization and efficient target code generation.

"Tree Graph Post Three" — Tree=Syntax Tree, Graph=DAG,

■ Memory Trick (English) Post=Postfix, Three=Three Address Code. Remember: Tree →
Graph → Post → Three

"Tree, Graph, Post, Teen" — Tree=Syntax Tree, Graph=DAG,

■ Memory Trick (Hindi) Post=Postfix, Teen=Three Address Code. Yaad rakh: Ped → Graph
→ Post → Teen Address
 Q2. Explain Dynamic Linking Loader in details.

Dynamic Linking Loader

Dynamic Linking Loader is a loading scheme in which linking of library functions is performed during
program execution instead of during compilation. In this method, the required library routines are loaded
into memory only when they are needed at run time. This technique is commonly used in modern
operating systems for shared libraries such as .dll files in Windows and .so files in Linux.

Definition
Dynamic Linking is a process in which external library routines are linked to the program at execution time
by the loader. The loader checks whether the required library routine is already present in memory. If
present, it uses the existing copy; otherwise, it loads the required routine dynamically.

Working of Dynamic Linking Loader

Step 1: Compilation: Source program is compiled. Calls to library functions are not fully linked. Only
reference information is stored.
Step 2: Program Execution: Program starts execution. When a library function is called, control goes to
the dynamic linker.
Step 3: Searching Library: Loader checks whether the required library routine is already loaded in
memory.
Step 4: Loading: If not available, the loader loads the required routine from disk into memory.
Step 5: Linking: Address of the routine is linked dynamically. Execution continues normally.

Diagram of Dynamic Linking:

Source Program → Compiler → Object Module → Dynamic Linking Loader → Shared Library
Loaded at Run Time → Execution

Example: Suppose a C program uses the function printf("Hello"). In dynamic linking, printf() is not
permanently copied into the executable file. During execution, the loader loads the required library routine
from the shared C library.

Advantages of Dynamic Linking Loader

• Saves Memory — Only one copy of shared library is kept in memory.
• Reduces Executable Size — Library code is not permanently included in executable file.
• Easy Library Update — Updating shared library automatically affects all programs using it.
• Faster Loading — Only required modules are loaded.
• Better Memory Utilization — Unused library routines are not loaded.

Disadvantages of Dynamic Linking Loader

• Slower Execution Initially — Program may pause while loading required libraries.
• Dependency Problem — Program may fail if required shared library is missing.
• Complex Implementation — Dynamic linking mechanism is more complicated.
• Version Compatibility Issues — Different versions of shared libraries may create errors.

Applications
Dynamic linking is used in: Operating Systems, Shared Libraries, Modern Compilers, GUI Applications,
Web Browsers. Examples: Windows DLL files, Linux Shared Object (.so) files.
Difference Between Static and Dynamic Linking

Static Linking Dynamic Linking

Linking done before execution Linking done during execution

Large executable size Smaller executable size

Separate copy for each program Shared library used

Faster execution Slightly slower initially

More memory usage Less memory usage

Conclusion: Dynamic Linking Loader improves memory utilization and reduces executable size by linking
library routines at run time. It is widely used in modern operating systems because it supports code
sharing, flexibility, and efficient memory management.

"Load Library Later" — Load=Loader, Library=Shared routines,

■ Memory Trick (English) Later=At run time. Meaning: Dynamic Linking = Libraries loaded later
during execution.

"Library Baad Mein Load Hoti Hai" — Compile ke time nahi, Run ke
■ Memory Trick (Hindi)
time library load hoti hai.
 Explain the flowchart of Pass-I of Two Pass Assembler.
Q3.
Explain its working with the database.

Pass-I of Two Pass Assembler

A Two Pass Assembler works in two phases: Pass-I and Pass-II. Pass-I mainly performs address
assignment and creates different tables required for Pass-II.

Definition
Pass-I of a two pass assembler scans the source program and: assigns addresses to statements, defines
symbols and literals, creates tables like SYMTAB, LITTAB, POOLTAB, and generates Intermediate Code
(IC). It does not generate machine code directly.

Flowchart of Pass-I
START ↓ Initialize LC = 0 ↓ Read next source statement ↓ Is opcode START directive?
Yes → Set LC value No → Continue ↓ Is label present? Yes → Add label in SYMTAB No →
Continue ↓ Is opcode Imperative Statement? Yes → Generate IC No → Check directives ↓
Is literal present? → Add literal to LITTAB ↓ Update LC ↓ Is LTORG or END? Yes →
Assign addresses to literals, Update POOLTAB ↓ More statements? Yes → Repeat No →
END

Working of Pass-I
Step 1: Initialize
Assembler starts execution. Location Counter (LC) is initialized. Tables are created empty: SYMTAB,
LITTAB, POOLTAB.
LC = 0 If START statement exists: START 200 → LC = 200

Step 2: Read Source Statement

Assembler reads one statement at a time from source program. Example: MOVER AREG, ='5'
Step 3: Process Label
If label exists, it is entered into SYMTAB with current LC.
LOOP MOVER AREG, ='5' SYMTAB: Symbol Address LOOP 200

Step 4: Process Opcode

Assembler checks type of instruction — Imperative Statement (IS), Declarative Statement (DL), or
Assembler Directive (AD). Assembler generates Intermediate Code.
Step 5: Process Symbols and Literals
Symbols (variables/labels) are stored in SYMTAB. Literals like ='5' are stored in LITTAB (address
assigned later).
SYMTAB: Symbol Address ONE 205 LITTAB: Literal Address ='5' -

Step 6: Process LTORG or END

When assembler finds LTORG or END, addresses are assigned to literals and POOLTAB is updated.
LITTAB after assignment: Literal Address ='5' 210 ='1' 211 POOLTAB: Pool No Starting
Literal 1 1

Step 7: Update LC
After every instruction, LC increases according to instruction length. Example: MOVER AREG, ='5' with
length 1 → LC = LC + 1
Databases/Tables Used in Pass-I
1) SYMTAB (Symbol Table) — Stores symbols and their addresses.

Symbol Address

LOOP 200

ONE 205

2) LITTAB (Literal Table) — Stores literals and addresses.

Literal Address

='5' 210

3) POOLTAB (Pool Table) — Stores starting index of literal pools.

Pool Index

1 1

4) Intermediate Code (IC) — Machine-independent representation generated in Pass-I. Example: (IS,04)

(1) (L,1)

Example of Pass-I Working

Source Program:
START 200 MOVER AREG, ='5' ADD BREG, ONE ONE DC 1 END

Step-by-Step Working:
• START 200 → LC = 200
• MOVER AREG, ='5' → Literal added to LITTAB, IC generated, LC incremented
• ADD BREG, ONE → Symbol ONE referenced, added in SYMTAB
• ONE DC 1 → Address assigned to ONE
• END → Literal address assigned, POOLTAB updated
Final Tables:

SYMTAB Symbol Address LITTAB Literal Address

ONE 202 ='5' 203

Conclusion: Pass-I of two pass assembler mainly performs address assignment, table generation, and
intermediate code generation. It prepares all required information for Pass-II, where actual machine code
is generated.

"Initialize → Read → Store → Update → End" — Initialize LC, Read

■ Memory Trick (English)
statement, Store symbols/literals, Update LC, End and assign literals.

"Shuru karo → Padho → Table mein dalo → Address badhao → End

■ Memory Trick (Hindi)
karo" — Initialize → Read → Store → LC Increase → END
 Explain with Flowchart the Design of Two Pass
Q4.
Assembler.

Design of Two Pass Assembler with Flowchart

A Two Pass Assembler translates assembly language program into machine language using two separate
scans of the source program. The assembler works in Pass-I and Pass-II.

Definition
A Two Pass Assembler is an assembler that scans the source program two times: Pass-I creates tables
and assigns addresses; Pass-II generates actual machine code. It solves the problem of forward
references effectively.

Why Two Pass Assembler is Needed?

In assembly language, symbols may be used before their declaration. Example: JMP LOOP ... LOOP
MOVER AREG, B — Here the address of LOOP is not known initially. So Pass-I collects symbol
information and Pass-II uses that information to generate machine code.

Overall Design
Source Program ↓ [ Pass-I ] ↓ SYMTAB, LITTAB, POOLTAB ↓ Intermediate Code ↓ [ Pass-II
] ↓ Machine Code

Pass-I — Functions & Flowchart

Pass-I performs: Assign addresses, Create Symbol Table (SYMTAB), Create Literal Table (LITTAB),
Create Pool Table (POOLTAB), Generate Intermediate Code (IC). Pass-I does NOT generate machine
code.
START ↓ Initialize LC ↓ Read source statement ↓ Is START directive? Yes→Set LC
No→Continue ↓ Is label present? Yes→Add symbol to SYMTAB ↓ Process opcode ↓ Is
literal present? → Add to LITTAB ↓ Generate IC ↓ Update LC ↓ Is LTORG/END?
Yes→Assign literal addresses, Update POOLTAB ↓ More statements? Yes→Repeat No→STOP
Working of Pass-I:
• Step 1: Initialize — LC (Location Counter) initialized, Tables created empty. Example: LC = 0
• Step 2: Read Statement — Assembler reads statements one by one.
• Step 3: Process Labels — Labels are stored in SYMTAB with address.
• Step 4: Process Literals — Literals are stored in LITTAB. Example: ='5'
• Step 5: Generate Intermediate Code — Assembler creates machine-independent representation.
• Step 6: Update LC — LC increases after instruction processing.
• Step 7: Handle LTORG/END — Literal addresses assigned and POOLTAB updated.

Pass-II — Functions & Flowchart

Pass-II: Reads Intermediate Code, Uses SYMTAB and LITTAB, Generates actual machine code.
START ↓ Read Intermediate Code ↓ Read next IC statement ↓ Is Imperative Statement?
Yes→Obtain opcode value ↓ Get symbol/literal address ↓ Generate machine code ↓ Write
output ↓ More statements? Yes→Repeat No→STOP

Working of Pass-II:
• Step 1: Read IC — Intermediate code generated in Pass-I is read.
• Step 2: Refer Tables — Addresses obtained from SYMTAB and LITTAB.
 • Step 3: Generate Machine Code — Example: IC: (IS,04) (1) (L,1) → Machine Code: 04 1 203

Databases Used in Two Pass Assembler

Table Contents Example

SYMTAB Symbol names and addresses LOOP → 205

LITTAB Literals and addresses ='5' → 210

POOLTAB Literal pool information Pool 1, Index 1

Advantages
• Handles Forward References — Symbols can be used before declaration.
• Better Organization — Separate analysis and code generation.
• Easier Error Detection — Errors detected efficiently.
• Supports Large Programs — Suitable for complex assembly programs.

Disadvantages
• More Time — Program scanned twice.
• More Memory — Tables must be stored.

Conclusion: A Two Pass Assembler converts assembly language into machine code using two separate
passes. Pass-I creates tables and intermediate code, while Pass-II generates final machine code using
those tables.

"Pass-1 Collects, Pass-2 Converts" — Pass-I→Collect addresses

■ Memory Trick (English)
and tables; Pass-II→Convert into machine code.

"Pehla Pass Jama karta hai, Dusra Pass Machine Code banata hai"
■ Memory Trick (Hindi)
— Pass-1=Information collect; Pass-2=Machine code generate.
 Explain the working of Single Pass Macro Processor
Q5.
with neat flowchart.

Single Pass Macro Processor

A Single Pass Macro Processor processes the macro definition and macro expansion in only one scan of
the source program. It reads each statement once and immediately expands macros whenever macro
calls are encountered.

Definition
A Single Pass Macro Processor is a macro processor that performs macro definition processing and
macro expansion simultaneously in a single pass over the source program. Unlike two pass macro
processors, it does not scan the program twice.

Basic Concept
When the processor encounters MACRO → it stores macro definition. When it encounters a Macro call →
it immediately expands the macro. Thus, definition and expansion happen together.

Flowchart of Single Pass Macro Processor

START ↓ Initialize tables ↓ Read source statement ↓ Is statement MACRO? Yes → Store
macro definition in MNT and MDT No ↓ Read next statement ↓ Is it macro call? Yes →
Expand macro using MDT and ALA → Generate expanded code No ↓ Write statement/output ↓
More statements? Yes→Repeat No→STOP

Databases Used
Single Pass Macro Processor mainly uses: MNT (Macro Name Table), MDT (Macro Definition Table), ALA
(Argument List Array).
1) MNT (Macro Name Table) — Stores macro name and pointer to MDT entry.

Macro Name MDT Pointer

INCR 1

2) MDT (Macro Definition Table) — Stores macro body.

Index Definition

1 ADD AREG, ='1'

2 MEND

3) ALA (Argument List Array) — Stores actual arguments during macro expansion.

Parameter Argument

&ARG; DATA

Working of Single Pass Macro Processor

Step 1: Initialize Tables: Initially MNT empty, MDT empty, ALA empty.
Step 2: Read Source Program: Processor reads statements one by one. Example: MACRO INCR
&ARG; ADD &ARG;, ='1' MEND
Step 3: Process Macro Definition: When MACRO keyword is found: Macro name stored in MNT, Macro
body stored in MDT.
Step 4: Detect Macro Call: Example: INCR DATA — Processor searches macro name in MNT. If found,
macro expansion begins.
Step 5: Create ALA: Actual argument is mapped to formal parameter: &ARG; → DATA
Step 6: Expand Macro: Processor reads MDT entries and replaces parameters using ALA. Expanded
code: ADD DATA, ='1'
Step 7: Generate Output: Expanded statements are written into output program.

Complete Example
Input Program:
MACRO INCR &X ADD &X, ='1' MEND START INCR NUM END

ALA During Expansion:

Parameter Argument

&X; NUM

Expanded Output:
START ADD NUM, ='1' END

Advantages
• Faster Processing — Only one scan of source program.
• Less Compilation Time — Expansion occurs immediately.
• Efficient for Small Programs — Simple implementation for basic macros.

Disadvantages
• Forward Reference Problem — Macro must be defined before use.
• More Complex Control — Definition and expansion handled together.
• Limited Flexibility — Not suitable for very large macro systems.

Conclusion: Single Pass Macro Processor processes macro definitions and macro calls simultaneously in
one scan. It uses tables like MNT, MDT, and ALA for storing definitions and expanding macros efficiently.

"Define and Expand Together" — Define macro, Expand

■ Memory Trick (English)
immediately, All in one pass. Short flow: Read → Store → Expand

"Ek hi baar mein Define bhi aur Expand bhi" — Read karo → Macro
■ Memory Trick (Hindi)
save karo → Turant expand karo.
 Explain in brief Forward Reference Problem. How TII
Q6.
handles forward references in Single Pass Assembler.

Forward Reference Problem

A Forward Reference occurs when a symbol is used before it is defined in the program. In assembly
language, the assembler may encounter an instruction that refers to a label whose address is not yet
known.

Definition
Forward Reference is a situation in which a symbol or label is referenced before its actual declaration or
definition appears in the source program.

Example of Forward Reference

JMP LOOP ... LOOP MOVER AREG, B

Here LOOP is used in JMP LOOP but its address is defined later. So during first reading, the assembler
does not know the address of LOOP. This creates the Forward Reference Problem.

Why Forward Reference is a Problem?

When assembler generates machine code, it needs the exact address of symbols. But in forward
reference, the symbol address is unavailable at that time. Therefore, the machine instruction cannot be
completed immediately.

Problems in Single Pass Assembler

In a Single Pass Assembler, the source program is scanned only once, so the assembler cannot go back
easily. Forward references become difficult to handle because symbol definition appears later and address
is unknown during instruction generation.

How TII Handles Forward Reference Problem

TII (Table of Incomplete Instructions) is used to solve forward references in a Single Pass Assembler. It
stores information about instructions whose symbol addresses are not yet known. Later, when the symbol
definition is found, the assembler updates incomplete instructions.

Working of TII
Step 1: Encounter Undefined Symbol: Example: JMP LOOP — Assembler checks SYMTAB. LOOP not
found, address unknown.
Step 2: Create Symbol Entry: Assembler creates entry in SYMTAB with incomplete status. SYMTAB:
LOOP → ?
Step 3: Store Instruction in TII: Instruction location is stored in TII. TII: LOOP → Instruction Address 200
(Means instruction at address 200 needs LOOP address later.)
Step 4: Continue Assembly: Assembler continues processing remaining statements.
Step 5: Symbol Definition Found: Later: LOOP MOVER AREG, B — Now assembler knows actual
address of LOOP. Example: LOOP = 350. SYMTAB updated.
Step 6: Backpatching: Assembler checks TII — all incomplete instructions referring to LOOP are updated
with correct address. This process is called Backpatching.

Flowchart of TII Handling

 START ↓ Read source statement ↓ Is symbol defined? Yes → Generate instruction →
Continue assembly No → Create SYMTAB entry → Store info in TII → Continue assembly
↓ Symbol definition found? ↓ Update SYMTAB address ↓ Backpatch instructions ↓ END

Example
Source Program: JMP LOOP ADD AREG, B LOOP SUB AREG, C

Step 1: JMP LOOP — LOOP undefined. TII: LOOP → Address 100

Step 2: LOOP Defined — LOOP SUB AREG, C. Suppose LOOP = 300. Assembler updates previous JMP
instruction with address 300.

Advantages of TII
• Solves Forward References — Handles symbols defined later.
• Supports Single Pass Assembly — No need for second scan.
• Faster Assembly — Only one pass required.

Disadvantages
• Extra Memory Needed — TII must store incomplete instructions.
• Complex Backpatching — Requires updating previous instructions.

Conclusion: Forward Reference Problem occurs when symbols are used before definition. In Single Pass
Assembler, TII handles this problem by storing incomplete instruction information and later updating
addresses through backpatching.

"Unknown Now, Update Later" — Symbol unknown initially, Store

■ Memory Trick (English) instruction in TII, Update later after definition. Short sequence: Store
→ Wait → Update

"Abhi address nahi pata, baad mein update karo" — Unknown

■ Memory Trick (Hindi)
symbol → TII mein store → Later update.
 Explain different Code Optimization Techniques in
Q7.
details.

Code Optimization Techniques

Code Optimization is a compiler technique used to improve the intermediate or target code so that
execution becomes faster, memory usage reduces, and overall program efficiency increases. Optimization
does not change the output of the program — it only improves performance.

Definition
Code Optimization is the process of modifying a program to produce optimized code that executes more
efficiently while preserving the original meaning of the program.

Objectives of Code Optimization

• Reduce execution time
• Reduce memory usage
• Reduce number of instructions
• Improve CPU utilization
• Improve program efficiency

1) Constant Folding
Constant expressions are calculated during compilation itself.
Before: x = 10 * 5; After: x = 50;

Explanation: Compiler directly computes the result instead of calculating at run time.
Advantages:
• Reduces execution time
• Reduces instructions

2) Constant Propagation
The compiler replaces variables having constant values directly into expressions.
Before: a = 10; b = a + 5; After: b = 10 + 5; → b = 15;

Advantages:
• Simplifies expressions
• Improves optimization opportunities

3) Common Subexpression Elimination

Repeated expressions are computed only once.
Before: x = a + b; y = a + b; After: t = a + b; x = t; y = t;

Explanation: The expression a+b is evaluated once and reused.

Advantages:
• Reduces repeated computation
• Saves CPU time

4) Dead Code Elimination

Unreachable or unused code is removed.
Before: x = 5; x = 10; print(x); After: x = 10; print(x);
Explanation: x = 5 is never used, so it is removed.
Advantages:
• Reduces program size
• Improves execution speed

5) Copy Propagation
Variable copies are replaced by original values.
Before: x = y; z = x + 1; After: z = y + 1;

Advantages:
• Reduces unnecessary assignments
• Simplifies code

6) Loop Optimization
Optimization techniques applied inside loops because loops execute repeatedly. Types: Loop Unrolling,
Loop Fusion, Loop Invariant Code Motion.
Before: for(i=0;i<100;i++) sum = sum + 2; Compiler may reduce repeated calculations.

Advantages:
• Faster loop execution
• Better CPU performance

7) Strength Reduction
Expensive operations are replaced with cheaper operations.
Before: x = y * 2; After: x = y << 1;

Explanation: Bit shifting is faster than multiplication.

Advantages:
• Reduces execution cost
• Improves speed

8) Code Motion
Statements that produce the same result inside loops are moved outside the loop.
Before: for(i=0;i<n;i++) { x = a*b; y[i] = x+i; } After: x = a*b; for(i=0;i<n;i++) {
y[i] = x+i; }

Advantages:
• Avoids repeated computation
• Improves loop efficiency

9) Peephole Optimization
Small sets of instructions are examined and replaced with efficient instruction sequences.
Before: MUL R1,2 After: SHIFT LEFT R1,1

Advantages:
• Reduces instruction count
• Produces efficient machine code

Classification of Optimization

Type Description

Machine Independent Optimization without considering hardware

 Type Description

Machine Dependent Optimization based on target machine

Advantages of Code Optimization

• Faster Execution — Program runs efficiently.
• Reduced Memory Usage — Less storage required.
• Better Resource Utilization — Efficient CPU and memory usage.
• Reduced Program Size — Fewer instructions generated.

Disadvantages
• Increased Compilation Time — Compiler needs extra analysis.
• Complex Compiler Design — Optimization algorithms are difficult.

Conclusion: Code optimization techniques improve the efficiency of compiled programs by reducing
unnecessary computations, minimizing memory usage, and generating faster executable code without
changing program output.

"Fold Propagate Common Dead Copy Loop Strong Motion Peep" —

■ Memory Trick (English) Fold→Propagate→Common→Dead→Copy→Loop→Strength→Moti
on→Peephole

"Fold karo, Propagate karo, Common hatao, Dead hatao" —

■ Memory Trick (Hindi)
Compiler faltu kaam hata kar fast code banata hai.
 Explain Absolute Loader. State its advantages and
Q8.
disadvantages.

Absolute Loader
An Absolute Loader is the simplest type of loader in which the object program is loaded into the memory at
a fixed or absolute address generated by the assembler or compiler. The loader does not perform
relocation or linking. It simply loads the program into specified memory locations and starts execution.

Definition
An Absolute Loader is a loader that loads object code into the exact memory addresses specified in the
object program and transfers control to the execution address.

Working of Absolute Loader

Step 1: Read Object Program: Loader reads the object program generated by assembler/compiler.
Example: Address Instruction 200 MOV AREG,B 201 ADD AREG,C
Step 2: Allocate Memory: Instructions are loaded into the same memory addresses mentioned in the
object program. Memory[200] = MOV AREG,B Memory[201] = ADD AREG,C
Step 3: Transfer Control: After loading all instructions, control is transferred to starting execution
address. Example: Execution starts from address 200

Flowchart of Absolute Loader

START ↓ Read object program ↓ Read address and code ↓ Load into memory at specified
address ↓ More records present? Yes → Repeat No → Transfer control → END

Example
H^PROG^200^20 T^200^MOV AREG,B T^201^ADD AREG,C E^200

Program starts at address 200, instructions loaded exactly at given addresses, execution begins from
address 200.

Features of Absolute Loader

• Simple loader
• No relocation
• No linking
• Uses fixed addresses
• Faster loading process

Advantages of Absolute Loader

• Simple Design — Easy to understand and implement.
• Faster Loading — No relocation or address modification required.
• Less Memory Requirement — No extra tables needed.
• Low Overhead — Minimal processing during loading.

Disadvantages of Absolute Loader

• No Relocation — Program cannot be loaded at different memory locations.
• Difficult Memory Management — Program must always use fixed addresses.
• No Linking Support — Cannot combine multiple modules easily.
• Poor Flexibility — Any address change requires recompilation.
 • Not Suitable for Multiprogramming — Modern systems require dynamic memory allocation.

Applications
Absolute loaders are mainly used in small systems, simple embedded systems, and for educational
purposes. They are rarely used in modern operating systems.

Difference Between Absolute Loader and Relocating Loader

Absolute Loader Relocating Loader

Uses fixed address Can load anywhere

No relocation Performs relocation

Simple More complex

Faster loading Slightly slower

Less flexible More flexible

Conclusion: Absolute Loader is the simplest loader that loads programs into fixed memory locations
without relocation or linking. It provides fast and simple loading but lacks flexibility and is not suitable for
modern memory management systems.

"Load Exactly Where Given" — Loader places code exactly at

■ Memory Trick (English)
specified address. Fixed Address = Absolute Loader.

"Jaha address diya hai wahi load karo" — Fixed memory address par
■ Memory Trick (Hindi)
direct loading.
 Explain different types of statements used in
Q9. Assemblers with respect to System Programming with
example.

Types of Statements Used in Assembler

In System Programming, an assembly language program contains different types of statements that help
the assembler understand operations, data declaration, and control information. Assembler statements are
mainly classified into: Imperative Statements (IS), Declarative Statements (DL), and Assembler Directives
(AD).

1) Imperative Statements (IS)

Imperative Statements are executable statements that specify actual machine operations to be performed
by the CPU. These statements generate machine instructions.
Examples:
MOVER AREG, B ADD BREG, C SUB AREG, D STOP

Explanation:
• MOVER → moves data
• ADD → performs addition
• SUB → performs subtraction
• STOP → terminates program
Features:
• Executable instructions
• Generate machine code
• Require opcode and operands

Statement Meaning

MOVER AREG, B Move data into register

ADD AREG, C Add value

STOP Stop execution

2) Declarative Statements (DL)

Declarative Statements are used to declare variables or constants in memory. They reserve storage
locations. These statements generally do not perform operations directly.
Types of Declarative Statements:
a) DC (Define Constant) — Used to store constant value. Example: NUM DC 5 → Store constant value 5.
b) DS (Define Storage) — Used to reserve memory space. Example: ARR DS 10 → Reserve 10 memory
locations.
Features:
• Used for memory allocation
• Define variables/constants
• Help in storage management
 Statement Meaning

X DC 1 Store constant 1

Y DS 5 Reserve 5 locations

3) Assembler Directives (AD)

Assembler Directives are instructions given to the assembler itself. They control the assembly process and
do not generate machine code.
START — Specifies starting address of program. Example: START 200 → Program starts from address
200.
END — Indicates end of source program. Example: END
ORIGIN — Changes value of Location Counter (LC). Example: ORIGIN 500
EQU — Assigns value to symbol. Example: A EQU 5
LTORG — Assigns addresses to literals. Example: LTORG
Features of Assembler Directives:
• Do not generate machine instructions
• Control assembler operations
• Manage addresses and symbols

Classification Summary

Machine Code
Type Purpose
Generated

Imperative Statement Perform operations Yes

Declarative Statement Declare storage/constants Partially

Assembler Directive Guide assembler No

Complete Example
START 200 MOVER AREG, ='5' ADD AREG, NUM NUM DC 1 END

Statement Type

START 200 Assembler Directive

MOVER AREG, ='5' Imperative Statement

ADD AREG, NUM Imperative Statement

NUM DC 1 Declarative Statement

END Assembler Directive

Conclusion: Assembly language programs use Imperative Statements for execution, Declarative
Statements for memory allocation, and Assembler Directives for controlling the assembly process. These
statement types help the assembler generate efficient machine code systematically.
 "Do, Declare, Direct" — Do=Imperative Statements perform
■ Memory Trick (English) operations; Declare=Declarative Statements reserve memory;
Direct=Assembler Directives guide assembler.

"Kaam karo, Memory banao, Assembler ko guide karo" —

■ Memory Trick (Hindi) Imperative=kaam karta hai; Declarative=memory banata hai;
Directive=assembler ko control karta hai.
 Q10. Explain Direct Linking Loader in details.

Direct Linking Loader (DLL)

Direct Linking Loader is a loader that performs loading, relocation, and linking of multiple program modules
directly during program execution. It allows separately compiled program modules to be linked together
and loaded into memory.

Definition
A Direct Linking Loader is a loader that links external symbols, relocates addresses, and loads object
programs directly into memory for execution. It is also called Linking Loader because it performs linking
during loading.

Need of Direct Linking Loader

Large programs are usually divided into multiple modules (Module A, Module B, Module C). These
modules may refer to symbols defined in other modules. A Direct Linking Loader combines all modules,
resolves external references, and loads them into memory.

Functions of Direct Linking Loader

A Direct Linking Loader performs three major functions:
• Allocation — Assigns memory locations to different program modules. Example: Module A → 200,
Module B → 400
• Linking — Links external symbols between modules. Example: Module A calls symbol X from
Module B; Loader finds address of X and updates instruction.
• Relocation — Adjusts addresses according to actual memory allocation. If module originally
designed for address 100 but loaded at 300, addresses are modified accordingly.

Structure / Diagram
Object Module 1 ↓ Object Module 2 ↓ Object Module 3 ↓ Direct Linking Loader ↓ Linking
+ Relocation ↓ Loaded Program in Memory ↓ Execution

Flowchart of Direct Linking Loader

START ↓ Read object modules ↓ Allocate memory space ↓ Build External Symbol Table
(ESTAB) ↓ Resolve external references ↓ Perform relocation ↓ Load program into memory
↓ Transfer control to program ↓ END

ESTAB (External Symbol Table)

Direct Linking Loader uses ESTAB to store external symbols, addresses, and control section information.

Symbol Address

ALPHA 200

BETA 450

Working — Two Passes

Pass 1 — Functions:
• Assign addresses to control sections
• Build ESTAB
Example: Module A defines ALPHA. Loader stores ALPHA → 200 in ESTAB.
Pass 2 — Functions:
• Resolve external references
• Perform relocation
• Load instructions into memory
Example: If Module B references ALPHA → MOV AREG, ALPHA. Loader replaces ALPHA with actual
address: MOV AREG, 200

Advantages of Direct Linking Loader

• Supports Multiple Modules — Large programs can be divided into modules.
• Allows Separate Compilation — Each module compiled independently.
• Efficient Memory Utilization — Programs loaded dynamically.
• Supports Relocation — Programs can load anywhere in memory.
• Easier Program Maintenance — Modules can be modified independently.

Disadvantages
• Complex Design — Linking and relocation increase complexity.
• More Loading Time — Additional processing required.
• Extra Memory Needed — ESTAB and relocation information must be stored.

Difference: Absolute Loader vs Direct Linking Loader

Absolute Loader Direct Linking Loader

No linking Performs linking

No relocation Supports relocation

Fixed address loading Flexible loading

Simple Complex

Single module Multiple modules

Conclusion: Direct Linking Loader is an advanced loader that performs loading, linking, and relocation
together. It supports modular programming, external references, and flexible memory allocation, making it
suitable for modern systems.

"Allocate, Link, Relocate, Load" — This is the complete DLL working

■ Memory Trick (English)
sequence.

"Jagah do, Symbols jodo, Address badlo, Program load karo" —

■ Memory Trick (Hindi) Allocate memory → Link symbols → Relocate addresses → Load
program.
 Explain the different phases of a Compiler with
Q11.
suitable example.

Phases of Compiler
A Compiler converts a high-level language program into machine language program through several steps
called phases of compiler. Each phase performs a specific task and passes output to the next phase.

Definition
Compiler phases are the different stages through which a source program passes during compilation to
generate machine code.

Diagram of Compiler Phases

Source Program → Lexical Analysis → Syntax Analysis → Semantic Analysis →
Intermediate Code Generation → Code Optimization → Target Code Generation → Machine
Code Additional: Symbol Table Management + Error Handling (used throughout all
phases)

Consider the statement: a = b + c * d; — We will see how each compiler phase processes this statement.

1) Lexical Analysis (Scanner)

Lexical Analysis is the first phase of compiler. It reads source code character by character and converts it
into tokens.
Functions:
• Removes spaces/comments
• Identifies keywords, identifiers, operators
• Generates tokens
• Creates symbol table entries
Example:
Input: a = b + c * d; Output Tokens: Lexeme → Token a → Identifier = → Assignment
Operator b → Identifier + → Arithmetic Operator c → Identifier * → Arithmetic
Operator d → Identifier Final: (id,1) (=) (id,2) (+) (id,3) (*) (id,4)

Output: A valid token stream is generated.

2) Syntax Analysis (Parser)

Syntax Analysis checks whether the program follows grammar rules of the language. It builds Parse Tree
or Syntax Tree.
Functions:
• Checks syntax errors
• Verifies grammatical structure
• Creates parse tree
Example:
Expression: a = b + c * d; Syntax Tree: = / \ a + / \ b * / \ c d

Output: A valid parse tree is generated.

3) Semantic Analysis
Semantic Analysis checks meaning of statements. It verifies data types, variable declarations,
compatibility of operations.
Functions:
• Type checking
• Scope checking
• Declaration checking
Example:
int a; a = "Hello"; // Semantic Error: string assigned to integer variable

Output: Annotated syntax tree with type information.

4) Intermediate Code Generation

Compiler converts source code into machine-independent intermediate code.
Functions:
• Easier optimization
• Machine independent representation
Example:
a = b + c * d; Three Address Code: t1 = c * d t2 = b + t1 a = t2

Output: Machine-independent intermediate code generated.

5) Code Optimization
Compiler improves intermediate code for better efficiency.
Functions:
• Removes redundant calculations
• Reduces execution time
• Reduces memory usage
Example:
Before: x = 2 * 4 After: x = 8 (Constant Folding)

Output: Optimized intermediate code.

6) Target Code Generation

Final phase of compiler. Generates machine code or assembly code.
Functions:
• Register allocation
• Instruction selection
• Machine code generation
Example:
Intermediate Code: t1 = c * d Machine Code: MOV R1,c MUL R1,d

Output: Final machine/assembly code generated.

Symbol Table Management

Symbol Table stores information about variables, functions, constants, memory addresses. It is used by all
compiler phases.

Symbol Type Address

a int 200

Error Handling
 Phase Error Type

Lexical Analysis Invalid tokens

Syntax Analysis Missing semicolon

Semantic Analysis Type mismatch

Summary of Compiler Phases

Phase Main Function

Lexical Analysis Generates tokens

Syntax Analysis Checks grammar

Semantic Analysis Checks meaning

Intermediate Code Generation Creates intermediate code

Code Optimization Improves efficiency

Target Code Generation Produces machine code

Conclusion: Compiler phases systematically convert high-level source code into machine code through
lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimization, and target
code generation.

"Lazy Students Study Intermediate Concepts Till Morning" —

■ Memory Trick (English) Lazy=Lexical, Students=Syntax, Study=Semantic, Intermediate=ICG,
Concepts=Code Optimization, Till Morning=Target Code Generation.

"Lexical se shuru, Target code par khatam" — Token banao →

■ Memory Trick (Hindi)
Grammar check karo → Meaning check karo → Code banao.
 Q12. What is Relocation and Linking concept in Loaders?

Relocation and Linking in Loaders

Relocation and Linking are two important concepts used in loaders for loading and executing programs in
memory efficiently. They help adjust program addresses, combine multiple modules, and execute
programs correctly.

1) Relocation
Definition
Relocation is the process of modifying address-dependent instructions when a program is loaded into a
memory location different from its original specified address. In simple words: If the program is loaded
somewhere else in memory, addresses are adjusted accordingly.

Need of Relocation
Suppose a program is originally designed for address 100 but memory is unavailable there, so the loader
loads it at 500. Now all addresses inside the program must be changed. This process is called Relocation.

Example of Relocation
Original Program: Address Instruction 100 MOV AREG, 150 Program loaded at: 500 New
instruction: MOV AREG, 550 Because: 550 = 150 + 400 (Relocation Factor = 500 - 100 =
400)

Working of Relocation
• Step 1: Loader checks actual loading address.
• Step 2: Find relocation factor = Actual Loading Address - Original Address.
• Step 3: Modify address-sensitive instructions.

Advantages of Relocation
• Flexible Memory Allocation — Program can load anywhere.
• Better Memory Utilization — Efficient use of available memory.
• Supports Multiprogramming — Multiple programs can execute together.

Disadvantages
• Extra Processing Required — Addresses must be modified.
• Complex Loader Design — Relocation logic increases complexity.

2) Linking
Definition
Linking is the process of combining multiple program modules and resolving external symbol references.
In simple words: Different program modules are connected together before execution.

Need of Linking
Large programs are divided into modules. Module A may use a function or variable defined in Module B.
Loader must connect them correctly.

Example of Linking
Module A: CALL SUM Module B: SUM ADD AREG, BREG Here SUM is defined in Module B but
used in Module A. Linker/Loader resolves this reference.
Working of Linking
• Step 1: Loader reads all object modules.
• Step 2: External symbols collected in ESTAB.
• Step 3: Addresses of symbols resolved. Example: SUM = 500
• Step 4: References updated with actual addresses.

Advantages of Linking
• Modular Programming — Large programs divided into modules.
• Reusability — Modules reused in multiple programs.
• Easier Maintenance — Separate modules modified independently.

Disadvantages
• More Loading Time — Linking requires extra processing.
• Complex Management — External references must be tracked.

Difference Between Relocation and Linking

Relocation Linking

Adjusts addresses Combines modules

Changes memory references Resolves external symbols

Needed when loading location changes Needed for multi-module programs

Uses relocation factor Uses external symbol table

Combined Example
Module A: CALL SUM Module B: SUM ADD AREG, BREG Linking connects CALL SUM with actual
SUM address. Relocation adjusts addresses if program loaded elsewhere.

Conclusion: Relocation modifies addresses when programs are loaded into different memory locations,
while linking combines multiple modules and resolves external references. Both concepts are essential for
efficient program execution and memory management in modern systems.

"Relocation Relocates, Linking Links" — Relocation=changes

■ Memory Trick (English) addresses; Linking=joins modules. Move Address=Relocation, Join
Modules=Linking.

"Relocation address badalta hai, Linking modules jodta hai" —

■ Memory Trick (Hindi)
Address shift=Relocation; Program join=Linking.
 Q13. What is Three Address Code (TAC)?

Three Address Code (TAC)

Three Address Code is a type of intermediate code used in compilers. In this representation, each
instruction contains at most two operands and one operator. Hence it is called Three Address Code
because generally three addresses are involved.

Definition
Three Address Code (TAC) is an intermediate code representation in which each statement contains at
most three addresses in the form: x = y op z. Where x=destination/result, y and z=operands, op=operator.

Purpose of TAC
• Complex expressions are broken into simple statements
• Optimization becomes easier
• Machine code generation becomes simpler

General Forms of TAC

x = y op z x = op y x = y if x goto L goto L param x call p,n return y

Example 1 — a = b + c * d
Step 1: Calculate c*d first.
t1 = c * d

Step 2: Add with b.

t2 = b + t1

Step 3: Assign result to a.

a = t2

Complex expression a = b + c*d is divided into smaller instructions using temporary variables t1, t2.

Example 2 — x = (a+b) * (c-d)

t1 = a + b t2 = c - d t3 = t1 * t2 x = t3

Types of TAC Representations

1) Quadruples — Contains: operator, operand1, operand2, result.

Op Arg1 Arg2 Result

* c d t1

2) Triples — Result field removed; position number used instead.

Index Op Arg1 Arg2

0 * c d

1 + b (0)

3) Indirect Triples — Uses pointer table to improve code movement efficiency.

Advantages of TAC
• Easy Optimization — Compiler can optimize simple statements easily.
 • Machine Independent — Independent of target machine architecture.
• Simplifies Code Generation — Easy conversion into machine code.
• Better Expression Representation — Complex expressions become manageable.

Disadvantages
• More Temporary Variables — Requires many temporary variables.
• Increased Number of Instructions — Complex expressions generate multiple TAC statements.

Conclusion: Three Address Code is an intermediate representation where complex expressions are
broken into simple instructions containing at most three addresses. It simplifies optimization and machine
code generation in compiler design.

"One Operation at a Time" — TAC breaks big expression into small

■ Memory Trick (English)
simple operations. Complex Expression → Small Steps.

"Bade expression ko chhote steps mein tod do" — Ek line mein ek

■ Memory Trick (Hindi)
operation.
 Explain different features of Macro with suitable
Q14.
example.

Features of Macro
A Macro is a group of instructions represented by a single name called a macro name. Whenever the
macro name is used, the complete set of instructions gets expanded automatically. Macros help in
reducing repetitive code, simplifying programming, and improving program readability.

Definition
A Macro is a user-defined instruction that expands into multiple assembly language statements during
macro expansion.

1) Macro Definition
Macro definition means defining a set of instructions using MACRO and MEND.
MACRO INCR ADD AREG, ='1' MEND Here INCR is macro name; macro body contains ADD
instruction.

2) Macro Call
Using macro name in program is called macro call. During expansion, assembler replaces macro call with
macro body.
INCR Expands to: ADD AREG, ='1'

3) Parameterized Macro
Macros can accept parameters. Parameters make macros reusable.
MACRO ADDNUM &X,&Y ADD &X,&Y MEND Macro Call: ADDNUM AREG,BREG Expanded Code: ADD
AREG,BREG

4) Argument Substitution
Actual arguments replace formal parameters during expansion.
Formal parameter: &X Actual argument: AREG Substitution: ADD AREG,BREG

5) Macro Expansion
Replacing macro call with actual macro statements is called macro expansion.
Macro Call: INCR Expanded form: ADD AREG, ='1'

6) Nested Macro
A macro can call another macro inside its definition. This is called nested macro.
MACRO M1 M2 MEND Here Macro M1 calls macro M2.

7) Conditional Macro Expansion

Macro expansion may depend on conditions.
AIF (&X EQ 1) .LABEL Meaning: Expand statements only if condition becomes true.

8) Recursive Macro
A macro calling itself is called recursive macro. Used carefully because infinite recursion may occur.
MACRO FACT &N FACT &N-1 MEND
9) Keyword Parameters
Parameters are passed using names.
MACRO TEST &A=AREG,&B=BREG Macro Call: TEST &B=CREG

10) Default Arguments

Macros may use default parameter values. If no value passed, default used automatically.
&A=AREG If no value passed: AREG used automatically.

Complete Example of Macro

MACRO SUM &X,&Y MOVER AREG,&X ADD AREG,&Y MEND START SUM A,B END Expanded Program:
MOVER AREG,A ADD AREG,B

Advantages of Macro
• Reduces Repetition — Repeated code written once.
• Saves Programming Time — Easy reuse of instructions.
• Improves Readability — Programs become shorter and cleaner.
• Easier Maintenance — Changes needed only once in macro definition.

Disadvantages
• Increased Program Size — Expanded code increases size.
• Debugging Difficult — Errors after expansion harder to trace.
• Complex Macro Processing — Advanced features increase complexity.

Applications of Macro
Macros are used in: Assembly language programming, System software, Operating systems, Reusable
coding libraries.

Conclusion: Macros provide reusable and flexible instruction groups in assembly language programming.
Features like parameterization, nesting, conditional expansion, and recursion make macros powerful tools
for reducing repetitive coding and improving programming efficiency.

"Define, Call, Pass, Expand" — Define macro, Call macro, Pass

■ Memory Trick (English) arguments, Expand code. Short: Define → Call → Replace →
Expand.

"Macro banao, use karo, parameter do, expand karo" — Define →

■ Memory Trick (Hindi)
Call → Argument → Expansion.
 Q15. Explain different issues in Code Generation.

Issues in Code Generation

Code Generation is the final phase of compiler design in which intermediate code is converted into target
machine code. While generating machine code, the compiler faces several challenges called Issues in
Code Generation. These issues affect efficiency, speed, memory usage, and correctness of generated
code.

Definition
Issues in Code Generation are the problems and considerations involved in converting intermediate code
into efficient target machine code.

1) Input to Code Generator

The code generator receives intermediate code, symbol table, and type information. The form of
intermediate code affects code generation efficiency.
Three Address Code: t1 = a + b t2 = t1 * c Compiler converts this into machine
instructions.

Issue: If intermediate code is poorly designed, code generation becomes difficult.

2) Target Program Form

Compiler must decide output form: assembly language, machine language, or relocatable code.
Assembly Code: MOV R1,a ADD R1,b

Issue: Compiler should generate compact, fast, and correct target code.

3) Memory Management
Compiler must manage memory efficiently for variables, temporary values, arrays, functions.
Temporary variables t1, t2 must be allocated properly.

Issue: Where to store variables? When to free memory? Stack or registers?

4) Instruction Selection
Compiler must choose efficient machine instructions.
Expression: x = y * 2 Options: MUL R1,2 or optimized: SHIFT LEFT R1,1

Issue: Selecting efficient instruction sequence improves speed.

5) Register Allocation and Assignment

CPU has limited registers. Compiler must decide which variables stay in registers and which move to
memory.
Registers: R1, R2, R3

Issue: Improper allocation causes extra memory access and slower execution.

6) Order of Evaluation
Compiler must determine correct order for evaluating expressions.
Expression: a+b*c Correct order: b*c first, then a+(result)

Issue: Wrong order may increase temporary variables and reduce efficiency.

7) Instruction Scheduling
Compiler arranges instruction sequence for better CPU performance.
Independent instructions may execute in parallel.

Issue: Poor scheduling may cause CPU waiting and pipeline stalls.

8) Handling of Control Flow

Compiler must generate proper code for loops, conditions, and jumps.
if(a>b) x=1; Generated code: CMP a,b JGT LABEL

Issue: Correct branching and jump addresses required.

9) Code Optimization
Compiler should generate optimized target code.
Before: MOV R1,a MOV R1,a After optimization: MOV R1,a

Issue: Optimization improves speed, memory usage, instruction count.

10) Machine Constraints

Every machine architecture has limitations: number of registers, instruction formats, addressing modes.
Some CPUs support fewer registers and limited instructions.

Issue: Compiler must generate code according to machine architecture.

Example of Code Generation

Intermediate Code: t1 = b * c t2 = a + t1 x = t2 Generated Code: MOV R1,b MUL R1,c ADD
R1,a MOV x,R1

Goals of Good Code Generation

• Correct code
• Efficient code
• Fast execution
• Minimum memory usage

Advantages of Efficient Code Generation

• Faster Execution — Optimized instructions improve speed.
• Better Resource Usage — Efficient register and memory use.
• Reduced Program Size — Fewer instructions generated.

Conclusion: Code generation is a complex compiler phase involving issues like instruction selection,
register allocation, memory management, optimization, and control flow handling. Efficient handling of
these issues helps generate fast and compact machine code.

"Input Memory Instructions Registers Order Control Optimize

■ Memory Trick (English) Machine" — Short: Input→Memory→Instruction→Register→Order→
Control→Optimize→Machine.

"Code banate waqt memory, register aur instruction ka dhyan rakho"

■ Memory Trick (Hindi) — Instruction→Register→Memory→Optimization. Fast aur small
machine code banana hi code generation ka goal hai.
 Explain Context Free Grammar (CFG) in Syntax
Q16.
Analysis.

Context Free Grammar (CFG) in Syntax Analysis

Context Free Grammar (CFG) is a formal grammar used in compiler design to describe the syntax of
programming languages. In Syntax Analysis, CFG helps the parser check whether the input program
follows the grammatical rules of the language.

Definition
A Context Free Grammar is a collection of production rules used to generate valid strings in a language. It
is called 'context free' because production rules can be applied regardless of surrounding symbols
(context).

Components of CFG
A CFG is represented as: G = (V, T, P, S)

Symbol Meaning

V Set of Non-terminals

T Set of Terminals

P Set of Production Rules

S Start Symbol

Non-Terminals: Variables used to define grammar structure (e.g. E, T, F). These can be replaced further.
Terminals: Actual symbols/tokens of the language (e.g. id, +, *, (, )). They cannot be replaced further.
Production Rules: Define how symbols are generated. General form: A → α, where A=non-terminal and
α=terminals/non-terminals.
Start Symbol: Grammar derivation starts from the start symbol (e.g. E).

Example of CFG
Consider arithmetic expression grammar:
E → E + T | T T → T * F | F F → (E) | id Where: E=Expression, T=Term, F=Factor

How CFG Works in Syntax Analysis

Parser uses CFG to: verify program syntax, construct parse tree, detect syntax errors.
Example String: id + id * id
Derivation Using CFG:
Start: E Step 1: E → E + T Step 2: E → T Step 3: T → F Step 4: F → id → gives: id +
T Step 5: T → T * F Step 6: T → F Step 7: F → id → gives: id + id * F Step 8: F →
id Final string: id + id * id

Parse Tree of CFG:

E / | \ E + T | /|\ T T * F | | | F F id | | id id

Types of Derivation
• Leftmost Derivation — Leftmost non-terminal replaced first.
 • Rightmost Derivation — Rightmost non-terminal replaced first.

Applications of CFG
CFG is used in: Syntax analysis, Parser design, Programming language definition, Compiler construction.

Advantages
• Easy Syntax Representation — Complex language syntax described clearly.
• Useful in Parser Design — Helps create LL and LR parsers.
• Detects Syntax Errors — Invalid statements identified easily.

Disadvantages
• Cannot Handle Some Semantic Rules — Only syntax handled, not meaning.
• Ambiguity Problem — Some grammars may generate multiple parse trees.

Ambiguous Grammar Example

E → E + E | E * E | id Expression: id + id * id can produce multiple parse trees.

Conclusion: Context Free Grammar is an important concept in syntax analysis used to define
programming language syntax through production rules. It helps parsers verify grammatical correctness
and construct parse trees during compilation.

"Variables produce valid language" — V=Variables(Non-terminals),

■ Memory Trick (English)
T=Tokens(Terminals), P=Productions, S=Start. Shortcut: VTPS.

"Grammar rules se valid program banta hai" — Non-terminal→Rule

■ Memory Trick (Hindi) follow; Terminal→Final token. Shortcut: VTPS = Variables, Tokens,
Productions, Start.
 What is System Programming? List some system
Q17.
programs and write their functions.

System Programming
System Programming is the development of system software that controls and manages computer
hardware and provides a platform for application software execution. It acts as an interface between
hardware and application programs. System programs are designed for efficient operation of the computer
system.

Definition
System Programming is the activity of designing and developing system software used for controlling,
operating, and managing computer resources.

Objectives of System Programming

• Efficient hardware utilization
• Resource management
• Program execution support
• User interaction with hardware
• Translation of programs into machine language

Features of System Programming

• Close interaction with hardware
• Machine-dependent operations
• High efficiency and speed
• Low-level resource management

System Programs and Their Functions

1) Assembler
Function: Assembler converts assembly language program into machine language.
Example: Assembly Code: ADD AREG,BREG → Converted into machine code by assembler.
Main Functions:
• Translate assembly instructions
• Generate object code
• Assign addresses
• Handle symbols and literals

2) Compiler
Function: Compiler converts high-level language into machine language.
Example: a = b + c; → Compiler generates machine code.
Main Functions:
• Lexical analysis
• Syntax analysis
• Code generation
• Optimization

3) Interpreter
Function: Interpreter translates and executes program line-by-line.
Example: Languages: Python, JavaScript
Main Functions:
• Immediate execution
• Error detection line-by-line

4) Loader
Function: Loader loads object program into memory for execution.
Main Functions:
• Allocate memory
• Relocation
• Linking
• Start execution

5) Linker
Function: Linker combines multiple object modules into a single executable program.
Example: Combines: Module A + Module B
Main Functions:
• Resolve external references
• Combine object files
• Generate executable file

6) Macro Processor
Function: Macro Processor expands macros into actual instructions.
Example: Macro Call: INCR → Expanded into: ADD AREG, ='1'
Main Functions:
• Macro definition processing
• Macro expansion
• Parameter substitution

7) Operating System
Function: Operating System manages hardware and software resources.
Example: Examples: Windows, Linux, Android
Main Functions:
• Memory management
• Process scheduling
• File management
• Device management

8) Text Editor
Function: Text editor is used to create and edit source programs.
Example: Examples: Notepad, VS Code, Vim
Main Functions:
• File editing
• Program writing
• Text formatting

9) Debugger
Function: Debugger helps find and remove errors from programs.
Main Functions:
• Error tracing
• Breakpoint handling
• Step-by-step execution

Summary Table

System Program Function

Assembler Converts assembly language to machine code

Compiler Converts high-level language to machine code

Interpreter Executes program line-by-line

Loader Loads program into memory

Linker Combines object modules

Macro Processor Expands macros

Operating System Manages system resources

Text Editor Creates/edits programs

Debugger Finds program errors

Advantages of System Programs

• Efficient Resource Management — System resources used properly.
• Simplifies Program Execution — Users need not interact directly with hardware.
• Improves Productivity — Provides automation and software support.

Conclusion: System Programming involves developing system software that controls computer
operations and supports application execution. Programs like assembler, compiler, loader, linker, macro
processor, and operating system play an important role in efficient system functioning.

"A Clever Intelligent Loader Links Many Operating Debuggers" —

A=Assembler, Clever=Compiler, Intelligent=Interpreter,
■ Memory Trick (English)
Loader=Loader, Links=Linker, Many=Macro Processor,
Operating=OS, Debuggers=Debugger.

"Assembler se lekar OS tak sab system ko chalate hain" —

■ Memory Trick (Hindi) Assembler→Compiler→Loader→Linker→OS. System programs
hardware aur software ke beech bridge hote hain.