पुशडाउन ऑटोमेटा और पार्सिंग
एक व्याकरण के उत्पादन नियमों का उपयोग करके स्ट्रिंग को प्राप्त करने के लिए पार्सिंग का उपयोग किया जाता है। यह एक स्ट्रिंग की स्वीकार्यता की जांच करने के लिए उपयोग किया जाता है। कंपाइलर का उपयोग यह जांचने के लिए किया जाता है कि कोई स्ट्रिंग वाक्यात्मक रूप से सही है या नहीं। एक पार्सर इनपुट लेता है और एक पार्स ट्री बनाता है।
एक पार्सर दो प्रकार का हो सकता है -
Top-Down Parser - टॉप-डाउन पार्सिंग स्टार्ट-सिंबल के साथ ऊपर से शुरू होता है और पार्स ट्री का उपयोग करके एक स्ट्रिंग प्राप्त करता है।
Bottom-Up Parser - बॉटम-अप पार्सिंग स्ट्रिंग के साथ नीचे से शुरू होती है और पार्स ट्री का उपयोग करके स्टार्ट सिंबल पर आती है।
टॉप-डाउन पार्सर का डिज़ाइन
टॉप-डाउन पार्सिंग के लिए, एक पीडीए में निम्नलिखित चार प्रकार के संक्रमण होते हैं -
स्टैक के शीर्ष पर उत्पादन के बाएं हाथ पर गैर-टर्मिनल को पॉप करें और इसके दाहिने हाथ की ओर स्ट्रिंग को धक्का दें।
यदि स्टैक का शीर्ष प्रतीक पढ़ा जा रहा इनपुट प्रतीक से मेल खाता है, तो इसे पॉप करें।
स्टैक में प्रारंभ प्रतीक 'S' को दबाएं।
यदि इनपुट स्ट्रिंग पूरी तरह से पढ़ी गई है और स्टैक खाली है, तो अंतिम स्थिति 'एफ' पर जाएं।
उदाहरण
निम्नलिखित उत्पादन नियमों के साथ व्याकरण जी के लिए अभिव्यक्ति "x + y * z" के लिए एक टॉप-डाउन पार्सर डिज़ाइन करें -
P: S → S + X | एक्स, एक्स → एक्स * वाई | वाई, वाई → (एस) | ईद
Solution
यदि PDA है (Q, ∑, S, (, q 0 , I, F), तो ऊपर-नीचे पार्स है -
(x + y * z, I) ⊢ (x + y * z, SI) z (x + y * z, S + XI) ⊢ (x + y * z, X + XI)
Y (x + y * z, Y + XI) x (x + y * z, x + XI) y (+ y * z, + XI) y (y * z, XI)
, (Y * z, X * YI) y (y * z, y * YI) ⊢ (* z, * YI) z (z, YI) z (z, zI) ⊢ (ε, I)
एक बॉटम-अप पार्सर का डिज़ाइन
नीचे-ऊपर पार्सिंग के लिए, एक पीडीए में निम्नलिखित चार प्रकार के संक्रमण होते हैं -
स्टैक में वर्तमान इनपुट प्रतीक को पुश करें।
स्टैक के शीर्ष पर किसी प्रोडक्शन के राइट-हैंड साइड को उसके लेफ्ट-हैंड साइड से बदलें।
यदि स्टैक तत्व का शीर्ष वर्तमान इनपुट प्रतीक के साथ मेल खाता है, तो इसे पॉप करें।
यदि इनपुट स्ट्रिंग पूरी तरह से पढ़ी गई है और केवल तभी जब स्टार्ट सिंबल 'S' स्टैक में रहता है, तो इसे पॉप करें और अंतिम स्थिति 'F' पर जाएं।
उदाहरण
निम्नलिखित उत्पादन नियमों के साथ व्याकरण जी के लिए अभिव्यक्ति "x + y * z" के लिए एक टॉप-डाउन पार्सर डिज़ाइन करें -
P: S → S + X | एक्स, एक्स → एक्स * वाई | वाई, वाई → (एस) | ईद
Solution
यदि PDA है (Q, (, S, (, q 0 , I, F), तो नीचे-ऊपर पार्स है -
(x + y * z, I) ⊢ (+ y * z, xI) z (+ y * z, YI) z (+ y * z, XI) z (+ y * z, SI)
Z (y * z, + SI) ⊢ (* z, y + SI) z (* z, Y + SI) z (* z, X + SI) ⊢ (z, * X + SI)
Ε (⊢, z * X + SI) ε (Y, Y * X + SI) ε (SI, X + SI) ⊢ (ε, SI)