📘 Topic: Symbol Tables: Data Structure for Symbol Tables

What is a Symbol Table?

Why Symbol Table is Needed?

• 💡 To store information about identifiers during compilation.
• 💡 To quickly find attributes of variables and functions.
• 💡 To check for errors like duplicate declarations.
• 💡 To help in type checking and memory allocation.
• 💡 To manage scope and lifetime of variables.

Common Attributes Stored in Symbol Table

• Name of identifier (variable or function).
• Data type (int, float, char, etc.).
• Scope (global, local, block).
• Memory address or offset.
• Size of the variable.
• Other info like parameters for functions.

Data Structures Used for Symbol Tables

• 1. Array
  • Simple, easy to implement.
  • Fast access by index.
  • Not efficient for large or dynamic symbol tables.
• 2. Linked List
  • Dynamic size, easy to insert/delete.
  • Search is slower (linear time).
  • Good for small symbol tables.
• 3. Hash Table
  • Most commonly used.
  • Provides fast average-time lookup, insertion, and deletion.
  • Uses hash function on identifier names.
  • Handles collisions by chaining or open addressing.
• 4. Binary Search Tree (BST)
  • Allows sorted order traversal.
  • Average case search is efficient (log n).
  • Can degrade to linear if unbalanced.

Example of Symbol Table Entry

Important Points about Symbol Tables

• 💡 Hash tables are preferred for fast access.
• 💡 Symbol tables grow as new identifiers are found.
• 💡 Different scopes may use different symbol tables or linked structures.
• 💡 Errors like redeclaration are detected using symbol tables.
• 💡 Symbol table helps during semantic analysis and code generation.

Summary in Hinglish

• Symbol table ek important data structure hai jisme compiler variables aur functions ki information rakhta hai.
• Hash table sabse jyada use hota hai kyunki wo fast searching deta hai.
• Array aur linked list bhi use kar sakte hain chhote symbol tables ke liye.
• Symbol table ki madad se compiler variables ke type, scope aur location ko manage karta hai.

📘 Topic: Representing Scope Information

What is Scope in Programming?

Why Representing Scope is Important?

• 💡 To distinguish variables with the same name but in different parts of the program.
• 💡 To manage lifetimes of variables.
• 💡 To prevent errors by checking if a variable is used outside its scope.
• 💡 To help compilers allocate memory correctly.
• 💡 To support nested blocks and functions.

Types of Scope

• Global Scope: Variable accessible throughout the program.
• Local Scope: Variable accessible only within a function or block.
• Block Scope: Variable accessible only within a particular block (like {} braces).
• Nested Scope: When a scope exists inside another scope.

How to Represent Scope Information?

• 1. Using Symbol Tables with Scope
  • Each scope can have its own symbol table or a chain of symbol tables.
  • When entering a new scope (like a function or block), create a new symbol table or scope record.
  • When leaving the scope, discard or hide that symbol table.
• 2. Using Stack of Symbol Tables
  • Maintain a stack where each element is a symbol table for a scope.
  • When entering a new scope, push a new symbol table on the stack.
  • When exiting, pop it off.
  • Lookup starts from top of the stack (current scope) downwards.
• 3. Using Display or Static/Dynamic Links
  • Display: Array or table that points to the symbol tables of active scopes, for quick access.
  • Static Link: Pointer in activation records to the symbol table of the static parent scope.
  • Dynamic Link: Pointer to caller’s activation record (for dynamic scoping).

Example of Scope Representation

int x = 10; // global scope

void func() {
   int x = 5; // local scope inside func
   {
      int x = 3; // block scope inside func
   }
}
                

Important Points about Scope Representation

• 💡 Scope information helps resolve variable names correctly.
• 💡 Symbol tables and scope chains keep track of active variables.
• 💡 Nested scopes mean symbol tables can be nested or linked.
• 💡 Stack-based approach is most common for managing scope during parsing/compilation.

Summary in Hinglish

• Scope batata hai ki variable program ke kis hissa mein accessible hai.
• Compiler har scope ke liye alag symbol table ya stack use karta hai.
• Jab naya scope start hota hai to naya symbol table banta hai, aur end hone par wo hata diya jata hai.
• Isse compiler ko pata chalta hai ki kis variable ko use karna hai jab same naam ke variables ho.

📘 Topic: Run-Time Administration: Implementation of Simple Stack Allocation Scheme

What is Run-Time Administration?

What is Stack Allocation Scheme?

Why Use Stack Allocation?

• 💡 Function calls need temporary memory (for parameters, local variables).
• 💡 Easy to allocate and deallocate memory when function starts and ends.
• 💡 Supports nested and recursive function calls.
• 💡 Keeps track of return addresses.
• 💡 Efficient memory usage.

How Simple Stack Allocation Works?

• When a function is called, its Activation Record (AR) or Stack Frame is pushed onto the stack.
• Activation record stores function’s parameters, local variables, return address, saved registers, etc.
• When function ends, the activation record is popped off (removed) from the stack.
• The stack pointer moves up and down to allocate or free memory.

Activation Record (Stack Frame) Structure

Example: Stack Allocation Flow

Important Points about Stack Allocation

• 💡 Stack allocation is LIFO (Last In First Out).
• 💡 Stack pointer keeps track of top of stack.
• 💡 Allows efficient function calls and returns.
• 💡 Supports recursion naturally.
• 💡 Simple and widely used in modern compilers.

Summary in Hinglish

• Run-time pe function ke liye memory stack mein allocate hoti hai jise activation record kehte hain.
• Jab function call hota hai to uska data stack mein push hota hai, aur function ke khatam ہونے par pop ho jata hai.
• Is tarah se stack pointer se memory manage karte hain.
• Yeh scheme simple, fast aur recursive functions ke liye perfect hai.

📘 Topic: Storage Allocation in Block-Structured Languages

What is Storage Allocation?

What is a Block-Structured Language?

How Storage Allocation Works in Block-Structured Languages?

• Each block has its own scope and variables declared inside the block live only during the execution of that block.
• When program enters a block, memory is allocated for its local variables.
• When program leaves the block, memory is deallocated (freed).
• This is usually managed using a stack allocation scheme (activation records).

Types of Storage Allocation

• 1. Static Allocation
  • Memory for variables is allocated before program starts and remains fixed.
  • Used for global variables or static variables.
• 2. Stack (Dynamic) Allocation
  • Memory for local variables in blocks/functions is allocated on stack when block is entered and freed on exit.
  • Supports recursion and nested blocks.
• 3. Heap Allocation
  • Memory allocated dynamically during runtime using pointers (not directly related to block scope).

Example: Block-Structured Allocation

begin
   int x;       // Allocated when block starts
   begin
       int y;   // Allocated when inner block starts
       // use x, y
   end          // y is deallocated here
   // x still exists here
end            // x is deallocated here
                

Important Points about Storage Allocation in Block-Structured Languages

• 💡 Block-structured languages use stack allocation to manage storage of local variables.
• 💡 Nested blocks mean nested activation records on stack.
• 💡 Variables from outer blocks are accessible inside inner blocks (if language allows).
• 💡 Helps in managing variable lifetime and memory efficiently.
• 💡 Reduces memory wastage by freeing memory when blocks end.

Summary in Hinglish

• Block-structured language mein har block ke variables ke liye memory allocate hoti hai jab block start hota hai, aur free hoti hai block khatam ہونے pe.
• Stack allocation sabse common technique hai iske liye.
• Is tarah se nested blocks ke liye nested memory management hota hai.
• Global variables ke liye static allocation hoti hai jo pura program chalne tak rehti hai.

📘 Topic: Error Detection & Recovery: Lexical, Syntactic, and Semantic Errors

What is Error Detection & Recovery?

Types of Errors in Compiler

• 1. Lexical Errors
  • Mistakes detected during the lexical analysis phase.
  • Related to invalid tokens or characters.
  • Example: Using an illegal symbol or invalid identifier like @var or 123abc.
• 2. Syntactic Errors
  • Detected during syntax analysis (parsing).
  • Related to wrong grammar or structure of the program.
  • Example: Missing semicolon, unmatched parentheses, incorrect statement order.
• 3. Semantic Errors
  • Detected during semantic analysis.
  • Related to meaning or logic of the code, even if syntax is correct.
  • Example: Using a variable before declaration, type mismatches, incompatible operations.

Lexical Phase Errors

• Occur when the input contains characters or tokens that the lexer can’t recognize.
• Example: int x = 100$; → $ is invalid character.
• Recovery: Skip invalid characters or report error and continue scanning.

Syntactic Phase Errors

• Occur if token sequence doesn’t follow grammar rules.
• Example: if (x > 0 { missing closing parenthesis.
• Recovery: Methods include panic mode (skip tokens until a safe point), phrase level recovery (insert/delete tokens).

Semantic Errors

• Occur when code is syntactically correct but meaning is wrong.
• Example: Trying to add integer and string without conversion.
• Recovery: Report error with line number and try to continue checking other parts.

Example of Each Error Type

Important Points about Error Handling

• 💡 Error detection happens in phases: lexical → syntax → semantic.
• 💡 Early detection improves error recovery and user feedback.
• 💡 Recovery techniques aim to continue compilation after an error to find more errors.
• 💡 Good compilers give clear, precise error messages.
• 💡 Sometimes errors in one phase lead to cascading errors in next phases.

Summary in Hinglish

• Lexical errors tab hote hain jab invalid character ya token mile.
• Syntactic errors tab hote hain jab grammar rule break ho jaye, jaise missing semicolon.
• Semantic errors tab hote hain jab code ka matlab galat ho, jaise type mismatch.
• Compiler alag alag technique se errors detect karta hai aur recover karne ki koshish karta hai.