आपका स्वागत है! मैं आपके लिए अपनी जावास्क्रिप्ट प्रोग्रामिंग भाषा - पीएल ट्यूटोरियल को लागू करने के लिए एक गाइड का एक शौकिया अनुवाद प्रस्तुत करता हूं।

अनुवादक से

हम अपनी प्रोग्रामिंग भाषा - λ भाषा (मूल - λanguage में) बनाएंगे। निर्माण की प्रक्रिया में, हम कई दिलचस्प तकनीकों का उपयोग करेंगे, जैसे कि पुनरावर्ती वंश, नियंत्रण हस्तांतरण शैली, और बुनियादी अनुकूलन तकनीक। दुभाषिया के दो संस्करण बनाए जाएंगे - नियमित और सीपीएस दुभाषियों, जावास्क्रिप्ट में ट्रांस-कंपाइलर।

मूल के लेखक मिहाई Bazon , प्रसिद्ध UglifyJS पुस्तकालय (जेएस कोड को कम करने और प्रारूपित करने का एक उपकरण) के लेखक हैं।

प्रविष्टि

यदि आपने कभी अपना कंपाइलर या दुभाषिया लिखा है, तो आपके लिए कोई नई बात नहीं होगी। लेकिन अगर आप प्रोग्रामिंग भाषा की तरह दिखने वाली चीज़ को पार्स करने के लिए नियमित अभिव्यक्ति का उपयोग करते हैं, तो पार्सिंग पर अनुभाग पढ़ें। कम बग के साथ कोड लिखें!

"सरल से जटिल" क्रम में लेख को भागों में विभाजित किया गया है। मेरा सुझाव है कि आप लेख के कुछ हिस्सों को छोड़ दें, जब तक कि आप विषय को अच्छी तरह से नहीं समझते हैं। अगर आपको कुछ समझ नहीं आ रहा है तो आप हमेशा पीछे जा सकते हैं।

हम क्या सीखने जा रहे हैं:

• एक पार्सर क्या है, और इसे कैसे लिखना है।
• इंटरप्रेटर कैसे लिखें।
• स्थानांतरण की अगली कड़ी, और यह क्यों मायने रखता है।
• (ट्रांस) संकलक लेखन।
• निरंतरता हस्तांतरण शैली।
• कुछ बुनियादी कोड अनुकूलन तकनीक।
• जावास्क्रिप्ट की तुलना में हमारी λ भाषा में क्या नया है, इसके उदाहरण।

इसके साथ, मैं दिखाऊंगा कि लिस्प एक महान प्रोग्रामिंग भाषा क्यों है। हालाँकि, हम जिस भाषा पर काम कर रहे हैं, वह लिस्प नहीं है। इसमें रिच सिंटैक्स (एक क्लासिक इन्फिक्स नोटेशन जिसे हर कोई जानता है), स्कीम (मैक्रोज़ को छोड़कर) जैसी कुछ है। अच्छी या नहीं, लेकिन मैक्रोज़ लिस्प की मुख्य विशेषता है - ऐसा कुछ जो अन्य भाषाओं (लिस्प बोलियों को छोड़कर) के रूप में अच्छी तरह से नहीं करता है। (हां, मुझे SweetJS के बारे में पता है ... करीब है, लेकिन ऐसा नहीं है।)

लेकिन पहले, आइए हमारी प्रोग्रामिंग भाषा का परिचय दें।

λ भाषा

कुछ भी करने से पहले, हमारे पास एक स्पष्ट तस्वीर होनी चाहिए कि हम क्या करना चाहते हैं। भाषा के व्याकरण का वर्णन लिखना अच्छा होगा, लेकिन मैं इसे आसान बनाने जा रहा हूं - एक साधारण कार्यक्रम का एक उदाहरण लिखें, इसलिए यहां λ भाषा के कुछ उदाहरण दिए गए हैं:

#   println("Hello World!"); println(2 + 3 * 4); #       `lambda`  `λ` fib = lambda (n) if n < 2 then n else fib(n - 1) + fib(n - 2); println(fib(15)); print-range = λ(a, b) # `λ`     ,   `lambda` if a <= b then { # `then`  ,      print(a); if a + 1 <= b { print(", "); print-range(a + 1, b); } else println(""); #   }; print-range(1, 5); 

निष्कर्ष:

 Hello World! 14 610 1, 2, 3, 4, 5 

भाषा जावास्क्रिप्ट के समान है, लेकिन कुल मिलाकर यह नहीं है। सबसे पहले, कोई बयान नहीं हैं, केवल अभिव्यक्ति। एक अभिव्यक्ति को एक मूल्य वापस करना चाहिए और किसी अन्य अभिव्यक्ति में कहीं भी उपयोग किया जा सकता है। अभिव्यक्तियों के "अनुक्रम" में अभिव्यक्तियों को अलग करने के लिए अर्धविराम की आवश्यकता होती है। घुंघराले ब्रेसेस { और } एक अनुक्रम बनाते हैं जो स्वयं एक अभिव्यक्ति है, और इसका मान अनुक्रम से अंतिम मान है। निम्नलिखित कार्यक्रम सही है:

 a = { fib(10); #    ,      fib(15) #        }; print(a); #  610 

lambda या λ कीवर्ड का उपयोग करके कार्य बनाए जाते हैं। उसके बाद, कोष्ठक में तर्क नामों की एक (संभवतः खाली) सूची है, जो अल्पविराम द्वारा अलग की जाती है। एक फ़ंक्शन का शरीर एक अभिव्यक्ति है, लेकिन एक अनुक्रम में संलग्न किया जा सकता है {...} । यह भी ध्यान देने योग्य है कि कोई return कीवर्ड नहीं है। फ़ंक्शन अंतिम अभिव्यक्ति का मान लौटाता है।

इसके अलावा, कोई var नहीं। एक चर जोड़ने के लिए आप उपयोग कर सकते हैं कि जावास्क्रिप्ट प्रोग्रामर IIFE क्या कहते हैं। lambda उपयोग करें, चर को तर्क के रूप में घोषित करें। चरों के लिए, दायरा एक फ़ंक्शन है, और फ़ंक्शन क्लोजर हैं, जैसा कि जावास्क्रिप्ट [लगभग। अनुवाद: ES6 तक]।

भले if एक अभिव्यक्ति है। जावास्क्रिप्ट ऐसा करने के लिए टर्नरी ऑपरेटर का उपयोग करता है:

 a = foo() ? bar() : baz(); // JavaScript a = if foo() then bar() else baz(); # λ 

then कीवर्ड वैकल्पिक है यदि शाखा एक अनुक्रम ( {...} ) है, जैसा कि आप ऊपर देख सकते हैं। एक अन्य मामले में, यह आवश्यक है। वैकल्पिक शाखा मौजूद होने पर else उपयोग किया जाता है। और फिर, then और अभिव्यक्ति को शरीर के रूप में लेते हैं, लेकिन आप {...} का उपयोग करके कई अभिव्यक्तियों को एक में जोड़ सकते हैं। यदि else अनुपस्थित है और स्थिति false , तो सभी का परिणाम false । यह ध्यान देने योग्य है कि false एक कीवर्ड है जो एक मान का प्रतिनिधित्व करता है जो एक λ भाषा में एकमात्र गलत मान है:

 if foo() then print("OK"); 

उत्पादन OK अगर और केवल अगर foo() परिणाम false नहीं false । इसके अलावा, वहाँ कीवर्ड true , लेकिन बिल्कुल सब कुछ जो false नहीं false (जावास्क्रिप्ट के भीतर, ऑपरेटर === ) शाखाओं में true माना जाएगा (नंबर 0 और खाली स्ट्रिंग सहित "" )।

ध्यान दें कि if में अभिव्यक्ति के आसपास कोष्ठक की कोई आवश्यकता नहीं है। यदि आप उन्हें जोड़ते हैं, तो यह एक गलती नहीं होगी, क्योंकि ( अभिव्यक्ति शुरू होती है, लेकिन वे सिर्फ सतही हैं।

संपूर्ण कार्यक्रम को तब भी पार्स किया जा सकता है, भले ही वह कोष्ठकों से घिरा हो, इसलिए आपको जोड़ना चाहिए ; प्रत्येक अभिव्यक्ति के बाद। अंतिम अभिव्यक्ति एक अपवाद है।

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

इसके बाद, हम अपनी भाषा के लिए एक पार्सर लिखेंगे।

एएसटी के लिए कोड रूपांतरण

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

उदाहरण के लिए, हमारे पास निम्नलिखित कोड हैं:

 sum = lambda(a, b) { a + b; }; print(sum(1, 2)); 

हमारा पार्सर एक जावास्क्रिप्ट ऑब्जेक्ट के रूप में एक पेड़ उत्पन्न करेगा:

 { type: "prog", prog: [ //  : { type: "assign", operator: "=", left: { type: "var", value: "sum" }, right: { type: "lambda", vars: [ "a", "b" ], body: { //     "prog",  ,  //     ,  //     . type: "binary", operator: "+", left: { type: "var", value: "a" }, right: { type: "var", value: "b" } } } }, //  : { type: "call", func: { type: "var", value: "print" }, args: [{ type: "call", func: { type: "var", value: "sum" }, args: [ { type: "num", value: 1 }, { type: "num", value: 2 } ] }] } ] } 

पार्सर बनाने में मुख्य कठिनाई कोड को ठीक से व्यवस्थित करने में कठिनाई है। एक स्ट्रिंग से वर्ण पढ़ने की तुलना में पार्सर को उच्च स्तर पर काम करना चाहिए। कोड जटिलता को कम करने के लिए कुछ दिशानिर्देश:

• बहुत सारी छोटी छोटी विशेषताएँ लिखिए। प्रत्येक फ़ंक्शन में, एक काम करें और इसे अच्छी तरह से करें।
• पार्सिंग के लिए नियमित अभिव्यक्ति का उपयोग करने की कोशिश न करें। वे सिर्फ काम नहीं करते। वे शाब्दिक विश्लेषक में उपयोगी हो सकते हैं, लेकिन, सादगी के लिए, हम उनका उपयोग नहीं करेंगे।
• अनुमान लगाने की कोशिश न करें। जब आप निश्चित नहीं हैं कि किसी चीज़ को पार्स कैसे करें, तो त्रुटि (पंक्ति और स्तंभ) के स्थान वाले अपवाद को फेंक दें।

कोड को सरल रखने के लिए, हम इसे तीन भागों में विभाजित करेंगे, जो बदले में कई छोटे कार्यों में विभाजित हैं:

• चरित्र की धारा
• टोकन प्रवाह (टोकन)
• पार्सर

चरित्र की धारा

यह सबसे आसान हिस्सा है। हम एक स्ट्रीम ऑब्जेक्ट बनाएंगे जो एक स्ट्रिंग से क्रमिक रूप से पढ़ने वाले पात्रों के संचालन का प्रतिनिधित्व करेगा। इसमें चार कार्य शामिल हैं:

• peek() - धारा से निकाले बिना अगला वर्ण लौटाता है।
• next() - धारा से निकालते हुए, अगला वर्ण लौटाता है।
• eof() - यदि धारा में अधिक वर्ण नहीं हैं तो यह true है।
• croak(msg) - संदेश ( msg ) और धारा में वर्तमान स्थिति वाले एक अपवाद को फेंकता है।

अंतिम फ़ंक्शन की आवश्यकता है ताकि आप त्रुटि के स्थान वाले अपवाद को फेंक सकें।

यहाँ इस ऑब्जेक्ट के लिए पूरा कोड है (चलो इसे InputStream कहते हैं)। यह काफी छोटा है, इसलिए आपको इसके साथ समस्या नहीं होनी चाहिए:

 function InputStream(input) { var pos = 0, line = 1, col = 0; return { next : next, peek : peek, eof : eof, croak : croak, }; function next() { var ch = input.charAt(pos++); if (ch == "\n") line++, col = 0; else col++; return ch; } function peek() { return input.charAt(pos); } function eof() { return peek() == ""; } function croak(msg) { throw new Error(msg + " (" + line + ":" + col + ")"); } } 

कृपया ध्यान दें कि यह एक सामान्य वस्तु नहीं है (जो new के माध्यम से बनाई गई है)। इस ऑब्जेक्ट को प्राप्त करने के लिए, आपको आवश्यकता है: var stream = InputStream(string) ।

अगला, हम अमूर्तता के निम्नलिखित स्तर को लिखेंगे: टोकन प्रवाह (टोकन) ।

टोकन प्रवाह (टोकन)

टोकेनाइज़र (lexer) वर्णों की एक धारा का उपयोग करता है और एक ही इंटरफ़ेस के साथ एक ऑब्जेक्ट देता है, लेकिन peek() / next() फ़ंक्शन के रिटर्न मान टोकन होंगे। एक टोकन दो गुणों वाला एक प्रकार है: type , value । यहाँ टोकन के कुछ उदाहरण दिए गए हैं:

 { type: "punc", value: "(" } // . : , ,     . . { type: "num", value: 5 } //  { type: "str", value: "Hello World!" } //  { type: "kw", value: "lambda" } //   { type: "var", value: "a" } //  { type: "op", value: "!=" } //  

व्हाट्सएप (स्पेस, टैब, लाइन ब्रेक) और टिप्पणियां बस छोड़ दी जाती हैं।

एक टोकन लिखने के लिए, हमें अपनी भाषा पर करीब से नज़र डालने की ज़रूरत है। विचार यह है कि वर्तमान चरित्र ( input.peek() ) के आधार पर हम यह तय कर सकते हैं कि कौन सा टोकन पढ़ना है:

• सबसे पहले, व्हाट्सएप को स्किप करें।
• यदि input.eof() , तो null लौटें।
• यदि यह # वर्ण है, तो सभी वर्णों को पंक्ति के अंत तक छोड़ें (और अगला टोकन लौटाएं)।
• यदि यह एक उद्धरण चिह्न है, तो स्ट्रिंग पढ़ें।
• यदि यह एक संख्या है, तो संख्या पढ़ें।
• यदि यह एक पत्र है, तो हम शब्द पढ़ते हैं, और पहचानकर्ता या कीवर्ड वापस करते हैं।
• यदि यह विशेष वर्णों में से एक है, तो संबंधित टोकन लौटाएं।
• यदि यह ऑपरेटरों के प्रतीकों में से एक है, तो हम संबंधित टोकन लौटाते हैं।
• यदि उपरोक्त में से कोई भी लागू नहीं होता है, तो input.croak() का उपयोग करके एक अपवाद फेंक दें।

हमारे पास tokenizer का मुख्य कार्य read_next फ़ंक्शन होगा:

 function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } 

यहां आप कई अतिरिक्त फ़ंक्शन देख सकते हैं जो विभिन्न प्रकार के टोकन read_string() , जैसे कि read_string() , read_number() , आदि ... उन्हें अलग-अलग फ़ंक्शन में रखा जाता है, ताकि कोड सरल और अधिक सुंदर दिखाई दे।

इसके अलावा, यह दिलचस्प है कि हम एक ही बार में सभी प्रतीकों को दूर नहीं करते हैं: हर बार जब पार्सर अगले टोकन के लिए पूछता है, तो हम एक टोकन पढ़ेंगे। यदि किसी प्रकार की गलती होती है, तो हमने सभी पात्रों को पढ़ा भी नहीं है।

read_ident() सभी वर्णों को एक पंक्ति में is_id() जो पहचानकर्ता ( is_id() ) का हिस्सा हो सकता है। पहचानकर्ता को पत्र, λ , या _ शुरू होना चाहिए, और इसमें एक ही वर्ण, संख्या या कोई भी शामिल हो सकता है: ?!-<>= । यह निम्नानुसार है कि foo-bar को तीन टोकन के रूप में नहीं पढ़ा जाएगा, लेकिन एक के रूप में ( var टोकन)। क्या यह इस तरह के is-pair? रूप is-pair? नाम के साथ कार्यों को परिभाषित करने में सक्षम होने के लिए आवश्यक है is-pair? या string>= (क्षमा करें, यह मेरे में लिस्पर है)।

इसके अलावा, read_ident() यह जांच करेगा कि क्या ज्ञात कीवर्ड की सूची में कोई पहचानकर्ता है, और यदि यह है, तो एक var -token को var -token के बजाय वापस कर दिया जाएगा।

मुझे लगता है कि कोड खुद के लिए बोलता है, इसलिए यहां हमारी भाषा के लिए एक तैयार टोकन है:

 function TokenStream(input) { var current = null; var keywords = " if then else lambda λ true false "; return { next : next, peek : peek, eof : eof, croak : input.croak }; function is_keyword(x) { return keywords.indexOf(" " + x + " ") >= 0; } function is_digit(ch) { return /[0-9]/i.test(ch); } function is_id_start(ch) { return /[a-zλ_]/i.test(ch); } function is_id(ch) { return is_id_start(ch) || "?!-<>=0123456789".indexOf(ch) >= 0; } function is_op_char(ch) { return "+-*/%=&|<>!".indexOf(ch) >= 0; } function is_punc(ch) { return ",;(){}[]".indexOf(ch) >= 0; } function is_whitespace(ch) { return " \t\n".indexOf(ch) >= 0; } function read_while(predicate) { var str = ""; while (!input.eof() && predicate(input.peek())) str += input.next(); return str; } function read_number() { var has_dot = false; var number = read_while(function(ch){ if (ch == ".") { if (has_dot) return false; has_dot = true; return true; } return is_digit(ch); }); return { type: "num", value: parseFloat(number) }; } function read_ident() { var id = read_while(is_id); return { type : is_keyword(id) ? "kw" : "var", value : id }; } function read_escaped(end) { var escaped = false, str = ""; input.next(); while (!input.eof()) { var ch = input.next(); if (escaped) { str += ch; escaped = false; } else if (ch == "\\") { escaped = true; } else if (ch == end) { break; } else { str += ch; } } return str; } function read_string() { return { type: "str", value: read_escaped('"') }; } function skip_comment() { read_while(function(ch){ return ch != "\n" }); input.next(); } function read_next() { read_while(is_whitespace); if (input.eof()) return null; var ch = input.peek(); if (ch == "#") { skip_comment(); return read_next(); } if (ch == '"') return read_string(); if (is_digit(ch)) return read_number(); if (is_id_start(ch)) return read_ident(); if (is_punc(ch)) return { type : "punc", value : input.next() }; if (is_op_char(ch)) return { type : "op", value : read_while(is_op_char) }; input.croak("Can't handle character: " + ch); } function peek() { return current || (current = read_next()); } function next() { var tok = current; current = null; return tok || read_next(); } function eof() { return peek() == null; } } 

• next() फ़ंक्शन हमेशा read_next() कॉल नहीं करता है, क्योंकि एक टोकन हो सकता है जिसे पहले पढ़ा गया हो ( peek() फ़ंक्शन का उपयोग करके)। इसके लिए, हमारे पास एक current चर है जिसमें वर्तमान टोकन शामिल है।
• केवल दशमलव संख्या नियमित संकेतन में समर्थित हैं (1E5, 0x, आदि समर्थित नहीं हैं)। लेकिन अगर हम उनका समर्थन जोड़ना चाहते हैं, तो हम केवल read_number() ।
• जावास्क्रिप्ट के विपरीत, केवल वर्ण जो एक स्ट्रिंग में अनसैप्ड नहीं किए जा सकते हैं, उद्धरण चिह्न और बैकलैश हैं। लाइनों में लाइन ब्रेक, टैब और कुछ भी हो सकता है। हम मानक संयोजनों जैसे \n , \t , आदि की व्याख्या नहीं करते हैं ... यह फिर से करना आसान है ( read_string() )।

अब हमारे पास आसानी से एक पार्सर लिखने के लिए शक्तिशाली उपकरण हैं, लेकिन पहले मैं एएसटी विवरण को देखने की सलाह दूंगा ।

एएसटी विवरण

जैसा कि ऊपर बताया गया है, पार्सर एक संरचना का निर्माण करेगा जो कार्यक्रम के शब्दार्थ को दर्शाता है। एएसटी में नोड्स होते हैं। प्रत्येक नोड एक नियमित जावास्क्रिप्ट ऑब्जेक्ट है जिसमें एक type संपत्ति होती है जो नोड के प्रकार को निर्धारित करती है, साथ ही अतिरिक्त जानकारी जो कि प्रकार पर निर्भर करती है।

 123.5 

 { type: "num", value: 123.5 } 

 "Hello World" 

 { type: "str", value: "Hello World!" } 

 true false 

 { type: "bool", value: true } { type: "bool", value: false } 

 foo 

 { type: "var", value: "foo" } 

 lambda (x) 10 #  λ (x) 10 

 { type: "lambda", vars: [ "x" ], body: { type: "num", value: 10 } } 

 foo(a, 1) 

 { "type": "call", "func": { "type": "var", "value": "foo" }, "args": [ { "type": "var", "value": "a" }, { "type": "num", "value": 1 } ] } 

 if foo then bar else baz 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" }, "else": { "type": "var", "value": "baz" } } 

 if foo then bar 

 { "type": "if", "cond": { "type": "var", "value": "foo" }, "then": { "type": "var", "value": "bar" } } 

 a = 10 

 { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } 

 x + y * z 

 { "type": "binary", "operator": "+", "left": { "type": "var", "value": "x" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "y" }, "right": { "type": "var", "value": "z" } } } 

 { a = 5; b = a * 2; a + b; } 

 { "type": "prog", "prog": [ { "type": "assign", "operator": "=", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 5 } }, { "type": "assign", "operator": "=", "left": { "type": "var", "value": "b" }, "right": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 2 } } }, { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } ] } 

 let (a = 10, b = a * 10) { a + b; } 

 { "type": "let", "vars": [ { "name": "a", "def": { "type": "num", "value": 10 } }, { "name": "b", "def": { "type": "binary", "operator": "*", "left": { "type": "var", "value": "a" }, "right": { "type": "num", "value": 10 } } } ], "body": { "type": "binary", "operator": "+", "left": { "type": "var", "value": "a" }, "right": { "type": "var", "value": "b" } } } 

पार्सर

पार्सर ऊपर वर्णित पेड़ का निर्माण करेगा।

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

 function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } 

यह फ़ंक्शन तब कहा जाएगा जब lambda कीवर्ड पहले से ही टोकन स्ट्रीम से लिया गया है, इसलिए हमें केवल तर्कों के नाम लेने होंगे। लेकिन चूंकि वे कोष्ठक में हैं और अल्पविराम द्वारा अलग किए गए हैं, हम इसे delimited फ़ंक्शन का उपयोग करके करेंगे, जो निम्न तर्क लेता है: start , stop , separator , parser फ़ंक्शन, जो प्रत्येक तत्व को अलग से पार्स करता है। इस मामले में, हम parse_varname फ़ंक्शन का उपयोग करते हैं, जो एक त्रुटि को फेंकता है यदि यह कुछ ऐसा नोटिस करता है जो एक चर की तरह नहीं दिखता है। फ़ंक्शन का शरीर एक अभिव्यक्ति है, इसलिए हम इसे parse_expression साथ प्राप्त करते हैं।

delimited फ़ंक्शन निम्न स्तर है:

 function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; //      a.push(parser()); } skip_punc(stop); return a; } 

जैसा कि आप देख सकते हैं, यह और भी अधिक फ़ंक्शंस का उपयोग करता है: is_punc और skip_punc । पहला रिटर्न true अगर वर्तमान टोकन दिया गया विराम चिह्न है (इसे निकाले बिना), जबकि skip_punc यह जांच करेगा कि क्या वर्तमान टोकन दिया गया विराम चिह्न वर्ण है और इसे निकालें (या अन्यथा एक अपवाद फेंकें)।

पूरे कार्यक्रम को पूरा करने वाला कार्य सबसे सरल प्रतीत होता है:

 function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } 

चूँकि हमारे पास केवल भाव हैं, हम बस parse_expression() कहते हैं और भावों को तब तक पढ़ते हैं जब तक हम सब कुछ नहीं पढ़ लेते। skip_punc(";") का उपयोग करते हुए, हम करते हैं ; प्रत्येक अभिव्यक्ति के बाद अनिवार्य है।

एक और सरल उदाहरण है parse_if() :

 function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } 

if वह कीवर्ड को छोड़ देता है (यदि वर्तमान टोकन if कीवर्ड नहीं है, if अपवाद को फेंकता है), if parse_expression() का उपयोग करके स्थिति पढ़ता है। यदि प्रतीक { आगे नहीं जाता है, तो तब कीवर्ड की आवश्यकता होती है (इसके बिना वाक्यविन्यास बहुत अच्छा नहीं लगता है)। शाखाएँ सिर्फ अभिव्यक्ति हैं, इसलिए हम उनके लिए फिर से parse_expression() उपयोग करते हैं। else शाखा वैकल्पिक है, इसलिए हम इसे पार्स करने से पहले कीवर्ड की उपस्थिति की जांच करते हैं।

कई छोटे कार्यों के साथ, हम कोड को सरल बना सकते हैं। हमने पार्सर को लगभग वैसा ही लिखा है, अगर हम विशेष रूप से वाक्य रचना को पार्स करने के लिए उच्च स्तरीय भाषा का उपयोग करते हैं। ये सभी फ़ंक्शन "पारस्परिक रूप से पुनरावर्ती" हैं, अर्थात, हमारे पास parse_atom() , जो कि वर्तमान टोकन के आधार पर, अन्य कार्यों को कॉल करता है। उनमें से एक है parse_if() (जिसे वर्तमान टोकन है if कहा जाता है) और यह बदले में parse_expression() कहता है। लेकिन parse_expression() कहता है। कोई अनंत पुनरावृत्ति नहीं है, क्योंकि कार्यों में से एक हमेशा कम से कम एक टोकन निकालता है।

इस तरह की पार्सिंग विधि को रिकर्सिव डिसेंट विधि कहा जाता है, और वास्तव में, लिखना सबसे आसान है।

निचला स्तर: parse_atom() और parse_expression()

parse_atom() फ़ंक्शन वर्तमान टोकन के आधार पर एक अन्य फ़ंक्शन को कॉल करता है:

 function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } 

जब वह शुरुआती ब्रैकेट को देखता है, तो कोष्ठक की अभिव्यक्ति को जाना चाहिए, इसलिए, ब्रैकेट को छोड़ते हुए, फ़ंक्शन parse_expression() कॉल करता है और उसके बाद समापन ब्रैकेट को छोड़ने की अपेक्षा करता है। यदि वह किसी प्रकार का कीवर्ड देखता है, तो वह संबंधित फ़ंक्शन को कॉल करता है। यदि वह एक स्थिर या पहचानकर्ता को देखती है, तो उसे उसी रूप में लौटाती है। और अगर कुछ भी नहीं आता है, तो यह unexpected() कहता है, जो एक अपवाद फेंकता है।

जब वह { देखता है, तो वह parse_prog के अनुक्रम को पार्स करने के लिए parse_prog कहता है। इसके अलावा, parse_prog एक सरल अनुकूलन करता है: यदि { और } बीच कोई भाव नहीं हैं, तो यह false , यदि केवल एक अभिव्यक्ति है, तो यह केवल इसे वापस करता है। अन्यथा, अभिव्यक्ति की एक सरणी के साथ prog नोड वापस आ गया है।

 //     FALSE   , //     . var FALSE = { type: "bool", value: false }; function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } 

और यहाँ parse_expression() फ़ंक्शन है। parse_atom() विपरीत, यह संभव के रूप में कई भावों को पार्स करेगा।

 function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } 

कार्य maybe_*

ये फ़ंक्शन यह जांचते हैं कि अभिव्यक्ति के बाद क्या आता है और यह तय करना है कि अभिव्यक्ति को उसके नोड में लपेटना है, या इसे वापस करना है जैसा कि यह है।

maybe_call() फ़ंक्शन बहुत सरल है: यह एक फ़ंक्शन प्राप्त करता है जो वर्तमान अभिव्यक्ति को पार्स करता है, और यदि यह सामना करता है ( अभिव्यक्ति के बाद, यह call में खुद को लपेटता है। ध्यान दें कि कैसे delimited() तर्कों की सूची को पार्स करने के लिए उपयुक्त है:

 function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression) }; } 

संचालक प्राथमिकता

maybe_binary(left, my_prec) फ़ंक्शन का उपयोग 1 + 2 * 3 जैसे अभिव्यक्तियों को संयोजित करने के लिए किया जाता है। लब्बोलुआब यह है कि उन्हें सही ढंग से पार्स करने के लिए, आपको ऑपरेटरों की प्राथमिकता को सही ढंग से निर्धारित करना होगा:

 var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; 

, * "", + , , 1 + 2 * 3 (1 + (2 * 3)) ((1 + 2) * 3) .

, ( read_atom ) maybe_binary() ( ), ( my_prec ). maybe_binary , . , , .

, , , binary , , , (*):

 function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); var right = maybe_binary(parse_atom(), his_prec) // (*); var binary = { type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : right }; return maybe_binary(binary, my_prec); } } return left; } 

, , , maybe_binary , ( my_prec ), , , . - , (, ), .

, , my_prec 0, binary ( assign = ).

, .

 var FALSE = { type: "bool", value: false }; function parse(input) { var PRECEDENCE = { "=": 1, "||": 2, "&&": 3, "<": 7, ">": 7, "<=": 7, ">=": 7, "==": 7, "!=": 7, "+": 10, "-": 10, "*": 20, "/": 20, "%": 20, }; return parse_toplevel(); function is_punc(ch) { var tok = input.peek(); return tok && tok.type == "punc" && (!ch || tok.value == ch) && tok; } function is_kw(kw) { var tok = input.peek(); return tok && tok.type == "kw" && (!kw || tok.value == kw) && tok; } function is_op(op) { var tok = input.peek(); return tok && tok.type == "op" && (!op || tok.value == op) && tok; } function skip_punc(ch) { if (is_punc(ch)) input.next(); else input.croak("Expecting punctuation: \"" + ch + "\""); } function skip_kw(kw) { if (is_kw(kw)) input.next(); else input.croak("Expecting keyword: \"" + kw + "\""); } function skip_op(op) { if (is_op(op)) input.next(); else input.croak("Expecting operator: \"" + op + "\""); } function unexpected() { input.croak("Unexpected token: " + JSON.stringify(input.peek())); } function maybe_binary(left, my_prec) { var tok = is_op(); if (tok) { var his_prec = PRECEDENCE[tok.value]; if (his_prec > my_prec) { input.next(); return maybe_binary({ type : tok.value == "=" ? "assign" : "binary", operator : tok.value, left : left, right : maybe_binary(parse_atom(), his_prec) }, my_prec); } } return left; } function delimited(start, stop, separator, parser) { var a = [], first = true; skip_punc(start); while (!input.eof()) { if (is_punc(stop)) break; if (first) first = false; else skip_punc(separator); if (is_punc(stop)) break; a.push(parser()); } skip_punc(stop); return a; } function parse_call(func) { return { type: "call", func: func, args: delimited("(", ")", ",", parse_expression), }; } function parse_varname() { var name = input.next(); if (name.type != "var") input.croak("Expecting variable name"); return name.value; } function parse_if() { skip_kw("if"); var cond = parse_expression(); if (!is_punc("{")) skip_kw("then"); var then = parse_expression(); var ret = { type: "if", cond: cond, then: then, }; if (is_kw("else")) { input.next(); ret.else = parse_expression(); } return ret; } function parse_lambda() { return { type: "lambda", vars: delimited("(", ")", ",", parse_varname), body: parse_expression() }; } function parse_bool() { return { type : "bool", value : input.next().value == "true" }; } function maybe_call(expr) { expr = expr(); return is_punc("(") ? parse_call(expr) : expr; } function parse_atom() { return maybe_call(function(){ if (is_punc("(")) { input.next(); var exp = parse_expression(); skip_punc(")"); return exp; } if (is_punc("{")) return parse_prog(); if (is_kw("if")) return parse_if(); if (is_kw("true") || is_kw("false")) return parse_bool(); if (is_kw("lambda") || is_kw("λ")) { input.next(); return parse_lambda(); } var tok = input.next(); if (tok.type == "var" || tok.type == "num" || tok.type == "str") return tok; unexpected(); }); } function parse_toplevel() { var prog = []; while (!input.eof()) { prog.push(parse_expression()); if (!input.eof()) skip_punc(";"); } return { type: "prog", prog: prog }; } function parse_prog() { var prog = delimited("{", "}", ";", parse_expression); if (prog.length == 0) return FALSE; if (prog.length == 1) return prog[0]; return { type: "prog", prog: prog }; } function parse_expression() { return maybe_call(function(){ return maybe_binary(parse_atom(), 0); }); } } 

Marijn Haverbeke, parse-js (Common Lisp), , . , , JS, .

: JavaScript. भाग 2: दुभाषिया