अर्ली पार्सर
| Class | Parsing grammars that are context-free |
|---|---|
| Data structure | String |
| Worst-case performance | |
| Best-case performance | |
| Average performance |
कंप्यूटर विज्ञान में, अर्ली पदच्छेदर स्ट्रिंग (कंप्यूटर विज्ञान) को पार्स करने के लिए एक कलन विधि है जो किसी दिए गए संदर्भ-मुक्त भाषा से संबंधित है, हालांकि (संस्करण के आधार पर) यह कुछ अशक्त व्याकरणों के साथ समस्याओं का सामना कर सकता है।[1] एल्गोरिथ्म, जिसका नाम इसके आविष्कारक जे अर्ली के नाम पर रखा गया है, एक चार्ट पार्सर है जो गतिशील प्रोग्रामिंग का उपयोग करता है; इसका उपयोग मुख्य रूप से कम्प्यूटेशनल भाषाविज्ञान में पार्सिंग के लिए किया जाता है। इसे पहली बार उनके शोध प्रबंध में पेश किया गया था[2] 1968 में (और बाद में एक पत्रिका में संक्षिप्त, अधिक सुपाठ्य रूप में प्रकाशित हुआ[3]).
अर्ली पार्सर आकर्षक हैं क्योंकि वे एलआर पार्सर और एलएल पार्सर के विपरीत सभी संदर्भ-मुक्त भाषाओं को पार्स कर सकते हैं, जो आमतौर पर संकलक ों में उपयोग किए जाते हैं लेकिन जो केवल भाषाओं के प्रतिबंधित वर्गों को संभाल सकते हैं। सामान्य स्थिति में अर्ली पार्सर घन समय में निष्पादित होता है , जहां n पार्स की गई स्ट्रिंग की लंबाई है, स्पष्ट व्याकरण के लिए द्विघात समय ,[4] और सभी नियतात्मक संदर्भ-मुक्त व्याकरणों के लिए रैखिक समय। यह विशेष रूप से तब अच्छा प्रदर्शन करता है जब नियम बाएँ पुनरावर्ती|बाएँ-पुनरावर्ती रूप से लिखे जाते हैं।
प्रारंभिक पहचानकर्ता
निम्नलिखित एल्गोरिदम अर्ली पहचानकर्ता का वर्णन करता है। पहचानकर्ता को एक पार्स ट्री बनाने के लिए संशोधित किया जा सकता है क्योंकि यह पहचानता है, और इस तरह इसे एक पार्सर में बदला जा सकता है।
एल्गोरिथ्म
निम्नलिखित विवरण में, α, β, और γ टर्मिनल और नॉनटर्मिनल प्रतीकों के किसी खाली स्ट्रिंग (कंप्यूटर विज्ञान) का प्रतिनिधित्व करते हैं।
अर्ली का एल्गोरिदम एक टॉप-डाउन डायनेमिक प्रोग्रामिंग एल्गोरिदम है। निम्नलिखित में, हम अर्ली के डॉट नोटेशन का उपयोग करते हैं: एक औपचारिक व्याकरण #व्याकरणों का वाक्यविन्यास X → αβ दिया गया है, नोटेशन
इनपुट स्थिति 0 इनपुट से पहले की स्थिति है। इनपुट स्थिति n, nवें टोकन को स्वीकार करने के बाद की स्थिति है। (अनौपचारिक रूप से, इनपुट स्थितियों को लेक्सिकल विश्लेषण सीमाओं पर स्थानों के रूप में सोचा जा सकता है।) प्रत्येक इनपुट स्थिति के लिए, पार्सर एक राज्य सेट उत्पन्न करता है। प्रत्येक अवस्था एक टुपल है (X → α • β, i), जिसमें शामिल है
- वर्तमान में उत्पादन का मिलान किया जा रहा है (X → α β)
- उस उत्पादन में वर्तमान स्थिति (दृश्यमान रूप से बिंदु द्वारा प्रदर्शित)
- इनपुट में वह स्थिति जिस पर इस उत्पादन का मिलान शुरू हुआ: मूल स्थिति
(अर्ली के मूल एल्गोरिदम में राज्य में आगे की ओर देखना शामिल था; बाद के शोध से पता चला कि इसका पार्सिंग दक्षता पर बहुत कम व्यावहारिक प्रभाव पड़ता है, और बाद में इसे अधिकांश कार्यान्वयन से हटा दिया गया है।)
एक राज्य तब समाप्त होता है जब उसकी वर्तमान स्थिति उत्पादन के दाईं ओर की अंतिम स्थिति होती है, अर्थात, जब राज्य के दृश्य प्रतिनिधित्व में बिंदु के दाईं ओर कोई प्रतीक नहीं होता है।
इनपुट स्थिति k पर निर्धारित स्थिति को S(k) कहा जाता है। पार्सर को S(0) के साथ सीड किया गया है जिसमें केवल शीर्ष-स्तरीय नियम शामिल है। पार्सर फिर तीन ऑपरेशनों को बार-बार निष्पादित करता है: भविष्यवाणी, स्कैनिंग और पूर्णता।
- भविष्यवाणी: फॉर्म (X → α • Y β, j) के S(k) में प्रत्येक अवस्था के लिए (जहाँ j ऊपर की तरह मूल स्थिति है), बाईं ओर Y के साथ व्याकरण में प्रत्येक उत्पादन के लिए S(k) में (Y → • γ, k) जोड़ें (Y → γ)।
- स्कैनिंग: यदि a इनपुट स्ट्रीम में अगला प्रतीक है, तो फॉर्म (X → α • a β, j) के S(k) में प्रत्येक स्थिति के लिए, S(k+1) में (X → α a • β, j) जोड़ें।
- समापन: फॉर्म (Y → γ •, j) के S(k) में प्रत्येक राज्य के लिए, फॉर्म (X → α • Y β, i) के S(j) में सभी राज्यों को खोजें और (X → α Y • β, i) को S(k) में जोड़ें।
राज्य सेट में डुप्लिकेट राज्य नहीं जोड़े जाते, केवल नए राज्य जोड़े जाते हैं। ये तीन ऑपरेशन तब तक दोहराए जाते हैं जब तक सेट में कोई नया राज्य नहीं जोड़ा जा सके। सेट को आम तौर पर संसाधित करने के लिए राज्यों की एक कतार के रूप में कार्यान्वित किया जाता है, जिसमें ऑपरेशन इस पर निर्भर करता है कि यह किस प्रकार की स्थिति है।
एल्गोरिदम स्वीकार करता है यदि (X → γ •, 0) S(n) में समाप्त होता है, जहां (X → γ) शीर्ष स्तर-नियम है और n इनपुट लंबाई है, अन्यथा यह अस्वीकार कर देता है।
स्यूडोकोड
भाषण और भाषा प्रसंस्करण से अनुकूलित[5] डेनियल जुराफ़्स्की और जेम्स एच. मार्टिन द्वारा,
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
यह राज्य सेटों का क्रम है:
| (state no.) | Production | (Origin) | Comment |
|---|---|---|---|
| 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) |
स्थिति (पी → एस •, 0) एक पूर्ण पार्स का प्रतिनिधित्व करती है। यह स्थिति S(3) और S(1) में भी दिखाई देती है, जो पूर्ण वाक्य हैं।
पार्स वन का निर्माण
अर्ली का शोध प्रबंध[6] अर्ली आइटम में प्रत्येक गैर-टर्मिनल से पॉइंटर्स का एक सेट जोड़कर पार्स ट्री के निर्माण के लिए एक एल्गोरिदम का संक्षेप में वर्णन करता है, जिसके कारण इसे पहचाना गया। लेकिन मैंने इसे मसरू के रूप में देखा ने ध्यान दिया[7] यह प्रतीकों के बीच संबंधों को ध्यान में नहीं रखता है, इसलिए यदि हम व्याकरण एस → एसएस | पर विचार करते हैं b और स्ट्रिंग bbb, यह केवल नोट करता है कि प्रत्येक S एक या दो b से मेल खा सकता है, और इस प्रकार bb और bbbb के लिए नकली व्युत्पत्ति के साथ-साथ bbb के लिए दो सही व्युत्पत्तियाँ उत्पन्न करता है।
एक और तरीका[8] जैसे-जैसे आप आगे बढ़ते हैं, पार्स फ़ॉरेस्ट का निर्माण करना है, प्रत्येक अर्ली आइटम को एक पॉइंटर के साथ साझा पैक्ड पार्स फ़ॉरेस्ट (एसपीपीएफ) नोड में ट्रिपल (एस, आई, जे) के साथ लेबल करना, जहां एस एक प्रतीक या एलआर (0) आइटम है (डॉट के साथ उत्पादन नियम), और आई और जे इस नोड द्वारा प्राप्त इनपुट स्ट्रिंग का अनुभाग देते हैं। एक नोड की सामग्री या तो एकल व्युत्पत्ति देने वाले चाइल्ड पॉइंटर्स की एक जोड़ी होती है, या पैक किए गए नोड्स की एक सूची होती है, जिनमें से प्रत्येक में पॉइंटर्स की एक जोड़ी होती है और एक व्युत्पत्ति का प्रतिनिधित्व होता है। एसपीपीएफ नोड्स अद्वितीय हैं (दिए गए लेबल के साथ केवल एक ही है), लेकिन वाक्यात्मक अस्पष्टता पार्स के लिए एक से अधिक व्युत्पत्ति हो सकती है। इसलिए भले ही कोई ऑपरेशन अर्ली आइटम नहीं जोड़ता (क्योंकि यह पहले से मौजूद है), फिर भी यह आइटम के पार्स फ़ॉरेस्ट में व्युत्पत्ति जोड़ सकता है।
- पूर्वानुमानित आइटम में एक शून्य SPPF सूचक होता है।
- स्कैनर एक एसपीपीएफ नोड बनाता है जो उस गैर-टर्मिनल का प्रतिनिधित्व करता है जिसे वह स्कैन कर रहा है।
- फिर जब स्कैनर या कंप्लीटर किसी आइटम को आगे बढ़ाता है, तो वे एक व्युत्पत्ति जोड़ते हैं जिसके बच्चे उस आइटम से नोड होते हैं जिसका बिंदु उन्नत था, और एक नए प्रतीक के लिए जो आगे बढ़ाया गया था (गैर-टर्मिनल या पूर्ण आइटम)।
एसपीपीएफ नोड्स को कभी भी पूर्ण एलआर (0) आइटम के साथ लेबल नहीं किया जाता है: इसके बजाय उन्हें उत्पादित प्रतीक के साथ लेबल किया जाता है ताकि सभी व्युत्पत्तियां एक नोड के तहत संयुक्त हो जाएं, चाहे वे किसी भी वैकल्पिक उत्पादन से आएं।
अनुकूलन
फिलिप मैकलीन और आर. निगेल हॉर्सपूल ने अपने पेपर में ए फास्टर अर्ली पार्सर अर्ली पार्सिंग को एलआर पार्सिंग के साथ जोड़ा और परिमाण के क्रम में सुधार हासिल किया।
यह भी देखें
- CYK एल्गोरिदम
- प्रसंग-मुक्त व्याकरण
- एल्गोरिदम की सूची#पार्सिंग
उद्धरण
- ↑ Kegler, Jeffrey. "What is the Marpa algorithm?". Retrieved 20 August 2013.
- ↑ Earley, Jay (1968). An Efficient Context-Free Parsing Algorithm (PDF). Carnegie-Mellon Dissertation.
- ↑ Earley, Jay (1970), "An efficient context-free parsing algorithm" (PDF), Communications of the ACM, 13 (2): 94–102, doi:10.1145/362007.362035, S2CID 47032707, archived from the original (PDF) on 2004-07-08
- ↑ John E. Hopcroft and Jeffrey D. Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Reading/MA: Addison-Wesley. ISBN 978-0-201-02988-8. p.145
- ↑ Jurafsky, D. (2009). Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Pearson Prentice Hall. ISBN 9780131873216.
- ↑ Earley, Jay (1968). An Efficient Context-Free Parsing Algorithm (PDF). Carnegie-Mellon Dissertation. p. 106.
- ↑ Tomita, Masaru (April 17, 2013). Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Springer Science and Business Media. p. 74. ISBN 978-1475718850. Retrieved 16 September 2015.
- ↑ Scott, Elizabeth (April 1, 2008). "प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.
अन्य संदर्भ सामग्री
- 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] - कुछ आवश्यक परीक्षण मामलों के साथ वोल्फ्राम भाषा प्रोग्रामिंग भाषा में अर्ली पार्सर का एक बुनियादी न्यूनतम कार्यान्वयन।
संसाधन
श्रेणी:पार्सिंग एल्गोरिदम श्रेणी:गतिशील प्रोग्रामिंग
