معظم المترجمين لديهم البنية التالية:
في هذه المقالة ، سأقوم بتشريح هذه البنية بالتفصيل ، عنصرًا بعد عنصر.
يمكننا القول أن هذه المقالة هي إضافة إلى الكم الهائل من الموارد الموجودة حول موضوع المترجمين. إنه مصدر مستقل يسمح لك بفهم أساسيات تصميم وتنفيذ لغات البرمجة.
الجمهور المستهدف للمقال هو الأشخاص الذين تكون فكرة عمل المترجمين محدودة للغاية (الحد الأقصى هو أنهم يشاركون في عملية التجميع). ومع ذلك ، أتوقع من القارئ فهم هياكل البيانات والخوارزميات.
هذه المقالة ليست مخصصة لمترجمي الإنتاج الحديثة بملايين الأسطر من التعليمات البرمجية - لا ، هذه دورة قصيرة "مترجمون للدمى" لمساعدتك في فهم ماهية المترجم.
مقدمة
أنا أعمل حاليًا على لغة نظام
Krug المستوحاة من Rust and Go. في المقالة سأشير إلى كروغ كمثال لتوضيح أفكاري. Krug قيد التطوير ، ولكنه متاح بالفعل على
https://github.com/krug-lang في مستودعات
caasper و
krug . اللغة ليست نموذجية تمامًا مقارنة بهندسة المترجم المعتادة ، والتي ألهمتني جزئيًا لكتابة مقال - لكن المزيد عن ذلك لاحقًا.
أسارع إلى إبلاغكم بأنني لست متخصصًا على الإطلاق في المجمعين! ليس لديّ شهادة دكتوراه ، ولم أحصل على أي تدريب رسمي - لقد درست كل شيء تم وصفه في المقال بمفردي في وقت فراغي. يجب أن أقول أيضًا أنني لا أصف الطريقة الفعلية الصحيحة فقط لإنشاء مترجم ، لكنني أقدم الأساليب الأساسية المناسبة لإنشاء مترجم صغير "لعبة".
الواجهة
دعنا نعود إلى الرسم البياني أعلاه: الأسهم الموجودة على اليسار والموجهة إلى حقل الواجهة الأمامية هي لغات معروفة ومحبوبة مثل C. الواجهة الأمامية تبدو مثل هذا: التحليل المعجمي -> المحلل اللغوي.
تحليل معجمي
عندما بدأت دراسة المترجمين وتصميم اللغة ، قيل لي أن التحليل المعجمي هو نفس الرمز. سوف نستخدم هذا الوصف. يأخذ المحلل بيانات الإدخال في شكل سلاسل أو مجموعة من الأحرف ويتعرف على الأنماط الموجودة فيها ، والتي تتحول إلى رموز.
في حالة برنامج التحويل البرمجي ، يتلقى برنامج مكتوب عند الإدخال. تتم قراءته في سلسلة من ملف ، ويقوم المحلل بتشفير كود المصدر الخاص به.
enum TokenType { Identifier, Number, }; struct Token { std::string Lexeme; TokenType type; // ... // It's also handy to store things in here // like the position of the token (start to end row:col) };
في هذا الجزء ، المكتوب بلغة على شكل C ، يمكنك رؤية البنية التي تحتوي على lexeme المذكور أعلاه ، وكذلك TokenType ، والذي يعمل على التعرف على هذا الرمز المميز.
ملاحظة: المقالة ليست تعليمة لإنشاء لغة بأمثلة - ولكن لفهم أفضل ، سأدرج مقتطفات برمجية من وقت لآخر.
المحللون هم عادة أبسط مكونات برنامج التحويل البرمجي. الواجهة الأمامية بالكامل ، في الواقع ، بسيطة للغاية مقارنة ببقية قطع الألغاز. على الرغم من أن ذلك يعتمد كثيرًا على عملك.
خذ الجزء التالي من الكود C:
int main() { printf("Hello world!\n"); return 0; }
بعد قراءته من ملف إلى سطر وإجراء فحص خطي ، قد تتمكن من قطع الرموز المميزة. نحدد الرموز بطريقة طبيعية - رؤية أن int هي "كلمة" ، و 0 في عبارة الإرجاع هي "رقم". يقوم المحلل اللغوي بنفس الإجراء الذي نقوم به - في وقت لاحق سنبحث هذه العملية بمزيد من التفصيل. على سبيل المثال ، قم بتحليل الأرقام:
0xdeadbeef — HexNumber ( ) 1231234234 — WholeNumber ( ) 3.1412 — FloatingNumber ( ) 55.5555 — FloatingNumber ( ) 0b0001 — BinaryNumber ( )
تحديد الكلمات يمكن أن يكون صعبا. تعرّف معظم اللغات الكلمة بتسلسل من الحروف والأرقام ، ويجب أن يبدأ المعرف عادة بحرف أو شرطة سفلية. على سبيل المثال:
123foobar := 3 person-age := 5 fmt.Println(123foobar)
في Go ، لن يعتبر هذا الرمز صحيحًا وسيتم تحليله في الرموز التالية:
Number(123), Identifier(foobar), Symbol(:=), Number(3) ...
تبدو معظم المعرّفات التي صادفتها كما يلي:
foo_bar __uint8_t fooBar123
سيتعين على المحللين حل المشكلات الأخرى ، على سبيل المثال ، مع وجود مسافات وتعليقات متعددة الأسطر وخط واحد ومعرفات وأرقام وأنظمة أرقام وتنسيق أرقام (على سبيل المثال ، 1000_000) وترميزات (على سبيل المثال ، دعم UTF8 بدلاً من ASCII).
وإذا كنت تعتقد أنه يمكنك اللجوء إلى تعبيرات منتظمة - من الأفضل ألا تستحق ذلك. من الأسهل بكثير كتابة محلل من نقطة الصفر ، لكنني أوصي بشدة بقراءة
هذا المقال من ملكنا وإلهنا روب بايك. تم وصف أسباب Regex غير المناسبة لنا في العديد من المقالات الأخرى ، لذلك سأحذف هذه النقطة. بالإضافة إلى ذلك ، تعد كتابة محلل أكثر إثارة للاهتمام من تعذب نفسك بتعابير مطوّلة طويلة تم تحميلها على regex101.com في الساعة 5:24 صباحًا. في لغتي الأولى ، استخدمت الدالة
split(str) للرمز المميز - ولم أذهب بعيدًا.
إعراب
التحليل أكثر تعقيدًا بعض الشيء من التحليل المعجمي. هناك العديد من المحللون والموزعون - حيث تبدأ اللعبة بشكل كبير.
عادةً ما يأخذ المحللون في المترجمات المدخلات في شكل رموز ويقومون ببناء شجرة معينة - شجرة بناء جملة مجردة أو شجرة تحليل. بطبيعتها ، فهي متشابهة ، ولكن لديها بعض الاختلافات.
يمكن تمثيل هذه المراحل كوظائف:
fn lex(string input) []Token {...} fn parse(tokens []Token) AST {...} let input = "int main() { return 0; }"; let tokens = lex(input); let parse_tree = parse(tokens); // ....
عادةً ما يتم إنشاء برامج التحويل البرمجي من العديد من المكونات الصغيرة التي تأخذ المدخلات أو تغيرها أو تحولها إلى مخرجات مختلفة. هذا هو أحد الأسباب التي تجعل اللغات الوظيفية مناسبة تمامًا لإنشاء برامج ترجمة. الأسباب الأخرى هي التقييم المعياري والمكتبات القياسية واسعة النطاق إلى حد ما. حقيقة ممتعة: أول تطبيق
لمجمع الصدأ كان على Ocaml.
أنصحك بالاحتفاظ بهذه المكونات بالبساطة والاستقلالية قدر الإمكان - فالنموذجية ستسهل العملية بشكل كبير. في رأيي ، يمكن قول الشيء نفسه عن العديد من الجوانب الأخرى لتطوير البرمجيات.
الأشجار
تحليل شجرة
ماذا بحق الجحيم هذا؟ تُعرف هذه الشجرة الكثيفة أيضًا باسم شجرة التحليل ، وهي تصور البرنامج المصدر. أنها تحتوي على جميع المعلومات (أو معظمها) حول برنامج الإدخال ، عادةً نفس المعلومات الموضحة في قواعد اللغة الخاصة بك. ستكون كل عقدة شجرة زائدة أو غير زائدة ، على سبيل المثال ، NumberConstant أو StringConstant.
شجرة بناء جملة مجردة
كما يوحي الاسم ، فإن ASD عبارة عن شجرة بناء جملة
مجردة . تحتوي شجرة التحليل على الكثير من المعلومات (غالبًا ما تكون زائدة عن الحاجة) حول البرنامج ، وفي حالة وجود ASD ، فإنها غير مطلوبة. لا يحتاج ASD إلى معلومات عديمة الفائدة حول البنية والنحو ، والتي لا تؤثر على دلالات البرنامج.
لنفترض أن شجرتك لها تعبير مثل ((5 + 5) -3) +2. في شجرة التحليل ، ستقوم بتخزينها تمامًا ، جنبًا إلى جنب مع الأقواس والمشغلين والقيم 5 و 5 و 3 و 2. ولكن يمكنك ببساطة ربط ASD - نحتاج فقط إلى معرفة القيم والمشغلين وترتيبهم.
الصورة أدناه توضح الشجرة للتعبير a + b / c.
يمكن تمثيل ASD على النحو التالي:
interface Expression { ... }; struct UnaryExpression { Expression value; char op; }; struct BinaryExpression { Expression lhand, rhand; string op; // string because the op could be more than 1 char. }; interface Node { ... }; // or for something like a variable struct Variable : Node { Token identifier; Expression value; };
وجهة النظر هذه محدودة للغاية ، لكنني آمل أن تتمكن من رؤية كيفية تنظيم عقدك. للتحليل ، يمكنك اللجوء إلى الإجراء التالي:
Node parseNode() { Token current = consume(); switch (current.lexeme) { case "var": return parseVariableNode(); // ... } panic("unrecognized input!"); } Node n = parseNode(); if (n != null) { // append to some list of top level nodes? // or append to a block of nodes! }
آمل أن تتعرفوا على كيفية سير عملية التحليل التدريجي للعقد المتبقية ، بدءًا من إنشاءات لغة عالية المستوى. كيف بالضبط محلل مع النسب العودية يتم تنفيذها ، تحتاج إلى دراسة نفسك.
قواعد
يمكن أن يكون تحليل في ADS من مجموعة من الرموز صعبة. عادة يجب أن تبدأ بقواعد اللغة الخاصة بك. في جوهرها ، ويحدد قواعد اللغة هيكل لغتك. هناك عدة لغات لتحديد اللغات التي يمكنها وصف (أو تحليل) نفسها.
مثال على لغة لتحديد اللغات هو
شكل موسع من Backus-Naur (RBNF). إنه تباين لـ
BNF مع أقواس زاوية أقل. فيما يلي مثال RBNF من مقالة ويكيبيديا:
digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit excluding zero ;
يتم تعريف قواعد الإنتاج: وهي تشير إلى قالب المحطة الطرفية "غير الطرفية". تعد المطاريف جزءًا من الأبجدية ، على سبيل المثال ، إذا كانت الرمز المميز أو 0 و 1 في المثال أعلاه مطاريف. غير المطاريف معاكس لها ، فهي على الجانب الأيسر من قواعد الإنتاج ، ويمكن اعتبارها متغيرات أو "مؤشرات مسماة" لمجموعات من المطاريف وغير الطرفية.
العديد من اللغات لها مواصفات تحتوي على قواعد. على سبيل المثال ، من أجل
Go و
Rust و
D.تكراري هبوط النسب
النسب التكراري هو أسهل طرق التحليل العديدة.
محللات النسب العودية - تنازليًا ، استنادًا إلى الإجراءات العودية. من الأسهل بكثير كتابة محلل ، لأن قواعد اللغة لديك لم
تترك العودية . في معظم لغات "الألعاب" ، هذه التقنية كافية للتحليل. يستخدم GCC محلل تنازلي مكتوب بخط اليد ، على الرغم من استخدام YACC من قبل.
ومع ذلك ، يمكن أن يسبب تحليل هذه اللغات مشاكل. على وجه الخصوص ، C ، أين
foo * bar
يمكن أن تفسر على النحو
int foo = 3; int bar = 4; foo * bar; // unused expression
او كيف
typedef struct { int b; } foo; foo* bar; bar.b = 3;
يستخدم تطبيق Clang أيضًا محلل النسب العودية:
نظرًا لأن هذا رمز C ++ منتظم ، فإن النسب المتكرر يجعل من السهل على المبتدئين فهمه. وهو يدعم القواعد المخصصة والأشياء الغريبة الأخرى التي تتطلبها C / C ++ وتساعدك على تشخيص الأخطاء وإصلاحها بسهولة.يجدر أيضًا الانتباه إلى الأساليب الأخرى:
- تنازلي LL ، النسب العودية
- LR تصاعدي ، تحول ، نزول تصاعدي
مولدات المحلل
طريقة جيدة أخرى. بالطبع ، هناك أيضًا عيوب - ولكن يمكن قول ذلك حول أي خيار آخر يقوم به المبرمجون عند إنشاء البرامج.
مولدات المحلل تعمل بخفة عالية. استخدامها أسهل من كتابة المحلل الخاص بك والحصول على نتيجة جيدة - على الرغم من أنها ليست سهلة الاستخدام للغاية ولا تعرض دائمًا رسائل خطأ. بالإضافة إلى ذلك ، سيتعين عليك معرفة كيفية استخدام أداة إنشاء المحلل اللغوي ، وعند الترقية إلى برنامج التحويل البرمجي ، من المحتمل أن تضطر إلى الاسترخاء في أداة إنشاء المحلل اللغوي.
مثال على مولد المحلل اللغوي هو
ANTLR ، وهناك العديد من الآخرين.
أعتقد أن هذه الأداة مناسبة لأولئك الذين لا يريدون قضاء وقت في كتابة الواجهة الأمامية ، والذين يفضلون كتابة الجزء الأوسط والخلفي من المترجم / المترجم الشفهي وتحليل أي شيء.
تحليل التطبيق
إذا كنت لا تزال لا تفهم نفسك. حتى الواجهة الأمامية للمترجم (lex / parse) يمكن استخدامها لحل المشكلات الأخرى:
- تسليط الضوء على بناء الجملة
- تحليل HTML / CSS لتقديم المحرك
- transpilers: TypeScript ، CoffeeScript
- linkers
- REGEX
- تحليل البيانات واجهة
- تحليل URL
- أدوات التنسيق مثل gofmt
- تحليل SQL وأكثر.
وسط
تحليل الدلالي! يعد تحليل دلالات اللغة أحد أصعب المهام عند إنشاء برنامج التحويل البرمجي.
تحتاج إلى التأكد من أن جميع برامج الإدخال تعمل بشكل صحيح. في لغتي Krug ، لم يتم بعد إدراج الجوانب المتعلقة بالتحليل الدلالي ، وبدون ذلك ، سيُطلب من المبرمج دائمًا كتابة الكود الصحيح. في الواقع ، هذا مستحيل - ونحن دائمًا نكتب الأخطاء ونصنّفها وأحيانًا نصلحها. هذا دوامة لا نهاية لها.
بالإضافة إلى ذلك ، تجميع البرامج مستحيل دون تحليل صحة الدلالات في المرحلة المناسبة من التجميع.
لقد صادفت رسمًا بيانيًا عن النسبة المئوية للواجهة الأمامية والوسطى والخلفية. ثم بدا الأمر كذلك
F: 20% M: 20%: B: 60%
اليوم هو شيء من هذا القبيل
F: 5% M: 60% B: 35%
تهتم الواجهة الأمامية بشكل أساسي بالمولد ، وفي اللغات التي لا تحتوي على سياق والتي لا تحتوي على ازدواجية القواعد ، يمكن إكمالها بسرعة كبيرة - سيساعد النسب التكراري هنا.
مع تقنية LLVM ، يمكن تحميل معظم أعمال التحسين إلى الإطار ، الذي يقدم عددًا من التحسينات الجاهزة.
والخطوة التالية هي التحليل الدلالي ، وهو جزء أساسي من مرحلة التجميع.
على سبيل المثال ، في Rust ، مع نموذج إدارة الذاكرة الخاص به ، يعمل المترجم كآلة كبيرة قوية تقوم بإجراء أنواع مختلفة من التحليل الثابت في النماذج التمهيدية. جزء من هذه المهمة هو تحويل بيانات الإدخال إلى نموذج أكثر ملاءمة للتحليل.
لهذا السبب ، يلعب التحليل الدلالي دورًا مهمًا في بنية المترجم ، ويتم العمل التحضيري الشاق مثل تحسين التجميع الذي تم إنشاؤه أو قراءة بيانات الإدخال في ASD نيابة عنك.
الممرات الدلالية
في سياق التحليل الدلالي ، تجري معظم المترجمات عددًا كبيرًا من "التمريرات الدلالية" على SDA أو أي شكل آخر من أشكال تعبير الرمز. توفر
هذه المقالة تفاصيل حول معظم التمريرات التي تم إجراؤها في برنامج التحويل البرمجي .NET C #.
لن أضع في الإعتبار كل مقطع ، خاصةً أنهما يختلفان تبعًا للغة ، ولكن هناك العديد من الخطوات الموضحة أدناه في كروغ.
إعلان المستوى الأعلى
سيقوم المحول البرمجي بالاطلاع على جميع إعلانات "المستوى الأعلى" في الوحدات النمطية ويكون مدركًا لوجودها. لن يتعمق في الكتل - سيعلن ببساطة عن الهياكل والوظائف وما إلى ذلك. متوفرة في وحدة واحدة أو أخرى.
اسم / رمز القرار
المترجم يمر عبر جميع كتل التعليمات البرمجية في وظائف ، الخ ويحلها - أي ، يجد الحروف التي تتطلب إذنًا. هذا تمرير شائع ، ومن هنا يأتي الخطأ "
لا يوجد رمز XYZ" عادةً عند تجميع Go code.
قد يكون إجراء هذا التمرين صعباً للغاية ، خاصةً إذا كانت هناك تبعيات دائرية في مخطط التبعية الخاص بك. بعض اللغات لا تسمح لهم بذلك ، على سبيل المثال ، سوف يرسل Go خطأ إذا كانت إحدى الحزم الخاصة بك تشكل حلقة ، مثل لغتي Krug. يمكن اعتبار التبعيات الدورية أحد الآثار الجانبية للعمارة الفقيرة.
يمكن تحديد الحلقات عن طريق تعديل DFS في مخطط التبعية ، أو باستخدام
خوارزمية تارجان (كما فعلت كروغ) لتحديد الحلقات (متعددة).
اكتب الاستدلال
المترجم يمر عبر جميع المتغيرات ويعرض أنواعها. إن الاستدلال على الكتابة في Krug ضعيف للغاية ؛ إنه ببساطة يخرج المتغيرات بناءً على قيمها. إنه ليس بأي حال نظامًا غريبًا ، كما هو الحال في اللغات الوظيفية مثل Haskell.
يمكن اشتقاق الأنواع باستخدام عملية "التوحيد" ، أو "توحيد الكتابة". بالنسبة للأنظمة الأكثر بساطة ، يمكن استخدام تطبيق بسيط للغاية.
يتم تنفيذ الأنواع في Krug مثل هذا:
interface Type {}; struct IntegerType : Type { int width; bool signed; }; struct FloatingType : Type { int width; }; struct ArrayType : Type { Type base_type; uint64 length; };
يمكنك أيضًا الحصول على استدلال بسيط على الكتابة ، حيث يمكنك تعيين نوع إلى عقد التعبير ، على سبيل المثال ، يمكن أن يكون IntegerConstantNode من النوع IntegerType (64). ثم يمكنك الحصول على وظيفة
unify(t1, t2) ، والتي ستحدد أوسع نوع يمكن استخدامه لاستنتاج نوع التعبيرات الأكثر تعقيدًا ، على سبيل المثال ، التعبيرات الثنائية. لذلك فهي مسألة تعيين متغير على اليسار لقيم الأنواع المحددة على اليمين.
كتبت ذات مرة
نوع بسيط
يلقي على Go ، والذي أصبح تطبيقًا أوليًا لكروج.
قابلية التحويل
Krug (مثل Rust) هي لغة ثابتة بشكل افتراضي ، أي أن المتغيرات تبقى كما هي دون تغيير ما لم ينص على خلاف ذلك:
let x = 3; x = 4; // BAD! mut y = 5; y = 6; // OK!
يمر المحول البرمجي بجميع الكتل والوظائف ويتحقق من أن "المتغيرات صحيحة" ، أي أننا لا نغير ما لا يتبع وأن جميع المتغيرات التي تم تمريرها إلى وظائف معينة ثابتة أو قابلة للتغيير عند الاقتضاء.
يتم ذلك بمساعدة المعلومات الرمزية التي تم جمعها على التصاريح السابقة. يحتوي جدول الرموز استنادًا إلى نتائج الممر الدلالي على أسماء رمزية وعلامات تباين متغير. قد يحتوي على بيانات أخرى ، على سبيل المثال ، في C ++ ، يمكن للجدول تخزين المعلومات حول ما إذا كان الرمز خارجيًا أم ثابتًا.
جداول الأحرف
جدول الأحرف ، أو "الطعنة" ، هو جدول للعثور على الحروف المستخدمة في البرنامج. يتم إنشاء جدول واحد لكل نطاق ، وكلها تحتوي على معلومات حول الأحرف الموجودة في نطاق معين.
تتضمن هذه المعلومات خصائص مثل اسم الرمز والنوع وعلامة قابلية التحويل ووجود اتصال خارجي والموقع في الذاكرة الساكنة وما إلى ذلك.
مجال
هذا مفهوم مهم في لغات البرمجة. بالطبع ، لا يتعين على لغتك أن تجعل من الممكن إنشاء نطاقات متداخلة ، يمكن وضع كل شيء في مساحة اسم واحدة مشتركة!
على الرغم من أن تمثيل النطاق يعد مهمة شيقة بالنسبة لبنية برنامج التحويل البرمجي ، إلا أن النطاق يتصرف (أو يشبه) في بنية بيانات مكدس في معظم اللغات المشابهة لـ C.
عادةً ما نقوم بإنشاء وتدمير النطاقات ، وعادةً ما يتم استخدامها لإدارة الأسماء ، أي أنها تسمح لنا بإخفاء (تظليل) المتغيرات:
{ // push scope let x = 3; { // push scope let x = 4; // OK! } // pop scope } // pop scope
يمكن تمثيله بشكل مختلف:
struct Scope { Scope* outer; SymbolTable symbols; }
صغيرة offtopic ، لكنني أوصي القراءة حول
مكدس السباغيتي . هذا هو هيكل البيانات الذي يتم استخدامه لتخزين مناطق الرؤية في العقد ASD من الكتل المعاكسة.
نظم نوع
يمكن تطوير العديد من الأقسام التالية في مقالات منفصلة ، لكن يبدو لي أن هذا العنوان يستحق ذلك. يتوفر اليوم الكثير من المعلومات حول أنظمة الكتابة ، بالإضافة إلى أنواع مختلفة من الأنظمة نفسها ، والتي يوجد حولها العديد من النسخ. لن
أتعمق في هذا الموضوع ، فقط اترك رابطًا
للمقال الممتاز الذي كتبه ستيف Klabnik .
نظام الكتابة هو ما يتم توفيره وتعريفه بشكل دلالي في المحول البرمجي باستخدام تمثيل المترجم وتحليل هذه التمثيلات.
حيازة
يستخدم هذا المفهوم في البرمجة أكثر وأكثر. إن مبادئ دلالات الملكية والحركة مضمنة في لغة
Rust ، وآمل أن تظهر في لغات أخرى. يؤدي Rust العديد من أنواع التحليل الثابت المختلفة ، والتي تتحقق لمعرفة ما إذا كان الإدخال يفي بمجموعة من القواعد المتعلقة بالذاكرة: من الذي يملك الذاكرة ، وعندما يتم إتلاف الذاكرة ، وعدد المراجع (أو الاقتراضات) الموجودة لهذه القيم أو الذاكرة.
يكمن جمال Rust في حقيقة أن كل هذا يتم أثناء التجميع ، داخل المترجم ، بحيث لا يتعين على المبرمج التعامل مع جمع القمامة أو حساب الارتباط. يتم تعيين كل هذه الدلالات إلى نظام الكتابة ويمكن توفيرها حتى قبل تقديم البرنامج في شكل ملف ثنائي كامل.
لا أستطيع أن أقول كيف يعمل كل شيء تحت الغطاء ، لكن كل هذا هو نتيجة التحليل الثابت والبحث الرائع الذي أجراه فريق موزيلا والمشاركون في مشروع
الإعصار .
الرسوم البيانية التحكم في التدفق
لتمثيل تدفقات البرنامج ، نستخدم الرسوم البيانية لتدفق التحكم (CFG) ، والتي تحتوي على جميع المسارات التي يمكن أن يتبعها تنفيذ البرنامج. يتم استخدام هذا في التحليل الدلالي لاستبعاد مقاطع الخمول من التعليمات البرمجية ، أي الكتل والوظائف وحتى الوحدات التي لن يتم تحقيقها أثناء تنفيذ البرنامج. يمكن أيضًا استخدام الرسوم البيانية لتحديد الدورات التي لا يمكن مقاطعتها. أو للبحث عن رمز يتعذر الوصول إليه ، على سبيل المثال ، عند استدعاء "حالة من الذعر" (استدعاء حالة من الذعر) ، أو العودة في حلقة ، وعدم تنفيذ التعليمات البرمجية خارج الحلقة. يلعب
تحليل تدفق البيانات دورًا مهمًا خلال المرحلة الدلالية من المحول البرمجي ، لذلك أوصي بالقراءة حول أنواع التحليل التي يمكنك تنفيذها وكيفية عملها وما يمكن أن تفعله التحسينات.
الخلفية
الجزء الأخير من مخطط العمارة لدينا.لقد قمنا بمعظم أعمال توليد ثنائيات قابلة للتنفيذ. يمكن القيام بذلك بطرق مختلفة ، والتي سنناقشها أدناه.
- , . , , «».
, . , , . , , , . , .
, . , ++ — Cfront — C.
JavaScript. TypeScript , , , , .
«» , , , , « » . — , , .
LLVM
LLVM: Rust, Swift, C/C++ (clang), D, Haskell.
« », , . , LLVM . , . , , , , 1, 4, 8 16-. , , - .
-
— , — , .
Go — , LLVM ( ). Go , Windows, Linux MacOS. , Krug -.
. , LLVM, , , LLVM , .
, , , LLVM, IR, , , , ( ).
. , , , . IR ( ) «» fprintf .
8cc .
. — Java: ,
JVM , , Kotlin.
, Java . , . , .
, JVM JIT , JIT-, .
, ! , , . - , , .
Godbolt — , , . , , .
, , (strip the debug symbols), , GCC. , - .
. . , . production-.
rwmj , 8 , 80% . 1971-!
, Rust.
IR
(intermediate representation, IR) , . , , .
IR . , , , .
IR, «», IR . , SSA — Static Single Assignment, , .
Go IR SSA. IR LLVM SSA, .
SSA , , (constant propagation), ( ) .
, . , , , , . ( 16 32), , (spill to the stack).
— ( ). , , .
:
- (graph colouring) — (NP- ). , (liveness ranges) .
- — .
. , . , , .
-, , . , .
fn main() int { let x = 0; { let x = 0; { let x = 0; } } return 0; }
, ( - :) ) , . , .
LLDB
DWARF . LLVM , DWARF GNU-. , , , .
(Foreign Function Interface, FFI )
libc , , . , ?
— . , ( .s/.asm)? ? ,
Jai . , .
(CaaS)
API-. , Krug-, . , , .
, , , . , API-.
production- CaaS. Microsofts Roslyn, , . , , , , API-, , , Rust
RLS .
Krug — — Caasper CaaS-.
Caasper (, , ), , krug, . , , (bootstrap) , .
Krug JavaScript, Go*, , , Krug. JavaScript , yarn/npm.
* Go () , JS.Caasper
.
Github Krug, D LLVM. YouTube-
.
Krug ()
.
روابط مفيدة