نحن نكتب مترجمًا بسيطًا في Lisp - II

المقال السابق

نقوم بتنفيذ عامل التعيين

الآن دعنا نعلم المترجم كيفية التعامل مع عامل التعيين. وهنا نواجه المهمة الكلاسيكية المتمثلة في ضمان حساب الصيغة الجبرية الواردة في التدوين المألوف لنا منذ سنوات دراستنا. إذا كان لنا أن نصنع مترجمًا ، فسنحتاج إلى حساب قيمة الصيغة. في حالتنا ، سيتم حساب نواة Lisp (في وقت التشغيل). ونحتاج فقط إلى تحويل الصيغة من التدوين المعتاد إلى Lisp.
العلامة التي نعرفها تسمى "تدوين infix" (علامة العملية تقع بين المعاملات). في Lisp ، يتم وضع علامة العملية قبل المعاملات (يسمى هذا التدوين "ترميز البادئة"). وبالتالي ، فإن مهمتنا هي تحويل نموذج infix إلى البادئة.

يمكنك حل هذه المشكلة بطرق مختلفة ...

أقترح تحويل الصيغة إلى ما يسمى "النموذج البولندي العكسي" (SCF). إن التدوين البولندي العكسي (الذي سمي على اسم عالم الرياضيات البولندي لوكاشفيتش) هو شكل من أشكال التدوين غير المحظورة حيث توجد علامات العمليات بعد المعاملات ("تدوين ما بعد الإصلاح"). الترجمة من postfix إلى شكل البادئة بسيطة للغاية. يمكن للمرء "حل المشكلة في إجراء واحد" - تنفيذ التحويل من البادئة إلى البادئة على الفور. لكن هذا القرار سيكون أكثر تعقيدًا إلى حد ما. ومع ذلك ، يمكن لأولئك الذين يرغبون في القيام بذلك بأنفسهم.

وسوف نشارك في تحويل الصيغة في SCR. عند الإدخال ، لدينا صيغة جبرية في تدوين infix ، يتم تقديمها في شكل قائمة Lisp متعددة المستويات. على سبيل المثال ، هذا:

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

في SCR ، سيكون لهذا التعبير الشكل التالي (للوهلة الأولى - غريب):

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

لحساب قيمة الصيغة في شكل SCR ، تحتاج إلى مكدس (بنية بيانات تقوم بتخزين البيانات وتسليمها على أساس مبدأ "من يأتي أولاً - الذهاب أولاً"). الحساب بسيط للغاية. تتم قراءة القائمة مرة واحدة. ولكل عنصر ، يتم تنفيذ الإجراءات التالية:

• يتم دفع عدد (القيم المتغيرة) ببساطة إلى المكدس ؛
• يتم تنفيذ العملية على العدد المقابل من المعاملات من أعلى المكدس.

يرجى ملاحظة أنه لا توجد أقواس في SCF ، ويتم تنفيذ العمليات حسب ترتيب كتابتها (الأولويات ، كما في نموذج infix ، لم تعد هنا).

قد يحتوي التعبير الذي نريد ترجمته إلى 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 *. يمكن القيام بذلك في إجراء الإجراء proc في الفرع الذي يعالج بيان proc. يمكن إنشاء متغير * 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))) 

تعطى الأولوية الدنيا للعمليات المنطقية "و" و "أو". ثم هناك عمليات المقارنة ، ثم الجمع والطرح ، إلخ. الوظائف لها الأولوية القصوى.

الآن نحن نصف الخوارزمية لترجمة التعبير في SCR. تقبل الدالة inf2ipn معلمة واحدة مطلوبة (صيغة الإدخال) واثنتين اختياريتين (قائمة التشغيل وقائمة المجمع). في قائمة البطاريات ، يتم تجميع النتيجة. تفحص الوظيفة قائمة الإدخال وتعمل على النحو التالي:

• إذا كان العنصر التالي هو رقم أو متغير ، يتم إدخاله في البطارية.
• إذا كان العنصر التالي عبارة عن قائمة ، يتم تطبيق الوظيفة على هذه القائمة بشكل متكرر ، وتتم إضافة نتيجتها إلى البطارية.
• إذا كان العنصر التالي عبارة عن عملية ، فعندها مع رزمة فارغة من العمليات ، يتم دفع العنصر التالي إلى رصة العمليات. مع رصة عملية غير فارغة ، تتم مقارنة أولوية العملية الواردة بأعلى رصة العملية. في حالة وصول عملية ذات أولوية أعلى ، يتم دفعها إلى مكدس العمليات.
• إذا وصلت عملية ذات أولوية أعلى من الجزء العلوي من المكدس ، فسيتم نقل الجزء العلوي من مجموعة العمليات إلى المجمع ، ويتم إدخال العملية التي تم الوصول إليها حديثًا في تكديس العمليات.
• إذا تم استنفاد قائمة الإدخال وكانت حزمة العملية فارغة ، فستقوم الوظيفة بإرجاع بطارية معكوسة (فرع طرفي). وبخلاف ذلك ، تقوم الوظيفة بإرجاع بطارية معكوسة مع قائمة العمليات المرفقة مسبقًا من المكدس.

الوظيفة التي تميز العملية عن المعامل بسيطة للغاية - يتعلق الأمر بالتحقق مما إذا كان الحرف المحدد في قائمة * oplist * الشاملة:

 (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 التعبير في SCR ومعلمة محرك الأقراص. تعمل الوظيفة على النحو التالي:

• إذا كانت قائمة الإدخال فارغة ، فسيتم إرجاع رأس المحرك ؛
• إذا كان العنصر التالي رقمًا أو متغيرًا ، فإن هذه الذرة مرتبطة بمحرك الأقراص ؛
• إذا كان العنصر التالي عبارة عن عملية لـ 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))) 

من المفترض أن تشير معلمة اللحوم إلى تعيين القائمة:

 ( = ) 

يتم التعرف على عامل التخصيص في وظيفة الإجراء proc ، التي تأخذ الشكل:

 (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)))) 

دعونا نتحقق من أداء الكود الخاص بنا. نقوم بتحميل الكود في بيئة Lisp ، واستدعاء وظيفة البدء وترجمة الإجراء التالي:

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 

مترجمنا ينبض بالحياة أمام أعيننا!

ومع ذلك ، فقد ابتعدنا كثيرًا: سعينا لتحقيق الهدف النهائي ، لم نفكر على الإطلاق في الأخطاء التي يمكن أن يرتكبها المستخدم (المبرمج الذي يستخدم المصغر - الأساسي). بطريقة جيدة ، كان علينا أن نفكر في الأخطاء على الفور ، ولكننا بدأنا للتو العمل ، ولم نذهب بعيدًا جدًا ، ولم يفت الأوان لتقديم معالجة الأخطاء والتشخيصات في الشفرة. بالإضافة إلى ذلك ، من الواضح أن "التحسينات الطفيفة" تقترح (على سبيل المثال ، يطلب المترجم من المشغل أن يشغل سطرًا واحدًا بالضبط ، وهو أمر غير ملائم).

سيتم تخصيص المقالة التالية لكل هذه الأسئلة.
يتبع

يمكن تنزيل رمز هذه المقالة هنا.