التحليل

الموسوعة الحرة

التحليل النحوي أو التحليل النحوي هو عملية تحليل سلسلة من الرموز ، سواء في اللغة الطبيعية أو لغات الكمبيوتر أو هياكل البيانات ، وفقًا لقواعد النحو الرسمي . يأتي مصطلح التحليل من الكلمة اللاتينية pars ( orationis )، والتي تعني جزءًا (من الكلام) . [1]

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

في اللغويات الحاسوبية، يستخدم المصطلح للإشارة إلى التحليل الرسمي الذي يقوم به الكمبيوتر لجملة أو سلسلة أخرى من الكلمات إلى مكوناتها، مما يؤدي إلى شجرة تحليل تُظهر علاقتها النحوية مع بعضها البعض، والتي قد تحتوي أيضًا على معلومات دلالية . [ بحاجة لمصدر ] تولد بعض خوارزميات التحليل غابة تحليل أو قائمة بأشجار التحليل من سلسلة غامضة نحويًا . [2]

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

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

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

الطرق التقليدية

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

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

الأساليب الحسابية

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

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

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

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

علم اللغة النفسي

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

يفهم علماء اللغويات العصبية عمومًا أن التحليل هو وظيفة الذاكرة العاملة، مما يعني أن التحليل يستخدم للاحتفاظ بعدة أجزاء من جملة واحدة قيد التشغيل في العقل في وقت واحد، وكلها متاحة بسهولة للتحليل حسب الحاجة. ولأن الذاكرة العاملة البشرية لها حدود، فإن وظيفة تحليل الجملة لها حدود أيضًا. [10] يتضح هذا من خلال عدة أنواع مختلفة من الجمل المعقدة نحويًا والتي تقترح مشكلات محتملة للتحليل العقلي للجمل.

النوع الأول، وربما الأكثر شهرة، من الجمل التي تتحدى القدرة على التحليل هو جملة مسار الحديقة. تم تصميم هذه الجمل بحيث يبدو التفسير الأكثر شيوعًا للجملة خاطئًا من الناحية النحوية، ولكن عند الفحص الدقيق، فإن هذه الجمل سليمة من الناحية النحوية. يصعب تحليل جمل مسار الحديقة لأنها تحتوي على عبارة أو كلمة لها أكثر من معنى، وغالبًا ما يكون معناها الأكثر شيوعًا هو جزء مختلف من الكلام. [11] على سبيل المثال، في الجملة "اندفع الحصان متجاوزًا الحظيرة"، يتم تفسير raced في البداية على أنها فعل في زمن الماضي، ولكن في هذه الجملة، تعمل كجزء من عبارة صفة. [12] نظرًا لاستخدام التحليل لتحديد أجزاء الكلام، فإن هذه الجمل تتحدى قدرة القارئ على التحليل.

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

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

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

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

تحليل الخطاب

يدرس تحليل الخطاب طرق تحليل استخدام اللغة والأحداث السيميائية. يمكن تسمية اللغة الإقناعية بالبلاغة .

لغات الحاسوب

المحلل

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

إن المدخلات إلى المحلل هي عادةً نص مكتوب بلغة كمبيوتر معينة ، ولكن قد تكون أيضًا نصًا مكتوبًا بلغة طبيعية أو بيانات نصية أقل هيكلة، وفي هذه الحالة يتم استخراج أجزاء معينة فقط من النص، بدلاً من إنشاء شجرة تحليل. تتراوح المحللات من وظائف بسيطة للغاية مثل scanf ، إلى برامج معقدة مثل الواجهة الأمامية لمترجم C++ أو محلل HTML لمتصفح الويب . يتم إجراء فئة مهمة من التحليل البسيط باستخدام التعبيرات العادية ، حيث تحدد مجموعة من التعبيرات العادية لغة عادية ومحرك تعبير عادي يقوم تلقائيًا بإنشاء محلل لتلك اللغة، مما يسمح بمطابقة الأنماط واستخراج النص. في سياقات أخرى، تُستخدم التعبيرات العادية بدلاً من ذلك قبل التحليل، كخطوة معجمية يستخدم المحلل ناتجها بعد ذلك.

يختلف استخدام المحللات باختلاف المدخلات. في حالة لغات البيانات، غالبًا ما يوجد المحلل كمرفق قراءة ملف لبرنامج، مثل القراءة في نص HTML أو XML ؛ هذه الأمثلة هي لغات الترميز . في حالة لغات البرمجة ، المحلل هو أحد مكونات المترجم أو المفسر ، والذي يحلل الكود المصدر للغة برمجة الكمبيوتر لإنشاء شكل من أشكال التمثيل الداخلي؛ المحلل هو خطوة أساسية في واجهة المترجم الأمامية . تميل لغات البرمجة إلى أن تكون محددة من حيث قواعد نحوية حتمية خالية من السياق لأنه يمكن كتابة محللات سريعة وفعالة لها. بالنسبة للمترجمين، يمكن إجراء التحليل نفسه في تمريرة واحدة أو تمريرات متعددة - راجع المترجم ذو التمريرة الواحدة والمترجم ذو التمريرات المتعددة .

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

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

على سبيل المثال، في Python، الكود التالي هو الكود الصحيح نحويًا: 

x  =  1 
طباعة ( x )

ومع ذلك، فإن الكود التالي صالح من الناحية النحوية من حيث قواعد اللغة الخالية من السياق، مما ينتج عنه شجرة نحوية بنفس بنية الكود السابق، لكنه ينتهك القاعدة الدلالية التي تتطلب تهيئة المتغيرات قبل الاستخدام: 

x  =  1 
طباعة ( y )

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

تدفق البيانات في المحلل النموذجي
تدفق البيانات في المحلل النموذجي

يوضح المثال التالي الحالة الشائعة لتحليل لغة الكمبيوتر باستخدام مستويين من القواعد: المعجمية والنحوية.

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

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

المرحلة الأخيرة هي التحليل الدلالي ، والذي يتضمن تحديد الآثار المترتبة على التعبير الذي تم التحقق من صحته واتخاذ الإجراء المناسب. [17] في حالة الآلة الحاسبة أو المترجم، يكون الإجراء هو تقييم التعبير أو البرنامج؛ من ناحية أخرى، يقوم المترجم بإنشاء نوع ما من التعليمات البرمجية. يمكن أيضًا استخدام قواعد السمات لتحديد هذه الإجراءات.

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

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

التحليل من أعلى إلى أسفل
يمكن النظر إلى التحليل من أعلى إلى أسفل باعتباره محاولة للعثور على اشتقاقات أقصى اليسار لتدفق الإدخال من خلال البحث عن أشجار التحليل باستخدام التوسع من أعلى إلى أسفل لقواعد النحو الرسمية المعطاة . يتم استهلاك الرموز من اليسار إلى اليمين. يتم استخدام الاختيار الشامل لاستيعاب الغموض من خلال توسيع جميع الجوانب اليمنى البديلة لقواعد النحو. [18] يُعرف هذا باسم نهج الحساء البدائي. على غرار رسم الجملة، يكسر الحساء البدائي الدوائر الانتخابية للجمل. [19]
التحليل من الأسفل إلى الأعلى
يمكن للمحلل أن يبدأ بالمدخلات ويحاول إعادة كتابتها إلى رمز البداية. وبشكل بديهي، يحاول المحلل تحديد العناصر الأساسية، ثم العناصر التي تحتوي عليها، وهكذا. محللات LR هي أمثلة على المحللات من الأسفل إلى الأعلى. مصطلح آخر يستخدم لهذا النوع من المحللات هو تحليل Shift-Reduce .

محللات LL ومحلل الانحدار التكراري هي أمثلة على المحللات من أعلى إلى أسفل التي لا يمكنها استيعاب قواعد الإنتاج التكرارية اليسرى . على الرغم من الاعتقاد بأن التنفيذات البسيطة للتحليل من أعلى إلى أسفل لا يمكنها استيعاب التكرار الأيسر المباشر وغير المباشر وقد تتطلب تعقيدًا زمنيًا ومكانيًا أسيًا أثناء تحليل قواعد نحوية غامضة خالية من السياق ، فقد تم إنشاء خوارزميات أكثر تطورًا للتحليل من أعلى إلى أسفل بواسطة Frost و Hafiz و Callaghan [20] [21] والتي تستوعب الغموض والتكرار الأيسر في وقت متعدد الحدود والتي تولد تمثيلات بحجم متعدد الحدود لعدد أسي محتمل لأشجار التحليل. خوارزميتهم قادرة على إنتاج اشتقاقات أقصى اليسار وأقصى اليمين لإدخال فيما يتعلق بقواعد نحوية خالية من السياق معينة .

من بين أهم الفروقات فيما يتعلق بالمحللات ما إذا كان المحلل يولد اشتقاقًا أقصى اليسار أم اشتقاقًا أقصى اليمين (انظر قواعد اللغة الخالية من السياق ). سوف يولد المحللون LL اشتقاقًا أقصى اليسار وسوف يولد المحللون LR اشتقاقًا أقصى اليمين (على الرغم من أن ذلك يحدث عادةً في الاتجاه المعاكس). [18]

بعضتم تصميم خوارزميات التحليل الرسومي للغات البرمجة المرئية.[22][23]تعتمد المحللات الخاصة باللغات المرئية أحيانًا علىقواعد الرسم البياني.[24]

تم استخدام خوارزميات التحليل التكيفي لبناء واجهات مستخدم لغة طبيعية "ذاتية الامتداد" . [25]

تطبيق

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

طرق تنفيذ المحلل البديلة:

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

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

تتضمن بعض أدوات تطوير المحلل المعروفة ما يلي:

نظرة إلى الأمام

برنامج C لا يمكن تحليله بأقل من 2 رمز استشرافي. أعلى: مقتطف من قواعد اللغة C. [28] أسفل: قام المحلل بتحليل الرموز " " وهو على وشك اختيار قاعدة لاستنتاج Stmt . بالنظر فقط إلى رمز الاستشراف الأول " "، لا يمكنه تحديد أي من البديلين يختاره Stmt ؛ يتطلب الأخير إلقاء نظرة خاطفة على الرمز الثاني.int v;main(){v

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

معظم لغات البرمجة ، الهدف الأساسي للمحللات، محددة بعناية بحيث يمكن للمحلل ذي النظرة المستقبلية المحدودة، عادةً واحد، تحليلها، لأن المحللات ذات النظرة المستقبلية المحدودة غالبًا ما تكون أكثر كفاءة. حدث أحد التغييرات المهمة [ بحاجة لمصدر ] لهذا الاتجاه في عام 1990 عندما أنشأ تيرينس بار ANTLR لأطروحته للدكتوراه، وهو مولد محلل لمحللات LL( k ) الفعالة، حيث k هي أي قيمة ثابتة.

عادةً ما يكون لدى محللي LR عدد قليل من الإجراءات بعد رؤية كل رمز. وهي: shift (إضافة هذا الرمز إلى المكدس للتخفيض لاحقًا)، وreduce (إخراج الرموز من المكدس وتكوين بنية نحوية)، وend، وerror (لا توجد قاعدة معروفة تنطبق)، أوconflict (لا يعرف ما إذا كان يجب التحويل أو التخفيض).

تتمتع ميزة Lookahead بميزتين. [ يحتاج إلى توضيح ]

  • يساعد المحلل على اتخاذ الإجراء الصحيح في حالة وجود تعارضات. على سبيل المثال، تحليل عبارة if في حالة وجود عبارة else.
  • إنه يزيل العديد من الحالات المكررة ويخفف العبء المتمثل في وجود كومة إضافية. سيحتوي محلل لغة AC غير الاستباقي على حوالي 10000 حالة. سيحتوي محلل الاستباقي على حوالي 300 حالة.

مثال: تحليل التعبير 1 + 2 * 3 [ مشكوك فيه – ناقش ]

مجموعة قواعد تحليل التعبيرات (تسمى القواعد النحوية) هي كما يلي،
القاعدة رقم 1: هـ → هـ + هـ التعبير هو مجموع تعبيرين.
القاعدة 2: هـ → هـ * هـ التعبير هو نتاج تعبيرين.
القاعدة رقم 3: ع → رقم التعبير هو رقم بسيط
القاعدة رقم 4: + له أولوية أقل من *

تعطي معظم لغات البرمجة (باستثناء بعض اللغات مثل APL وSmalltalk) والصيغ الجبرية الأولوية للضرب مقارنة بالجمع، وفي هذه الحالة يكون التفسير الصحيح للمثال أعلاه هو 1 + (2 * 3) . لاحظ أن القاعدة 4 أعلاه هي قاعدة دلالية. ومن الممكن إعادة كتابة القواعد النحوية لدمجها في بناء الجملة. ومع ذلك، لا يمكن ترجمة كل هذه القواعد إلى بناء جملة.

إجراءات محلل بسيطة غير استباقية

الإدخال الأولي = [1، +، 2، *، 3]

  1. انقل "1" إلى المكدس من الإدخال (تحسبًا للقاعدة 3). الإدخال = [+, 2, *, 3] المكدس = [1]
  2. يُختزل "1" إلى التعبير "E" استنادًا إلى القاعدة 3. المكدس = [E]
  3. انقل "+" إلى المكدس من الإدخال (تحسبًا للقاعدة 1). الإدخال = [2، *، 3] المكدس = [E، +]
  4. انقل "2" إلى المكدس من الإدخال (تحسبًا للقاعدة 3). الإدخال = [*, 3] المكدس = [E, +, 2]
  5. قم بتقليص عنصر المكدس "2" إلى التعبير "E" استنادًا إلى القاعدة 3. المكدس = [E، +، E]
  6. قم بتقليل عناصر المكدس [E، +، E] وأدخل "E" إلى "E" استنادًا إلى القاعدة 1. المكدس = [E]
  7. انقل "*" إلى المكدس من الإدخال (تحسبًا للقاعدة 2). الإدخال = [3] المكدس = [E,*]
  8. انقل "3" إلى المكدس من الإدخال (تحسبًا للقاعدة 3). الإدخال = [] (فارغ) المكدس = [E, *, 3]
  9. قم بتقليص عنصر المكدس "3" إلى التعبير "E" استنادًا إلى القاعدة 3. المكدس = [E, *, E]
  10. قم بتقليل عناصر المكدس [E, *, E] وأدخل "E" إلى "E" استنادًا إلى القاعدة 2. المكدس = [E]

شجرة التحليل والرمز الناتج عنها غير صحيحين وفقًا لدلالات اللغة.

لإجراء تحليل صحيح دون النظر إلى الأمام، هناك ثلاثة حلول:

  • يتعين على المستخدم وضع التعبيرات بين قوسين. وهذا ليس حلاً عمليًا في كثير من الأحيان.
  • يحتاج المحلل إلى مزيد من المنطق للرجوع إلى الوراء وإعادة المحاولة كلما تم انتهاك قاعدة ما أو لم تكتمل. يتم اتباع الطريقة المماثلة في محللات LL.
  • بدلاً من ذلك، يحتاج المحلل أو القواعد النحوية إلى منطق إضافي لتأخير التخفيض والتخفيض فقط عندما يكون متأكدًا تمامًا من القاعدة التي يجب تخفيضها أولاً. تُستخدم هذه الطريقة في محللات LR. تقوم هذه الطريقة بتحليل التعبير بشكل صحيح ولكن مع المزيد من الحالات وزيادة عمق المكدس.
إجراءات محلل النظرة المستقبلية [ التوضيح مطلوب ]
  1. انقل 1 إلى المكدس عند الإدخال 1 تحسبًا للقاعدة 3. ولا يتم تقليله على الفور.
  2. تقليل عنصر المكدس 1 إلى تعبير بسيط عند الإدخال + استنادًا إلى القاعدة 3. يكون التطلع للأمام +، لذا فنحن على المسار إلى E +، لذا يمكننا تقليل المكدس إلى E.
  3. اضغط على Shift + على المكدس عند الإدخال + تحسبًا للقاعدة 1.
  4. قم بنقل 2 إلى المكدس في الإدخال 2 تحسبًا للقاعدة 3.
  5. قم بتقليص عنصر المكدس 2 إلى تعبير عند الإدخال * استنادًا إلى القاعدة 3. يتوقع البحث المسبق * فقط E قبله.
  6. الآن أصبح لدى المكدس E + E وما زال المدخل هو *. لديه الآن خياران، إما التحويل بناءً على القاعدة 2 أو التخفيض بناءً على القاعدة 1. نظرًا لأن * له أولوية أعلى من + بناءً على القاعدة 4، فإننا نحول * إلى المكدس تحسبًا للقاعدة 2.
  7. قم بنقل 3 إلى المكدس في الإدخال 3 تحسبًا للقاعدة 3.
  8. قم بتقليل عنصر المكدس رقم 3 إلى تعبير بعد رؤية نهاية الإدخال استنادًا إلى القاعدة 3.
  9. قم بتقليل عناصر المكدس E * E إلى E بناءً على القاعدة 2.
  10. قم بتقليل عناصر المكدس E + E إلى E استنادًا إلى القاعدة 1.

شجرة التحليل الناتجة صحيحة وأكثر كفاءة ببساطة [ توضيح ] [ بحاجة لمصدر ] من المحللات غير الاستباقية. هذه هي الاستراتيجية المتبعة في محللات LALR .

قائمة خوارزميات التحليل

انظر أيضا

مراجع

  1. ^ ab "Parse". dictionary.reference.com . تم الاسترجاع في 27 نوفمبر 2010 .
  2. ^ ماسارو توميتا (6 ديسمبر 2012). تحليل LR المعمم. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ^ "القواعد والتكوين". مؤرشف من الأصل في 2016-12-01 . استرجاع 2012-11-24 .
  4. ^ كريستوفر د. مانينغ. كريستوفر د. مانينغ؛ هينريش شوتز (1999). أسس معالجة اللغات الطبيعية الإحصائية. مطبعة معهد ماساتشوستس للتكنولوجيا. رقم ISBN 978-0-262-13360-9.
  5. ^ Jurafsky, Daniel (1996). "نموذج احتمالي للوصول إلى المفردات والنحو وتوضيح الغموض". Cognitive Science . 20 (2): 137–194. CiteSeerX 10.1.1.150.5711 . doi :10.1207/s15516709cog2002_1. 
  6. ^ كلاين، دان، وكريستوفر د. مانينج. "التحليل الدقيق غير المعجمي". وقائع الاجتماع السنوي الحادي والأربعين لجمعية اللغويات الحاسوبية - المجلد 1. جمعية اللغويات الحاسوبية، 2003.
  7. ^ تشارنياك، يوجين. "محلل مستوحى من الحد الأقصى للإنتروبيا محفوظ في 2019-04-01 على موقع واي باك مشين ." وقائع المؤتمر الأول لأمريكا الشمالية لجمعية اللغويات الحاسوبية. جمعية اللغويات الحاسوبية، 2000.
  8. ^ تشن، دانكي، وكريستوفر مانينج. "محلل تبعيات سريع ودقيق باستخدام الشبكات العصبية". وقائع مؤتمر 2014 حول الأساليب التجريبية في معالجة اللغة الطبيعية (EMNLP). 2014.
  9. ^ جيا، روبن؛ ليانغ، بيرسي (2016-06-11). "إعادة تجميع البيانات للتحليل الدلالي العصبي". arXiv : 1606.03622 [cs.CL].
  10. ^ ساندرا إتش فوس، توماس سي جونتر، هربرت شريفرز وأنجيلا دي فريديريس (2001) التحليل النحوي والذاكرة العاملة: تأثيرات التعقيد النحوي، ومدى القراءة، والحمل المتزامن، اللغة والعمليات المعرفية، 16:1، 65-103، DOI: 10.1080/01690960042000085
  11. ^ ab Pritchett, BL (1988). ظاهرة مسار الحديقة والأساس النحوي لمعالجة اللغة. اللغة، 64(3)، 539-576. https://doi.org/10.2307/414532
  12. ^ توماس جي بيفر (1970). الأساس المعرفي للبنى اللغوية . OCLC  43300456.
  13. ^ كارلسون، ف. (2010). قيود الذاكرة العاملة على التضمين المتعدد للمركز. وقائع الاجتماع السنوي لجمعية العلوم الإدراكية، 32. تم الاسترجاع من https://escholarship.org/uc/item/4j00v1j2
  14. ^ فيريرا، ف.، وكليفتون، س. (1986). استقلال المعالجة النحوية. مجلة الذاكرة واللغة، 25(3)، 348-368. https://doi.org/10.1016/0749-596X(86)90006-9
  15. ^ Atlas, JD (1997). حول وحدات معالجة الجملة: العمومية الدلالية ولغة الفكر. اللغة والتصور، 213-214.
  16. ^ Lopopolo, Alessandro, van den Bosch, Antal, Petersson, Karl-Magnus, and Roel M. Willems; Distinguishing Syntactic Operations in the Brain: Dependency and Phrase-Structure Parsing. Neurobiology of Language 2021; 2 (1): 152–175. doi: https://doi.org/10.1162/nol_a_00029
  17. ^ بيرانت، جوناثان، وبرسي ليانج. "التحليل الدلالي من خلال إعادة الصياغة". وقائع الاجتماع السنوي الثاني والخمسين لجمعية اللغويات الحاسوبية (المجلد 1: أوراق بحثية طويلة). 2014.
  18. ^ ab Aho, AV, Sethi, R. and Ullman, JD (1986) "المترجمون: المبادئ والتقنيات والأدوات". Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
  19. ^ سيكل، كلااس، 1954- (1997). مخططات التحليل: إطار عمل لتحديد وتحليل خوارزميات التحليل . برلين: سبرينغر. ISBN 9783642605413. OCLC  606012644.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
  20. ^ Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars Archived 2018-08-22 at the Wayback Machine ." ورشة العمل الدولية العاشرة حول تقنيات التحليل (IWPT)، ACL-SIGPARSE ، الصفحات: 109 - 120، يونيو 2007، براغ.
  21. ^ Frost, R., Hafiz, R. and Callaghan, P. (2008) "Parser Combinators for Ambiguous Left-Recursive Grammars." الندوة الدولية العاشرة حول الجوانب العملية للغات التصريحية (PADL)، ACM-SIGPLAN ، المجلد 4902/2008، الصفحات: 167 - 181، يناير 2008، سان فرانسيسكو.
  22. ^ Rekers, Jan, and Andy Schürr. "تعريف وتحليل اللغات المرئية باستخدام قواعد الرسم البياني الطبقية". مجلة اللغات المرئية والحوسبة 8.1 (1997): 27-55.
  23. ^ Rekers, Jan, and A. Schurr. "A graph gram grammar approach to graphical parsing." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.
  24. ^ Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "صيغة قواعد الرسم البياني الحساسة للسياق لتحديد اللغات المرئية". مجلة الكمبيوتر 44.3 (2001): 186-200.
  25. ^ جيل فاين ليمان (6 ديسمبر 2012). التحليل التكيفي: واجهات اللغة الطبيعية ذاتية التوسع. سبرينغر ساينس آند بيزنس ميديا. رقم ISBN 978-1-4615-3622-2.
  26. ^ باتريك بلاكبيرن وكريستينا ستريجنيتز. "تقنيات معالجة اللغة الطبيعية في برولوج".
  27. ^ سونغ تشون تشو. "خوارزميات التحليل الكلاسيكية".
  28. ^ مأخوذ من Brian W. Kernighan وDennis M. Ritchie (أبريل 1988). لغة البرمجة C. سلسلة برامج برنتيس هول (الطبعة الثانية). Englewood Cliffs/NJ: برنتيس هول. ISBN 0131103628.(الملحق أ.13 "القواعد النحوية"، ص 193 وما يليها)

قراءة إضافية

  • تشابمان، نايجل ب.، تحليل LR: النظرية والتطبيق، مطبعة جامعة كامبريدج ، 1987. ISBN 0-521-30413-X 
  • Grune, Dick; Jacobs, Ceriel JH, Parsing Techniques – A Practical Guide, Vrije Universiteit Amsterdam , Amsterdam, the Netherlands. تم النشر في الأصل بواسطة Ellis Horwood, Chichester, England, 1990؛ ISBN 0-13-651431-6 
ابحث عن كلمة parse  أو parsing في ويكاموس، القاموس الحر.
  • مولد محلل LALR Lemon
  • محلل ستانفورد محلل ستانفورد
  • محلل جامعة تورينو محلل اللغة الطبيعية للغة الإيطالية، مفتوح المصدر، تم تطويره في Common Lisp بواسطة ليوناردو ليسمو، جامعة تورينو، إيطاليا.
  • تاريخ مختصر لبناء المحلل
Retrieved from "https://en.wikipedia.org/w/index.php?title=Parsing&oldid=1254644827"
Original text
Rate this translation
Your feedback will be used to help improve Google Translate