अगर आप GATE 2026 (CS / IT) की तैयारी कर रहे हैं, तो Compiler Design का एक ऐसा topic है जो almost हर साल exam में पूछा जाता है – Parsing. इस article में हम Parsing in Compiler Design को बिल्कुल simple Hindi में समझेंगे ताकि beginners भी आसानी से concept पकड़ सकें।
इस guide को पढ़ने के बाद आप जानेंगे – parsing क्या होती है, parser कैसे काम करता है, Top-Down और Bottom-Up Parsing, Parse Tree, और वे सभी concepts जो GATE में repeatedly पूछे जाते हैं।
पार्सिंग क्या है (What is Parsing in Compiler Design in Hindi) ?
Parsing compiler का वह process है जिसमें source code के tokens को grammar rules के अनुसार analyze किया जाता है ताकि यह check किया जा सके कि program की syntax सही है या नहीं।
Simple words में –
Lexical Analysis tokens बनाता है और Parsing यह verify करता है कि tokens सही order में हैं या नहीं।
Example:
अगर user लिखता है:
a = b + c;
तो lexer tokens बनाता है – a , = , b , + , c , ;
अब Parsing check करता है कि यह statement grammar rules के अनुसार valid है या नहीं।
Parsing in Compiler Design – Overview
Compiler में parsing को Syntax Analysis भी कहा जाता है। यह phase grammar की help से parse tree बनाता है।
Parsing के मुख्य काम
- Tokens को grammar के साथ match करना
- Syntax error detect करना
- Parse Tree generate करना
- आगे के phases (Semantic Analysis) के लिए structure तैयार करना
अगर parsing गलत हो जाए, तो program compile ही नहीं होता।
पार्सिंग के प्रकार (Types of Parsing in Compiler Design)
Parsing in Compiler Design mainly दो categories में divide होती है 1) Top Down Parsing and 2) Bottom Up Parsing:
1. Top-Down Parsing
इस type की parsing में parse tree को root से leaves की तरफ बनाया जाता है।
कैसे काम करता है?
- Start symbol से शुरुआत होती है
- Grammar rules apply करके input string तक पहुँचते हैं
Common Techniques of Top Down Parsing
- Recursive Descent Parsing
- Predictive Parsing
- LL(1) Parsing
Example Grammar
E → T + E | T
T → id
अगर input है: id + id
तो parser start symbol E से expand करेगा।
Advantages of Top-Down Parsing
- यह parsing technique समझने और implement करने में बहुत simple होती है।
- Grammar को directly follow करता है, इसलिए beginners के लिए easy to learn होती है।
- Parse tree को root से leaves की तरफ build करता है, जिससे flow clear रहता है।
- Small grammar वाले programs के लिए efficient होती है।
- Recursive Descent Parsing के रूप में इसे आसानी से code में implement किया जा सकता है।
- Error detection early stage पर हो जाती है, जिससे debugging आसान हो जाती है।
- LL(1) parsing table use करके fast parsing possible होती है।
Disadvantages of Top-Down Parsing
- यह Left Recursion वाली grammar को handle नहीं कर सकता।
- Backtracking की जरूरत पड़ सकती है, जिससे parsing slow हो जाती है।
- Ambiguous grammar के लिए suitable नहीं होती।
- Complex grammar पर LL(1) parsing table बनाना difficult होता है।
- Large programs के लिए यह approach efficient नहीं रहती।
- Predictive parsing में grammar को पहले modify / transform करना पड़ता है, जो tedious होता है।
2. Bottom-Up Parsing
इसमें parse tree को leaves से root की तरफ बनाया जाता है।
कैसे काम करता है?
- Input symbols से शुरुआत
- धीरे-धीरे grammar के start symbol तक पहुँचना
Common Techniques of Bottom Up Parsing
- Shift Reduce Parsing
- Operator Precedence Parsing
- LR Parsing (LR(0), SLR, LALR, CLR)
Example
अगर input है: id + id
तो parser पहले id को reduce करेगा, फिर grammar rules apply करेगा।
Advantages of Bottom-Up Parsing
- यह parsing technique grammar को बहुत powerful तरीके से handle कर सकती है।
- Almost सभी प्रकार की grammar (including left-recursive) को आसानी से parse कर लेती है।
- Backtracking की जरूरत नहीं होती, इसलिए parsing faster और reliable होती है।
- LR, SLR, LALR जैसे methods के कारण यह industry-standard parsing approach मानी जाती है।
- Syntax error detection ज्यादा accurate और strong होती है।
- Complex programming languages के compilers बनाने में यह approach ज्यादा suitable होती है।
Disadvantages of Bottom-Up Parsing
- इसे समझना और implement करना काफी complex होता है, खासकर beginners के लिए।
- Parsing table और states बनाना time-consuming process है।
- LR, SLR, LALR जैसे parsers में बहुत सारी states बनती हैं, जिससे memory ज्यादा consume होती है।
- Grammar ambiguity handle करना मुश्किल हो सकता है।
- Debugging करना Top-Down parsing की तुलना में hard होता है।
- Hand-written implementation almost impractical होती है, इसलिए mostly parser generators की जरूरत पड़ती है।
यह भी पढ़ें: Lexical Analysis in Compiler Design for GATE 2026 CS&IT – Complete Guide
Difference between Parse Tree vs AST
| Basis | Parse Tree | AST |
| Definition | Grammar rules को exactly follow करके बनाया गया tree | Parse tree से simplified, unnecessary nodes हटाकर बनाया गया tree |
| Purpose | Syntax structure दिखाना | Program का actual logical structure दिखाना |
| Nodes | Terminal और Non-terminal दोनों होते हैं | Mostly only important nodes होते हैं |
| Size | Size बड़ा होता है | Compact और optimized होता है |
| Complexity | Complex और detailed | Simple और easy to process |
| Usage | Syntax checking और debugging में helpful | Semantic analysis, code generation में use होता है |
| Example | Grammar based full representation | Expression based minimal representation |
यह भी पढ़ें: Operating System Notes for GATE CS & IT 2026 – Master OS Concepts
Parsing Algorithms Important for GATE
GATE exam में कुछ parsing algorithms बहुत famous हैं:
1. LL(1) Parsing
- Top-Down parsing technique
- Look ahead = 1 token
- Parsing table based
2. LR Parsing
- Bottom-Up technique
- Most powerful parsing method
- Types: LR(0), SLR, LALR, CLR
3. Operator Precedence Parsing
- Arithmetic expressions handle करने के लिए
- Operators की precedence use करता है
GATE Exam के लिए Parsing क्यों Important है ?
Parsing, Compiler Design का सबसे scoring और repeatedly पूछा जाने वाला topic है, इसलिए यह GATE aspirants के लिए बहुत जरूरी है।
- GATE CS / IT exam में हर साल 1–2 questions directly Parsing से आते हैं।
- LL(1), LR, SLR, LALR जैसे concepts पर आधारित questions अक्सर पूछे जाते हैं।
- Parse Tree और Abstract Syntax Tree (AST) पर conceptual और numerical दोनों तरह के सवाल आते हैं।
- Syntax Analysis compiler का core part है, इसलिए इसका strong understanding पूरे subject को आसान बना देता है।
- Parsing के questions comparatively easy और less time consuming होते हैं, जिससे scoring potential ज्यादा रहता है।
- अगर Parsing अच्छे से prepare कर लिया जाए तो Compiler Design का बड़ा हिस्सा automatically cover हो जाता है।
यह भी पढ़ें: Searching Algorithms Notes for GATE CS: Complete Guide 2026 in Hindi
Parsing Questions with Answers (GATE PYQs)
Q1. Which of the following is/are Bottom-Up Parser(s)?
(A) LR Parser
(B) LL Parser
(C) Operator Precedence Parser
(D) Recursive Descent Parser
Ans. (A) LR Parser, (C) Operator Precedence Parser
Q2. Consider the augmented grammar with terminals {+, *, (, ), id}. Which parsing technique is most suitable for this grammar?
Ans. LR Parsing (Bottom-Up)
Q3. Which one of the following statements is TRUE?
(A) LL(1) parsing uses leftmost derivation
(B) LR parsing uses rightmost derivation in reverse
(C) Both LL and LR parsers can handle left recursion
(D) Recursive descent parsing is always non-deterministic
Ans. (A) and (B) are correct; LR uses rightmost derivation in reverse, LL uses leftmost derivation
Q4. Which of the following grammars can be parsed using an LL(1) parser?
(A) Left recursive grammar
(B) Ambiguous grammar
(C) Grammar with left factoring
(D) Grammar without left recursion and ambiguity
Ans. (D) Grammar without left recursion and ambiguity
Q5. In LR parsing, the conflicts that may arise are:
(A) Shift-Reduce Conflict
(B) Reduce-Reduce Conflict
(C) Left Recursion Conflict
(D) Ambiguity Conflict
Ans. (A) Shift-Reduce Conflict, (B) Reduce-Reduce Conflict
Q6. Which of the following parsers is most powerful?
(A) LL(1)
(B) LR(0)
(C) SLR(1)
(D) LALR(1)
Ans. (D) LALR(1) is more powerful than LL(1), LR(0), and SLR(1)
Q7. Recursive Descent Parsing is an example of:
(A) Top-Down Parsing
(B) Bottom-Up Parsing
(C) Operator Precedence Parsing
(D) LR Parsing
Ans. (A) Top-Down Parsing
Q8. Which of the following grammars is ambiguous?
(A) E → E + E | E * E | id
(B) E → id | id * id
(C) E → (E) | id
(D) E → E + id
Ans. (A) E → E + E | E * E | id (classic ambiguous grammar)
Q9. Predictive parsing requires:
(A) Grammar should be left recursive
(B) Grammar should be ambiguous
(C) Grammar should be left factored and non-left recursive
(D) Grammar should be operator-precedence
Ans. (C) Grammar should be left factored and non-left recursive
Q10. Which of the following parsers can handle left recursion?
(A) LL(1) Parser
(B) LR Parser
(C) Recursive Descent Parser
(D) Operator Precedence Parser
Ans. (B) LR Parser
यह भी पढ़ें: Dynamic Programming Notes for GATE 2026 CS & IT – Complete Guide
निष्कर्ष (Conclusion)
इस article में आपने Parsing in Compiler Design को step-by-step समझा – introduction से लेकर parse tree, LL(1), LR और GATE focused concepts तक। अगर आप इस topic को अच्छी तरह master कर लेते हैं, तो Compiler Design में आपके marks almost confirm हैं।
अब इस article को bookmark करें और रोज 10 मिनट revise करें – GATE 2026 में Parsing आपका strong weapon बनेगा।
यह भी पढ़ें:
