टॉप-डाउन पार्सिंग

From Vigyanwiki

कंप्यूटर विज्ञान में टॉप-डाउन पार्सिंग विधि वह होती है, जहां पहले ही पार्स ट्री के उच्चतम स्तर को दिखता है और एक औपचारिक व्याकरण के पुनर्लेखन नियमों का उपयोग करके पार्स ट्री पर काम करता है।।[1] एलएल पार्सर एक प्रकार का पार्सर है जो टॉप-डाउन पार्सिंग विधि का उपयोग करता है।

टॉप-डाउन पार्सिंग सामान्य पार्स ट्री संरचनाओं की परिकल्पना करके अज्ञात डेटा संबंधों का विश्लेषण करने की एक विधि है और फिर यह विचार करना कि ज्ञात मूलभूत संरचनाएं परिकल्पना के अनुकूल हैं या नहीं। इसमें प्राकृतिक भाषाओं और कंप्यूटर भाषाओं दोनों के विश्लेषण में होता है।

टॉप-डाउन पार्सिंग में दिए गए औपचारिक व्याकरण नियमों के टॉप-डाउन विस्तार का उपयोग करके पार्स ट्री कि खोज करके इनपुट-स्ट्रीम के बाएं-सबसे डेरिवेशन खोजने के प्रयास के रूप में देखा जा सकता है। व्याकरण के नियमों के सभी वैकल्पिक दाएं-पक्षों का विस्तार करके अस्पष्टता को समायोजित करने के लिए समावेशी विकल्प का उपयोग किया जाता है।[2]

टॉप-डाउन पार्सिंग के सरल कार्यान्वयन बाएं पुनरावर्ती व्याकरण के लिए समाप्त नहीं होते हैं, और बैकट्रैकिंग के साथ टॉप-डाउन पार्सिंग में अस्पष्ट सीएफजी के लिए इनपुट की लंबाई के संबंध में घातीय समय की जटिलता हो सकती है।[3] चूँकि अधिक परिष्कृत टॉप-डाउन पार्सर फ्रॉस्ट, हाफिज और कैलाघन द्वारा बनाए गए हैं,[4][5] जो अस्पष्टता को समायोजित करते हैं और बहुपद समय में पुनरावृत्ति से अलग कर देते हैं और और जो पार्स ट्री की संभावित घातीय संख्या के बहुपद-आकार के प्रतिनिधित्व उत्पन्न करते हैं। .

प्रोग्रामिंग भाषा अनुप्रयोग

एक संकलनकर्ता में आने वाले प्रतीकों को उत्पादन नियमों से मेल करके एक प्रोग्रामिंग भाषा से आंतरिक प्रतिनिधित्व के लिए इनपुट पार्स करता है। उत्पादन नियम सामान्यतः बैकस-नौर फॉर्म का उपयोग करके परिभाषित किए जाते हैं। एक एलएल पार्सर एक प्रकार का पार्सर है जो प्रत्येक उत्पादन नियम को आने वाले प्रतीकों पर लागू करके टॉप-डाउन पार्सिंग करता है, उत्पादन नियम पर उत्पन्न बाएं-सबसे प्रतीक से काम करता है और फिर प्रत्येक गैर-टर्मिनल प्रतीक के लिए अगले उत्पादन नियम पर आगे बढ़ता है। सामना करना पड़ता है। इस तरह पार्सिंग उत्पादन नियम के परिणाम पक्ष (दाईं ओर) के बाईं ओर प्रारंभ होती है और पहले बाएं से गैर-टर्मिनलों का मूल्यांकन करते है, और इस प्रकार, उत्पादन नियम के लिए अगले प्रतीक को जारी रखने से पहले प्रत्येक नए गैर-टर्मिनल के लिए पार्स ट्री को आगे बढ़ाता है।

उदाहरण के लिए:

जो स्ट्रिंग ए = एसीडीएफ उत्पन्न करता है

मिलान करना और मिलान करने का प्रयास करें अगला। तब कोशिश की जाएगी। जैसा कि कोई उम्मीद कर सकता है, कुछ भाषाएँ दूसरों की तुलना में अधिक अस्पष्ट हैं। एक गैर-संदिग्ध भाषा के लिए, जिसमें एक गैर-टर्मिनल के लिए सभी निर्माण अलग-अलग तार उत्पन्न करते हैं, एक उत्पादन द्वारा उत्पादित स्ट्रिंग उसी प्रतीक के साथ प्रारंभ नहीं होगी, जो किसी अन्य उत्पादन द्वारा निर्मित स्ट्रिंग है। एक गैर-संदिग्ध भाषा को एलएल (1) व्याकरण द्वारा पार्स किया जा सकता है जहां (1) पार्सर एक समय में एक टोकन को आगे पढ़ता है। एलएल पार्सर द्वारा एक अस्पष्ट भाषा को पार्स करने के लिए, पार्सर को 1 से अधिक प्रतीकों को देखना चाहिए, उदा। एलएल (3).

इस समस्या का सामान्य समाधान एक एलआर पार्सर का उपयोग करना है, जो एक प्रकार का शिफ्ट-कम पार्सर है, और नीचे-ऊपर पार्सिंग करता है।

टॉप-डाउन पार्सिंग में बाएं रिकर्सन को समायोजित करना

एक औपचारिक व्याकरण जिसमें बाएं पुनरावर्तन होता है, एक सरल पुनरावर्ती मूल पार्सर द्वारा पार्स नहीं किया जा सकता है, जब तक कि वे एक कमजोर समतुल्य दाएं-पुनरावर्ती रूप में परिवर्तित नहीं हो जाते। चूँकि, हाल के शोध से पता चलता है कि कटौती के उपयोग से अधिक परिष्कृत टॉप-डाउन पार्सर में बाएं-पुनरावर्ती व्याकरण (सामान्य सीएफजी के अन्य सभी रूपों के साथ) को समायोजित करना संभव होता है। एक मान्यता एल्गोरिदम जो अस्पष्ट व्याकरण को समायोजित करता है और इनपुट लंबाई और वर्तमान इनपुट स्थिति के संबंध में गहराई प्रतिबंध लगाकर एक निरंतर बढ़ते प्रत्यक्ष बाएं-पुनरावर्ती पार्स को कम करता है, 2006 में फ्रॉस्ट और हाफिज द्वारा वर्णित किया गया है।[6] उस एल्गोरिदम को अप्रत्यक्ष (वर्तमान संदर्भ के साथ पहले गणना किए गए संदर्भ की तुलना करके) के साथ-साथ बहुपद समय में प्रत्यक्ष बाएं-रिकर्सन को समायोजित करने के लिए एक पूर्ण पार्सिंग एल्गोरिदम तक बढ़ाया गया था, और पार्स ट्री की संभावित घातीय संख्या के कॉम्पैक्ट बहुपद-आकार के प्रतिनिधित्व उत्पन्न करने के लिए 2007 में फ़्रॉस्ट, हाफ़िज़ और कैलाघन द्वारा अत्यधिक अस्पष्ट व्याकरण।[4] एल्गोरिथम तब से हास्केल (प्रोग्रामिंग भाषा) में लिखे गए पार्सर कॉम्बिनेटर के एक सेट के रूप में लागू किया गया है। कॉम्बिनेटर के इन नए सेट के कार्यान्वयन का विवरण लेखकों द्वारा एक पेपर[5] में पाया जा सकता है, जिसे PADL'08 में प्रस्तुत किया गया था। X-SAIGA साइट में एल्गोरिदम और कार्यान्वयन विवरण के बारे में अधिक है।

इसके अतिरिक्त, ऊपर उल्लिखित कटौती के अलावा एक ग्राफ़-संरचित स्टैक (GSS) का उपयोग किया जा सकता है जिससे की आम उपसर्गों के साथ 'मर्जिंग' स्टैक द्वारा बाएं रिकर्सन को समायोजित किया जा सके और अनंत रिकर्सन को रोका जा सके, जिससे प्रत्येक स्टैक की संख्या और सामग्री को कम किया जा सके, जिससे पार्सर के समय और स्थान की जटिलता को कम करना। जिसे सामान्यीकृत एलएल पार्सिंग के रूप ज्ञात एल्गोरिदम की ओर जाता है, जिसमें आप किसी दिए गए सीएफजी के सापेक्ष इनपुट स्ट्रिंग्स को पार्स करने के लिए एक जीएसएस, बाएं-रिकर्सन कर्टेलमेंट और एक एलएल (के) पार्सर का उपयोग करते हैं।[7][8]

टॉप-डाउन पार्सिंग का समय और स्थान जटिलता

जब टॉप-डाउन पार्सर एक अस्पष्ट CFG के संबंध में एक अस्पष्ट इनपुट को पार्स करने का प्रयास करता है, तो उसे सभी संभावित पार्स पेड़ बनाने के लिए CFG के सभी विकल्पों को आज़माने के लिए चरणों की संख्या (इनपुट की लंबाई के संबंध में) की आवश्यकता हो सकती है। जिसके लिए अंततः एक्सपोनेंशियल मेमोरी स्पेस की आवश्यकता होगी। पारस्परिक रूप से पुनरावर्ती कार्यों के सेट के रूप में निर्मित टॉप-डाउन पार्सर्स में घातीय समय जटिलता की समस्या को 1991 में पीटर नॉरविग द्वारा परस्पर पुनरावर्ती कार्यों के सेट के रूप में निर्मित टॉप-डाउन पार्सर्स में घातीय समय जटिलता की समस्या को हल किया गया है।[9] उनकी तकनीक गतिशील प्रोग्रामिंग और अर्ली के एल्गोरिथम (1970) में स्टेट-सेट के उपयोग के समान है, और कॉके, यंगर और कासामी के अर्ली सीवाई के एल्गोरिदम में तालिकाएँ हैं।

मुख्य विचार यह है कि पार्सर p को पोजीशन j पर लागू करने के परिणामों को एक यादगार स्थिति में संग्रहित किया जाए और जब भी वही स्थिति उत्पन्न हो तो परिणामों का पुन: उपयोग किया जाए। फ्रॉस्ट, हाफ़िज़ और कैलाघन[4][5] बहुपद समय में सीएफजी के किसी भी रूप को समायोजित करने के लिए निरर्थक संगणनाओं से बचने के लिए मेमोइज़ेशन का उपयोग करते हैं (बाएं-पुनरावर्ती व्याकरण के लिए Θ(n4) और गैर-पुनरावर्ती व्याकरण के लिए Θ(n3)। उनके टॉप-डाउन पार्सिंग एल्गोरिदम को 'कॉम्पैक्ट प्रतिनिधित्व' और 'स्थानीय अस्पष्टता समूह' द्वारा संभावित घातीय अस्पष्ट पार्स पेड़ के लिए बहुपद स्थान की भी आवश्यकता होती है। उनका कॉम्पैक्ट प्रतिनिधित्व टोमिटा के बॉटम-अप पार्सिंग के कॉम्पैक्ट प्रतिनिधित्व के साथ तुलनीय है।[10]

पीईजी का उपयोग करना, व्याकरण का एक और प्रतिनिधित्व, पैकरैट पार्सर्स एक सुरुचिपूर्ण और शक्तिशाली पार्सिंग एल्गोरिदम प्रदान करते हैं। पार्सिंग अभिव्यक्ति व्याकरण देखें।

उदाहरण

टॉप-डाउन पार्सिंग का उपयोग करने वाले कुछ पार्सर्स में शामिल हैं:

यह भी देखें

  • बॉटम-अप पार्सिंग
  • पार्सिंग
  • पार्सिंग अभिव्यक्ति व्याकरण

संदर्भ

  1. ↑ Dick Grune; Ceriel J.H. Jacobs (29 October 2007). Parsing Techniques: A Practical Guide. Springer Science & Business Media. ISBN 978-0-387-68954-8.
  2. ↑ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers, principles, techniques, and tools (Rep. with corrections. ed.). Addison-Wesley Pub. Co. ISBN 978-0201100884.
  3. ↑ Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice-Hall. ISBN 978-0139145568.
  4. ↑ 4.0 4.1 4.2 Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague. Archived from the original on 12 November 2018.
  5. ↑ 5.0 5.1 5.2 Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.
  6. ↑ Frost, R. and Hafiz, R. (2006) " A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time." ACM SIGPLAN Notices, Volume 41 Issue 5, Pages: 46 - 54. doi:10.1145/1149982.1149988
  7. ↑ http://dotat.at/tmp/gll.pdf[bare URL PDF]
  8. ↑ https://pure.royalholloway.ac.uk/portal/files/26408385/postprint.pdf[bare URL PDF]
  9. ↑ Norvig, P. (1991) “Techniques for automatic memoisation with applications to context-free parsing.” Journal - Computational Linguistics Volume 17, Issue 1, Pages: 91 - 98.
  10. ↑ Tomita, M. (1985) “Efficient Parsing for Natural Language.” Kluwer, Boston, MA.
  11. ↑ Pereira, Fernando CN, and David HD Warren. "Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks." Artificial intelligence 13.3 (1980): 231-278.


बाहरी संबंध

  • X-SAIGA - eXecutable SpecificAtIons of GrAmmars
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टॉप-डाउन_पार्सिंग&oldid=98105’