हम लिस्प - II में एक सरल अनुवादक लिख रहे हैं

पिछला लेख

हम असाइनमेंट ऑपरेटर को लागू करते हैं

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

आप इस समस्या को विभिन्न तरीकों से हल कर सकते हैं ...

मैं सूत्र को तथाकथित में परिवर्तित करने का सुझाव देता हूं "रिवर्स पोलिश फॉर्म" (SCF)। रिवर्स पोलिश नोटेशन (पोलिश गणितज्ञ लुकाशेविच के नाम पर) संकेतन का एक गैर-अवरुद्ध रूप है जिसमें ऑपरेशन के संकेत ऑपरेंड्स ("पोस्टफिक्स नोटेशन") के बाद स्थित हैं। उपसर्ग से उपसर्ग रूप में अनुवाद काफी सरल है। "समस्या को एक कार्रवाई में हल कर सकता है" - तुरंत infix से उपसर्ग में रूपांतरण को लागू कर सकता है। लेकिन यह फैसला कुछ ज्यादा ही बोझिल होगा। हालांकि, जो लोग चाहते हैं वे इसे स्वयं करने का प्रयास कर सकते हैं।

और हम एससीआर में सूत्र के परिवर्तन में लगे रहेंगे। इनपुट में, हमारे पास इनफ़िक्स नोटेशन में एक बीजगणितीय सूत्र है, जिसे लिस्प बहु-स्तरीय सूची के रूप में प्रस्तुत किया गया है। उदाहरण के लिए, यह एक:

(12 + x / ( y ^ 2 + z ^ 4))

SCR में, इस अभिव्यक्ति के निम्नलिखित (पहली नज़र में - विचित्र) रूप होंगे:

(12 xy 2 ^ z 4 ^ + / +)

SCR के रूप में सूत्र के मूल्य की गणना करने के लिए, आपको एक स्टैक की आवश्यकता होती है (एक डेटा संरचना जो "अंतिम रूप - पहले जाना") के सिद्धांत पर डेटा संग्रहीत और वितरित करती है। गणना बहुत सरल है। सूची को एक बार पढ़ा जाता है। और प्रत्येक तत्व के लिए, निम्नलिखित क्रियाएं की जाती हैं:

• संख्या (चर मानों) को केवल स्टैक पर धकेल दिया जाता है;
• स्टैक के शीर्ष से ऑपरेंड की संख्या के आधार पर ऑपरेशन किया जाता है।

कृपया ध्यान दें कि एससीएफ में कोई कोष्ठक नहीं हैं, और ऑपरेशन उस क्रम में किए जाते हैं जो वे लिखे गए हैं (प्राथमिकताएं, जैसा कि इन्फिक्स रूप में, अब यहां नहीं हैं)।

जिस अभिव्यक्ति को हम SCR में अनुवाद करना चाहते हैं, उसमें संख्याएँ, चर, कार्य और संचालन संकेत हो सकते हैं। एक समस्या है - एक फ़ंक्शन से एक चर को कैसे अलग किया जाए? इस समस्या को हल करने का एक प्राकृतिक तरीका यह है कि आप सभी कार्यों और कार्यों की एक सूची बना लें और इस सूची में आवश्यक चरित्र की जाँच करें: यदि सूची में वर्ण पाया जाता है, तो यह एक ऑपरेशन है, अन्यथा यह एक चर है।
इसके अलावा, प्रत्येक फ़ंक्शन / ऑपरेशन के लिए, आपको इसकी समता (तर्कों की संख्या) को संग्रहीत करने की आवश्यकता है। संचालन की एक मूल सूची इस तरह दिख सकती है:

 (setq *oplist* '((+ 2) (- 2) (* 2) (/ 2) (^ 2) (\ 2) (% 2) (= 2) (== 2) (/= 2) (> 2) (>= 2) (< 2) (<= 2) (and 2) (or 2) (not 1) (sin 1) (cos 1) (abs 1) (exp 1) (log 1) (sqrt 1))) 

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

 (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt)) (setq *oplist* (cons (list proc-name (length proc-parm)) *oplist*))) 

अब प्रत्येक ऑपरेशन के लिए आवश्यक है जो फ़ंक्शन में एक निश्चित प्राथमिकता निर्धारित करने के लिए होता है। प्राथमिकताएँ निम्नलिखित फ़ंक्शन द्वारा निर्धारित की जाती हैं:

 (defun prty (OP) (cond ((EQ OP 'and) 1) ((EQ OP 'or) 1) ((EQ OP '>) 2) ((EQ OP '>=) 2) ((EQ OP '<) 2) ((EQ OP '<=) 2) ((EQ OP '=) 2) ((EQ OP '==) 2) ((EQ OP '/=) 2) ((EQ OP '+) 3) ((EQ OP '-) 3) ((EQ OP '*) 4) ((EQ OP '/) 4) ((EQ OP '\) 4) ((EQ OP '%) 4) ((EQ OP '^) 5) ((member op (mapcar 'car *oplist*)) 6))) 

सबसे कम प्राथमिकता तार्किक संचालन "और" और "या" को दी जाती है। फिर तुलनात्मक संचालन, फिर जोड़ और घटाव आदि होते हैं। कार्यों में सर्वोच्च प्राथमिकता है।

अब हम एससीआर में अभिव्यक्ति का अनुवाद करने के लिए एल्गोरिदम का वर्णन करते हैं। Inf2ipn फ़ंक्शन एक आवश्यक पैरामीटर (इनपुट सूत्र) और दो वैकल्पिक (ऑपरेशन स्टैक और संचायक सूची) को स्वीकार करता है। बैटरी सूची में, परिणाम जमा होता है। फ़ंक्शन इनपुट सूची को स्कैन करता है और निम्नानुसार कार्य करता है:

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

फ़ंक्शन जो ऑपरेंड से ऑपरेशन को अलग करता है वह बहुत सरल है - यह जांचने के लिए नीचे आता है कि क्या दिया गया चरित्र वैश्विक * ओपलिस्ट * सूची में है:

 (defun is-op (o) (member o (mapcar 'car *oplist*))) 

और SCR में स्थानांतरण फ़ंक्शन का रूप है:

 (defun inf2ipn (f &optional (s nil) (r nil)) (cond ((null f) (if (null s) (reverse r) (inf2ipn nil (cdr s) (cons (car s) r)))) ((listp (car f)) (inf2ipn (cdr f) s (append (reverse (inf2ipn (car f))) r))) ((numberp (car f)) (inf2ipn (cdr f) s (cons (car f) r))) ((not (is-op (car f))) (inf2ipn (cdr f) s (cons (car f) r))) (t (cond ((null s) (inf2ipn (cdr f) (cons (car f) s) r)) ((> (prty (car f)) (prty (car s))) (inf2ipn (cdr f) (cons (car f) s) r)) (t (let ((a (car s))) (inf2ipn (cdr f) (cons (car f) (cdr s)) (cons ar)))))))) 

आप इसे सीधे कॉल करके इस फ़ंक्शन की कार्यक्षमता को सत्यापित कर सकते हैं:

 (inf2ipn '(2 + 3 * 6)) ==> (2 3 6 * +) (inf2ipn '((2 + 3) * 6)) ==> (2 3 + 6 *) (inf2ipn '(3 + a * sin ( 5 + x))) ==> (3 A 5 X + SIN * +) 

SCR से उपसर्ग प्रविष्टि प्राप्त करना काफी सरल है। Ipn2inf फ़ंक्शन एससीआर और ड्राइव पैरामीटर में अभिव्यक्ति को स्वीकार करता है। फ़ंक्शन इस तरह काम करता है:

• यदि इनपुट सूची खाली है, तो ड्राइव हेड वापस आ गया है;
• यदि अगला तत्व एक संख्या या चर है, तो यह परमाणु ड्राइव से जुड़ा हुआ है;
• यदि अगला तत्व arity n का एक ऑपरेशन है, तो इस ऑपरेशन के प्रतीक से युक्त एक सूची और लंबाई n की ड्राइव का एक उल्टा खंड पहले n तत्वों के बिना ड्राइव में जोड़ा जाता है।

यहाँ कोड में ऐसा दिखता है:

 ;;    (defun arity (o) (iter (for a in *oplist*) (when (eq o (car a)) (return (cadr a))))) ;;      (defun ipn2pref (f &optional (s nil)) (cond ((null f) (car s)) ((numberp (car f)) (ipn2pref (cdr f) (cons (car f) s))) ((is-op (car f)) (let ((ar (arity (car f)))) (ipn2pref (cdr f) (cons (cons (car f) (reverse (subseq s 0 ar))) (subseq s ar))))) (t (ipn2pref (cdr f) (cons (car f) s))))) ;; -,      (defun i2p (f) (ipn2pref (inf2ipn f))) 

कोड के स्वास्थ्य की जाँच करें:

 (i2p '(3 + a * sin ( 5 + x))) ==> (+ 3 (* A (SIN (+ 5 X)))) (i2p '((3 + a) * sin ( 5 ) + x)) ==> (* (+ 3 A) (+ (SIN 5) X)) (i2p '((3 + a) * sin ( 5 ^ 2 - x ) + x)) ==> (* (+ 3 A) (+ (SIN (- (^ 5 2) X)) X)) 

अब यह केवल असाइनमेंट ऑपरेटर के हैंडलर को लिखना और इसे प्रक्रिया हैंडलर से जोड़ना है। असाइनमेंट हैंडलर निम्नानुसार लागू किया जा सकता है:

 (defun action-set (meat) (let ((name-var (car meat)) (r-value (i2p (cddr meat)))) `(setq ,name-var ,r-value))) 

मांस पैरामीटर सूची असाइनमेंट को संदर्भित करने वाला है:

 ( = ) 

असाइनमेंट ऑपरेटर की मान्यता एक्शन-प्रोक फंक्शन में की जाती है, जो फॉर्म लेता है:

 (defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (lv nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) ((eq (car stmt) 'local) (setq loc-var (append loc-var (cdr stmt)))) ((eq (cadr stmt) '=) (setq body (append body (list (action-set stmt))))) (t (printsline (strCat "****  " (output stmt) "  ")) (setq *flagerr* t)))) (iter (for a in (setof loc-var)) (collecting (list a 0) into lv)) `(defun ,proc-name ,proc-parm (let ,lv ,@body)))) 

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

0001 proc main()
0002 local x,y,z
0003 x=3
0004 y=4
0005 z=x^2+y^2
0006 print z
0007 end_proc


आइए देखें कि हमारे अनुवादक ने क्या किया:

 (getd 'main) ==> (EXPR NIL (LET ((X 0) (Y 0) (Z 0)) (SETQ X 3) (SETQ Y 4) (SETQ Z (+ (^ X 2) (^ Y 2))) (PRINTLINE Z))) 

सब कुछ सही होने लगता है। अब, चलो हमारी प्रक्रिया कहते हैं और अपेक्षित परिणाम प्राप्त करते हैं:

 (main) 25 ==> 25 

हमारे अनुवादक भी अंतर्निहित कार्यों को सही ढंग से संभाल लेंगे। इसे सत्यापित करने के लिए, हम निम्नलिखित कोड को निष्पादित करेंगे:

0001 proc main()
0002 local x,y,z,pi
0003 pi=3.1415926535
0004 x=sin(pi/6)
0005 y=cos(pi/6)
0006 z=x^2+y^2
0007 print x
0018 print y
0019 print z
0010 end_proc


और हम प्राप्त करते हैं:

 (main) 0.499999999987039 0.866025403791922 1.0 ==> 1.0 

हमारा अनुवादक हमारी आँखों के सामने जीवन में आता है!

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

निम्नलिखित लेख इन सभी सवालों के लिए समर्पित होगा।
जारी रखा जाए

इस लेख का कोड यहाँ डाउनलोड किया जा सकता है।