Bottom-Up Parsing and Operator Precedence Parsing | बॉटम-अप पार्सिंग और ऑपरेटर प्रीसीडेंस पार्सिंग - Compiler Design Notes 2025


बॉटम-अप पार्सिंग और ऑपरेटर प्रीसीडेंस पार्सिंग (Bottom-Up Parsing and Operator Precedence Parsing)

Syntax Analysis में दो प्रमुख पार्सिंग तकनीकें होती हैं — Top-Down Parsing और Bottom-Up Parsing। जहाँ Top-Down Parsing पार्स ट्री को ऊपर से नीचे बनाती है, वहीं Bottom-Up Parsing leaves से शुरू होकर root की ओर बढ़ती है। यह तकनीक सबसे शक्तिशाली और आमतौर पर प्रयोग की जाने वाली विधि है।

📘 Bottom-Up Parsing क्या है?

Bottom-Up Parsing वह प्रक्रिया है जिसमें input string को grammar rules के अनुसार धीरे-धीरे reduce करते हुए start symbol में बदला जाता है। इस प्रक्रिया को Shift-Reduce Parsing भी कहा जाता है।

मुख्य सिद्धांत:

  • Parsing process leaves से root की ओर चलता है।
  • Input को symbols के समूह में divide करके reductions किए जाते हैं।
  • Parse Tree को धीरे-धीरे ऊपर की ओर build किया जाता है।

⚙️ Shift-Reduce Parsing:

Shift-Reduce Parser सबसे सामान्य Bottom-Up Parser है। यह input string को stack और input buffer का उपयोग करके parse करता है। चार मुख्य क्रियाएँ होती हैं:

  • 🔹 Shift: Input symbol को stack पर push करना।
  • 🔹 Reduce: Stack के symbols को grammar के production rule से match करके non-terminal में बदलना।
  • 🔹 Accept: जब stack में केवल start symbol रह जाए और input समाप्त हो जाए।
  • 🔹 Error: कोई valid reduction संभव न हो।

📗 उदाहरण:

Grammar:

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

Input: id + id * id

Parsing Table (Simplified):

StepStackInputAction
1$id + id * id$Shift
2$ id+ id * id$Reduce F → id
3$ F+ id * id$Reduce T → F
4$ T+ id * id$Reduce E → T
5$ E+ id * id$Shift
6$ E +id * id$Shift
7$ E + id* id$Reduce F → id
8$ E + F* id$Reduce T → F
9$ E + T* id$Shift
10$ E + T *id$Shift
11$ E + T * id$Reduce F → id
12$ E + T * F$Reduce T → T * F
13$ E + T$Reduce E → E + T
14$ E$Accept ✅

🧩 Handle Pruning (Handle Concept):

Handle input string का वह भाग होता है जिसे grammar के production rule से replace किया जा सकता है। Shift-Reduce Parsing का उद्देश्य हर चरण में सही handle को पहचानना और reduce करना होता है।

📘 Handle Example:

E + E * E
→ Handle: E * E → Reduced to T
→ Handle: E + T → Reduced to E

⚙️ Operator Precedence Parsing:

Operator Precedence Parsing Bottom-Up Parsing का एक विशेष रूप है जो उन grammars पर लागू होता है जिनमें operators (+, -, *, /) की precedence और associativity स्पष्ट रूप से परिभाषित होती है।

📘 Operator Precedence Grammar:

ऐसी grammar जिसमें:

  • कोई ε-productions न हों।
  • कोई दो adjacent non-terminals न हों।

उदाहरण:

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

📊 Operator Precedence Table:

Operator+*()id$
+><<><>
*>><><>
(<<<=<
)>> > >
id>> > >
$<<< <

📗 Parsing Example (Operator Precedence):

Input: id + id * id

Stack       | Input         | Action
-----------------------------------------
$ id        | + id * id $   | Shift
$ id +      | id * id $     | Shift
$ id + id   | * id $        | Reduce E → id
$ E +       | * id $        | Shift
$ E + *     | id $          | Shift
$ E + * id  | $             | Reduce E → id
$ E + E * E | $             | Reduce E → E + E * E
Accept ✅

🚀 आधुनिक उपयोग (Bottom-Up Parsing in 2025):

  • 🔹 LR(1) Parser Generators जैसे YACC, Bison।
  • 🔹 Machine Learning आधारित Error Recovery।
  • 🔹 Cloud Compiler Tools में optimized parsing engines।

📙 निष्कर्ष:

Bottom-Up Parsing सबसे शक्तिशाली parsing तकनीक है जो large-scale compilers में प्रयोग होती है। Operator Precedence Parsing arithmetic expressions के लिए तेज़ और प्रभावी विधि है। 2025 में, AI-सक्षम parser generators ने इन तकनीकों को और अधिक स्मार्ट व error-tolerant बना दिया है।

Related Post