👨🏿‍🚒 👎🏾 🍞 जावास्क्रिप्ट में पार्सर्स कैसे लिखें 🕸️ 🤷🏾 🎅🏼

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

मुख्य विचार

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

var digit = { exec: function (str, pos) { var chr = str.charAt(pos); if (chr >= "0" && chr <= "9") return { res: +chr, end: pos + 1}; } };

अब डिजिट एक पार्सिंग डिजिट पैटर्न है और इसे इस तरह इस्तेमाल किया जा सकता है:

 assert.deepEqual(digit.exec("5", 0), { res: 5, end: 1 }); assert.deepEqual(digit.exec("Q", 0), void 0);

ऐसा इंटरफेस क्यों? क्योंकि JS में बिल्ट-इन RegExp क्लास है जिसमें बहुत ही समान इंटरफ़ेस है। सुविधा के लिए, हम पैटर्न क्लास का परिचय देते हैं (इसे RegExp के एक एनालॉग के रूप में देखें) जिनके उदाहरण ये पैटर्न होंगे:

 function Pattern(exec) { this.exec = exec; }

फिर हम कुछ सरल पैटर्न पेश करते हैं जो अधिक या कम जटिल पार्सर में उपयोगी होते हैं।

सरल पैटर्न

सबसे सरल पैटर्न txt है - यह पाठ की एक निश्चित, पूर्व निर्धारित रेखा को पार करता है:

 function txt(text) { return new Pattern(function (str, pos) { if (str.substr(pos, text.length) == text) return { res: text, end: pos + text.length }; }); }

इसे निम्नानुसार लागू किया जाता है:

 assert.deepEqual(txt("abc").exec("abc", 0), { res: "abc", end: 3 }); assert.deepEqual(txt("abc").exec("def", 0), void 0);

यदि JS के पास डिफ़ॉल्ट निर्माता (C ++ में) हैं, तो अधिक जटिल पैटर्न बनाने के संदर्भ में txt ("abc") प्रविष्टि को "abc" छोटा किया जा सकता है।

फिर हम नियमित अभिव्यक्तियों के लिए इसके एनालॉग को पेश करते हैं और इसे आरजीएक्स कहते हैं:

 function rgx(regexp) { return new Pattern(function (str, pos) { var m = regexp.exec(str.slice(pos)); if (m && m.index === 0) return { res: m[0], end: pos + m[0].length }; }); }

इसे इस तरह लागू करें:

 assert.deepEqual(rgx(/\d+/).exec("123", 0), { res: "123", end: 3 }); assert.deepEqual(rgx(/\d+/).exec("abc", 0), void 0);

फिर, यदि JS के पास डिफ़ॉल्ट निर्माता हैं, तो rgx (/ abc /) प्रविष्टि को / abc / तक छोटा किया जा सकता है।

संयोजक पैटर्न

अब आपको कई पैटर्न दर्ज करने की आवश्यकता है जो मौजूदा पैटर्न को जोड़ती है। इनमें से सबसे सरल "कॉम्बीनेटर" विकल्प है - यह किसी भी पैटर्न को वैकल्पिक बनाता है, अर्थात यदि मूल पैटर्न p पाठ को पार्स नहीं कर सकता है, तो उसी पाठ पर ऑप्ट (p) कहेंगे कि सब कुछ पार्स हो गया है, केवल पार्सिंग परिणाम रिक्त है:

 function opt(pattern) { return new Pattern(function (str, pos) { return pattern.exec(str, pos) || { res: void 0, end: pos }; }); }

उपयोग उदाहरण:

 assert.deepEqual(opt(txt("abc")).exec("abc"), { res: "abc", end: 3 }); assert.deepEqual(opt(txt("abc")).exec("123"), { res: void 0, end: 0 });

यदि ऑपरेटर ओवरलोडिंग और डिफ़ॉल्ट कन्स्ट्रक्टर जेएस में संभव था, तो रिकॉर्ड ऑप्ट (पी) को कम किया जा सकता है पी || शून्य 0 (यह स्पष्ट रूप से देखा जाता है कि ऑप्ट कैसे लागू किया जाता है)।

अगला सबसे जटिल कॉम्बीनेटर एक्स है - यह केवल वही बताता है जो पहले पैटर्न को पार्स कर सकता है और दूसरे को पार्स नहीं कर सकता है:

 function exc(pattern, except) { return new Pattern(function (str, pos) { return !except.exec(str, pos) && pattern.exec(str, pos); }); }

यदि W (p) उन पाठों का समूह है जो p पैटर्न को पार्स करता है, तो W (exc (p, q)) = W (p) \ W (q)। यह सुविधाजनक है, उदाहरण के लिए, जब आपको पत्र एच को छोड़कर सभी पूंजी पत्रों को पार्स करने की आवश्यकता होती है:

 var p = exc(rgx(/[AZ]/), txt("H")); assert.deepEqual(p.exec("R", 0), { res: "R", end: 1 }); assert.deepEqual(p.exec("H", 0), void 0);

यदि JS में ऑपरेटर ओवरलोडिंग था, तो exc (p1, P2) को p1 - P2 या to! P2 && p1 तक कम किया जा सकता है (हालांकि, इसके लिए, सभी को एक संयोजन पैटर्न लागू करना आवश्यक होगा / और जो && ऑपरेटर के रूप में काम करेगा) ।

फिर कोई भी कॉम्बिनेटर पैटर्न आता है - यह कई पैटर्न लेता है और एक नया निर्माण करता है जो इन पैटर्नों में से सबसे पहले पार्स करता है। हम कह सकते हैं कि W (कोई भी (p1, P2, p3, ...) = W (p1) v W (P2) v W (p3) v ...

 function any(...patterns) { return new Pattern(function (str, pos) { for (var r, i = 0; i < patterns.length; i++) if (r = patterns[i].exec(str, pos)) return r; }); }

मैंने ... [(.slice.call (तर्क, 0)) जैसे अनाड़ी कोड से बचने के लिए पैटर्न (सामंजस्य: rest_parameters) का निर्माण किया। किसी का उपयोग करने का एक उदाहरण:

 var p = any(txt("abc"), txt("def")); assert.deepEqual(p.exec("abc", 0), { res: "abc", end: 3 }); assert.deepEqual(p.exec("def", 0), { res: "def", end: 3 }); assert.deepEqual(p.exec("ABC", 0), void 0);

यदि जेएस में ऑपरेटर ओवरलोडिंग थे, तो कोई भी (पी 1, पी 2) पी 1 से कम हो सकता है || p2।

अगला संयोजन पैटर्न seq है - यह क्रमबद्ध रूप से पैटर्न के अनुक्रम द्वारा इसे दिए गए पाठ को पार्स करता है और परिणामों की एक सरणी उत्पन्न करता है:

 function seq(...patterns) { return new Pattern(function (str, pos) { var i, r, end = pos, res = []; for (i = 0; i < patterns.length; i++) { r = patterns[i].exec(str, end); if (!r) return; res.push(r.res); end = r.end; } return { res: res, end: end }; }); }

इसे निम्नानुसार लागू किया जाता है:

 var p = seq(txt("abc"), txt("def")); assert.deepEqual(p.exec("abcdef"), { res: ["abc", "def"], end: 6 }); assert.deepEqual(p.exec("abcde7"), void 0);

यदि JS में ऑपरेटर ओवरलोडिंग थे, तो seq (p1, P2) को p1, P2 तक कम किया जा सकता है (अल्पविराम ऑपरेटर ओवरलोडेड है)।

और अंत में, रेप कॉम्बिनेटर पैटर्न - यह कई बार पाठ के लिए प्रसिद्ध पैटर्न को लागू करता है और परिणामों की एक सरणी पैदा करता है। एक नियम के रूप में, यह एक ही प्रकार के कुछ संरचनाओं को पार्स करने के लिए उपयोग किया जाता है, कहते हैं, कॉमास, इसलिए प्रतिनिधि दो तर्क लेते हैं: मुख्य पैटर्न जिसके परिणाम हमारे लिए दिलचस्प हैं और अलग-अलग पैटर्न जिनके परिणाम त्याग दिए गए हैं:

 function rep(pattern, separator) { var separated = !separator ? pattern : seq(separator, pattern).then(r => r[1]); return new Pattern(function (str, pos) { var res = [], end = pos, r = pattern.exec(str, end); while (r && r.end > end) { res.push(r.res); end = r.end; r = separated.exec(str, end); } return { res: res, end: end }; }); }

आप एक जोड़े को और अधिक पैरामीटर मिनट और अधिकतम जोड़ सकते हैं जो नियंत्रित करेगा कि कितने पुनरावृत्ति की अनुमति है। यहाँ मैंने फ़ंक्शन (z) {रिटर्न z [1]} नहीं लिखने के लिए तीर फ़ंक्शन r => r [1] (सद्भाव: arrow_functions) का उपयोग किया। ध्यान दें कि पैटर्न के बाद seq को कैसे कम करता है # (फिर Promise # से लिया गया विचार):

 function Pattern(exec) { ... this.then = function (transform) { return new Pattern(function (str, pos) { var r = exec(str, pos); return r && { res: transform(r.res), end: r.end }; }); }; }

यह विधि आपको पहले के परिणामों के लिए एक मनमाना परिवर्तन लागू करके दूसरे पैटर्न से अनुमान लगाने की अनुमति देती है। वैसे, हास्केल के विशेषज्ञ, क्या यह कहना संभव है कि यह पैटर्न # फिर एक पैटर्न से एक सनक बनाता है?

खैर, प्रतिनिधि इस तरह से लागू किया जाता है:

 var p = rep(rgx(/\d+/), txt(",")); assert.deepEqual(p.exec("1,23,456", 0), { res: ["1", "23", "456"], end: 8 }); assert.deepEqual(p.exec("123ABC", 0), { res: ["123"], end: 3 }); assert.deepEqual(p.exec("ABC", 0), void 0);

प्रतिनिधि के लिए ओवरलोडिंग के साथ कोई स्पष्ट सादृश्य मेरे लिए नहीं होता है।

परिणाम इन सभी प्रतिनिधि / seq / किसी के लिए लगभग 70 लाइनें है। यह कॉम्बिनेटर पैटर्न की सूची को पूरा करता है, और हम एक पैटर्न के वास्तविक निर्माण के लिए आगे बढ़ सकते हैं जो एक्सएमएल-जैसे पाठ को पहचानता है।

XML- जैसे पाठ के लिए पार्सर

हम खुद को ऐसे XML-जैसे ग्रंथों तक सीमित रखते हैं:

 <?xml version="1.0" encoding="utf-8"?> <book title="Book 1"> <chapter title="Chapter 1"> <paragraph>123</paragraph> <paragraph>456</paragraph> </chapter> <chapter title="Chapter 2"> <paragraph>123</paragraph> <paragraph>456</paragraph> <paragraph>789</paragraph> </chapter> <chapter title="Chapter 3"> ... </chapter> </book>

इसके साथ शुरू करने के लिए, हम एक पैटर्न लिखेंगे जो फॉर्म नाम के एक नामित विशेषता को पहचानता है = "मूल्य" - यह स्पष्ट रूप से अक्सर एक्सएमएल में पाया जाता है:

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join('')); var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] }));

यहाँ attr एक स्ट्रिंग के रूप में एक मूल्य के साथ एक नामित विशेषता को उद्धृत करता है, उद्धृत - उद्धरण चिह्नों में एक स्ट्रिंग को पार्स करता है, चार - स्ट्रिंग में एक अक्षर को पार्स करता है (इसे एक अलग पैटर्न के रूप में क्यों लिखा जाना चाहिए? तो, तो "सिखाने" इस चार्ट तथाकथित xml संस्थाओं को पार्स करने के लिए? ), लेकिन नाम विशेषता नाम को पार्स करता है (ध्यान दें कि यह पूंजी और छोटे अक्षरों दोनों को पार्स करता है, लेकिन पार्स नाम को वापस लौटाता है जहां सभी अक्षर छोटे हैं)। एटर एप्लिकेशन इस तरह दिखता है:

 assert.deepEqual( attr.exec('title="Chapter 1"', 0), { res: { name: "title", value: "Chapter 1" }, end: 17 });

अगला, हम एक ऐसा पैटर्न बनाते हैं जो हेडर को <<?

 var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]);

यहाँ wsp parses एक या एक से अधिक रिक्त स्थान, एक या अधिक नामित विशेषताओं को पार्स करता है और पार्स को एक शब्दकोश के रूप में लौटाता है (प्रतिनिधि नाम-मान जोड़े की एक सरणी लौटाता है, लेकिन शब्दकोश अधिक सुविधाजनक होता है, इसलिए सरणी तब शब्दकोश में परिवर्तित हो जाती है), और शीर्ष लेख शीर्ष लेख को स्वयं प्रकट करता है। एक ही शब्दकोश के रूप में केवल शीर्षक गुण देता है:

 assert.deepEqual( header.exec('<?xml version="1.0" encoding="utf-8"?>', 0), { res: { version: "1.0", encoding: "utf-8" }, end: ... });

अब चलते हैं फॉर्म के नोड्स को पार्स करने के लिए आगे बढ़ते हैं <नोड ...> ...:

 var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = seq( txt('<'), name, wsp, attrs, txt('>'), rep(any(text, subnode), opt(wsp)), txt('</'), name, txt('>')) .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] }));

यहाँ टेक्स्ट नोड के अंदर टेक्स्ट को पार्स करता है और एक चार पैटर्न का उपयोग करता है जिसे xml एंटिटीज को पहचानने के लिए सीखा जा सकता है, सब्नोड आंतरिक नोड (वास्तव में सब्नोड = नोड) को पार्स करता है और नोड नोड को विशेषताओं और आंतरिक नोड के साथ पार्स करता है। सब्नोडे की ऐसी पेचीदा परिभाषा क्यों? यदि आप नोड को सीधे नोड की परिभाषा में संदर्भित करते हैं (कुछ इस तरह: नोड = seq (..., नोड, ...)), तो यह पता चलता है कि नोड की परिभाषा के समय यह चर अभी भी खाली है। सबनोड ट्रिक इस परिपत्र निर्भरता को समाप्त करती है।

यह उस पैटर्न को निर्धारित करने के लिए रहता है जो हेडर के साथ पूरी फाइल को पहचानता है:

 var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));

आवेदन तदनुसार है:

 assert.deepEqual( xml.exec(src), { attrs: { version: '1.0', encoding: 'utf-8' }, root: { name: 'book', attrs: { title: 'Book 1' }, nodes: [ { name: 'chapter', attrs: { title: 'Chapter 1' }, nodes: [...] }, ... ] } });

यहाँ मैं पैटर्न को एक तर्क के साथ निष्पादित करता हूं और इसका अर्थ यह है कि मैं शुरुआत से ही तार को पार्स करना चाहता हूं और सुनिश्चित करता हूं कि इसे अंत तक पार्स किया गया है, लेकिन चूंकि यह अंत तक पार्स किया गया है, यह केवल उस जगह पर एक पॉइंटर के बिना पार्स किए गए एक को वापस करने के लिए पर्याप्त है जहां पार्सर बंद हो गया (मुझे पहले से ही पता है कि यह पंक्ति का अंत है):

 function Pattern(name, exec) { ... this.exec = function (str, pos) { var r = exec(str, pos || 0); return pos >= 0 ? r : !r ? null : r.end != str.length ? null : r.res; }; }

वास्तव में पूरा पार्सर 20 लाइनों में है (उन 70 के बारे में मत भूलो जो प्रतिनिधि, seq, किसी भी, आदि को लागू करते हैं):

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join('')); var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] })); var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]); var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = seq( txt('<'), name, wsp, attrs, txt('>'), rep(any(text, subnode), opt(wsp)), txt('</'), name, txt('>')) .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] })); var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));

JS (या C ++) में ऑपरेटर ओवरलोडिंग के साथ, यह कुछ इस तरह दिखाई देगा:

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = ('"' + rep(char) + '"').then(r => r[1].join('')); var attr = (name + '=' + quoted).then(r => ({ name: r[0], value: r[2] })); var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = ('<?xml' + wsp + attrs + '?>').then(r => r[2]); var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = ('<' + name + wsp + attrs + '>' + rep(text | subnode) + (wsp | null) + '</' + name + '>') .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] })); var xml = (header + node).then(r => ({ root: r[1], attrs: r[0] }));

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

 var dataurl = new ABNF('"data:" mime ";" attrs, "," data', { mime: /[az]+\/[az]+/i, attrs: ..., data: /.*/ }).then(r => ({ mime: r[1], attrs: r[3], data: r[5] }));

और हमेशा की तरह लागू करें:

 assert.deepEqual( dataurl.exec('data:text/plain;charset="utf-8",how+are+you%3f'), { mime: "text/plain", attrs: { charset: "utf-8" }, data: "how are you?" });

कुछ और बीचे

यदि पार्स विफल हुआ तो पैटर्न # निष्पादन रिटर्न अशक्त / अपरिभाषित क्यों है? अपवाद क्यों नहीं फेंकते? यदि आप इस तरह से अपवादों का उपयोग करते हैं, तो पार्सर हर बीस धीमा हो जाएगा। अपवाद असाधारण मामलों के लिए अच्छे हैं।

वर्णित विधि आपको एलएल पार्सर लिखने की अनुमति देती है जो सभी उद्देश्यों के लिए उपयुक्त नहीं हैं। उदाहरण के लिए, यदि आपको फ़ॉर्म के XML को पार्स करने की आवश्यकता है

 <book attr1="..." attr2="..."    ???

उस जगह पर जहां यह खड़ा है ??? यह दोनों / और बस> हो सकता है। अब अगर LL पार्सर ने यह सब <किताब ...> के रूप में पार्स करने की कोशिश की लेकिन जगह में ??? यह निकला >>, तो पार्सर सब कुछ त्याग देगा कि यह पार्स करने में इतना लंबा समय लगा और इस धारणा के तहत फिर से शुरू होता है कि यह <किताब है ... />। एलआर पार्सर इस खामी से मुक्त हैं, लेकिन उन्हें लिखना मुश्किल है।

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

मुझे उम्मीद है कि कोई काम आएगा। एक समय में, मैंने अनाड़ी डिग्री के अलग-अलग अंशों के पार्सर लिखे थे, और ऊपर वर्णित विधि मेरे लिए एक खोज थी।

जावास्क्रिप्ट में पार्सर्स कैसे लिखें

मुख्य विचार

सरल पैटर्न

संयोजक पैटर्न

XML- जैसे पाठ के लिए पार्सर

कुछ और बीचे

More articles: