التحليل المعجمي والنحوي

يشكل التحليل المعجمي والنحوي الواجهة الأمامية للمترجم البرمجي (compiler)، حيث يقومان بتقسيم النص المصدري إلى رموز (tokens) والتعرف على بنيته النحوية كشجرة تحليل أو شجرة تركيب.

Definition

التحليل المعجمي هو المرحلة التي تجمع أحرف الإدخال في رموز، والتحليل النحوي (parsing) هو المرحلة التي تحدد ما إذا كانت تلك الرموز تشكل برنامجًا صالحًا وفقًا لقواعد نحوية، وكيفية ذلك، مما ينتج عنه شجرة تركيب.

Scope

يغطي هذا الموضوع التحليل المعجمي، الذي يحول تدفقات الأحرف إلى رموز باستخدام اللغات المنتظمة (regular languages) والآلات ذات الحالات المحدودة (finite automata)، والتحليل النحوي (parsing)، الذي يتعرف على بنية العبارات لبرنامج ما مقابل قواعد نحوية خالية من السياق (context-free grammar). ويشمل ذلك التحليل من أعلى إلى أسفل (LL) ومن أسفل إلى أعلى (LR)، ومولدات المحللات النحوية (parser generators)، والغموض واستعادة الأخطاء، وبناء أشجار التركيب المجردة (abstract syntax trees).

Core questions

• كيف تُستخدم اللغات المنتظمة والخالية من السياق لوصف بنية البرنامج؟
• ما هي المفاضلات بين تحليل LL وتحليل LR؟
• كيف يتم اكتشاف ومعالجة الغموض وأخطاء التحليل؟
• كيف يتم بناء شجرة تركيب مجردة من تدفق الرموز؟

Key theories

تحليل LR

قدم كانوث (Knuth) تحليل LR، وهي تقنية من أسفل إلى أعلى تقوم بتحليل الفئة الواسعة من قواعد LR النحوية بشكل حتمي في وقت خطي، وتشكل أساس العديد من مولدات المحللات النحوية.

التحليل العام الخالي من السياق

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

الأسس المنتظمة والخالية من السياق للواجهة الأمامية

يقوم كتاب التنين (The Dragon Book) بمنهجة استخدام التعبيرات المنتظمة والآلات ذات الحالات المحدودة للمسح (scanning) والقواعد النحوية الخالية من السياق للتحليل (parsing)، بما في ذلك خوارزميات بناء LL و LR القياسية.

Clinical relevance

يُعد التحليل المعجمي والنحوي أساسًا ليس فقط للمترجمات البرمجية ولكن أيضًا للمفسرات (interpreters)، ومدققات الأكواد (linters)، ومنسقات الأكواد (formatters)، وبيئات التطوير المتكاملة (IDEs)، ومعالجات تنسيقات البيانات. ويُعد التحليل القوي مع استعادة جيدة للأخطاء أمرًا ضروريًا لتجربة المطور لأي أداة لغوية.

History

قدم تسلسل تشومسكي الهرمي للغات الرسمية في أواخر الخمسينيات نظرية اللغات المنتظمة والخالية من السياق. وقام كانوث (Knuth) بصياغة تحليل LR رسميًا في عام 1965، وقدم إيرلي (Earley) خوارزمية عامة خالية من السياق في عام 1970. وقد جعلت مولدات المحللات النحوية مثل yacc تحليل LR عمليًا، بينما استكشفت الأعمال اللاحقة قواعد تحليل التعبير (parsing expression grammars) والمحللات النحوية القائمة على المجمعات (combinator-based parsers).

Debates

المحللات النحوية المولدة مقابل المكتوبة يدويًا

يناقش الممارسون استخدام مولدات المحللات النحوية من القواعد الرسمية، والتي تكون موجزة وقابلة للتحقق، مقابل المحللات النحوية المكتوبة يدويًا ذات النزول التكراري (recursive-descent parsers)، والتي غالبًا ما تقدم رسائل خطأ وتحكمًا أفضل على حساب المزيد من التعليمات البرمجية.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

ما الفرق بين المحلل المعجمي (lexer) والمحلل النحوي (parser)؟

يقوم المحلل المعجمي بتجميع الأحرف الخام في رموز مثل المعرفات (identifiers) والمعاملات (operators)، بينما يقوم المحلل النحوي بترتيب تلك الرموز في شجرة تركيب هرمية وفقًا لقواعد اللغة النحوية.

ما الفرق بين تحليل LL وتحليل LR؟

تعمل محللات LL من أعلى إلى أسفل، متوقعة الإنتاجات من بادئة الإدخال، بينما تعمل محللات LR من أسفل إلى أعلى، مختزلة السلاسل الفرعية المعترف بها؛ تتعامل LR مع فئة أكبر بشكل صارم من القواعد النحوية ولكنها أكثر تعقيدًا في البناء.