✨ Topic: Introduction to Compiler: Phases and Passes

Definition of Compiler (Simple Language)

5 Simple Bullet Points About Compiler

• Compiler checks the whole program at once and then gives errors, if any. (Poore program ko ek baar mein check karta hai.)
• It converts the code into machine code before running it. (Code ko machine code mein badal kar fir chalata hai.)
• It is used in languages like C, C++, Java, etc.
• Compiler improves program performance by optimizing code.
• It helps in finding syntax errors during compilation.

Phases of Compiler (Definition)

List of Phases of Compiler (With Explanation)

Diagram Suggestion:

Source Code
   ↓
Lexical Analyzer
   ↓
Syntax Analyzer
   ↓
Semantic Analyzer
   ↓
Intermediate Code Generator
   ↓
Code Optimizer
   ↓
Code Generator
   ↓
Target Code (Machine Code)
            

What is Pass in Compiler? (Definition)

Types of Passes

Difference Between Single Pass and Multi Pass Compiler

Example (Simple)

int a = 5 + 3;

Important Formulas/Concepts

• 💡 Token = Smallest meaningful unit in code (e.g., int, =, 5)
• 💡 Lexeme = Actual string in the code (e.g., int, main, a)
• 💡 Parsing = Process of checking syntax
• 💡 IR (Intermediate Representation) = Temporary code between high-level and machine code

Advantages and Disadvantages of Compilers

• 👍 Fast execution after compilation
• 👍 Code optimization improves performance
• 👍 Errors are shown before running the code
• 👍 Helps in large-scale development
• 👍 Secure: No source code exposed while running
• 👍 Converts code only once
• 👍 Produces standalone executables

• 👎 Compilation takes time
• 👎 Hard to debug in machine code
• 👎 Not suitable for dynamic features (like scripting)
• 👎 Error messages can be hard for beginners
• 👎 Recompilation needed after changes
• 👎 Takes more memory
• 👎 No runtime flexibility

Summary

• Compiler changes source code into machine code.
• It works in phases: lexical, syntax, semantic, intermediate code, optimization, and code generation.
• Pass means one full reading of the program.
• Single pass reads once, multi-pass reads multiple times.
• It helps make fast and optimized programs.

🌟 Topic: Bootstrapping in Compiler Design

Definition of Bootstrapping (Simple Language)

5 Simple Bullet Points About Bootstrapping

• 🔄 Bootstrapping is used to create a compiler using its own language.
• 🏗 It helps to build new versions of a compiler from a simple version.
• 🧱 It starts from a minimal or existing compiler (written in machine or assembly code).
• 🔧 Bootstrapping is common when a new programming language is developed.
• 📦 It’s like compiling a compiler using the compiler itself!

Why Bootstrapping is Needed?

Types of Bootstrapping

Simple Example of Bootstrapping

Bootstrapping Process Flow (Diagram Suggestion)

Small Compiler (in Assembly)
         ↓
Compile → Big Compiler (in C)
         ↓
Use Big Compiler to Compile Itself
         ↓
Final Self-Sustaining Compiler ✅
            

Important Points about Bootstrapping

• 💡 Bootstrapping saves development effort in writing a compiler from scratch.
• 💡 It requires at least a minimal initial compiler in some basic language.
• 💡 It allows a language to evolve by improving the compiler itself.
• 💡 Most modern compilers (like GCC for C/C++) are built using bootstrapping.

Advantages of Bootstrapping

• 👍 Code Reusability – You can write the compiler in the same high-level language.
• 👍 Language Improvement – You can enhance the compiler and the language easily.
• 👍 Portability – You can move the compiler from one machine to another.
• 👍 Self-hosting – Compiler can compile itself (self-dependent).
• 👍 Faster development of new versions.
• 👍 Easy to test and debug in higher-level language.
• 👍 Bootstrapping shows the maturity of a language (like C, Pascal, etc.).

Disadvantages of Bootstrapping

• 👎 You need an initial basic compiler written in low-level language.
• 👎 Complex process if starting from scratch.
• 👎 Debugging a compiler that compiles itself can be confusing.
• 👎 Time-consuming to test all paths of the new compiler.
• 👎 Needs perfect correctness in base compiler.
• 👎 If one bug exists, it can be copied in future versions.
• 👎 Not ideal for very new or unstable languages.

Applications of Bootstrapping

• Building a new compiler from scratch.
• Updating existing compiler versions.
• Creating self-hosted compilers.
• Porting a compiler to different operating systems.
• Testing and research in language development.
• Developing a compiler in the same high-level language.
• Foundation of modern compiler development (e.g., LLVM, GCC).

Summary of Bootstrapping

🌟 Topic: Finite State Machines (FSM) and Regular Expressions (RE) and Their Applications to Lexical Analysis

Part 1: Finite State Machines (FSM)

Definition (Simple Words) of FSM

5 Important Points About FSM

• 🔄 FSM has states, inputs, and transitions.
• 🎯 It is used to accept or reject strings.
• 🧠 It remembers only the current state, not the history.
• 🧩 FSMs are of two types – DFA (Deterministic) and NFA (Non-deterministic).
• 🧮 It is used in lexical analysis, protocol design, and control systems.

Types of FSM

A. DFA (Deterministic Finite Automaton)

• ✅ Each state has only one transition for each symbol.
• 💡 Fast and simple to implement.

B. NFA (Non-deterministic Finite Automaton)

• 🔁 A state can have multiple transitions for one symbol.
• 💭 Easier to design, but needs to be converted to DFA for implementation.

Example of FSM (Numerical)

Applications of FSM

• 🧠 Used in lexical analyzers to tokenize source code.
• 📟 Used in hardware design and digital circuits.
• 🎮 Game AI for state-based decisions.
• 🧾 Used in pattern recognition and text processing.
• 📧 Used in communication protocols (e.g., TCP/IP).
• 🧪 Compiler front-end for token generation.
• 🧩 Used in form validation and UI state management.

Advantages of FSM

• 👍 Simple structure and easy to implement.
• 👍 Can be used in both hardware and software.
• 👍 Fast and efficient for string pattern matching.
• 👍 Foundation for lexical analyzer in compilers.
• 👍 Clear state transitions for logic.
• 👍 Good for repetitive behavior modeling.
• 👍 Can be visualized using diagrams easily.

Disadvantages of FSM

• 👎 Cannot remember past input beyond current state.
• 👎 Not suitable for nested patterns (like parentheses).
• 👎 Becomes complex for large input sets.
• 👎 Limited memory (can’t store full input history).
• 👎 Needs conversion to DFA for practical use.
• 👎 Not suitable for context-free grammar.
• 👎 Difficult to scale for large languages.

Part 2: Regular Expressions (RE)

Definition (Simple Words) of RE

5 Important Points About RE

• ✍️ Regular Expressions describe the syntax of string patterns.
• 🔁 Used in search engines, validators, and lexical analysis.
• 🔗 Every Regular Expression has an equivalent FSM.
• 🧮 REs use symbols and operators like *, +, |, etc.
• 🔡 Can define sets like: all strings that start with “a” or contain “01”.

Basic Operators in RE

Example of Regular Expression

Applications of Regular Expressions

• 🔍 Searching and pattern matching in text editors (like VS Code, Notepad++).
• 🔏 Input validation (e.g., Email, Phone number).
• 🧪 Token generation in lexical analysis of compilers.
• 📂 File filters (e.g., *.txt, *.jpg).
• 🕵️‍♂️ Log analysis tools.
• 📧 Spam filter and virus detection.
• 🧠 NLP tasks for keyword extraction and token splitting.

Advantages of RE

• 👍 Compact and easy to write.
• 👍 Fast pattern matching.
• 👍 Powerful text-processing tool.
• 👍 Easily converted to FSM for lexical analysis.
• 👍 Platform independent (used in almost all languages).
• 👍 Great for tokenization and preprocessing.
• 👍 Easy to test with online tools.

Disadvantages of RE

• 👎 Hard to read for complex patterns.
• 👎 Cannot handle nested structures.
• 👎 No memory of previous matches (stateless).
• 👎 Limited to regular languages only.
• 👎 Debugging complex RE is tough.
• 👎 Cannot parse programming language grammars.
• 👎 Overuse can lead to performance issues.

Part 3: Comparison Between FSM and Regular Expressions

🌟 Topic: Implementation of Lexical Analyzer (Lexer)

Definition of Lexical Analyzer (Lexer)

5 Important Points about Lexer

• 🔍 Works like a scanner that reads one character at a time.
• 🎯 Converts long source code into meaningful tokens.
• 📚 Uses Finite Automata and Regular Expressions for pattern matching.
• ⛔ Removes whitespace and comments.
• 🧾 Passes tokens to the next phase: Syntax Analyzer.

Example of Lexical Analysis

int x = 10 + y;

Phases of Lexical Analysis Implementation

• Input Buffering
  • Efficient reading of input characters using buffers.
  • Deals with lookahead and rollback.
• Lexeme Detection
  • Identifies sequence of characters that form a token.
• Token Generation
  • Creates token structure (type + value).
• Symbol Table Maintenance
  • Stores identifiers and literals with attributes.
• Error Handling
  • Detects invalid symbols (e.g., @, #).

Steps to Implement a Lexical Analyzer

• A. Manual Approach
  • ✍️ Write code using if-else or switch-case to match patterns.
  • ✅ Good for small languages or educational tools.
• B. Using Finite Automata
  • 🧠 Design DFA/NFA for each token type (keywords, identifiers, numbers).
  • 🧮 Convert regular expressions into DFA using tools or by hand.
• C. Using Lex Tool (like Lex or Flex)
  • 📄 Define token patterns using regex.
  • ⚙️ Compile the lexer using lex or flex.
  • 🎯 Connect with parser (like Yacc or Bison).

Techniques Used in Lexical Analyzer

Components / Architecture

Lexical Analyzer Architecture includes:

• 📥 Input Buffer – holds source code
• 🔍 Scanner (DFA) – identifies lexemes
• 🧾 Token Generator – builds tokens
• 🗂 Symbol Table – saves variables/constants
• 🧰 Error Handler – catches lexical errors

Diagram Suggestion:

+-----------------+
| Source Program  |
+--------+--------+
         |
         v
+-----------------+      +-----------------+
| Input Buffering | ---> |  Lexeme Matcher |
+-----------------+      +--------+--------+
                                 |
                                 v
                    +--------------------------+
                    |   Token + Symbol Table   |
                    +------------+-------------+
                                 |
                                 v
                         Syntax Analyzer
            

Advantages of Lexer Implementation

• 👍 Faster tokenization of source code
• 👍 Separates lexical and syntactic concerns
• 👍 Easy to debug errors at character level
• 👍 Regular Expressions make design simpler
• 👍 Can ignore irrelevant things like whitespace
• 👍 Makes compiler modular
• 👍 Enables optimization (e.g., constant folding)

Disadvantages of Lexer Implementation

• 👎 Limited to regular languages only
• 👎 Cannot detect grammar-based errors
• 👎 Complex tokens need more states in DFA
• 👎 Backtracking increases time in some cases
• 👎 Needs precise RE design
• 👎 Limited support for nested tokens
• 👎 Not suitable for semantic checking

Applications of Lexer

• 🧪 Compilers (C, Java, Python, etc.)
• 🧠 Interpreters and virtual machines
• 📂 Text editors and search tools
• 🔐 Token-based authentication systems
• 📊 Log file analysis
• 📧 Spam filter systems
• 📜 Scripting language execution engines

Formulae and Theoretical Concepts

• DFA Construction from RE
• Transition Table: δ(q, a) = next state
• Token Tuple:

RE to DFA Conversion Steps:

• RE → NFA
• NFA → DFA
• DFA → Minimized DFA

📘 Topic: LEX Compiler

Definition of LEX

5 Key Points about LEX

• 🛠️ LEX is used to create lexical analyzers.
• 🔍 It uses regular expressions to match patterns (like keywords, identifiers, numbers).
• 💻 Generates a C program which can scan and tokenize input.
• 🤝 Often used with YACC (parser generator).
• 📦 Final output is an executable scanner that reads input and returns tokens.

Structure of a LEX Program

%{
  // C declarations (optional)
%}

%%
  // Rules: Regular Expression    Action (C code)
  [0-9]+       printf("NUMBER");
  if           printf("IF KEYWORD");
  [a-zA-Z]+    printf("IDENTIFIER");
%%

int main() {
  yylex();   // calls the lexer
}
            

Explanation (Hinglish):

• First part: optional C code.
• Second part: rules likhte hain (RE + action).
• Third part: C code jahan yylex() call hota hai.

Working of LEX Compiler

Simple Example (with Explanation)

%{
#include 
%}
%%
[0-9]+      printf("NUMBER\n");
[a-zA-Z]+   printf("IDENTIFIER\n");
.           printf("UNKNOWN CHARACTER\n");
%%

int main() {
  yylex();
  return 0;
}
                

age 25 name x1

IDENTIFIER
NUMBER
IDENTIFIER
IDENTIFIER
                

Important Functions in LEX

Advantages of LEX

• 👍 Fast generation of lexers from RE.
• 👍 Easy integration with C and YACC.
• 👍 Reduces manual code writing for token scanning.
• 👍 Ideal for building custom interpreters and compilers.
• 👍 Supports powerful pattern matching.

Disadvantages of LEX

• 👎 Limited to regular language patterns.
• 👎 Error handling is basic unless customized.
• 👎 Cannot handle nested structures like balanced parentheses.
• 👎 Coupled tightly with C language.
• 👎 Needs separate tool (YACC) for syntax parsing.

Applications of LEX

• 🔍 Compilers (C, Java, Python)
• 🧠 Custom interpreters
• 🧾 Data format scanners (e.g., XML, CSV)
• 📜 Configuration file readers
• 📚 Source code analyzers
• 🚀 Shell command parsers
• 🔐 Token-based login systems

Comparison: LEX vs Manual Lexical Analyzer

Suggested Diagram for LEX Workflow

LEX File (.l)
     ↓
 [LEX Compiler]
     ↓
Generated C Program (lex.yy.c)
     ↓
  [GCC Compiler]
     ↓
Final Executable Scanner
     ↓
Input Code → Tokens Output
            

Formulas & Concepts (Brief) of LEX

• Token = (token-name, attribute-value)
• Regular Expression → NFA → DFA → Scanner code
• LEX internally builds Finite Automata using regex rules.

📘 Topic: Formal Grammars and their Application to Syntax Analysis

Definition of Syntactic Specification

Context-Free Grammar (CFG) - Definition

Components of CFG

CFG is represented as a 4-tuple: G = (V, T, P, S)

Example of CFG

E → E + T | T
T → T * F | F
F → (E) | id
                

Derivation

Types of Derivation

• Leftmost Derivation: At each step, replace the leftmost non-terminal.
• Rightmost Derivation: At each step, replace the rightmost non-terminal.

Example of Leftmost Derivation

E → E + T  
E → T  
T → T * F  
T → F  
F → id
                

E
  → E + T (replace leftmost E)
  → T + T (replace leftmost E again)
  → F + T (replace leftmost T)
  → id + T (replace F with id)
  → id + T * F (replace T with T * F)
  → id + F * F (replace T with F)
  → id + id * F (replace F with id)
  → id + id * id (replace F with id)
                

Parse Trees

Example Parse Tree for id + id * id

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

Why CFG for Programming Languages?

• CFG can express nested structures easily (like parentheses, blocks).
• CFGs are powerful enough for most programming language syntax.
• Parsers can efficiently process CFGs (using LL, LR parsers).

Advantages of Formal Grammars

• 👍 Simple way to describe complex syntax.
• 👍 Helps in building automatic parsers.
• 👍 Supports recursive language constructs.
• 👍 Basis for compiler syntax analysis.

Disadvantages of Formal Grammars

• 👎 Not suitable for context-sensitive syntax (like variable declarations before use).
• 👎 Ambiguity can occur (multiple parse trees for same input).
• 👎 May require grammar transformations for efficient parsing.

Applications of Formal Grammar

• 🧑‍💻 Compiler Design (Syntax Checking)
• 📘 Programming Language Design
• 🧠 Artificial Intelligence (Natural Language Processing)
• 📝 Document Parsing (HTML, XML)
• 📚 Educational Tools (Language simulation, grammar checking)

Important Concepts and Formulas

• Leftmost Derivation: Replace leftmost non-terminal first.
• Rightmost Derivation: Replace rightmost non-terminal first.
• Ambiguous Grammar: One input has more than one parse tree.
• Unambiguous Grammar: One parse tree per input.

Comparison Table: Regular Grammar vs Context-Free Grammar

Suggested Diagram: Grammar to Parse Tree Workflow

Formal Grammar
     ↓
 Production Rules
     ↓
 Syntax Analysis (Parsing)
     ↓
   Parse Tree
     ↓
Syntax Checking ✅ or Error ❌
            

Summary in Hinglish about Formal Grammars

• Formal grammar ek rule system hai jo batata hai ki valid strings (syntax) kaise banayi jaaye.
• Is grammar ko syntax analysis mein use karte hain taaki program ke structure ko check kiya jaa sake.
• Syntax analysis parse tree banata hai aur invalid syntax ko pakadta hai.
• Chomsky ne 4 grammar types diye: Type 0 (most powerful), Type 1, Type 2 (CFG), Type 3 (Regular Grammar).
• CFG compilers mein sabse jyada use hota hai.

📘 Topic: Ambiguity in Grammar

Definition of Ambiguity

5 Simple Bullet Points about Ambiguity

• 📚 Ambiguity matlab ek sentence ke multiple meanings ya parse trees.
• 🧩 Yeh problem syntax analysis mein confusion create karta hai.
• 🤔 Ek grammar agar ambiguous ho to parser ko samajhne mein dikkat hoti hai.
• ❌ Ambiguous grammar se error detection mushkil ho jata hai.
• 🛠️ Ambiguity ko kam karne ke liye grammar ko simplify ya rewrite karna padta hai.

Example of Ambiguity

E → E + E | E * E | (E) | id

Types of Ambiguity

• Structural Ambiguity: When sentence structure gives multiple interpretations.
• Semantic Ambiguity: When sentence meaning is unclear even if structure is clear.

(Note: In compiler grammar, we usually talk about structural ambiguity.)

Causes of Ambiguity

• Lack of operator precedence rules.
• Missing associativity rules.
• Overlapping production rules.
• Recursive rules without clear distinction.
• Ambiguous natural language constructs.

How to Remove Ambiguity?

• Define operator precedence and associativity rules explicitly.
• Rewrite grammar in an unambiguous form.
• Use separate rules for different precedence levels.
• Use parser generators that resolve ambiguities (like YACC with precedence declarations).

Example: Unambiguous Grammar for Arithmetic Expressions

E → E + T | T
T → T * F | F
F → (E) | id
                

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

Effects of Ambiguity

• 👎 Parser may produce different interpretations for the same code.
• 👎 Compiler behavior can become unpredictable.
• 👎 Harder to detect syntax errors.
• 👎 Can cause wrong code generation.
• 👎 Leads to confusing error messages.

Advantages and Disadvantages of Ambiguity

Applications of Ambiguity Handling

• Important in compiler design to create clear and predictable syntax rules.
• Used in natural language processing to identify and resolve multiple interpretations of sentences.
• Helps improve programming language design by clarifying syntactic behavior.
• Useful in automated grammar checking tools.

Summary in Hinglish about Ambiguity

• Ambiguity matlab ek sentence ke do ya zyada meanings ya parse trees hona.
• Compiler ke liye ambiguity problem hai, kyunki woh decide nahi kar pata ki kaunsa meaning sahi hai.
• Operator precedence aur associativity se ambiguity hata sakte hain.
• Grammar ko rewrite karke unambiguous bana sakte hain.

Suggested Diagram for Ambiguity Resolution

Ambiguous Grammar
        ↓
Multiple Parse Trees (Confusion!)
       /            \
Parse Tree 1    Parse Tree 2
       ↓              ↓
 (Interpretation A)   (Interpretation B)

Solution:
Rewritten Grammar with Precedence & Associativity
       ↓
Single Unambiguous Parse Tree (Clarity!)
            

📘 Topic: Capabilities of Context-Free Grammars (CFG)

Definition of CFG Capabilities

5 Important Capabilities of CFG

• 👍 Can generate nested structures — jaise brackets, parentheses, function calls (recursive patterns).
• 👍 Can describe most programming language syntax — loops, if-else, expressions.
• 👍 Can represent recursive rules — jise complex languages banate hain.
• 👍 Can be used to build parsers for compilers and interpreters.
• 👍 Can express hierarchical structures clearly — jaise expressions inside expressions.

Examples of CFG Capabilities in Action

• Balanced Parentheses: CFG can generate strings like (()()) with correct matching pairs.
• Arithmetic Expressions: CFG can accurately describe expressions like id + id * (id), respecting operator precedence.
• Control Structures: CFG can represent complex nested if-else blocks and various loop structures.
• Function Calls: Nested function calls and passing multiple parameters can be precisely represented by CFGs.

Limitations (What CFG cannot do)

While powerful, CFGs have limitations, particularly with context-dependent rules:

• 👎 CFG cannot handle context-sensitive languages — e.g., variable type checking (ensuring a variable is used according to its declared type). This meaning depends on the context of the variable's declaration.
• 👎 CFG cannot enforce rules like “number of a’s equals number of b’s and c’s” simultaneously. For example, anbncn (same count of a's, b's, c's).
• 👎 CFG cannot handle indentation-based syntax (like Python's significant whitespace rules) as part of its structural definition alone.
• 👎 CFG cannot enforce variable declaration before use (these are semantic rules, not just syntactic ones).

Summary in Hinglish about CFG Capabilities

• CFG bahut powerful hai nested aur recursive structures banane mein.
• CFG se hum programming language ke jyadatar syntax ko describe kar sakte hain.
• Lekin CFG context-sensitive rules nahi samajh sakta (jaise type checking ya variable scope).
• Isi wajah se compiler ke syntax analysis ke baad semantic analysis bhi karna padta hai taaki poori correctness check ho.

Suggested Diagram: CFG Capabilities Spectrum

CFG
↓
Can Describe:
- Nested Structures (Parentheses, Loops)
- Recursive Patterns (Function Calls, Expressions)
- Most Programming Language Syntax (Statements, Declarations)
- Hierarchical Structures (Grammar Trees)

↓

Cannot Directly Describe (Requires Semantic Analysis):
- Context Sensitive Rules (Variable Typing, Scope)
- Numerical/Quantitative Equalities (a^n b^n c^n)
- Indentation Rules (Beyond simple structural patterns)
- Variable Declaration Before Use