تفسير كلمة

(تم التحويل من Parsing)

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

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

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

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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


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

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

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

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

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

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

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

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

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

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

تحليل الخطاب

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

لغات الحاسب

المفسر

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

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

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

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

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

على سبيل المثال، في پايثون ما يلي هو رمز صالح من الناحية التركيبية:

x = 1
print(x)

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

x = 1
print(y)

بدلاً من أن يتم تحليلها في مرحلة التحليل، يتم اكتشاف ذلك عن طريق التحقق من القيم في شجرة التركيب، وبالتالي كجزء من التحليل الدلالي: غالباً ما يتم تحليل البنية الحساسة للسياق في الممارسة العملية بسهولة على أنها دلالات.

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

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

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

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

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

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


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

أنواع المفسرات

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

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

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

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

وقد تم تصميم بعض خوارزميات تفسير الرسم البياني لـ لغات البرمجة المرئية.[15][16] تعتمد مفسرات اللغات المرئية أحياناً على قواعد الرسم البياني.[17]

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

برامج تطوير المفسرات

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

Lookahead

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

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

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

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

يتميز Lookahead بميزتين.[مطلوب توضيح]

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

Example: تفسير التعبير 1 + 2 * 3 [محل شك]

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

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

إجراءات المفسر non-lookahead البسيطة

الإدخال الأولي = [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]

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

للتحليل بشكل صحيح دون lookahead، هناك ثلاثة حلول:

  • يجب على المستخدم إحاطة التعبيرات بين أقواس. هذا في كثير من الأحيان ليس حلاً قابلاً للتطبيق.
  • يحتاج المحلل اللغوي إلى مزيد من المنطق للتراجع وإعادة المحاولة كلما تم انتهاك قاعدة أو عدم اكتمالها. يتم اتباع نفس الطريقة في محللات LL.
  • بدلاً من ذلك، يحتاج المحلل اللغوي أو النحوي إلى منطق إضافي لتأخير الاختزال والتقليل فقط عندما يكون متأكداً تماماً من القاعدة التي يجب تقليلها أولاً. تُستخدم هذه الطريقة في محللات LR. هذا ما يوزع التعبير بشكل صحيح ولكن مع العديد من الحالات وزيادة عمق المكدس.
إجراءات مفسر Lookahead[مطلوب توضيح]
  1. إزاحة 1 على المكدس عند الإدخال 1 تحسباً للقاعدة 3. ولا يتم تقليله على الفور.
  2. تقليل عنصر المكدس 1 إلى تعبير بسيط عند الإدخال + استناداً إلى القاعدة 3. إن lookahead هو +، لذلك نحن في طريقنا إلى E +، لذلك يمكننا تقليل المكدس إلى E.
  3. إزاحة + على المكدس عند الإدخال + تحسباً للقاعدة 1.
  4. إزاحة 2 على المكدس عند الإدخال 2 تحسبًا للقاعدة 3.
  5. تقليل عنصر المكدس 2 إلى التعبير عند الإدخال * بناءً على القاعدة 3. يتوقع lookahead * فقط 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.

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

انظر أيضاً

المراجع

  1. ^ أ ب "Parse". dictionary.reference.com. Retrieved 27 November 2010.
  2. ^ Masaru Tomita (6 December 2012). Generalized LR Parsing. Springer Science & Business Media. ISBN 978-1-4615-4034-2.
  3. ^ "Grammar and Composition".
  4. ^ Christopher D.. Manning; Christopher D. Manning; Hinrich Schütze (1999). Foundations of Statistical Natural Language Processing. MIT Press. ISBN 978-0-262-13360-9.
  5. ^ Jurafsky, Daniel (1996). "A Probabilistic Model of Lexical and Syntactic Access and Disambiguation". Cognitive Science. 20 (2): 137–194. CiteSeerX 10.1.1.150.5711. doi:10.1207/s15516709cog2002_1.
  6. ^ Klein, Dan, and Christopher D. Manning. "Accurate unlexicalized parsing." Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1. Association for Computational Linguistics, 2003.
  7. ^ Charniak, Eugene. "A maximum-entropy-inspired parser." Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference. Association for Computational Linguistics, 2000.
  8. ^ Chen, Danqi, and Christopher Manning. "A fast and accurate dependency parser using neural networks." Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). 2014.
  9. ^ قالب:Cite arxiv
  10. ^ Berant, Jonathan, and Percy Liang. "Semantic parsing via paraphrasing." Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2014.
  11. ^ أ ب Aho, A.V., Sethi, R. and Ullman, J.D. (1986) " Compilers: principles, techniques, and tools." Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
  12. ^ Sikkel, Klaas, 1954- (1997). Parsing schemata : a framework for specification and analysis of parsing algorithms. Berlin: Springer. ISBN 9783642605413. OCLC 606012644.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
  13. ^ Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.
  14. ^ Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167 - 181, January 2008, San Francisco.
  15. ^ Rekers, Jan, and Andy Schürr. "Defining and parsing visual languages with layered graph grammars." Journal of Visual Languages & Computing 8.1 (1997): 27-55.
  16. ^ Rekers, Jan, and A. Schurr. "A graph grammar approach to graphical parsing." Visual Languages, Proceedings., 11th IEEE International Symposium on. IEEE, 1995.
  17. ^ Zhang, Da-Qian, Kang Zhang, and Jiannong Cao. "A context-sensitive graph grammar formalism for the specification of visual languages." The Computer Journal 44.3 (2001): 186-200.
  18. ^ Jill Fain Lehman (6 December 2012). Adaptive Parsing: Self-Extending Natural Language Interfaces. Springer Science & Business Media. ISBN 978-1-4615-3622-2.
  19. ^ taken from Brian W. Kernighan and Dennis M. Ritchie (Apr 1988). The C Programming Language. Prentice Hall Software Series (2nd ed.). Englewood Cliffs/NJ: Prentice Hall. ISBN 0131103628. (Appendix A.13 "Grammar", p.193 ff)

للاستزادة


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

وصلات خارجية

شعار قاموس المعرفة.png

قالب:Parsers قالب:Strings

الكلمات الدالة: