इस अनुभाग में, हम अपना ध्यान सामान्य पार्सर-निर्देशित निर्माण पर केंद्रित करते हैं और CFG के रूप में उपलब्ध कराए गए पायथन-जैसे व्याकरण के लिए एक सरल मार्गदर्शिका के साथ शुरुआत करते हैं।
"d" और "ef" जैसे स्ट्रिंग्स से युक्त एक शब्दावली पर विचार करें, जिन्हें एक अंतर्निहित CFG के अनुसार पायथन-जैसे वाक्यविन्यास का उत्पादन करने के लिए संयोजित किया जा सकता है, और मान लें कि इन स्ट्रिंग्स को एल्गोरिदम 1 जैसी प्रक्रिया के अनुसार क्रमिक रूप से नमूना और संयोजित किया गया है।
इसके अलावा, CFG में एक टर्मिनल प्रतीक DEF पर विचार करें जो स्ट्रिंग "def" से मेल खाता है और ट्रिवियल रेगुलर एक्सप्रेशन def द्वारा दिया गया है। इसके अलावा, रेगुलर एक्सप्रेशन [^\W\d]\w* (जैसे पायथन पहचानकर्ता) द्वारा दिए गए NAME प्रतीक पर विचार करें। हम उपर्युक्त शब्दावली से लिए गए स्ट्रिंग को क्रमिक रूप से पार्स करना चाहते हैं ताकि पायथन सिंटैक्स का पालन किया जा सके।
उदाहरण के लिए, निम्नलिखित एक ऐसा अनुक्रम हो सकता है: ["d", "ef", " f", "oo(", "):", " ", "pass"]। अनुक्रम के सभी तत्व परिभाषा के अनुसार शब्दावली के तत्व हैं। अनुक्रम को संयोजित करने से "def foo(): pass" उत्पन्न होता है, जो फ़ंक्शन को परिभाषित करने वाले टोकन का एक वैध अनुक्रम है। जिस स्थिति पर हम विचार कर रहे हैं, उसमें हमने एक निश्चित बिंदु तक सभी टोकन देखे होंगे और उस बिंदु के बाद के टोकन के बारे में कुछ नहीं जानते होंगे।
उदाहरण के लिए, उदाहरण अनुक्रम में तीसरे अवलोकन पर, हमारे पास संयोजित स्ट्रिंग "def f" है। यदि हम इस स्ट्रिंग को लेक्स/पार्स करते हैं तो एक पारंपरिक दृष्टिकोण प्रतीक अनुक्रम DEF NAME लौटाएगा, जो "f" को पूर्ण NAME टोकन के रूप में गलत पहचानता है। जैसा कि हम अनुक्रम के बाकी हिस्सों से देख सकते हैं, सही NAME टोकन "foo" होगा।
सामान्य तौर पर, शब्दावली से नमूना लिए जा सकने वाले अगले वैध स्ट्रिंग वे हैं जो या तो
वर्तमान में "f" से शुरू होने वाले NAME को विस्तारित/आगे बढ़ाना जारी रखें (जैसा कि हमारे उदाहरण में पूर्ण अनुक्रम करता है), और/या
कुछ भी जो "(" से शुरू होता है - यानी नियमित अभिव्यक्ति (के साथ एक LPAR प्रतीक - और एक वैध तर्क हस्ताक्षर निर्दिष्ट करने के लिए आगे बढ़ता है।
पहले मामले में, "f" को पायथन में आंशिक रूप से मेल खाने वाले NAME प्रतीक के रूप में देखा जा सकता है, और - यह याद करते हुए कि इसका नियमित अभिव्यक्ति [^\W\d]\w* है - हम कह सकते हैं कि यह नियमित अभिव्यक्ति में दोनों उप-पैटर्न (यानी [^\W\d] और \w*) से मेल खाता है। FSM का हमारा उपयोग FSM की स्थितियों के माध्यम से उप-पैटर्न की धारणा को औपचारिक रूप देता है। इस मामले में, NAME के लिए रेगेक्स को तीन स्थितियों के साथ एक FSM, M द्वारा दर्शाया जा सकता है: 0 (यानी प्रारंभिक स्थिति q0), 1 (यानी [^\W\d]), और 2 (यानी \w*), जहाँ 1, 2 ∈ F.
एल्गोरिथ्म 3 का उपयोग करके, हम "f" के लिए FSM अवस्था अनुक्रम (0, 1), (1, 2), (2, 2) और NAME प्रतीक के अनुरूप FSM, M प्राप्त करेंगे। "f" के लिए ये FSM अनुक्रम हमें बताते हैं कि इस शब्दावली स्ट्रिंग के लिए मिलान 0, 1, या 2 अवस्थाओं में शुरू हो सकता है, और यह 1 या 2 अवस्थाओं में समाप्त हो सकता है।
ऊपर दिए गए मामले 1 के अनुसार, पार्सिंग को NAME प्रतीक के लिए जारी रखा जा सकता है - पहले 1 या 2 अवस्थाओं में समाप्त होने के बाद। मामले 2 के अनुसार, अगली स्ट्रिंग भी LPAR से शुरू हो सकती है या उसमें LPAR हो सकती है, जिसका अर्थ है कि M समाप्त हो गया होगा, जो यह हो सकता है कि 1 और 2 M में अंतिम अवस्थाएँ हैं, जिस पर "f" पढ़ने के बाद पार्सिंग बंद हो गई होगी। M का समाप्त होना यह भी दर्शाता है कि NAME प्रतीक पूरा हो गया था, और व्याकरण द्वारा LPAR को स्वीकार करने वाली अवस्था में संक्रमण की अनुमति दी गई थी।
इस चित्रण में, अगली मान्य शब्दावली स्ट्रिंग कम से कम "d", "ef", "pass", " ", "oo(" हैं, क्योंकि वे सभी स्ट्रिंग आंशिक रूप से मेल खाने वाले NAME का विस्तार करेंगे, और अंतिम स्ट्रिंग भी पार्स स्थिति को उस स्थिति में ले जाएगी जो LPAR पढ़ती है। हमारे द्वारा विचार की गई शब्दावली के उपसमूह से शेष स्ट्रिंग, "):", अमान्य सिंटैक्स वाले अनुक्रम में परिणामित होगी।
एफएसएम अनुक्रमण दृष्टिकोण के संबंध में, इसका अर्थ है कि एल्गोरिथ्म 4 एफएसएम अवस्थाओं 0, 1, और 2 को प्रतीक NAME और उसके एफएसएम, M के लिए उपसमुच्चय "d", "ef", "pass", " ", "oo(" में मैप करेगा।
यह चित्रण अंतर्निहित पार्सर स्थितियों को छोड़ देता है जो निर्धारित करते हैं कि कौन से व्याकरण प्रतीकों और संक्रमणों की अनुमति है। हम FSM दृष्टिकोण को विस्तारित करने और शेष विवरणों को संबोधित करने के साधन के रूप में पुशडाउन ऑटोमेटा (PDA) का उपयोग करते हैं।
4.1 पुशडाउन ऑटोमेटा फॉर्मूलेशन
हम निम्नलिखित 6-टपल प्रतिनिधित्व का उपयोग करके पुशडाउन ऑटोमेटा को परिभाषित करते हैं [सिपसर, 1996, परिभाषा 2.13]:
पीडीए-संचालित पार्सर के लिए अनुक्रमण दृष्टिकोण का निर्माण करने के लिए, हमें सीएफजी के प्रतीकों के बीच संबंध का उपयोग करने की आवश्यकता है - संबंधित पीडीए के वर्णमाला के माध्यम से - और लेक्सिंग और स्कैनिंग चरणों के माध्यम से जो पीडीए द्वारा पढ़े गए प्रतीकों का उत्पादन करते हैं।
अधिक विशेष रूप से, पार्सर लेक्सर और स्कैनर द्वारा समर्थित होते हैं जो वर्ण इनपुट के अनुक्रम से प्रतीकों की पहचान करते हैं, जैसा कि हमने अनुभाग 4 में स्पष्ट रूप से दर्शाया है। प्रत्येक पार्स/पीडीए राज्य के लिए टर्मिनल प्रतीकों की क्रमबद्ध सूचियाँ बनाई जा सकती हैं, जो प्रत्येक राज्य में मैप δ द्वारा अनुमत प्रतीक और स्टैक संक्रमणों पर आधारित होती हैं। इसका मतलब है कि हम प्रत्येक पार्स राज्य के लिए एक FSM बना सकते हैं जो राज्य द्वारा पढ़े गए टर्मिनल प्रतीकों के अनुरूप प्रत्येक FSM का संघ है।
स्कैनिंग चरण तब पार्सिंग प्रक्रिया में अंतिम पूर्ण रूप से पहचाने गए प्रतीक के बाद से पढ़े गए वर्णों के लिए संभावित टर्मिनल प्रतीकों V ⊂ Σ के एक सेट की पहचान करेगा। उदाहरण के लिए, अनुभाग 4 में पायथन जैसे CFG के लिए PDA की प्रारंभिक अवस्था q0 में, स्ट्रिंग "de" को स्कैन करने और लेक्स करने से V = {DEF, NAME} प्राप्त होगा: यानी स्ट्रिंग "def" को पूरा करने वाली किसी भी शब्दावली स्ट्रिंग के लिए DEF - उसके बाद NAME FSM द्वारा न पढ़ी गई स्ट्रिंग (जैसे "def ") - और इसके FSM द्वारा पढ़ी गई किसी भी अन्य स्ट्रिंग के लिए NAME (जैसे "default")। ध्यान दें कि स्कैनर के चरण - और LLM के सैंपलिंग चरण - अंततः सेट V को तब तक कम कर देंगे जब तक कि एक एकल टर्मिनल प्रतीक v ∈ V निर्धारित न हो जाए।
प्रत्येक पार्स अवस्था के लिए संयुक्त FSM का उपयोग करके V में प्रत्येक स्ट्रिंग पर एल्गोरिथम 3 को लागू करके, हम पार्सर कॉन्फ़िगरेशन निर्धारित कर सकते हैं जिसमें PDA अवस्थाएं, संबंधित FSM अवस्थाएं और संभावित टर्मिनल प्रतीक शामिल होते हैं।
एल्गोरिथ्म 3 में दिए गए चरणों के अनुरूप, हम PDA के संक्रमण मानचित्र की पूर्व-छवि का उपयोग PDA स्टैक मानों को निर्धारित करने के लिए कर सकते हैं जो एक पार्सर कॉन्फ़िगरेशन के PDA अवस्थाओं q ∈ Q और टर्मिनल प्रतीक सेट V को पढ़ेंगे:
इस मानचित्र द्वारा प्रदान किए गए स्टैक मानों की आवश्यकता PDA के माध्यम से पथों को खोजने के लिए होती है - यदि कोई हो - जो V में प्रत्येक स्ट्रिंग के सफल, पूर्ण पार्स की अनुमति देता है, जो उनके संभावित पार्सर कॉन्फ़िगरेशन से शुरू होता है। LALR(1) पार्सर के REDUCE संचालन के अनुरूप पार्सर स्थिति और टर्मिनल संयोजनों के लिए, ये पार्सर कॉन्फ़िगरेशन Γ में केवल टॉपऑफ़-स्टैक मानों से अधिक शामिल होंगे; वे शब्दावली स्ट्रिंग द्वारा शामिल REDUCE संचालन के लिए सभी वैध उपसर्गों के अनुरूप उप-स्टैक शामिल करेंगे। अंततः, प्रत्येक पार्सर कॉन्फ़िगरेशन जो शब्दावली स्ट्रिंग के पूर्ण पार्स की अनुमति देता है, उसे PDA के लिए इंडेक्स में एक प्रविष्टि के रूप में जोड़ा जाता है, और, इस मामले में, पार्सर के स्टैक मानों के विरुद्ध क्वेरी की अनुमति देने के लिए इंडेक्स को एक ट्राई डेटा संरचना होने की आवश्यकता होगी।
यह पेपर CC 4.0 लाइसेंस के अंतर्गत है।
L O A D I N G . . . comments & more!
About Author
Writings, Papers and Blogs on Text Models@textmodels
We publish the best academic papers on rule-based techniques, LLMs, & the generation of text that resembles human text.
