ग्राफ़-संरचित स्टैक को कैसे कार्यान्वित करें?

Question

ठीक है, इसलिए मैं एक जीएलआर पार्सर जेनरेटर बनाना चाहता हूं। मुझे पता है कि मैं ऐसे कार्यक्रमों से बेहतर हूं जो मैं शायद करूँगा, लेकिन मैं इसे मजेदार/सीखने के लिए कर रहा हूं ताकि यह महत्वपूर्ण न हो।

मैं जीएलआर पार्सिंग के बारे में पढ़ रहा हूं और मुझे लगता है कि मेरे पास अब इसकी सभ्य उच्च स्तर की समझ है। लेकिन अब यह व्यवसाय करने के लिए समय है।

ग्राफ़-संरचित स्टैक (जीएसएस) जीएलआर पार्सर्स में उपयोग के लिए महत्वपूर्ण डेटा संरचना है। संकल्पनात्मक रूप से मुझे पता है कि जीएसएस कैसे काम करता है, लेकिन अब तक जिन स्रोतों को मैंने देखा है, उनमें से कोई भी जीएसएस को कार्यान्वित करने की व्याख्या नहीं करता है। मेरे पास समर्थन के लिए संचालन की आधिकारिक सूची भी नहीं है। क्या कोई मुझे जीएसएस के लिए कुछ अच्छे नमूना कोड/ट्यूटोरियल पर इंगित कर सकता है? Google ने अब तक मदद नहीं की है। मुझे आशा है कि यह सवाल बहुत अस्पष्ट नहीं है।

Answer 1

जो सवाल आप पूछ रहे हैं वह छोटा नहीं है। मुझे ऐसा करने के दो मुख्य तरीके दिखाई देते हैं:

1. प्रत्यक्ष प्रतिनिधित्व। आपकी डेटा संरचना को स्मृति में नोड ऑब्जेक्ट्स/स्ट्रक्चर के रूप में दर्शाया गया है, जहां प्रत्येक नोड के पास स्टैक पर नीचे दिए गए structs पर संदर्भ/सूचक होता है (कोई संदर्भ के रूप में संदर्भ द्वि-दिशात्मक भी संदर्भित कर सकता है)। इस तरह सूचियों और पेड़ों को आम तौर पर स्मृति में दर्शाया जाता है। यह इस मामले में थोड़ा अधिक जटिल है, क्योंकि पेड़ या सूची के विपरीत, जहां पेड़ का ट्रैक रखने के लिए केवल रूट नोड या हेड नोड का संदर्भ बनाए रखने की आवश्यकता होती है, यहां हमें सभी के संदर्भों की एक सूची बनाए रखने की आवश्यकता होगी 'शीर्ष स्तर' नोड्स।

2. आसन्नता सूची का प्रतिनिधित्व। यह गणितज्ञों के बारे में सोचने के तरीके के समान है: जी = (वी, ई)। आप किनारों की एक सूची बनाए रखते हैं, जो कि किनारों से अनुक्रमित होते हैं जो प्रत्येक किनारे के लिए मूल और समाप्ति बिंदु होते हैं।

पहला विकल्प यह लाभ है कि ट्रैवर्सल तेज हो सकता है, जब तक कि जीएसएस बहुत सपाट न हो। लेकिन संरचना के साथ काम करना थोड़ा मुश्किल है। आपको अपने बहुत सारे एल्गोरिदम रोल करना होगा।

दूसरे विकल्प के साथ काम करने के लिए और अधिक सरल होने का लाभ है। पाठ्यपुस्तकों में अधिकांश एल्गोरिदम किसी प्रकार की आसन्नता सूची प्रतिनिधित्व मानते हैं, जो वहां ग्राफ एल्गोरिदम की संपत्ति को लागू करना आसान बनाता है।

कुछ संसाधन:

समीपता सूची, उदा के विभिन्न प्रकार

रहे हैं हैश टेबल आधारित, सरणी आधारित आदि। विकिपीडिया adjacency list पृष्ठ शुरू करने के लिए एक अच्छी जगह है।

Here's a blog post किसी ऐसे व्यक्ति से जो एक ही मुद्दे से जूझ रहा है। कोड क्लोजर है, जो परिचित हो सकता है या नहीं भी हो सकता है, लेकिन चर्चा एक लायक है, भले ही नहीं।

मुझे यह उल्लेख करना चाहिए कि मुझे लगता है कि मैं चाहता हूं कि डायरेक्टेड एसाइक्लिक ग्राफ (या ग्राफ स्ट्रक्चरर्ड स्टैक्स, यदि आप चाहें) का प्रतिनिधित्व करने के बारे में अधिक जानकारी हो, तो इस तरह के मॉडल के व्यापक आवेदन को देखते हुए। मुझे लगता है कि बेहतर समाधान खोजने के लिए एक जगह है।

Answer 2

सबसे पहले, यदि आपके पास पहले से नहीं है, तो आपको मैकपीक के पेपर को जीएलआर http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps पर पढ़ना चाहिए। यह एक अकादमिक पेपर है, लेकिन यह जीएसएस, जीएलआर, और उन्हें लागू करने के लिए उपयोग की जाने वाली तकनीकों पर अच्छा विवरण देता है। यह एक जीएलआर पार्सर को लागू करने के साथ कुछ बालों के मुद्दों को भी समझाता है।

आपके पास ग्राफ-संरचित ढेर को लागू करने के लिए तीन भाग हैं।

I. ग्राफ़ डेटा संरचना स्वयं

II। ढेर

III। जीएलआर का उपयोग जीएसएस

आप सही हैं, Google बहुत मदद नहीं है। और जब तक आप एल्गोरिदम पुस्तकें पढ़ना पसंद नहीं करते हैं, तब तक वे बहुत मदद नहीं करेंगे।

आई ग्राफ डेटा संरचना

के बारे में "प्रत्यक्ष प्रतिनिधित्व" को लागू करने के लिए सबसे आसान होगा रोब के जवाब। यह एक लिंक्ड-लिस्ट की तरह है, सिवाय इसके कि प्रत्येक नोड में केवल एक के बजाय अगले नोड्स की एक सूची है।

यह डेटा संरचना एक निर्देशित ग्राफ है, लेकिन मैकपीक के अनुसार, जीएसएस में ईपीएसलॉन-व्याकरण के लिए चक्र हो सकते हैं।

II। ढेर

एक ग्राफ-संरचित ढेर अवधारणात्मक रूप से केवल नियमित ढेर की एक सूची है। एक स्पष्ट व्याकरण के लिए, आपको केवल एक ढेर की आवश्यकता है। जब आप एक पार्सिंग टकराव करते हैं तो आपको अधिक ढेर की आवश्यकता होती है ताकि आप एक ही समय में दोनों पार्सिंग क्रियाएं कर सकें और दोनों कार्य अलग-अलग राज्य बनाए रख सकें। ग्राफ का उपयोग करने से आप इस तथ्य का लाभ उठा सकते हैं कि ये ढेर तत्व साझा करते हैं।

यह समझने में मदद कर सकता है कि पहले लिंक किए गए सूची के साथ एक स्टैक को कैसे कार्यान्वित किया जाए। लिंक्ड सूची का मुखिया ढेर का शीर्ष है। स्टैक पर एक तत्व को धक्का देना सिर्फ एक नया सिर बनाना और इसे पुराने सिर पर इंगित करना है। ढेर से एक तत्व को रोकना सिर्फ पॉइंटर को सिर पर ले जा रहा है-> अगला।

एक जीएसएस में, सिद्धांत समान है। तत्व को धक्का देना सिर्फ एक नया सिर नोड बनाना और इसे पुराने सिर पर इंगित करना है। यदि आपके पास दो शिफ्ट ऑपरेशन हैं, तो आप दो तत्वों को पुराने सिर पर धक्का देंगे और फिर दो हेड नोड्स होंगे। संकल्पनात्मक रूप से यह केवल दो अलग-अलग ढेर हैं जो शीर्ष तत्व को छोड़कर प्रत्येक तत्व को साझा करते हैं। एक तत्व को रोकना सिर्फ अगले पॉइंट्स में से प्रत्येक का पालन करके हेड पॉइंटर को स्टैक के नीचे ले जा रहा है।

III। जीएलआर का उपयोग जीएसएस

यह है जहां मैकपीक का पेपर उपयोगी पढ़ा जाता है।

जीएलआर एल्गोरिदम एक ही राज्य तत्व वाले स्टैक हेड विलय करके जीएसएस का लाभ उठाता है। इसका मतलब है कि एक राज्य तत्व में एक से अधिक बच्चे हो सकते हैं। कम करने पर, जीएलआर एल्गोरिदम को स्टैक हेड से सभी संभावित पथों का पता लगाना होगा।

आप प्रत्येक नोड की निर्धारिक गहराई को बनाए रखकर जीएलआर अनुकूलित कर सकते हैं। यह ढेर में एक विभाजन से दूरी है। इस तरह आपको हमेशा एक स्टैक स्प्लिट की खोज नहीं करना पड़ता है।

यह एक कठिन काम है! इतनी अच्छी किस्मत!