💻 computer science

An Empirical Comparison of General Context-Free Parsers

यह शोध पत्र रस्ट (Rust) में कार्यान्वित छह सामान्य संदर्भ-मुक्त पार्सिंग एल्गोरिदम के पहले एकीकृत बेंचमार्क को प्रस्तुत करता है, जो यह प्रदर्शित करता है कि GLR परिवार पूर्ण भाषा अभिव्यक्ति का समर्थन करते हुए नियतकालिक LR(1) पार्सरों की तुलना में केवल 3x मध्यम प्रदर्शन ओवरहेड का भार वहन करके सॉफ्टवेयर इंजीनियरिंग उपकरणों के लिए एक व्यावहारिक डिफ़ॉल्ट विकल्प प्रदान करता है।

मूल लेखक: Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, Rahul Gopinath

प्रकाशित 2026-06-09

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, Rahul Gopinath

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक अनुवादक हैं जो किसी विदेशी भाषा (सोर्स कोड) को ऐसी चीज़ में बदलना चाहते हैं जिसे कंप्यूटर समझ सके। इस प्रक्रिया को पार्सिंग (parsing) कहा जाता है।

दशकों से, सॉफ्टवेयर इंजीनियरों द्वारा उपयोग किए जाने वाले अनुवादक कठोर, नियमों से बंधे रोबोटों की तरह थे। वे अविश्वसनीय रूप से तेज़ थे, लेकिन वे बहुत ही नखरेबाज़ भी थे। यदि आपके द्वारा दी गई भाषा में थोड़ा सा भी अस्पष्टता या जटिल वाक्य संरचना होती, तो रोबोट काम करने से मना कर देता था। रोबोट को खुश करने के लिए, इंजीनियरों को भाषा को "हैक" करने में घंटों बिताने पड़ते थे—वाक्यों को फिर से लिखना, प्राकृतिक संरचनाओं को हटाना, और व्याकरण को इस तरह मरोड़ना ताकि वह रोबोट के संकीर्ण नियमों में फिट हो सके। यह एक गोल लकड़ी के टुकड़े को चौकोर सांचे में डालने जैसा था क्योंकि आपके पास केवल चौकोर सांचा ही उपलब्ध था।

इस कारण से, कई इंजीनियरों ने पूरी तरह से इन औपचारिक रोबोटों का उपयोग करना छोड़ दिया और अपने स्वयं के अनुवादक हाथ से बनाना शुरू कर दिया। ये हाथ से बने अनुवादक अक्सर त्रुटिपूर्ण (buggy), रखरखाव में कठिन और असुरक्षित होते हैं।

बड़ा सवाल
वर्षों तक, यह विश्वास था कि "सामान्य" (General) पार्सर—वे अनुवादक जो बिना किसी हैकिंग के किसी भी भाषा संरचना को संभाल सकते हैं—उपयोगी होने के लिए बहुत धीमे थे। उन्हें सख्त रोबोटों की तुलना में एक धीमे, अनाड़ी दैत्य की तरह माना जाता था।

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

धावक
उन्होंने छह अलग-अलग रणनीतियों का परीक्षण किया:

मैट्रिक्स मूवर्स (CYK और Valiant): ये एक विशाल ग्रिड को भरने के माध्यम से पहेली को हल करने की कोशिश करते हैं।
टॉप-डाउन एक्सप्लोरर्स (Earley और GLL): ये ऊपर से नीचे की ओर संरचना का अनुमान लगाने की कोशिश करते हैं, और एक साथ कई रास्तों की खोज करते हैं।
बॉटम-अप बिल्डर्स (RNGLR और BRNGLR): ये ज़मीन से ऊपर की ओर संरचना का निर्माण करते हैं, और संघर्षों को संभालने के लिए एक साथ कई रास्तों पर अपना ध्यान केंद्रित करते हैं।
सख्त रोबोट (LL(1) और LR(1)): पुराने ज़माने के, तेज़-लेकिन नखरेबाज़ पार्सर।

परिणाम: चौंकाने वाला विजेता

"अनाड़े दैत्य" (CYK और Valiant): ये बहुत खराब थे। वे इतने धीमे थे कि वास्तविक दुनिया के कार्यों के लिए लगभग बेकार थे। वे एक शहर के बीच से टैंक चलाने की कोशिश करने जैसे हैं; वे यहाँ ठीक से काम नहीं करते।
"टॉप-डाउन एक्सप्लोरर्स" (Earley और GLL):
- Earley सबसे धीमा था।
- GLL कुछ भाषाओं पर तेज़ था लेकिन अन्य भाषाओं पर बहुत धीमा और मेमोरी-खपत वाला हो गया। यह एक ऐसे धावक की तरह था जो सीधे ट्रैक पर तो महान है लेकिन घुमावदार रास्ते पर अपने ही पैरों में उलझकर गिर जाता है।
"बॉटम-अप बिल्डर्स" (RNGLR और BRNGLR): ये चैंपियन थे।
- ये सभी "सामान्य" पारर्स में सबसे तेज़ थे।
- ये मेमोरी के मामले में भी अविश्वसनीय रूप से कुशल थे, और लगभग सख्त रोबोटों जितना ही कम मेमोरी का उपयोग करते थे।
- बड़ा खुलासा: जब भाषा इतनी सरल थी कि सख्त रोबोटों के लिए उपयुक्त थी, तो ये नए "सामान्य" पार्सर केवल 3 गुना धीमे थे। लेखक तर्क देते हैं कि बिना हैकिंग के किसी भी भाषा को संभालने की क्षमता के लिए 3 गुना धीमा होना एक बहुत छोटी कीमत है।

"ग्रामर हैकिंग" का जाल
पेपर ने यह भी देखा कि क्या होता है जब आप सख्त रोबोटों में फिट होने के लिए किसी भाषा को "हैक" करने की कोशिश करते हैं।

गति: हाँ, सख्त रोबोट को फिट करने के लिए भाषा को हैक करने से यह 4 से 7 गुना तेज़ हो जाता है।
नुकसान: लेकिन, भाषा को हैक करना अक्सर नए "सामान्य" पार्सरों के लिए सबसे खराब स्थिति पैदा कर देता है। यह अपने पसंदीदा खिलाड़ी को जिताने के लिए खेल के नियम बदलने जैसा है, लेकिन अनजाने में यह खेल को बाकी सभी के लिए खेलने के अयोग्य बना देता है।
फैसला: लेखक कहते हैं कि आपको थोड़ी सी अतिरिक्त गति निकालने के लिए अपनी भाषा को हैक नहीं करना चाहिए। "सामान्य" पार्सर लगभग हर चीज़ के लिए पर्याप्त तेज़ हैं, और भाषा को हैक करने से उसे पढ़ना और बनाए रखना कठिन हो जाता है।

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

यह पेपर साबित करता है कि यह चुनाव एक मिथक है। नए "सामान्य" पार्सर (विशेष रूप से GLR परिवार) डिफ़ॉल्ट विकल्प बनने के लिए पर्याप्त तेज़ हैं। वे एक यूनिवर्सल अडैप्टर की तरह हैं: वे लगभग किसी भी प्लग में फिट हो जाते हैं, और हालांकि वे एक विशिष्ट अडैप्टर की तुलना में थोड़े भारी हो सकते हैं, वे आपको हर एक डिवाइस के लिए अलग अडैप्टर खरीदने से बचाते हैं।

संक्षेप में: पुराने, नखरेबाज़ पार्सरों में फिट होने के लिए अपनी भाषाओं को हैक करना बंद करें। नए, लचीले "सामान्य" पार्सर का उपयोग करें। वे तेज़ हैं, वे कम मेमोरी का उपयोग करते हैं, और वे आपको अपनी भाषाओं को स्वाभाविक रूप से लिखे जाने देने की अनुमति देते हैं।

तकनीकी सारांश: सामान्य संदर्भ-मुक्त पार्सर्स का एक अनुभवजन्य तुलनात्मक अध्ययन

समस्या विवरण

पार्सिंग (Parsing) सॉफ्टवेयर इंजीनियरिंग टूल्स का एक मौलिक घटक है, जिसमें कंपाइलर, स्टैटिक एनालाइजर, लैंग्वेज सर्वर्स और फज़र्स शामिल हैं। हालांकि, तैनात किए गए पार्सर्स का विशाल बहुमत संदर्भ-मुक्त भाषाओं (context-free languages) के नियतात्मक उपवर्गों (deterministic subclasses) जैसे कि LL या LR तक ही सीमित है। यह सीमा डेवलपर्स को "ग्रामर हैकिंग" (grammar hacking) करने के लिए मजबूर करती है—यानी लेफ्ट रिकर्सन (left recursion) को हटाने, शिफ्ट-रिड्यूस संघर्षों (shift-reduce conflicts) को हल करने, या पार्सर की बाधाओं को संतुष्ट करने के लिए भाषा की संरचनाओं को बदलने के लिए व्याकरण को मैन्युअल रूप से फिर से लिखना। यह प्रक्रिया अक्सर भाषा की अभिव्यक्ति क्षमता (expressiveness) का बलिदान देती है, रखरखाव का बोझ बढ़ाती है, और डेवलपर्स को औपचारिक पार्सिंग के बजाय हाथ से लिखे गए (hand-written) पार्सर्स को अपनाने की ओर ले जाती है, जो सूक्ष्म बगों और सुरक्षा कमजोरियों के प्रति संवेदनशील होते हैं।

जबकि सामान्य संदर्भ-मुक्त पार्सर्स (जैसे CYK, Earley, GLR, GLL) बिना किसी संशोधन के किसी भी संदर्भ-मुक्त व्याकरण को स्वीकार कर सकते हैं, उन्हें ऐतिहासिक रूप से उनके $O(n^3)$ के वर्स्ट-केस कॉम्प्लेक्सिटी (worst-case complexity) के कारण अव्यवहारिक माना गया है। दशकों के एल्गोरिदम विकास के बावजूद, प्रमुख पार्सिंग एल्गोरिदम परिवारों के बीच कोई कठोर, आमने-सामने की तुलना नहीं की गई है। मौजूदा मूल्यांकन अक्सर संकीर्ण होते हैं, जो अलग-अलग कार्यान्वयन भाषाओं, डेटा संरचनाओं या आउटपुट निरूपणों का उपयोग करते हैं, जिससे प्रत्यक्ष तुलना असंभव हो जाती है। फलस्वरूप, यह गलत धारणा कि सामान्यीकृत पार्सिंग अत्यधिक महंगी है, निर्विवाद बनी हुई है।

कार्यप्रणाली (Methodology)

इस अंतर को दूर करने के लिए, लेखकों ने छह सामान्यीकृत पारर्सिंग एल्गोरिदम के साथ-साथ नियतात्मक LL(1) और LR(1) बेसलाइन के एक एकीकृत, नियंत्रित बेंचमार्क को लागू किया।

मूल्यांकित एल्गोरिदम:
- नियतात्मक बेसलाइन (Deterministic Baselines): LL(1) और LR(1)।
- सामान्यीकृत (ऑनलाइन, टॉप-डाउन): Earley और Generalized LL (GLL)।
- सामान्यीकृत (ऑनलाइन, बॉटम-अप): Right-Nulled GLR (RNGLR) और Binary RNGLR (BRNGLR)।
- सामान्यीकृत (ऑफलाइन, बॉटम-अप): CYK और Valiant (Method of Four Russians का उपयोग करके)।
कार्यान्वयन (Implementation): सभी पार्सर्स को कार्यान्वयन संबंधी विसंगतियों को समाप्त करने के लिए एक ही फ्रेमवर्क के भीतर Rust में लागू किया गया था। वे समान व्याकरण निरूपण, टोकन-स्ट्रीम प्रारूप, AST संरचनाएं और मेमोरी प्रबंधन रणनीतियां साझा करते हैं। सभी कार्यान्वयन समान ऑप्टिमाइज़ेशन सेटिंग्स (--release) के साथ कंपाइल किए गए थे।
बेंचमार्क: अध्ययन में 22 व्याकरणों का मूल्यांकन किया गया, जिनमें सरल एक्सप्रेशन और JSON से लेकर पूर्ण-स्तरीय प्रोग्रामिंग भाषाएं (C++, Java, ANSI C, Pascal, SQL, आदि) शामिल हैं।
- नियतात्मक बेसलाइन के लिए, व्याकरणओं को LL(1) या LR(1) बाधाओं को पूरा करने के लिए रिफैक्टर (refactor) किया गया था (लेफ्ट रिकर्सन एलिमिनेशन, लेफ्ट-फैक्टरिंग, रूल स्प्लिटिंग)।
- सामान्यीकृत पार्सर्स ने मूल, बिना संशोधित व्याकरणों का उपयोग किया।
इनपुट: टेस्ट इनपुट को बाउंडेड-डेप्थ ग्रामर-बेस्ड फज़िंग के माध्यम से जनरेट किया गया था। इनपुट साइज को इस तरह सीमित किया गया था कि सबसे तेज़ पार्सर एक सेकंड के भीतर पूरा हो सके।
मेट्रिक्स: सिस्टम शोर (noise) को कम करने के लिए कई पुनरावृत्तियों (iterations) में मीडियन रनटाइम (मिलीसेकंड) और पीक मेमोरी उपयोग (MB) द्वारा प्रदर्शन को मापा गया।

मुख्य योगदान

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

परिणाम

1. ऑफलाइन सामान्यीकृत पार्सर (CYK और Valiant)

Valiant की बेहतर एसिम्प्टोटिक कॉम्प्लेक्सिटी ( $O(n^3 / \log n)$ ) होने के बावजूद, CYK ( $O(n^3)$ ) की तुलना में, व्यावहारिक रूप से Valiant बहुत धीमा था (उदाहरण के लिए, विशिष्ट इनपुट पर 330× धीमा)। दोनों ऑफलाइन एल्गोरिदम 100 टोकन से कम के इनपुट के लिए भी अव्यवहारिक साबित हुए। Earley दोनों ऑफलाइन एल्गोरिदम की तुलना में काफी बेहतर रहा, जो यह सुझाव देता है कि ऑफलाइन मैट्रिक्स-मल्टीप्लिकेशन दृष्टिकोण विशिष्ट सॉफ्टवेयर इंजीनियरिंग कार्यों के लिए व्यवहार्य नहीं हैं।

2. ऑनलाइन सामान्यीकृत पार्सर (Earley, GLL, RNGLR, BRNGLR)

RNGLR और BRNGLR: ये लगातार सबसे तेज़ सामान्यीकृत पार्सर रहे, जो आमतौर पर GLL की तुलना में 2–3× और Earley की तुलना में 4–10× तेज़ थे। वे आपस में (15% रनटाइम अंतर के भीतर) लगभग समान थे।
GLL: प्रदर्शन व्याकरण की संरचना के प्रति अत्यधिक संवेदनशील था। GLL LL-फ्रेंडली (राइट-रिकर्सिव) इनपुट पर प्रतिस्पर्धी था, लेकिन लेफ्ट-रिकर्सिव व्याकरणओं पर गंभीर रूप से खराब प्रदर्शन किया (जैसे, लेफ्ट-रिकर्सिव JSON पर RNGLR से 20× धीमा)।
Earley: सभी व्याकरणओं में लगातार सबसे धीमा सामान्यीकृत पार्सर रहा।

3. नियतात्मक बनाम सामान्यीकृत पार्सर

रनटाइम ओवरहेड: नियतात्मक व्याकरणओं पर, GLR परिवार (RNGLR/BRNGLR) ने LR(1) की तुलना में केवल 3× मीडियन स्लोडाउन दर्ज किया, जिसका विचरण (variance) बहुत कम और अनुमानित था (Interquartile Range ±0.2×)।
GLL विचरण: GLL ने बहुत अधिक विचरण दिखाया, जिसमें मीडियन 6× ओवरहेड और लेफ्ट-रिकर्सिव व्याकरणओं पर 139× का वर्स्ट-केस स्लोडाउन देखा गया।
मेमोरी: नियतात्मक पार्सर और GLR वेरिएंट्स ने सभी इनपुट साइज के लिए नगण्य मेमोरी उपयोग बनाए रखा (~0.016 MB के मेजरमेंट फ्लोर पर)। इसके विपरीत, GLL ने पर्याप्त मेमोरी वृद्धि प्रदर्शित की (Pascal पर 12.5 MB तक), जबकि Earley मध्यम लेकिन GLR से अधिक रहा।

4. ग्रामर रिफैक्टरिंग (ग्रामर हैकिंग)

नियतात्मक लाभ: व्याकरण को LL(1) या LR(1) में रिफैक्टर करने से उस विशिष्ट व्याकरण रूप के लिए सर्वश्रेष्ठ सामान्यीकृत पार्सर की तुलना में निरंतर 4–7× स्पीडअप प्राप्त हुआ।
संरचना संवेदनशीलता: व्याकरण की संरचना सामान्यीकृत पार्सर को महत्वपूर्ण रूप से प्रभावित करती है। RNGLR लेफ्ट-रिकर्सन से लाभान्वित होता है लेकिन राइट-रिकर्सन पर घटता है; GLL इसके विपरीत व्यवहार करता है। LL(1) को संतुष्ट करने के लिए व्याकरण को रिफैक्टर करना (राइट-रिकर्सन पेश करना) अनजाने में GLR पार्सर्स को दंडित कर सकता है जबकि GLL की मदद कर सकता है।
अस्पष्टता (Ambiguity): यदि अंतर्निहित रिकर्सन संरचना स्थिर रहती है, तो रिकर्सिव नियमों में अस्पष्टता जोड़ने का सामान्यीकृत पार्सर्स पर नगण्य रनटाइम प्रभाव पड़ा।

महत्व और दावे

यह पेपर तर्क देता है कि सामान्यीकरण की लागत उतनी अधिक नहीं है जितनी व्यापक रूप से मानी जाती है। विशेष रूप से:

GLR एक व्यावहारिक डिफ़ॉल्ट है: सामान्यीकृत पार्सर्स के बीच, GLR परिवार (RNGLR/BRNGLR) गति और मेमोरी दक्षता का सबसे अच्छा संयोजन प्रदान करता है। LR(1) पर इसका 3× मीडियन ओवरहेड सॉफ्टवेयर इंजीनियरिंग टूल्स (कंपाइलर, लैंग्वेज सर्वर, स्टैटिक एनालाइजर) की एक विस्तृत श्रृंखला के लिए स्वीकार्य माना जाता है।
ग्रामर हैकिंग ट्रेड-ऑफ: जबकि ग्रामर हैकिंग नियतात्मक पार्सिंग को सक्षम करके महत्वपूर्ण प्रदर्शन लाभ (4–7×) अनलॉक कर सकती है, यह रखरखाव की लागत और नाजुकता भी लाती है। लेखक सुझाव देते हैं कि अधिकांश टूल्स के लिए, मामूली GLR ओवरहेड रिफैक्टर्ड व्याकरणओं की जटिलता की तुलना में बेहतर है।
एल्गोरिदम चयन:
- RNGLR/BRNGLR: उन टूल्स के लिए अनुशंसित है जो व्याकरण लचीलेपन को प्राथमिकता देते हैं।
- LL(1)/LR(1): केवल उन टूल्स के लिए अनुशंसित है जिन्हें अधिकतम थ्रूपुट की आवश्यकता है जहाँ व्याकरण को सख्ती से नियतात्मक रखा जा सकता है।
- GLL: एक उचित विकल्प है यदि टॉप-डाउन आर्किटेक्चरल स्टाइल की आवश्यकता है, बशर्ते कि लेफ्ट-रिकर्सन की समस्याओं से बचने के लिए व्याकरण के रूप को सावधानीपूर्वक चुना गया हो।
- Earley/CYK/Valiant: खराब प्रदर्शन या अव्यवहारिकता के कारण इस संदर्भ में प्रोडक्शन उपयोग के लिए अनुशंसित नहीं हैं।

अध्ययन निष्कर्ष निकालता है कि सामान्यीकृत पार्सिंग, विशेष रूप से GLR, एक सुरक्षित और कुशल डिफ़ॉल्ट है जो प्रतिबंधात्मक व्याकरण इंजीनियरिंग की आवश्यकता को समाप्त करता है, जिससे अधिक मजबूत और रखरखाव योग्य सॉफ्टवेयर इंजीनियरिंग टूल्स का समर्थन मिलता है।