रिकर्सिव चढ़ाई पार्सर्स कैसे काम करते हैं? मैंने एक रिकर्सिव वंश खुद को पार्सर लिखा है लेकिन मुझे एलआर पार्सर्स को अच्छी तरह से समझ में नहीं आता है। मैं found on Wikipedia क्या केवल मेरे भ्रम में जोड़ा गया है।रिकर्सिव चढ़ाई पार्सर्स कैसे काम करते हैं?
एक और सवाल यह है कि रिकर्सिव चढ़ाई पार्सर्स का उपयोग उनके टेबल-आधारित समकक्षों से अधिक नहीं किया जाता है। ऐसा लगता है कि रिकर्सिव चढ़ाई पार्सर्स में कुल प्रदर्शन अधिक होता है।
क्लासिकल dragon book बहुत अच्छी तरह से बताता है कि एलआर पार्सर्स कैसे काम करते हैं। Parsing Techniques. A Practical Guide. भी है जहां आप उनके बारे में पढ़ सकते हैं, अगर मुझे अच्छी तरह याद है। विकिपीडिया में लेख (कम से कम परिचय) सही नहीं है। वे डोनाल्ड Knuth द्वारा बनाए गए थे, और वह उन्हें अपने आर्ट ऑफ कंप्यूटर प्रोग्रामिंग वॉल्यूम 5 में बताते हैं। यदि आप स्पेनिश समझते हैं, तो मेरे द्वारा पोस्ट की गई here पुस्तकों की पूरी सूची है। वह किताबें स्पेनिश में नहीं हैं, या तो।
यह समझने से पहले कि वे कैसे काम करते हैं, आपको कुछ अवधारणाओं को समझना चाहिए जैसे कि पहले, अनुसरण करें और देखो। इसके अलावा, मैं वास्तव में आपको एलआर (वंश) पार्सर्स को समझने की कोशिश करने से पहले एलएल (वंश) पार्सर्स के पीछे अवधारणाओं को समझने की सलाह देता हूं।
पार्स एलआर, विशेष रूप से एलआर (के), एसएलआर (के) और एलएएलआर (के) के परिवार हैं, जहां के काम करने के लिए उन्हें कितने दिखने की जरूरत है। Yacc एलएएलआर (1) पार्सर्स का समर्थन करता है, लेकिन आप इसे अधिक शक्तिशाली प्रकार के व्याकरण के साथ काम करने के लिए, सिद्धांत आधारित नहीं, tweaks बना सकते हैं।
प्रदर्शन के बारे में, यह व्याकरण का विश्लेषण किया जा रहा है पर निर्भर करता है। वे रैखिक समय में निष्पादित होते हैं, लेकिन उन्हें कितनी जगह चाहिए, इस पर निर्भर करता है कि आप अंतिम पार्सर के लिए कितने राज्य बनाते हैं।
वॉल्यूम 5 साल दूर है! सबसे अच्छे रूप में। मुझे आशा है कि मैं इस पृष्ठ पर 2020 में वापस आ सकता हूं या जब भी इस टिप्पणी पर हंस सकता हूं। –
मुझे व्यक्तिगत रूप से समझने में कठिनाई हो रही है कि एक फ़ंक्शन कॉल कैसे तेज हो सकता है - तालिका लुकअप से बहुत कम "काफी तेज"। और मुझे संदेह है कि लेक्सर/पार्सर को अन्य सभी चीजों की तुलना में "काफी तेज़" भी महत्वहीन होता है (मुख्य रूप से फ़ाइल को पढ़ना और टोकन करना)। मैंने विकिपीडिया पेज को देखा, लेकिन संदर्भों का पालन नहीं किया; क्या लेखक वास्तव में एक पूर्ण लेक्सर/पार्सर प्रोफाइल करते थे?
मेरे लिए अधिक दिलचस्प है रिकर्सिव वंश के संबंध में टेबल-संचालित पार्सर्स की गिरावट। मैं एक सी पृष्ठभूमि से आया हूं, जहां yacc (या समतुल्य) पसंद का पार्सर जनरेटर था। जब मैं जावा में स्थानांतरित हुआ, तो मुझे एक टेबल-संचालित कार्यान्वयन (जावाकप), और कई पुनरावर्ती मूल कार्यान्वयन (जावासीसी, एएनटीएलआर) मिला।
मुझे संदेह है कि उत्तर "सी के बजाय जावा क्यों" के जवाब के समान है: निष्पादन की गति विकास की गति जितनी महत्वपूर्ण नहीं है। जैसा कि विकिपीडिया लेख में उल्लेख किया गया है, तालिका-संचालित पार्सर कोड से समझने के लिए बहुत असंभव हैं (जब मैं उनका उपयोग कर रहा था, मैं उनके कार्यों का पालन कर सकता था लेकिन पार्सर से व्याकरण का पुनर्निर्माण करने में कभी सक्षम नहीं होता)। तुलनात्मक रूप से रिकर्सिव वंश, बहुत सहज है (इसमें कोई संदेह नहीं है कि यह कुछ 20 वर्षों तक टेबल-संचालित क्यों करता है)।
मेरे द्वारा +1 - वास्तव में एक अच्छा जवाब। – duffymo
रिकर्सिव वंश तालिका संचालित एलआर पार्सर्स से धीमा है। मैं रिकर्सिव चढ़ाई के बारे में सोच रहा हूं जो एक अलग जानवर है। –
हां, लेख प्रति पुनरावर्ती चढ़ाई में एक चर और फ़ंक्शन की बजाय राज्य मशीन का प्रतिनिधित्व करने के लिए इनलाइन फ़ंक्शन कॉल हैं। और जैसा कि मैंने अपने पहले पैराग्राफ में कहा था, मैं यह नहीं खरीद रहा हूं कि यह तेज़ है, खासकर एक पार्सर का उपयोग कैसे किया जाता है इसके संदर्भ में। – kdgregory
रिकर्सिव चढ़ाई पर विकिपीडिया लेख पार्सिंग संदर्भ जो इस विषय पर मूल पेपर ("बहुत तेज़ एलआर पार्सिंग") प्रतीत होता है। उस पत्र को स्किम करने से मेरे लिए कुछ चीजें साफ हो गईं। जिन चीजों को मैंने देखा:
असेंबली कोड उत्पन्न करने के बारे में पेपर वार्ता। मुझे आश्चर्य है कि अगर आप सी या जावा कोड उत्पन्न कर रहे हैं तो आप वही काम कर सकते हैं; खंड 4 और 5, "त्रुटि पुनर्प्राप्ति" और "ढेर ओवरफ़्लो जांच" देखें। (मैं अपनी तकनीक को एफयूडी करने की कोशिश नहीं कर रहा हूं - यह ठीक काम कर सकता है - सिर्फ यह कह रहा है कि ऐसा कुछ ऐसा है जिसे आप करने से पहले देखना चाहते हैं।)
वे अपने रिकर्सिव चढ़ाई उपकरण की तुलना अपने स्वयं के टेबल-संचालित पार्सर से करते हैं। उनके परिणाम खंड में विवरण से, ऐसा लगता है कि उनके टेबल-संचालित पार्सर "पूरी तरह से व्याख्या" है; इसे किसी भी कस्टम जेनरेट कोड की आवश्यकता नहीं है। मुझे आश्चर्य है कि क्या एक मध्यम जमीन है जहां समग्र संरचना अभी भी टेबल संचालित है लेकिन आप चीजों को गति देने के लिए कुछ कार्यों के लिए कस्टम कोड उत्पन्न करते हैं।
कागज विकिपीडिया पृष्ठ द्वारा संदर्भित:
तालिका के बजाय कोड पीढ़ी के उपयोग के बारे में एक और कागज - व्याख्या:
इसके अलावा, ध्यान दें कि रिकर्सिव-डिसेंट पार्स डालूँगा-व्याकरण आधारित भाषाओं पार्स करने के लिए सबसे तेज़ तरीका नहीं है "(बहुत कम प्रयास के लिए) बहुत तेजी से YACC संगत पारसर्स":
+1 मैं एक ही बात सोच रहा की है। रिकर्सिव वंश पार्सर्स को समझना इतना आसान है, लेकिन सही होने के लिए बहुत मुश्किल है। एलआर पार्सर्स जेनरेटर (जैसे वाईएसीसी) के साथ लिखना आसान है, लेकिन मैंने कभी नहीं समझा है कि यह "हुड के नीचे" कैसे काम करता है। – Zifre
हैप्पी "अच्छा सवाल" बैज :) –