تحليل نحوي

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

كما أن التحليل أيضاً مصطلح أولي فيما يخص تخطيط جمل اللغات الطبيعية وما زال مستخدما في تخطيط اللغات الاشتقاقية inflected languages مثل اللغات الرومانية أو اللاتينية. وجاء مصطلح التحليل من الكلمة اللاتينية pars (ōrātiōnis) والتي تعني قسم (من أقسام الكلام).

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

المحلل

المحلل هو أحد المكونات في المُفسر interpreter أو المجمع - البرنامج الذي يحول أوامر الكمبيوتر إلى لغة الحاسبة compiler- الذي يبحث عن التركيب الصحيح للجمل ويبني هيكل البيانات (غالبا بعض أنواع شجرة الإعراب أو شجرة بناء الجملة المجردة أو الهيكل الهرمي) بشكل ضمني في رموز المدخلات. وغالبا ما يُستخدم محلل مفردات منفصل لإنشاء رموز من سلسلة من حروف المدخلات. ويمكن برمجية المحللات يدويا أو ربما يتم توليدها بشكل شبه تلقائي باستخدام أداة (في بعض لغات البرمجة).

اللغات البشرية

في بعض نظم معالجة اللغة الطبيعية والترجمة الآلية يقوم الكمبيوتر بتحليل اللغات البشرية. والجمل البشرية لا يمكن ترجمتها بسهولة باستخدام البرامج إذ أن هناك شيء من الغموض الأساسي في هيكل اللغة البشرية والتي تستخدم من أجل نقل معنى (أو دلالات) بين إطار غير محدود من الاحتمالات لكن بعضها فقط وثيق الصلة بالحالة بعينها. وهكذا فإن النطق بجملة "الرجل عض الكلب" “Man bites dog” مقابل جملة "الكلب عض الرجل" “Dog bites man” لها تفاصيل واحدة لكن في لغات أخرى ربما تظهر هكذا “Man dog is biting” باعتماد على السياق الأكبر للتمييز بين هذين الاحتمالين، إذا كان للاختلاف أهمية بالفعل. ومن الصعب إعداد قواعد رسمية لوصف السلوك غير الرسمي حتى على الرغم من وضوح إتباع بعض القواعد.

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

معظم المحللين المعاصرين يعملون بشكل إحصائي على الأقل جزئيا، أي يعتمدون على مجموعة بيانات التدريب المشروحة من قبل بالفعل (محللة يدويا). وهذا المنهج يسمح للنظام بتجميع معلومات عن التكرار الذي يظهر معه العديد من التعليمات في سياقات معينة. (انظر التعلم باستخدام الآلة). ومن بين المناهج التي استخدمت المنهج المباشر PCFGs (اختصار القواعد النحوي الاحتمالية للسياق الحر) أقصى مقياس، وشبكات عصبية. ومعظم النظم الناجحة تستخدم إحصائيات ترادفية أو معجمية (أي أنهم يشاركون هويات الكلمات وكذلك أجزاء الكلام الخاصة بها). لكن هذه النظم ضعيفة وعرضه لخطر المغالاة في القياس وتتطلب نوع من النعومة لكي تكون فعالة.^{[بحاجة لمصدر]}

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

لغات البرمجة

أشهر استخدام المحلل هو استخدامه كمكون للمُفسر interpreter أو المجمع - البرنامج الذي يحول أوامر الكمبيوتر إلى لغة الحاسبة compiler. إذ أنه يقوم بتحليل الكود الأصلي للغة برمجة الكمبيوتر لإنشاء بعض صيغ العرض الداخلي. وتميل لغات البرمجة إلى أن تكون محددة فيما يتعلق بالقواعد الخالية من السياق لان المحللات السريعة والفعالة يمكن كتابتها لهم. ويتم كتابة المحللات يدويا أو يتم توليدها باستخدام مولدات محللات.

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

نظرة عامة عن العملية

المثال التالي يوضح الحالة العامة لتحليل لغة كمبيوتر بمستويين من القواعد: المستوى المعجمي والمستوى النحوي المرحلة الأولى هي مرحلة إنتاج الرموز أو التحليل المعجمي، وينقسم فيها حروف المدخلات إلى رموز ذات معنى محددة بقواعد التعبيرات المنتظمة، فعلى سبيل المثال برنامج الآلة الحاسبة يمكن أن ينظر إلى مدخلات مثل "12*(3+4)^2" ويقسمها إلى رموز 12 و* و(و 3و + و 4 و) و^ و 2، ولكل واحد منها رمز له معنى في سياق تعبير الحساب. ويقد يحتوي الحرف على قواعد فيده بأن الحروف * و+ و^ و(و) تمثل بدء رمز جديد، وهكذا فإن الرموز التي لها معنى مثل "12*" أو "(3" لن يتم توليدها. المرحلة التالية هي الإعراب أو التحليل النحوي والتي تبحث في أن الرموز تشكل تعبير مسموح به. وعادة ما يتم ذلك بالإشارة إلى القواعد الخالية من السياق والتي تحدد العناصر التي تكون تعبيرا والترتيب الذي لابد أن تبدو عليه. لكن ليس كل القواعد التي تحدد لغات بمرجة يمكن التعبير عنها باستخدام القواعد الخالية من السياق وحدها مثل صحة النوع والإعلان المناسب للمحددات. ويمكن التعبير عن هذه القواعد رسميا باستخدام القواعد قواعد السمة. المرحلة الأخيرة هي التحليل أو الإعراب الدلالي والذي يعمل على دلائل التعبير المصحح لتوه واتخاذ الإجراء المناسب. ففي حالة الآلة الحاسبة أو المُفسر سيكون الإجراء هو تقويم التعبير أو البرنامج؛ والمجمع compilerعلى الجانب الآخر يمكن أن ينتج نوع من الكود. كما يمكن استخدام قواعد السمة أيضاً في تحديد هذه الإجراءات.

أنواع المحللات

مهمة المحلل أساسا هي تحديد إذا كان من الممكن اشتقاق المدخلات من رمز البدء في القواعد وكيف ذلك، وهذا يتم بطريقتين أساسيتين وهما:

• التحليل التنازلي Top-down parsing – يمكن اعتباره محاولة للبحث عن مشتقات من أقصى اليسار لتيار المدخلات من خلال البحث عن شجر تحليل باستخدام توسع تنازلي لقواعد النحو الرسمية. وتستهلك الرموز من اليسار إلى اليمين. ويستخدم الاختيار الشامل في استيعاب الغموض من خلال توسيع كافة بدائل جوانب اليد اليمنى للقواعد النحوية.

• التحليل التصاعدي - يمكن أن يبدأ المحلل بالمدخلات ومحاولة إعادة كتابتها على رموز البدء. ومن البديهي أن يحاول المحلل وضع العناصر الأساسية ثم العناصر التي تحتوي على هذه المدخلات. ومن المصطلحات الأخرى المستخدمة في هذا النوع من المحلل مصطلح التحليل بالحد من التحويل.

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

أمثلة للمحللات

محللات تنازلية

بعض المحللات التي تستخدم التحليل التنازلي:

• محللات تنازلية تكرارية
• محلل ال ال (Left-to-right, Leftmost derivation)
• محلل Earley
• محلل X-SAIGA، مواصفات القوات التي يمكن تنفيذها eXecutable SpecificAtIons of GrAmmars؛ ويحتوي على منشورات تتعلق بلوغاريتم التحليل التنازلي التي تدعم التكرار اليساري والغموض في المسافة والوقت المتعدد.

محللات تصاعدية

بعض المحللات التي تستخدم التحليل التصاعدي:

• محلل Precedence
  • محلل Operator-precedence
  • محلل Simple precedence
• تحليل بي سي (النص المحدد) bounded context
• محلل ال آر (Left-to-right, Rightmost derivation)
  • محلل ال آر بسيط SLR
  • محلل ال ايه ال ىر LALR
  • محلل كانونيكال ال آر Canonical LR
  • محلل جي ال آر GLR
• محلل سي واي كي CYK

برمجيات تطوير المحلل

بعض وسائل تطوير المحلل المعروفة تشمل ما يلي، وانظر أيضاً مقارنة مولدات المحللات:

• ANTLR
• Bison
• Coco/R
• GOLD
• JavaCC
• Lemon
• Lex
• Parboiled
• ParseIT
• Ragel
• Syntax Definition Formalism
• Spirit Parser Framework
• SYNTAX
• Yacc

أنظر أيضا

• LALR parser
• Backtracking
• Lexing
• Chart parser
• Compiler-compiler
• Deterministic parsing
• Generating strings
• Grammar checker
• Shallow parsing

لمزيد من الاطلاع

• Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987. ISBN 0-521-30413-X
• Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0-13-651431-6

وصلات خارجية

• Objective-C parser written in C#
• The Lemon LALR Parser Generator

ca:Analitzador sintàctic cs:Syntaktická analýza da:Parser de:Parser Parsing]] es:Analizador sintáctico fa:تجزیه کننده fi:Jäsennin fr:Décomposition analytique hr:Parsiranje hu:Elemző (informatika) id:Parsing it:Parsing ja:構文解析 kk:Синтаксистік талдау ko:구문 분석 mk:Парсер nl:Parser pl:Analizator składniowy pt:Análise sintática (computação) ro:Parsare ru:Синтаксический анализ sk:Syntaktická analýza sr:Parsiranje sv:Parser ta:இலக்கணப் பாகுபடுத்தி uk:Синтаксичний аналіз zh:語法分析器