अर्ली पार्सर

अर्ली पार्सर

Class	Parsing grammars that are context-free
Data structure	String
Worst-case performance	$O(n^{3})$
Best-case performance	$\Omega (n)$ for all deterministic context-free grammars $\Omega (n^{2})$ for unambiguous grammars
Average performance	$\Theta (n^{3})$

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

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

अर्ली पहचानकर्ता

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

एल्गोरिथ्म

निम्नलिखित विवरण में, α, β, और γ टर्मिनल/नॉनटर्मिनल (रिक्त स्ट्रिंग सहित) किसी भी स्ट्रिंग का प्रतिनिधित्व करते हैं, X और Y एकल नॉनटर्मिनल का प्रतिनिधित्व करते हैं, और a एक टर्मिनल प्रतीक का प्रतिनिधित्व करते है।

अर्ली एल्गोरिदम एक अधोशीर्ष गतिक क्रमादेशन एल्गोरिदम है। निम्नलिखित में, हम अर्ली के डॉट नोटेशन का उपयोग करते हैं: एक उत्पादन X → αβ दिया गया है, नोटेशन X → α • β एक ऐसी अवस्था का प्रतिनिधित्व करता है जिसमें α को पहले ही पार्स किया जाता है और β अपेक्षित है।

इनपुट अवस्था 0 इनपुट से पहले की अवस्था है। इनपुट अवस्था n, nवें टोकन को स्वीकार करने के बाद की अवस्था है। (अनौपचारिक रूप से, इनपुट अवस्था को टोकन सीमाओं पर स्थित स्थानों के रूप में माना जा सकता है।) प्रत्येक इनपुट अवस्था के लिए, पार्सर एक अवस्था समुच्चय उत्पन्न करता है। प्रत्येक अवस्था एक टुपल (X → α • β, i) है, जिसमें सम्मिलित है

• वर्तमान में उत्पादन (X → α β) से जोड़ा जाता है।
• उस उत्पादन में वर्तमान अवस्था (दृश्यमान रूप से बिंदु • द्वारा प्रदर्शित)
• इनपुट में वह अवस्था जहां इस उत्पादन का सुमेलन प्रारम्भ हुआ: मूल अवस्था

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

एक अवस्था तब समाप्त होती है जब उसकी वर्तमान अवस्था उत्पादन के दाईं ओर की अंतिम अवस्था होती है, अर्थात, जब अवस्था के दृश्य प्रतिनिधित्व में बिंदु के दाईं ओर कोई प्रतीक नहीं होता है।

इनपुट अवस्था k पर निर्धारित अवस्था को S(k) कहा जाता है। पार्सर को S(0) के साथ सीडित किया गया है जिसमें केवल शीर्ष-स्तरीय नियम सम्मिलित है। पार्सर फिर तीन संचालन को बार-बार निष्पादित करता है: पूर्वानुमान, स्कैनिंग और पूर्णता।

• पूर्वानुमान: फॉर्म (X → α • Y β, j) के S(k) में प्रत्येक अवस्था के लिए (जहाँ j ऊपर की तरह मूल अवस्था है), प्रत्येक उत्पादन के लिए S(k) में (Y → • γ, k) जोड़ें बाईं ओर Y व्याकरण (Y → γ) है।
• स्कैनिंग: यदि a इनपुट स्ट्रीम में अगला प्रतीक है, तो फॉर्म (X → α • a β, j) के S(k) में प्रत्येक अवस्था के लिए, S(k+1) में (X → α a • β, j) जोड़ें है।
• पूर्णता: फॉर्म (Y → γ •, j) के S(k) में प्रत्येक अवस्था के लिए, (X → α • Y β, i) फॉर्म के S(j) में सभी अवस्था खोजें और S(k) में (X → α Y • β, i) जोड़ें है।

अवस्था समुच्चय में प्रतिलिपि अवस्था नहीं जोड़े जाते, केवल नए अवस्था जोड़े जाते हैं। ये तीन संचालन तब तक दोहराए जाते हैं जब तक समुच्चय में कोई नई अवस्था नहीं जोड़ी जा सकती है। समुच्चय को सामान्यतः संसाधित करने के लिए अवस्था की एक क्यू के रूप में कार्यान्वित किया जाता है, जिसमें संचालन इस पर निर्भर करता है कि यह किस प्रकार की अवस्था है।

एल्गोरिदम स्वीकार करता है यदि (X → γ •, 0) S(n) में समाप्त होता है, जहां (X → γ) शीर्ष स्तर-नियम है और n इनपुट लंबाई है, अन्यथा यह अस्वीकार कर देता है।

स्यूडोकोड

डेनियल जुराफ़्स्की और जेम्स एच. मार्टिन द्वारा भाषण और लैंग्वेज प्रसंस्करण से अनुकूलित,

DECLARE ARRAY S;

function INIT(words)
    S ← CREATE_ARRAY(LENGTH(words) + 1)
    for k ← from 0 to LENGTH(words) do
        S[k] ← EMPTY_ORDERED_SET

function EARLEY_PARSE(words, grammar)
    INIT(words)
    ADD_TO_SET((γ → •S, 0), S[0])
    for k ← from 0 to LENGTH(words) do
        for each state in S[k] do  // S[k] can expand during this loop
            if not FINISHED(state) then
                if NEXT_ELEMENT_OF(state) is a nonterminal then
                    PREDICTOR(state, k, grammar)         // non_terminal
                else do
                    SCANNER(state, k, words)             // terminal
            else do
                COMPLETER(state, k)
        end
    end
    return chart

procedure PREDICTOR((A → α•Bβ, j), k, grammar)
    for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do
        ADD_TO_SET((B → •γ, k), S[k])
    end

procedure SCANNER((A → α•aβ, j), k, words)
    if j < LENGTH(words) and a ⊂ PARTS_OF_SPEECH(words[k]) then
        ADD_TO_SET((A → αa•β, j), S[k+1])
    end

procedure COMPLETER((B → γ•, x), k)
    for each (A → α•Bβ, j) in S[x] do
        ADD_TO_SET((A → αB•β, j), S[k])
    end

उदाहरण

अंकगणितीय अभिव्यक्तियों के लिए निम्नलिखित सरल व्याकरण पर विचार करें:

<P> ::= <S>      # the start rule
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"

इनपुट के साथ:

2+3*4

यह अवस्था समुच्चयों का क्रम है:

(राज्य संख्या)	उत्पादन	(मूल)	टिप्पणी
S(0): • 2 + 3 * 4
1	P → • S	0	start rule
2	S → • S + M	0	predict from (1)
3	S → • M	0	predict from (1)
4	M → • M * T	0	predict from (3)
5	M → • T	0	predict from (3)
6	T → • number	0	predict from (5)
S(1): 2 • + 3 * 4
1	T → number •	0	scan from S(0)(6)
2	M → T •	0	complete from (1) and S(0)(5)
3	M → M • * T	0	complete from (2) and S(0)(4)
4	S → M •	0	complete from (2) and S(0)(3)
5	S → S • + M	0	complete from (4) and S(0)(2)
6	P → S •	0	complete from (4) and S(0)(1)
S(2): 2 + • 3 * 4
1	S → S + • M	0	scan from S(1)(5)
2	M → • M * T	2	predict from (1)
3	M → • T	2	predict from (1)
4	T → • number	2	predict from (3)
S(3): 2 + 3 • * 4
1	T → number •	2	scan from S(2)(4)
2	M → T •	2	complete from (1) and S(2)(3)
3	M → M • * T	2	complete from (2) and S(2)(2)
4	S → S + M •	0	complete from (2) and S(2)(1)
5	S → S • + M	0	complete from (4) and S(0)(2)
6	P → S •	0	complete from (4) and S(0)(1)
S(4): 2 + 3 * • 4
1	M → M * • T	2	scan from S(3)(3)
2	T → • number	4	predict from (1)
S(5): 2 + 3 * 4 •
1	T → number •	4	scan from S(4)(2)
2	M → M * T •	2	complete from (1) and S(4)(1)
3	M → M • * T	2	complete from (2) and S(2)(2)
4	S → S + M •	0	complete from (2) and S(2)(1)
5	S → S • + M	0	complete from (4) and S(0)(2)
6	P → S •	0	complete from (4) and S(0)(1)

अवस्था (P → S •, 0) एक पूर्ण पार्स का प्रतिनिधित्व करती है। यह अवस्था S(3) और S(1) में भी दिखाई देती है, जो पूर्ण वाक्य हैं।

पार्स फ़ॉरेस्ट का निर्माण

अर्ली का शोध प्रबंध संक्षेप में अर्ली वस्तु में प्रत्येक गैर-टर्मिनल से पॉइंटर्स का एक समुच्चय जोड़कर पार्स ट्री के निर्माण के लिए एक एल्गोरिदम का वर्णन करता है, जिसके कारण इसे पहचाना जाता हैं। टोमिता ने देखा कि यह प्रतीकों के मध्य संबंधों को ध्यान में नहीं रखता है, इसलिए यदि हम व्याकरण S → SS | b और स्ट्रिंग bbb, यह केवल नोट करता है कि प्रत्येक S एक या दो b से समान है, और इस प्रकार bb और bbbb के लिए मिथ्या व्युत्पत्ति के साथ-साथ bbb के लिए दो सही व्युत्पत्तियाँ उत्पन्न करता है।

एक और प्रकार यह है कि पार्स फ़ॉरेस्ट का निर्माण करें, प्रत्येक अर्ली विषय को एक पॉइंटर के साथ साझा पैक्ड पार्स फ़ॉरेस्ट (एसपीपीएफ) नोड में ट्रिपल (s, i, j) के साथ लेबल करना, जहां s एक प्रतीक या LR(0) है (डॉट के साथ उत्पादन नियम), और i और j इस नोड द्वारा प्राप्त इनपुट स्ट्रिंग का अनुभाग देते हैं। एक नोड की विषय सूची या तो एकल व्युत्पत्ति देने वाले चाइल्ड पॉइंटर्स की एक जोड़ी होती है, या "पैक्ड" नोड्स की एक सूची होती है, जिनमें से प्रत्येक में पॉइंटर्स की एक जोड़ी होती है और एक व्युत्पत्ति का प्रतिनिधित्व होता है। एसपीपीएफ नोड्स अद्वितीय हैं (दिए गए लेबल के साथ केवल एक ही है), लेकिन अस्पष्ट पार्स के लिए एक से अधिक व्युत्पत्ति हो सकती है। इसलिए संचालन अर्ली विषय नहीं जोड़ता (क्योंकि यह पहले से उपस्तिथ है), फिर भी यह विषय के पार्स फ़ॉरेस्ट में व्युत्पत्ति जोड़ता है।

• पूर्वानुमानित विषय में एक शून्य SPPF सूचक होता है।
• स्कैनर एक एसपीपीएफ नोड बनाता है जो उस गैर-टर्मिनल का प्रतिनिधित्व करता है जिसे वह स्कैन करता है।
• जब स्कैनर या कंप्लीटर किसी विषय को आगे बढ़ाता है, तो वे एक व्युत्पत्ति जोड़ता हैं जिससे बच्चे उस विषय से नोड होते हैं जिसका बिंदु उन्नत था, और एक नए प्रतीक के लिए जो आगे बढ़ाया गया था (गैर-टर्मिनल या पूर्ण विषय)।

एसपीपीएफ नोड्स को कभी भी पूर्ण LR(0) विषय के साथ लेबल नहीं किया जाता है: इसके बदले उन्हें उत्पादित प्रतीक के साथ लेबल किया जाता है ताकि सभी व्युत्पत्तियां एक नोड के अंतर्गत संयुक्त हो जाएं, चाहे वे किसी भी वैकल्पिक उत्पादन से किया है।

अनुकूलन

फिलिप मैकलीन और आर. निगेल हॉर्सपूल ने अपने दस्तावेज़ में एक तेज़ अर्ली पार्सर में अर्ली पार्सिंग को एलआर पार्सिंग के साथ जोड़ा और परिमाण के क्रम में सुधार प्राप्त किया है।

यह भी देखें

• CYK एल्गोरिदम
• प्रसंग-मुक्त व्याकरण
• पार्सिंग एल्गोरिदम

अन्य संदर्भ सामग्री

• Aycock, John; Horspool, R. Nigel (2002). "प्रैक्टिकल अर्ली पार्सिंग". The Computer Journal. 45 (6): 620–630. CiteSeerX 10.1.1.12.4254. doi:10.1093/comjnl/45.6.620.
• Leo, Joop M. I. M. (1991), "A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead", Theoretical Computer Science, 82 (1): 165–176, doi:10.1016/0304-3975(91)90180-A, MR 1112117

• Tomita, Masaru (1984). "प्राकृतिक भाषाओं के लिए एलआर पार्सर्स" (PDF). COLING. 10th International Conference on Computational Linguistics. pp. 354–357.

कार्यान्वयन

सी, सी++

• 'येट अदर अर्ली पार्सर (YAEP)' - C (प्रोग्रामिंग लैंग्वेज)/C++ लाइब्रेरी

हास्केल

• 'Earley' - हास्केल में एक अर्ली पार्सर डोमेन-विशिष्ट लैंग्वेज (प्रोग्रामिंग लैंग्वेज)

जावा

• [1] - अर्ली एल्गोरिथम का जावा कार्यान्वयन
• PEN - एक जावा लाइब्रेरी जो अर्ली एल्गोरिदम लागू करती है
• Pep - एक जावा लाइब्रेरी जो अर्ली एल्गोरिदम को लागू करती है और पार्सिंग कलाकृतियों के रूप में चार्ट और पार्स पेड़ों को प्रदान करती है
• Digitalheir/java-probability-earley-parser - एक जावा लाइब्रेरी जो संभाव्य अर्ली एल्गोरिथ्म को लागू करती है, जो एक अस्पष्ट वाक्य से सबसे संभावित पार्स ट्री को निर्धारित करने के लिए उपयोगी है।

सी#

• coonsta/earley - C# में एक अर्ली पार्सर
• patrickhuber/pliant - एक अर्ली पार्सर जो मार्पा द्वारा अपनाए गए सुधारों को एकीकृत करता है और एलिजाबेथ स्कॉट के वृक्ष निर्माण एल्गोरिदम को प्रदर्शित करता है।
• elisonch/CFGLib - C# के लिए संभाव्य संदर्भ मुक्त व्याकरण (PCFG) लाइब्रेरी (अर्ली + SPPF, CYK)

जावास्क्रिप्ट

• नियरली - एक अर्ली पार्सर जो मार्पा द्वारा अपनाए गए सुधारों को एकीकृत करना शुरू कर रहा है
• एक पिंट आकार का अर्ली पार्सर - साझा पैक्ड पार्स फ़ॉरेस्ट के निर्माण के लिए एलिजाबेथ स्कॉट की तकनीक को प्रदर्शित करने के लिए एक खिलौना पार्सर (एनोटेटेड छद्म कोड के साथ)
• lagodiuk/earley-parser-js - अर्ली पार्सर का एक छोटा जावास्क्रिप्ट कार्यान्वयन (पार्सिंग-फ़ॉरेस्ट की पीढ़ी सहित)
• Digitalheir/probability-earley-parser-javascript - संभाव्य अर्ली पार्सर का जावास्क्रिप्ट कार्यान्वयन

ओकैमल

• सिंपल अर्ली - दस्तावेज़ीकरण के साथ एक सरल अर्ली-जैसे पार्सिंग एल्गोरिदम का कार्यान्वयन।

पर्ल

• Marpa::R2 - एक पर्ल मॉड्यूल। Marpa एक अर्ली का एल्गोरिदम है जिसमें जोप लियो और ऐकॉक और हॉर्सपूल द्वारा किए गए सुधार सम्मिलित हैं।
• Parse::Earley - जे अर्ली के मूल एल्गोरिदम को लागू करने वाला एक पर्ल मॉड्यूल

पायथन

• Lark - अर्ली पार्सर का एक ऑब्जेक्ट-ओरिएंटेड, प्रक्रियात्मक कार्यान्वयन, जो एक SPPF आउटपुट करता है।
• NLTK - अर्ली पार्सर के साथ एक पायथन (प्रोग्रामिंग लैंग्वेज) टूलकिट
• स्पार्क - अर्ली पार्सर को लागू करने वाले पायथन के लिए एक ऑब्जेक्ट-ओरिएंटेड छोटी लैंग्वेज रूपरेखा
• spark_parser - उपरोक्त स्पार्क पार्सर का अद्यतन और पैकेज्ड संस्करण, जो पायथन 3 और पायथन 2 दोनों में चलता है
• [2] - कोड की 150 से भी कम लाइनों में एल्गोरिदम का एक स्टैंड-अलोन कार्यान्वयन, जिसमें पार्सिंग-फ़ॉरेस्ट और नमूनों की पीढ़ी सम्मिलित है
• tjr_python_earley_parser - पायथन में एक न्यूनतम अर्ली पार्सर
• अर्ली पार्सिंग - एप्सिलॉन हैंडलिंग और राइट-रिकर्सन के लिए लियो ऑप्टिमाइज़ेशन के साथ पायथन में एक अच्छी तरह से समझाया और संपूर्ण अर्ली पार्सर ट्यूटोरियल।

जंग

• सैंटियागो - अर्ली पार्सर को लागू करने वाले रस्ट के लिए एक लेक्सिंग और पार्सिंग टूलकिट।

सामान्य लिस्प

• CL-Earley-parser - एक सामान्य लिस्प लाइब्रेरी जो अर्ली पार्सर को लागू करती है

योजना, रैकेट

• चार्टी-रैकेट - एक योजना (प्रोग्रामिंग लैंग्वेज) - रैकेट (प्रोग्रामिंग लैंग्वेज) अर्ली पार्सर का कार्यान्वयन

वोल्फ्राम

• [3] - कुछ आवश्यक परीक्षण मामलों के साथ वोल्फ्राम लैंग्वेज प्रोग्रामिंग लैंग्वेज में अर्ली पार्सर का एक बुनियादी न्यूनतम कार्यान्वयन।

संसाधन

• एक्सेंट कंपाइलर-कंपाइलर

श्रेणी:पार्सिंग एल्गोरिदम श्रेणी:गतिशील प्रोग्रामिंग