रिकर्सिव डेसेंट बनाम जेनरेटेड पार्सर्स - क्षमता

Question

हाथ से लिखे गए रिकर्सिव वंश पार्सर्स (जो अनिवार्य रूप से एलएल (के) हैं, प्रदर्शन के संदर्भ में जेनरेट किए गए एलएएलआर पार्सर्स की तुलना कैसे करते हैं?

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

एनबी। मैं पूंछ-कॉल अनुकूलन (एफ #) के साथ एक कार्यात्मक भाषा का उपयोग कर रहा हूं, इसलिए [अच्छी तरह से तैयार] रिकर्सन अन्य भाषाओं में जितना अधिक मुद्दा नहीं होगा।

Answer 1

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

Answer 2

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

व्यक्तिगत रूप से, मुझे एलएएलआर व्याकरण के साथ काम करना आसान लगता है, और एफ # के fsyacc एकीकरण (जिसे मैंने पार्सिंग सीखा है) आपके प्रोजेक्ट में yacc को एकीकृत करना बहुत आसान बनाता है।