مرحبا أقدم لكم ترجمة هواة لدليل لتطبيق لغة برمجة جافا سكريبت JavaScript - برنامج PL التعليمي .

من المترجم

سنقوم بإنشاء لغة البرمجة الخاصة بنا - ((باللغة الأصلية - λanguage). في عملية الإنشاء ، سنستخدم الكثير من التقنيات المثيرة للاهتمام ، مثل النسب العودية ونمط نقل التحكم وتقنيات التحسين الأساسية. سيتم إنشاء نسختين من المترجم الشفهي - المترجمين العاديين والمترجمين الفوريين CPS ، المترجم الشفهي في JavaScript.

مؤلف النسخة الأصلية هو Mihai Bazon ، مؤلف مكتبة UglifyJS الشهيرة (أداة لتقليل وتنسيق رمز JS).

دخول

إذا كنت قد كتبت المترجم أو المترجم الخاص بك ، فلن يكون هناك شيء جديد بالنسبة لك. ولكن إذا كنت تستخدم تعبيرات منتظمة لتحليل شيء يشبه لغة البرمجة ، فاقرأ القسم الخاص بالتحليل . دعنا نكتب الكود مع عدد أقل من الأخطاء!

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

ما الذي سنتعلمه:

• ما هو المحلل اللغوي ، وكيفية كتابته.
• كيف تكتب مترجم.
• تتمة للنقل ، ولماذا يهم.
• كتابة مترجم (trans).
• استمرار نمط النقل.
• بعض تقنيات تحسين الكود الأساسية.
• أمثلة عما هو جديد في لغتنا compared مقارنة بـ JavaScript.

جنبا إلى جنب مع هذا ، سأوضح لماذا تعد لغة Lisp لغة برمجة رائعة. ومع ذلك ، فإن اللغة التي نعمل عليها ليست لغة Lisp. يحتوي على بناء جملة أكثر ثراءً (تدوين إنفكس كلاسيكي يعرفه الجميع) ، مثل المخطط (باستثناء وحدات الماكرو). جيد أم لا ، ولكن وحدات الماكرو هي السمة الرئيسية لـ Lisp - شيء لا تستطيع اللغات الأخرى (باستثناء لهجات Lisp) أن تفعل ما تفعله. (نعم ، أنا أعرف عن 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 . لإضافة متغير ، يمكنك استخدام ما يسميه مبرمجو JavaScript بـ IIFE . استخدم lambda ، أعلن المتغيرات كوسائط. بالنسبة للمتغيرات ، يعد النطاق وظيفة ، والوظائف عبارة عن عمليات إغلاق ، كما هو الحال في JavaScript [تقريبا. الترجمة: حتى ES6.].

حتى if تعبيرا. يستخدم JavaScript المشغل الثلاثي للقيام بذلك:

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

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

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

سينتج OK إذا وفقط إذا كانت نتيجة foo() ليست false . أيضًا ، هناك الكلمة الأساسية true ، لكن كل شيء غير false (في JavaScript ، المشغل === ) سيعتبر true في الفروع (بما في ذلك الرقم 0 والسلسلة الفارغة "" ).

لاحظ أنه لا توجد حاجة للأقواس حول التعبير في. إذا قمت بإضافتها ، فلن يكون ذلك خطأً ، لأنه ( يبدأ التعبير ، لكنها لا لزوم لها.

يمكن تحليل البرنامج بأكمله حتى لو كان محاطًا بالأقواس ، لذا يجب عليك إضافته ; بعد كل تعبير. التعبير الأخير هو استثناء.

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

بعد ذلك ، سنكتب محلل لغتنا.

تحويل الرمز إلى AST

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

على سبيل المثال ، لدينا الكود التالي:

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

سيقوم المحلل اللغوي الخاص بنا بإنشاء شجرة ككائن JavaScript:

 { 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() برمي استثناء باستخدام input.croak() .

سيكون لدينا وظيفة read_next ، الوظيفة الرئيسية في 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_number() ، وما إلى ذلك ... يتم وضعها في وظائف منفصلة ، بحيث تبدو الشفرة أكثر بساطة وجمالًا.

أيضًا ، من المثير للاهتمام أننا لا نتخلص من جميع الرموز مرة واحدة: في كل مرة يطلب فيها المحلل اللغوي الرمز التالي ، سنقرأ رمزًا واحدًا. في حالة حدوث خطأ ما ، لن نقرأ جميع الأحرف.

read_ident() جميع الأحرف في صف قد تكون جزءًا من المعرف ( is_id() ). يجب أن يبدأ المعرف بالحرف أو λ أو _ ، وقد يحتوي على نفس الأحرف أو الأرقام أو أي من: ?!-<>= . ويترتب على ذلك أنه لن يتم قراءة foo-bar شكل ثلاثة رموز ، ولكن var واحد ( var token). هل هذا ضروري حتى تكون قادرًا على تحديد الوظائف بأسماء مثل is-pair? أو string>= (آسف ، هذا ليسبير لي).

أيضًا ، read_ident() بالتحقق مما إذا كان هناك معرف في قائمة الكلمات الأساسية المعروفة ، وإذا كان هناك ، فسيتم إرجاع رمز مميز بدلاً من رمز مميز.

أعتقد أن الشفرة تتحدث عن نفسها ، لذلك هنا رمز مميز جاهز للغتنا:

 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() فقط read_number() .
• بخلاف JavaScript ، فإن الأحرف الوحيدة التي لا يمكن إلغاء إزالتها في سلسلة هي علامة اقتباس و شرطة مائلة عكسية. يمكن أن تحتوي الخطوط على فواصل أسطر وعلامات تبويب وأي شيء آخر. لا نفسر المجموعات القياسية مثل \n ، \t ، إلخ ... من السهل جدًا إعادة ( read_string() ).

لدينا الآن أدوات قوية لكتابة المحلل اللغوي بسهولة ، لكن أولاً أوصي بالنظر إلى وصف AST .

AST الوصف

كما هو موضح أعلاه ، سيقوم المحلل اللغوي ببناء هيكل يوضح دلالات البرنامج. يتكون AST من العقد. كل عقدة هي كائن JavaScript عادي يحتوي على خاصية 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 مما إذا كان الرمز المميز الحالي هو علامة ترقيم معيّنة 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 ) ، تقرأ الشرط باستخدام parse_expression() . إذا كان الرمز { لا يذهب إلى أبعد من ذلك ، فستكون الكلمة الأساسية المطلوبة (بناء الجملة لا تبدو جيدة بدونها). الفروع مجرد تعبيرات ، لذلك نستخدم parse_expression() مرة أخرى لهم. الفرع else اختياري ، لذلك نتحقق أولاً من وجود الكلمة الرئيسية قبل تحليلها.

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

يُطلق على هذا النوع من طريقة التحليل طريقة الهبوط العودية ، وفي الواقع ، أسهل طريقة للكتابة.

المستوى الأدنى: parse_atom() و parse_expression()

parse_atom() الدالة 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 بتحسين بسيط: إذا لم تكن هناك تعبيرات بين { و } ، فسوف تُرجع 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() ، فإنه سيتم تحليل أكبر عدد ممكن من التعبيرات باستخدام maybe_binary() :

 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: مترجم