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):

Step	Stack	Input	Action
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 बना दिया है।

Symbolic Debugging of Optimized Code | ऑप्टिमाइज़्ड कोड का प्रतीकात्मक डीबगिंग

ऑप्टिमाइज़्ड कोड का प्रतीकात्मक डीबगिंग (Symbo...

Data Flow Analysis of Structured Flow Graph | स्ट्रक्चर्ड फ्लो ग्राफ का डेटा फ्लो विश्लेषण

स्ट्रक्चर्ड फ्लो ग्राफ का डेटा फ्लो विश्ले�...

Code Improving Transformations in Compiler Design | कोड सुधार परिवर्तन की उन्नत तकनीकें

कोड सुधार परिवर्तन की उन्नत तकनीकें (Code Improving Tran...

Introduction to Global Data Flow Analysis | ग्लोबल डेटा फ्लो एनालिसिस का परिचय

ग्लोबल डेटा फ्लो एनालिसिस का परिचय (Introduction to Global...

Loop Optimization | लूप ऑप्टिमाइज़ेशन

लूप ऑप्टिमाइज़ेशन (Loop Optimization in Compiler Design) Loop Optimiza...

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