स्कैला पार्सर कॉम्बिनेटर, संदिग्ध व्याकरण और पारसे वन

Question

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

स्कैला और उसके पार्सर कॉम्बिनेटर्स दोनों के लिए नया होने के नाते, मैं यह नहीं समझ सकता कि यह कैसे करें या यह बिल्कुल किया जा सकता है या नहीं। क्या कोई मदद कर सकता है? बहुत सराहना की।

सादर, थॉमस जुआन

Answer 1

आप के साथ ऐसा नहीं कर सकते स्काला के अंतर्निहित पार्सर combinators। पैक्रेट संयोजक केवल स्पष्ट व्याकरण तक ही सीमित हैं। यदि आप अस्पष्टता से निपटने का प्रयास करते हैं, तो आप याद रखने की क्षमता खो देते हैं और पार्स जटिलता ओ (के^एन) भी अस्पष्ट ट्रेल्स के लिए बन जाती है। तो, ऐसा मत करो।

आप जो चाहते हैं वह एक पार्सर संयोजक ढांचा है जो सही ढंग से अस्पष्टता को संभालता है। जहां तक ​​मुझे पता है, स्कैला के लिए एकमात्र ऐसा ढांचा मेरा GLL combinators है। सिंटैक्स लगभग स्कैला के पार्सर संयोजकों के समान है (मुख्य अंतर यह है कि उच्च-धर्मार्थ कार्य सही ढंग से) काम करते हैं, लेकिन आउटपुट Stream[A] है, जहां A परिणाम प्रकार है। इस प्रकार, आपको एक पार्स वन मिलता है। ध्यान दें कि नतीजा वास्तव में एक एसपीपीएफ (साझा पैक पार्स वन) नहीं है, इसलिए यदि आप परिणामों की घातीय संख्या उत्पन्न करते हैं, तो धारा आनुपातिक आकार का होगा। यह परिणाम प्रकार में अंतिम लचीलापन बनाए रखने के लिए किया गया था।

जीएलएल संयोजक ओ (एन^3) में सबसे खराब मामले है, यहां तक ​​कि रोगजनक रूप से संदिग्ध व्याकरण के लिए भी। औसत मामले में, जहां पार्स ट्रेल अस्पष्ट है, जीएलएल संयोजक ओ (एन) है। निरंतर समय ओवरहेड वर्तमान में थोड़ा अधिक है, लेकिन अनुकूलन एक चल रही परियोजना है। हम Precog पर उत्पादन में जीएलएल संयोजकों का उपयोग करते हैं, ताकि आप लाइब्रेरी को आगे बढ़ने के लिए अच्छी तरह से बनाए रखा जा सके।