محلل GLR

محلل GLR ( محلل الاشتقاق الأيمن المعمم من اليسار إلى اليمين ) هو امتداد لخوارزمية محلل LR لمعالجة القواعد النحوية غير الحتمية والغامضة . ^{[ 1 ]} وُضعت الأسس النظرية في ورقة بحثية عام 1974 ^{[ 2 ]} لبرنارد لانغ (إلى جانب محللات نحوية عامة أخرى خالية من السياق مثل GLL ). تصف هذه الورقة طريقة منهجية لإنتاج مثل هذه الخوارزميات، وتقدم نتائج موحدة فيما يتعلق بإثباتات الصحة، والتعقيد بالنسبة لفئات القواعد النحوية، وتقنيات التحسين. وُصف أول تطبيق فعلي لمحلل GLR في ورقة بحثية عام 1984 لماسارو توميتا ، ويُشار إليه أيضًا باسم "المحلل المتوازي". قدم توميتا خمس مراحل في عمله الأصلي، ^{[ 3 ]} مع أن المرحلة الثانية هي التي تُعرف عمليًا باسم محلل GLR.

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

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

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

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

يتمتع التعرف باستخدام خوارزمية GLR بنفس التعقيد الزمني في أسوأ الحالات ^{لخوارزميتي} CYK و Earley : O ( n³ ). ومع ذلك، تتميز خوارزمية GLR بميزتين إضافيتين:

• إن الوقت اللازم لتشغيل الخوارزمية يتناسب مع درجة عدم الحتمية في القواعد النحوية: في القواعد النحوية الحتمية، تعمل خوارزمية GLR في وقت O ( n ) (هذا لا ينطبق على خوارزميات Earley و CYK، ولكن يمكن تعديل خوارزميات Earley الأصلية لضمان ذلك).
• خوارزمية GLR هي " متصلة بالإنترنت " - أي أنها تستهلك رموز الإدخال بترتيب معين وتؤدي أكبر قدر ممكن من العمل بعد استهلاك كل رمز (ينطبق هذا أيضًا على Earley).

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

يمكن دمج GLR مع خوارزمية LALR (1) في محلل نحوي هجين، مما يسمح بأداء أعلى. ^{[ 5 ]}

• مقارنة مولدات المحلل اللغوي
• مجموعة أدوات إعادة هندسة برمجيات إدارة المستندات
• GNU Bison ، مولد محللات نحوية يمكنه إنشاء محللات نحوية من نوعي LALR و GLR
• محلل Packrat ، ​​وهو محلل آخر يمكنه تحليل اللغات الغامضة وغير الحتمية

• غرون، ديك؛ جاكوبس، سيريل جيه إتش (2008). تقنيات التحليل النحوي . سبرينغر ساينس + بيزنس ميديا. ISBN 978-0-387-20248-8.
• توميتا، ماسارو (1984). "محللات LR للغات الطبيعية". المؤتمر الدولي العاشر للغويات الحاسوبية (COLING ). الصفحات 354-357 . 
• توميتا، ماسارو (1985). " خوارزمية تحليل نحوي فعالة للغات الطبيعية دون سياق". المؤتمر الدولي المشترك حول الذكاء الاصطناعي. الصفحات 756-764 .