مُجمِّع المُحلِّل

في برمجة الحاسوب ، يُعدّ مُركِّب المُحلِّلات دالةً من الرتبة العليا تقبل عدة مُحلِّلات كمدخلات وتُعيد مُحلِّلاً جديداً كمخرج. في هذا السياق، المُحلِّل هو دالة تقبل سلاسل نصية كمدخلات وتُعيد بنيةً ما كمخرجات، عادةً ما تكون شجرة تحليل أو مجموعة من المؤشرات التي تُمثِّل مواقع في السلسلة النصية حيث توقف التحليل بنجاح. تُتيح مُركِّبات المُحلِّلات استراتيجية تحليل تنازلي متكرر تُسهِّل البناء والاختبار المعياريين المُجزَّأين. تُسمى تقنية التحليل هذه بالتحليل التوافقي .

استُخدمت المحللات اللغوية التي تستخدم المُركِّبات على نطاق واسع في تصميم نماذج أولية للمترجمات والمعالجات للغات خاصة بمجالات محددة ، مثل واجهات المستخدم للغة الطبيعية لقواعد البيانات، حيث تتكامل العمليات الدلالية المعقدة والمتنوعة بشكل وثيق مع المعالجة النحوية. في عام 1989، أوضح ريتشارد فروست وجون لانشبري ^{[ 1 ]} استخدام مُركِّبات المحلل اللغوي لبناء مترجمات للغة الطبيعية . استخدم غراهام هاتون أيضًا وظائف من الرتبة العليا للتحليل الأساسي في عام 1992 ^{[ 2 ]} والتحليل الأحادي في عام 1996. ^{[ 3 ]} كما عرض إس دي سويرسترا الجوانب العملية لمركبات المحلل في عام 2001. ^{[ 4 ]} في عام 2008، وصف فروست وحافظ وكالاغان ^{[ 5 ]} مجموعة من مركبات المحلل في لغة البرمجة الوظيفية هاسكل التي تحل المشكلة القديمة المتمثلة في استيعاب الاستدعاء الذاتي الأيسر ، وتعمل كأداة تحليل كاملة من أعلى إلى أسفل في وقت ومساحة متعددة الحدود .

في أي لغة برمجة تدعم الدوال من الدرجة الأولى ، يمكن استخدام مُركِّبات المُحلِّلات لدمج المُحلِّلات الأساسية وبناء مُحلِّلات لقواعد أكثر تعقيدًا. على سبيل المثال، قد تحتوي قاعدة إنتاج في قواعد اللغة الخالية من السياق (CFG) على بديل واحد أو أكثر، وقد يتكون كل بديل من سلسلة من الرموز غير الطرفية و/أو الرموز الطرفية، أو قد يتكون من رمز غير طرفي واحد أو رمز طرفي واحد أو سلسلة فارغة. إذا كان هناك مُحلِّل بسيط مُتاح لكل بديل من هذه البدائل، فيمكن استخدام مُركِّب المُحلِّلات لدمج كل هذه المُحلِّلات، مما يُنتج مُحلِّلًا جديدًا قادرًا على التعرّف على أيٍّ من البدائل أو جميعها.

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

لتبسيط النقاش، سنناقش مُركِّبات المُحلِّل اللغوي من منظور المُعرِّفات فقط. إذا كان طول سلسلة الإدخال n #input، ويتم الوصول إلى عناصرها عبر فهرس n j، فإن المُعرِّف هو مُحلِّل لغوي يُعيد، كناتج، مجموعة من الفهارس تُمثِّل الفهارس التي نجح المُحلِّل اللغوي عندها في التعرُّف على سلسلة من الرموز تبدأ بالفهرس n j. تشير مجموعة النتائج الفارغة إلى أن المُعرِّف لم يتعرّف على أي سلسلة تبدأ بالفهرس n j.

• يتعرف المُحلل emptyعلى السلسلة الفارغة. ينجح هذا المُحلل دائمًا، ويعيد مجموعة أحادية تحتوي على فهرس الإدخال:

${\displaystyle فارغة(ي)=\{ي\}}$

• يتعرف المُحلل على الرمز الطرفي . إذا كان الرمز الموجود في الفهرس في سلسلة الإدخال هو ، فإن هذا المُحلل يُرجع مجموعة أحادية تحتوي على ؛ وإلا فإنه يُرجع المجموعة الفارغة.term xxjxj + 1

${\displaystyle term(x,j)={\begin{cases}\left\{\right\},&j\geq \#input\\\left\{j+1\right\},&j^{th}{\mbox{ عنصر من }}input=x\\\left\{\right\},&{\mbox{otherwise}}\end{cases}}}$

بفرض وجود اثنين من أدوات التعرف p، qيمكننا تحديد اثنين من مُركِّبات التحليل الرئيسية، أحدهما لمطابقة القواعد البديلة والآخر لتسلسل القواعد:

• يقوم مُجمِّع المُحلِّل "البديل"، ⊕، بتطبيق كل من المُعرِّفات على نفس الفهرس jويعيد اتحاد الفهارس النهائية للمُعرِّفات:

${\displaystyle (p\oplus q)(j)=p(j)\cup q(j)}$

• يقوم مُجمِّع "التسلسل"، ⊛، بتطبيق المُعرِّف الأول pعلى فهرس الإدخال j، ولكل فهرس نهائي، يُطبِّق المُعرِّف الثاني qمع اعتباره فهرس بداية. ويُعيد اتحاد الفهارس النهائية المُعادة من جميع استدعاءات q:

${\displaystyle (p\circledast q)(j)=\bigcup \{q(k):k\in p(j)\}}$

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

لنفترض وجود قواعد نحوية خالية من السياق شديدة الغموض . باستخدام المُركِّبات المُعرَّفة سابقًا، يُمكننا تعريف تدوينات قابلة للتنفيذ لهذه القواعد النحوية في لغة برمجة وظيفية حديثة (مثل هاسكل ) على النحو التالي: . عند تطبيق المُعرِّف عند فهرس من سلسلة الإدخال، فإنه يُعيد مجموعة نتائج ، مما يُشير إلى وجود تطابقات تبدأ من الفهرس 2 وتنتهي عند أي فهرس بين 2 و5 شاملًا.s ::= ‘x’ s s | εs = term ‘x’ <*> s <*> s <+> emptys2x x x x x{2,3,4,5}

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

تُعاني التطبيقات البسيطة لمُركِّبات المُحلِّل النحوي من بعض أوجه القصور الشائعة في التحليل النحوي من أعلى إلى أسفل. يتطلب التحليل النحوي التوافقي البسيط وقتًا ومساحةً أُسِّيين عند تحليل قواعد نحوية غامضة خالية من السياق. في عام ١٩٩٦، أوضح فروست وشيدلوفسكي كيفية استخدام التخزين المؤقت مع مُركِّبات المُحلِّل النحوي لتقليل التعقيد الزمني إلى كثير الحدود. ^{[ ٦ ]} لاحقًا، استخدم فروست المونادات لبناء المُركِّبات من أجل ربط جدول التخزين المؤقت بشكل منهجي وصحيح طوال عملية الحساب. ^{[ ٧ ]}

كما هو الحال في أي تحليل نحوي تنازلي متكرر ، فإن مُركِّبات المُحلِّل النحوي التقليدية (مثل المُركِّبات المذكورة أعلاه) لن تتوقف أثناء معالجة قواعد نحوية تكرارية يسارية (على سبيل المثال ). وقد وصف فروست وحافظ في عام 2006 خوارزمية تعرّف تُراعي القواعد النحوية الغامضة ذات القواعد التكرارية اليسارية المباشرة. ^{[ 8 ]} تعمل هذه الخوارزمية على تقليص حجم التحليل التكراري اليساري المتزايد باستمرار من خلال فرض قيود على العمق. وفي عام 2007، قام فروست وحافظ وكالاغان بتوسيع هذه الخوارزمية لتصبح خوارزمية تحليل نحوي كاملة تُراعي التكرار اليساري المباشر وغير المباشر في وقت متعدد الحدود ، وتُنتج تمثيلات مُدمجة بحجم متعدد الحدود لعدد أشجار التحليل النحوي الذي قد يكون أُسّيًا للقواعد النحوية شديدة الغموض. ^{[ 9 ]} تُراعي هذه الخوارزمية المُوسَّعة التكرار اليساري غير المباشر من خلال مُقارنة "السياق المحسوب" مع "السياق الحالي". كما وصف المؤلفون أنفسهم تطبيقهم لمجموعة من مُركِّبات المُحلِّل اللغوي المكتوبة بلغة هاسكل والمستندة إلى الخوارزمية نفسها. ^{[ 5 ] [ 10 ]}s ::= s <*> term ‘x’|empty