Complete Compiler Design Notes for GATE CSE 2026 – Best Notes

Compiler Design GATE CSE ka sabse logical subject hai. Har saal 3-4 marks aate hain. Isme se LL(1), LR(0) Parsing aur Intermediate Code se har saal question aata hai. Ye last core subject hai, iske baad aapka pura syllabus complete.

1. Phases of Compiler – Base

Compiler 6 Phases me kaam karta hai:

1. Lexical Analyzer: Source code ko Tokens me todta hai. Keywords, Identifiers. NFA/DFA use hota hai. Longest Prefix Matching.
2. Syntax Analyzer (Parsing): Tokens se Parse Tree banata hai. CFG use hota hai.
3. Semantic Analyzer: Type Checking, Scope Checking.
4. Intermediate Code Generator: 3-Address Code banata hai. a = b + c ko t1 = b + c; a = t1.
5. Code Optimizer: Code ko fast banata hai. Constant Folding, Dead Code Elimination.
6. Code Generator: Target Machine Code banata hai.

2. Parsing – Har Saal 2 Marks Pakka – Most Important

Parsing 2 type ka: Top-Down aur Bottom-Up.

Top-Down: LL(1) Parser:

• L=Left to Right Scanning, L=Leftmost Derivation, 1=1 Lookahead.
• LL(1) ke liye Grammar me Left Recursion nahi hona chahiye aur Left Factoring hona chahiye.
• First and Follow: First(A) = A se shuru hone wale terminals. Follow(A) = A ke baad aane wale terminals. GATE me First/Follow nikalna har saal aata hai.
• Parsing Table: M[A,a] = A -> alpha jahan a in First(alpha). Agar Epsilon hai to Follow(A) dekho.

Bottom-Up: LR Parser: Sabse powerful. 4 type:

1. LR(0): Simplest, No Lookahead. Closure aur Goto se States bante hain.
2. SLR(1): Simple LR, Follow se Conflict solve karta hai.
3. CLR(1)/LR(1): Most Powerful, Canonical LR. Sabse zyada states.
4. LALR(1): CLR ke states ko merge karke banta hai. YACC is par kaam karta hai. States SLR ke barabar lekin Powerful.

GATE Trick: Number of States: LR(0) = SLR = LALR < CLR. Har Grammar jo SLR hai wo LALR bhi hai, LALR hai to CLR bhi hai. Lekin Reverse True nahi.

Conflict: Shift/Reduce aur Reduce/Reduce. SLR me Shift ko Priority dete hain.

3. Syntax Directed Translation and Intermediate Code

SDD: CFG + Attributes. Synthesized (Bacche se Parent) aur Inherited (Parent/Bhai se). S-Attributed sirf Synthesized, L-Attributed dono ho sakte hain lekin Left to Right evaluate hota hai.

Intermediate Code:

• 3-Address Code: Max 3 address. t1 = b + c
• Quadruple: 4 fields: op, arg1, arg2, result. Temporary variable ka naam explicit.
• Triple: Temporary ka naam nahi, location se kaam.
• Indirect Triple: Triple ki list ka pointer.

4. Code Optimization and Runtime Environment

Optimization:

• Constant Folding: 2+3 ko 5 karna.
• Common Subexpression Elimination: a = b + c; d = b + c -> d = a
• Dead Code Elimination: Jo code execute hi nahi hoga use hatana.
• Loop Optimization: Code Motion, Strength Reduction (i*2 ko i+i).

Data Flow Analysis: Basic Block, Flow Graph, DAG. DAG se Common Subexpression milta hai.

Runtime: Activation Record: Return Value, Parameters, Control Link, Access Link, Local Data. Static Scoping me Access Link, Dynamic me Control Link.

Final Checklist: First/Follow Numerical, LL(1) Table, LR(0) Items, LALR vs CLR States. Ye 4 se 4 marks pakke.