دعونا نحاول الكتابة بلغة Lisp ... مترجم لغة حتمية بسيطة. لا ، لا ، لم أكن مخطئًا - إنه المترجم. سيتم بثه في كود Lisp. ومن ثم يمكن تنفيذ هذا الرمز بواسطة نظام Lisp.
هنا ، سيتم تقديم الخدمة التي لا تقدر بثمن من خلال حقيقة أنه في Lisp لا يوجد حاجز بين التعليمات البرمجية والبيانات (هذه خاصية نادرة لبعض لغات البرمجة تسمى "الهوية المتجانسة"). لكن القدرات البصرية لـ Lisp ستلعب أيضًا دورًا مهمًا.
كتطبيق ، سأستخدم HomeLisp . يمكن للمهتمين تكييف هذا المشروع مع Common Lisp. سأقول على الفور - فيما يتعلق بالمشكلة قيد النظر ، فإن الفرق الكبير بين Common Lisp و HomeLisp هو فقط في معالجة الخطوط والملفات.
قم بتنزيل نسخة محمولة من HomeLisp هنا . الوثائق موجودة أيضا على نفس الموقع. يمكن لأولئك الذين يرغبون في نسخ الرمز من المقالة والتحقق من الأداء على الفور.
كان الموضوع الذي لفت انتباهك إليه هو الأساس لورشتي في معرض Novosibirsk LSHUP-2018 الشهير . يمكن العثور على نتائج ورشة العمل هنا . ثم حددت منهجي. أفترض أن القارئ على دراية بلغة Lisp.
النزول
لنبدأ بـ "اللغة الحتمية البسيطة" التي سنبثها في Lisp.
ستقوم اللغة بمعالجة البيانات الرقمية فقط. يتكون الرمز في هذه اللغة من الوظائف (الإجراءات التي تُرجع القيم). من بين هذه الوظائف ، يجب أن يسمى واحد الرئيسي. مع هذه الوظيفة يبدأ تنفيذ التعليمات البرمجية. على الرغم من لماذا ربط نفسك بذلك؟ نكتب دوال بلغة حتمية ، يتم بثها في Lisp ويمكن استخدامها مع وظائف Lisp. ولكن دعونا لا نتقدم على أنفسنا ...
مجموعة عوامل اللغة معتادة: التعيين ، التفرع ، الدورة الحسابية ، الخروج المبكر من الدورة ، الإدخال ، الإخراج واستدعاء الوظيفة. ومع ذلك ، من الناحية النحوية يتم تنفيذ استدعاء دالة كمهمة (نتيجة مكالمة). دع التعليقات تحتوي على علامة النجمة في الموضع الأول من السطر. اللغة ، بالطبع ، يجب أن توفر القدرة على إنشاء وظائف تعاودية. لتوضيح الأمر ، سأقدم أمثلة على التعليمات البرمجية - طباعة أرقام فردية متتالية وحساب مجموعها:
proc main() local s,n,k input n for i=1 to n k=2*i-1 print k s=s+k end_for print s end_proc
إنها في روحها لغة أساسية. سأسميها "mini-basic". يجب على مترجمنا تحويل الكود المعطى إلى دالة Lisp التالية:
(defun main nil (let ((s 0) (n 0) (k 0)) (setq n (read)) (iter (for i from 1 to n) (setq k (- (* 2 i) 1)) (printline k) (setq s (+ sk))) (printline s)))
تعجبني حقًا حزمة التكرار ، التي يتم تنفيذها باعتبارها ماكرو في حزم Common Lisp الاحترافية. في HomeLisp ، يتم تضمين وظيفة iter (التي تنفذ جزءًا كبيرًا من إمكانات التكرار الكلي) في اللغة الأساسية. كان إدماني للتكرار هو الذي تسبب في ترجمة دورات "mini-basic" الخاصة بنا إلى مكالمات iter.
من أين تبدأ التنفيذ؟ لنبدأ بتحديد الملف المراد بثه وقراءته وطباعته سطرًا تلو الآخر. سيتعين علينا أن نبدأ المترجم عدة مرات ، لذا دع هذا البدء من البداية يكون مناسبًا. إليك ما قد تبدو عليه هذه الوظيفة:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (let ((fi (gensym 'fi))) (when fname (filOpen fi fname _INPUT) (loop (getLine fi) (when (or *flagerr* (filEOF fi)) (return t))) (filClose fi) (when *flagerr* (printsline "**** ")))) (unset '*numline*) (unset '*flagerr*))
تحتوي الوظيفة على اسم معلمة اختياري - اسم الملف الذي سيتم بث محتوياته. عند إدخال الوظيفة ، يتم إنشاء متغيرين عموميين : numLine ، رقم سطر الملف المصدر ، وعلامة ، إشارة حالة الخطأ. قبل إنهاء الوظيفة ، يتم إتلاف هذه المتغيرات (وظيفة HomeLisp unset تدمر المتغيرات العامة).
إذا تم حذف اسم ملف الإدخال ، فسيتم استدعاء مربع حوار windows القياسي لتحديد الملف (sysGetOpenName) . يتم استخدام الدليل الحالي (sysHome) كدليل البدء. بعد ذلك ، يتم إنشاء حرف فريد لمعالج الملف ويتم فتح الملف لقراءة النص. بعد ذلك ، في حلقة لا نهائية ، يتم قراءة الملف سطرا بسطر (وظيفة getLine ). بعد كل عملية ، يتم التحقق مما إذا كان هناك خطأ ما وإذا تم الوصول إلى نهاية الملف. إذا حدث خطأ أو تم إصلاح نهاية الملف ، فواصل الدورة ، يتم إغلاق الملف ، وفي حالة وجود أخطاء ، يتم عرض رسالة نهائية.
في الواقع تتم القراءة من الملف بواسطة وظيفة getLine :
(defun getLine (fil) (let ((stri "")) (loop (when (filEof fil) (return "")) (setq *numline* (add1 *numline*)) (setq stri (filGetline fil)) (printsline (strCat (format *numline* "0000") " " (strRTrim stri))) (setq stri (strATrim stri)) (unless (or (eq "" stri) (eq "*" (strLeft stri 1))) (return stri)))))
تقبل هذه الوظيفة معرف الملف المفتوح ، وتقوم في حلقة لا نهائية بتنفيذ الإجراءات التالية:
- يتحقق من نهاية حالة الملف. في هذه الحالة ، تنكسر الحلقة وتعيد الدالة سلسلة فارغة ؛
- يزداد عداد خطوط القراءة بمقدار واحد ؛
- يتم قراءة السطر التالي من الملف ؛
- تتم طباعة سطر القراءة مع إزالة المسافات المحتملة على اليمين ؛
- إذا لم يكن سطر القراءة فارغًا ولا يحتوي على علامة النجمة في الموضع الأول ، فحينئذٍ
العوائد من الوظيفة ؛
وبالتالي ، تقع جميع أسطر الملف في شكلها الأصلي في قائمة الإخراج.
نحن نقتحم الإجراءات
الآن دعنا نعلم الكود الخاص بنا لكسر تدفق المدخلات إلى إجراءات منفصلة. أولاً ، يجب تقسيم السلسلة المدخلة إلى رموز مميزة (وحدات معجمية مدخلة غير قابلة للتجزئة). هذه العملية تسمى التحليل ؛ علينا إنشاء محلل. كتابة المحللون هي موضوع كلاسيكي ، وهناك مكتبات من المحللون الجاهزون والأدوات الخاصة التي تسمح لك بإنشاء المحلل اللغوي الضروري ... سنذهب في طريقنا الخاص.
قبل وصف خوارزمية المحلل ، ننتبه إلى حقيقة أنه يمكن تقسيم جميع أحرف سلسلة الإدخال إلى فئتين:
- الشخصيات العادية
- أحرف فاصلة.
لذا ، في عامل التعيين "x = 15 + y ^ 2" ، فإن الأحرف x و 1،5 و y و 2 أحرف عادية ، والأحرف "مسافة" ، + ، ^ هي محددات. كيف تختلف الشخصية العادية عن الفاصل؟ فاصل - يفصل دائمًا رمزًا مميزًا عن الآخر. عامل التعيين الخاص بنا ، الذي يتم تقسيمه إلى رموز مميزة ، يبدو كما يلي: "x" و "=" و "15" و "y" و "^" و "2" .
كما ترى ، لا تقع جميع المحددات في نتيجة التحليل (المسافات ، على وجه الخصوص ، لا تقع). سوف ندعو الفواصل التي لا تقع في النتيجة كفواصل من النوع الأول. ستسمى الفواصل الأخرى فواصل من النوع الثاني.
سيكون إدخال المحلل عبارة عن سلسلة ، والإخراج هو قائمة من رموز سلسلة. كمحرك ، سيتم استخدام متغير محلي - البطارية. تحتوي البطارية في البداية على سلسلة فارغة.
يمكن أن تكون خوارزمية التحليل كما يلي: نقرأ حرف سطر الإدخال حرفًا. إذا قابلت شخصية عادية ، قم بتسلسلها مع البطارية. إذا تم العثور على محدد ، فحينئذٍ:
- بالنسبة للفاصل من النوع الأول ، نقوم بإعادة تعيين قيمة البطارية (إذا لم تكن فارغة) إلى قائمة الإخراج ، قم بمسح البطارية ومتابعة قراءة الحرف التالي ؛
- بالنسبة للفاصل من النوع الثاني ، نقوم أيضًا بإلقاء قيمة البطارية غير الفارغة في قائمة الإخراج ، وبعد ذلك ندخل الفاصل المقبول من النوع الثاني (كرمز مستقل) في قائمة الإخراج ، قم بمسح البطارية ومتابعة قراءة الحرف التالي.
إليك رمز المحلل:
(defun parser (txt &optional (d1 " ,") (d2 "()+-*/\^=<>%")) (let ((res nil) (lex "") ) (iter (for s in-string (strCat txt (strLeft d1 1))) (cond ((plusp (strInd d1 s)) (when (> (strLen lex) 0) (collecting lex into res)) (setq lex "")) ((plusp (strInd d2 s)) (when (> (strLen lex) 0) (collecting lex into res)) (collecting s into res) (setq lex "")) (t (setq lex (strCat lex s))))) res))
بالإضافة إلى المعلمة المطلوبة ، تحتوي الوظيفة على معلمتين اختياريتين: تحتوي d1 على سلسلة ، يحتوي كل حرف منها على فاصل من النوع الأول ، ويحتوي السطر d2 على فواصل من النوع الثاني.
تم وصف منطق برنامج وظيفة المحلل أعلاه. تجدر الإشارة فقط إلى أنه قبل بدء العمل ، يتم إلحاق الفاصل بنهاية خط الإدخال. يتم ذلك بحيث يتم تعليق آخر رمز مميز تمت معالجته في البطارية (يلعب المتغير المحلي lex دور البطارية).
دعونا تحقق من المحلل اللغوي لدينا "في العمل":
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
هذا صحيح ، أليس كذلك؟ لكن العمل مع قوائم السلاسل ليس Lisp تمامًا. دعنا ننتقل من قائمة السلاسل إلى قائمة الذرات. للقيام بذلك ، نحتاج إلى وظيفة ... تلصق جميع الرموز المميزة مرة أخرى في سطر طويل (ولكن تُدرج مسافة بين الرموز) ، ثم تلصق قوس فتح في بداية هذا السطر ، قوس إغلاق في النهاية ... ثم تجبر Lisp على قراءة القائمة:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
الآن ، إذا قدمنا عامل التخصيص لإدخال دالة mk-intf ، نحصل على:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
وهو ، كما ترى ، أجمل بكثير.
الآن دعنا نغير وظيفة البدء قليلاً: سيتعين على هذه الوظيفة قراءة ومعالجة الإجراءات بأكملها:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (when fname (let ((fi (gensym 'fi))) (filOpen fi fname _INPUT) (loop (let ((curr-proc (action-proc fi))) (when (or *flagerr* (filEOF fi)) (return t)) (eval curr-proc))) (filClose fi)) (when *flagerr* (printsline "**** "))) (unset '*numline*) (unset '*flagerr*))
في جسم الحلقة ، تسمى وظيفة الإجراء (معالجة الإجراء) ، والتي ستشكل نص الإجراء المقبول بالفعل على Lisp. ثم يتم تمرير نص الإجراء ، المخزن كتعبير S في متغير curr-proc ، إلى مدخلات تقييم . والوظيفة المقبولة "مجسدة" في بيئة Lisp!
ماذا يجب أن تفعل proc-proc ؟ تستقبل هذه الوظيفة معرف الملف المفتوح كمعلمة. تقوم الوظيفة بقراءة الملف سطرًا تلو الآخر من الملف ، وتخطي الأسطر والتعليقات الفارغة ، وتحليل بقية الأسطر ، وترجمتها إلى نموذج قائمة ، وإنشاء نص الإجراء.
سوف "نتعلم" بشكل تدريجي جيل العمل بروك . ودعونا نبدأ بتدريس وظيفتنا للتعرف على بداية ونهاية الإجراء. في الإجراء الأساسي المصغر ، بداية الإجراء هي:
proc name(p1,p2,p3)
حاول تحليل خط مثل هذا:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
كيف يجب أن تستجيب وظيفة الإجراء proc لهذا المدخل؟ بطبيعة الحال ، تأكد من أن رأس القائمة هو ذرة PROC ، تحتاج إلى أخذ العنصر الثاني من القائمة كاسم الوظيفة ، والعنصر الثالث كقائمة المعلمات. يجب تخزين اسم وقائمة المعلمات في المتغيرات المحلية. عندما تتم قراءة عامل التشغيل end_proc ، فأنت بحاجة إلى تشكيل نموذج defun مع نص فارغ (حتى الآن) من اسم الوظيفة وقائمة المعلمات ، وإرجاع هذا النموذج كنتيجة. إليك ما يبدو عليه:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm 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)) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm (quote OK))))
للتشكيل النهائي لشرط defun ، يتم استخدام القفل العكسي. لاحظ أن الإجراء الذي تم إنشاؤه سيُرجع ذرة OK كنتيجة.
الآن يمكننا التحقق من رمزنا في العمل. ضع الكود التالي في الملف 0000.mbs:
proc f1(x,y) end_proc proc f2(x) end_proc
قم بتشغيل إجراء البدء ، وحدد 0000.mbs وانظر على وحدة التحكم:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
إذا كنت ترغب في ذلك ، يمكنك التأكد من أن آلة Lisp لديها الآن وظيفتان (عديمة الفائدة حتى الآن) f1 و f2 :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
علاوة على ذلك! يمكن أن تبدأ بالفعل:
(f1 1 2) ==> OK (f2 2) ==> OK
مترجمنا أخذ نفسا أول ...
المدخلات والمخرجات والمتغيرات المحلية
حان الوقت الآن لتعليم مترجمنا الجديد كيفية التعامل مع المدخلات والطباعة والعوامل المحلية .
أسهل طريقة للتعامل مع المدخلات والطباعة. كلا المشغلين لهما نفس البنية اللغوية: الكلمة الأساسية والمتغير. يجب أن يتحول إدخال المشغل x إلى شكل Lisp (setq x (قراءة)) . وفقًا لذلك ، يتحول عامل الطباعة x إلى نموذج (printline x) . لتخزين هذه النماذج ، يجب عليك توفير الجسم المتغير المحلي في وظيفة الإجراء proc . سيجمع هذا المتغير النماذج التي تقوم بإجراء حسابات للدالة المستقبلية. ثم كل شيء بسيط للغاية:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var 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) ))))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm ,@body)))
الآن دعنا نعد شفرة المصدر هذه على أساس أساسي صغير:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
ومحاولة ترجمتها ... سيكون لدينا وظيفتين Lisp f1 و f2 . دعونا نلقي نظرة على تعابير تعريفها ونتأكد من أنها تم إنشاؤها بشكل صحيح:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
يمكنك استدعاء هذه الوظائف ، والتأكد من أنها تعمل تمامًا كما هو مقصود. لا داعي للقلق بشأن إدخال القيمة في متغير المعلمة - ليس لدينا متغيرات محلية حتى الآن ... دعنا نضيفها.
يمكن أن يكون عامل التشغيل المحلي في أي مكان في الإجراء ويحدث أكثر من مرة. إذا واجه عامل التشغيل المحلي أثناء معالجة الإجراء ، فأنت بحاجة إلى أخذ قائمة بالمتغيرات وحفظها في متغير محلي. بعد استيفاء عبارة end_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)))) (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))))
يتم تجميع قائمة المتغيرات المحلية في متغير loc-var . بعد اكتمال معالجة الإجراء ، يتم إنشاء قائمة أزواج من النموذج (الاسم 0) من هذه القائمة. في الوقت نفسه ، ازدواجية الأسماء المتطابقة أمر غير مرغوب فيه ... كيف نمنع ذلك؟ بالطبع ، من الممكن التحقق من كل معالجة للعامل المحلي سواء كانت هناك أسماء مكررة (إن وجدت ، أعط رسالة خطأ). ولكن ، يبدو لي أنه من الأفضل التخلص من التكرار ، وهو ما تفعله مجموعة setof . الآن دعنا نترجم ونشغل هذا البرنامج:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
نتأكد من أنها تعمل تمامًا كما تقترح الخوارزمية. ولكن كل ما هو أكثر إثارة للاهتمام في المستقبل!
من هنا يمكنك تنزيل النسخة النهائية لما نحن عليه ث مشفرة ...
يتبع!