तीन-पता कोड दुभाषिया लिखना

परिचय

शुभ दोपहर
मैं निकट-संकलक विषयों के बारे में लिखना जारी रखता हूं। इस बार मैं एक दुभाषिया के डिजाइन और निर्माण पर स्पर्श करूँगा जो सिंटेक्स पेड़ों के साथ काम करता है।
मेरा सुझाव है कि आप पिछले लेख को पढ़ें - “हम एक LR (0) विश्लेषक लिखते हैं। जटिल के बारे में सरल शब्दों में, " क्योंकि दुभाषिया में मैं खरोंच से पार्सर का निर्माण नहीं कर रहा हूं, लेकिन उस लेख में वर्णित सर्वोत्तम प्रथाओं का उपयोग कर रहा हूं। अरे हाँ, एक और महत्वपूर्ण बिंदु - हम जावास्क्रिप्ट में लिखेंगे। मैं इस भाषा का प्रशंसक नहीं हूं, लेकिन मुझे लगता है कि यह जनता के लिए परिणाम देखने का सबसे सुविधाजनक तरीका है। हर कोई इसे डाउनलोड करने की हिम्मत नहीं करता है, यह ज्ञात नहीं है कि क्या है, और यह अभी भी केवल एक पृष्ठ खोलने की तुलना में अधिक कठिन है। साधन की atypicality उदाहरण के "सीखने" द्वारा ऑफसेट है। काम की गति महत्वपूर्ण नहीं है (100-150 लाइनों की सीमा, ऐसा लगता है कि कोई और नहीं, जो दुभाषिया के साथ खेलने के लिए टाइप करना चाहता है), और जेएस में कोड की समझ काफी अधिक है।

तीन पता कोड

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

a = (b + c) * (d - e) 

यह इस में बदल जाएगा:

 f = b + c g = d - e a = f * g 

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

 //   <line> = <vars_decl>|<command> //    <var_decl> = <ident>|<ident><left_sq_bracket><number><right_sq_bracket> //   <var_list> = <var_decl>|<var_list><comma><whitespace><var_decl> //    <vars_decl> = <var_keyword><whitespace><var_list> //  L: operation <command> = <ident><colon><whitespace><operation>|<operation> //  <operation> = <io>|<binary>|<control>|<assign>|<stack> // / in var, out var <io> = <in_keyword><whitespace><var_output_array>|<out_keyword><whitespace><var_input_array> //     - [], ,   <var_output> = <var_ptr>|<ident> <var_output_array> = <var_output>|<var_ar> //  <var_ar> = <ident><left_sq_bracket><var_numb><right_sq_bracket> <var_numb> = <ident>|<number> //  <var_ptr> = <asterisk><ident> //  <var_ref> = <ref><ident> //     - [], ,  ,   ,  <var_input_array> = <var_input>|<var_ar> <var_input> = <var_output>|<var_ref>|<number> //   ,  3  <binary> = <var_output><assign_sign><var_input><operator><var_input> <operator> = <plus>|<minus>|<asterisk>|<div>|<mod> //  <control> = <goto>|<if> //  <goto> = <goto_keyword><whitespace><ident> //  <if> = <if_keyword><whitespace><var_input><comp_operator><var_input><whitespace><goto> //  <assign> = <var_output_array><assign_sign><var_input>|<var_output><assign_sign><var_input_array> //    <stack> = <pop_keyword><whitespace><var_output_array>|<push_keyword><whitespace><var_input_array> 

अन्य सभी वर्ण (जो दाएं भागों में हैं, लेकिन बाएं में नहीं हैं) टर्मिनल हैं, मैं उन्हें नीचे थोड़ा वर्णन करूंगा।

पार्सिंग ट्री का निर्माण

जैसा कि मैंने पहले लिखा था, टोकन की धारा पार्सर के इनपुट पर आती है, यह धारा इनपुट स्ट्रिंग के आधार पर लेक्सिकल विश्लेषक द्वारा निर्मित की जाती है।
उदाहरण के लिए, एक स्ट्रिंग के लिए

 if a<b goto L 

हम टोकन की निम्नलिखित धारा प्राप्त करते हैं - लेक्सकेयर्डआईएफ , लेक्सवाइटस्पेस , लेक्सआईडेंट , लेक्सकॉम , लेक्सआईडेंट , लेक्सवाइटस्पेस , लेक्सकेयर्डगोटो , लेक्सविट्सस्पेस , लेक्सआईडेंट ।
गैर-टर्मिनलों के विवरण से आवश्यक टोकन का पता लगाना आसान है:

 <ident> = <letter>|<ident><letter>|<ident><digit> <number> = <digit>|<number><digit> <plus> = '+' <minus> = '-' <div> = '/' <mod> = '%' <comp_operator> = '<'|'>'|'>='|'<='|'=='|'!=' <whitespace> = ' ' <pop_keyword> = "pop" <push_keyword> = "push" <goto_keyword> = "goto" <in_keyword> = "in" <out_keyword> = "out" <var_keyword> = "var" <if_keyword> = "if" <left_sq_bracket> = '[' <right_sq_bracket> = ']' <colon> = ':' <asterisk> = '*' <assign_sign> = '=' <ref> = '&' <comma> = ',' $ = end of line 

कोड अपने आप में बहुत सरल है, मैं केवल सामान्य रूप में दूंगा:

 function GetLex(stream) { var c = stream.get(); switch ( c ) { case ' ': return {type: LexTypes.LexWhitespace}; ... } if (c <= '9' && c >= '0') return {type: LexTypes.LexNumber, number: readNumber()}; if (c > 'z' || c < 'a') return {type: LexTypes.LexError}; var ident = readIdent(); if (ident == 'pop') return {type: LexTypes.LexKeywordPop}; ... return {type: LexTypes.LexIdent, ident: ident}; } 

अब हमारे पास टोकन की एक धारा है।
हम इसे पार्सर को पास कर सकते हैं। बेशक, मैंने दुभाषिया के लिए पूर्व-उत्पन्न तालिकाओं के साथ अपना एलआर (0) चुना (मैंने यह भी लिखा कि उन्हें कैसे प्राप्त किया जाए)। इसने तालिका के लिए 82 राज्यों और स्वरूपित कोड की 1400 पंक्तियों को बदल दिया। पार्सर कोड स्वयं व्यावहारिक रूप से C ++ में एक समान के साथ नहीं बदला है, आपको बस पेड़ के निर्माण का उल्लेख करना होगा।
प्रत्येक एक्शनशिफ्ट एक्शन के लिए, हम अपने टोकन वाले एक पेड़ का पत्ता (एक नोड जिसमें कोई बच्चे नहीं हैं) बनाते हैं। और जब हम नियम को ध्वस्त करते हैं, तो हम दाएं हाथ की तरफ के समान प्रतीकों को एक बंडल में जोड़ते हैं, जो एक नया नोड बनाता है, जो इस नोड (जो हमारे व्याकरण के ढांचे में एक नोड है) को इंगित करता है। यह थोड़ा जटिल लगता है, लेकिन यह वास्तव में सरल है, एक बाइनरी ऑपरेशन के लिए एक पेड़ का उदाहरण:

इंटरप्रेटर संरचना और लॉन्च की तैयारी

दुभाषिया में स्रोत कोड की प्रत्येक पंक्ति के लिए एक पेड़, वर्तमान लाइन की संख्या (त्रुटियों को प्रदर्शित करने की आवश्यकता होती है, और आईपी के रूप में - निर्देश सूचक, निष्पादित कोड के पते), लेबल की एक सरणी, चर की एक सरणी, स्टैक संचालन के लिए वास्तविक स्टैक और वस्तुओं के एक जोड़े शामिल हैं। सहायकों।

शुरू करने से पहले, आपको सभी वस्तुओं को रीसेट करना होगा। फिर हम प्रत्येक पंक्ति को पार्स करते हैं। हम ऐसा क्यों कर रहे हैं? लेबल की एक सरणी की रचना करने के लिए, क्योंकि कमांड में हम लेबल पर संक्रमण को पूरा कर सकते हैं, जो कि निष्पादित होने वाली लाइन की तुलना में कोड में आगे स्थित है। इसलिए, हम निष्पादन शुरू करने से पहले कोड विश्लेषण करते हैं। यहां हमें ऐसे क्षण को भी ध्यान में रखना चाहिए, भले ही हमें एक वाक्यविन्यास गलत रूप से मिल जाए, इसका मतलब यह नहीं है कि हमें इसके बारे में तुरंत रिपोर्ट करने की आवश्यकता है।
व्याख्या करते समय, हम इस अनुभाग तक नहीं पहुँच सकते हैं।

कोड निष्पादन

मैंने दो निष्पादन मोड पेश किए - चरण दर चरण और सरल। नामों से यह स्पष्ट है कि उनमें से प्रत्येक क्या है।
कोड:

 function executeLine() { if (input_data.active) { setTimeout(executeLine, 100); return ; } if (input_data.error) return ; var line = lines[currentline]; var ret; if (!line.correct) { addlog('syntax error at position ' + line.pos); return ; } var general = line.tree.childs[0]; if (general.nonterm == NonTerminals.vars_decl) ret = interp_var_list(general.childs[0]); else ret = interp_operation(general.childs[0]); if (!ret) return ; currentline++; if (currentline == linecount) { addlog('Finish!', true); return ; } if (!step_by_step) setTimeout(executeLine, 0); } 

input_data पहली सहायक वस्तु है। जावास्क्रिप्ट का अपना ईवेंट मॉडल है, और यह हमारे स्वयं के ईवेंट का उपयोग करना संभव नहीं है, इसलिए जब हम वैल्यू इनपुट डायलॉग (कमांड में) प्रदर्शित करते हैं, तो हम "फ़्रीज़" फ़्लैग - input_data.active सेट करते हैं, जिसका अर्थ है कि हमें डायलॉग को पूरा करने के लिए प्रतीक्षा करने की आवश्यकता है, और उसके बाद ही कोड निष्पादित करना जारी रखें। । दूसरा ऑब्जेक्ट, step_by_step, इंगित करता है कि चरण-दर-चरण मोड का उपयोग किया जाता है, यदि नहीं, तो हम फ़ंक्शन को फिर से कॉल करने की योजना बना रहे हैं।
निष्पादन ही आदिम है - लगभग हर गैर-टर्मिनल के लिए हमारे पास एक फ़ंक्शन है जो इसे संसाधित करता है। और हम वृक्षों को उनके मूल्यों को प्राप्त करने के लिए, गैर-वृक्षों को इकट्ठा करने के लिए नीचे जाते हैं।
गैर-टर्मिनल प्रसंस्करण उदाहरण:

 function interp_control_goto(node) { var ident = node.childs[0].lex.ident; if (ident in labels) { currentline = labels[ident] - 1; return true; } if (!check_var(ident)) return false; var val = vars[ident]; if (val >= linecount) { addlog('invalid address of code'); return false; } currentline = val.value - 1; return true; } 

यह सब आप यहां काम में देख सकते हैं, दर्पण ।
यह फायरफॉक्स में सबसे अच्छा काम करता है, ओपेरा (कीबोर्ड / कीडाउन) में संपादक के कुछ "चिप्स" काम नहीं करते हैं, क्रोम और आईई (सिलेक्शनस्टार्ट) में यह समान है। लेकिन दुभाषिए को खुद ठीक से काम करना चाहिए।
एक उदाहरण के रूप में, फैक्टरियल की गणना के लिए एक पुनरावर्ती कार्य होता है (कोड के साथ अतिभारित, निश्चित रूप से, लेकिन यह विशेष रूप से भाषा की क्षमताओं को दिखाने के लिए है)।