محلل الإزاحة والاختزال

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

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

لنفترض السلسلة A = B + C * 2.

في الخطوة 7 من المثال، تم تحليل العبارة "A = B +" فقط. يوجد فقط الجزء المظلل في الزاوية السفلية اليسرى من شجرة التحليل. لا توجد أي من عقد شجرة التحليل المرقمة 8 وما فوق. العقد 1 و2 و6 و7 هي جذور أشجار فرعية معزولة تغطي جميع العناصر من 1 إلى 7. العقدة 1 هي المتغير A، والعقدة 2 هي الفاصل = ، والعقدة 6 هي المجموع B، والعقدة 7 هي عامل الجمع +. يتم الاحتفاظ بهذه العقد الجذرية الأربع مؤقتًا في مكدس التحليل. الجزء المتبقي غير المُحلل من دفق الإدخال هو "C * 2".

يعمل محلل الإزاحة والاختزال من خلال القيام ببعض مزيج من خطوات الإزاحة وخطوات الاختزال، ومن هنا جاء الاسم.

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

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

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

مثال على قواعد اللغة كجزء صغير من لغة جافا أو سي القادرة على المطابقة A = B + C*2قد يكون كالتالي:

تعيين ← المعرف = المجموع

المجاميع ← المجاميع + النواتج

المجاميع ← المنتجات

المنتجات ← المنتجات * القيمة

المنتجات ← القيمة

القيمة ← عدد صحيح

القيمة ← المعرف

الرموز الطرفية للقواعد النحوية هي رموز متعددة الأحرف أو "رموز مميزة" يعثر عليها الماسح المعجمي في دفق الإدخال . تشمل هذه الرموز = + * و int لأي ثابت عددي صحيح، و id لأي اسم مُعرِّف. لا تُعير القواعد النحوية اهتمامًا لقيم int أو تهجئة id ، كما لا تُعير اهتمامًا للفراغات أو فواصل الأسطر. تستخدم القواعد النحوية هذه الرموز الطرفية دون تعريفها، وهي موجودة دائمًا في الطرف السفلي المتفرع لشجرة التحليل.

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

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

يحتوي المحلل اللغوي المعتمد على الجداول على جميع معلوماته حول القواعد النحوية مُشفّرة في بيانات ثابتة تُسمى جداول المحلل. يتكون كود برنامج المحلل من حلقة عامة بسيطة تُطبّق دون تغيير على العديد من القواعد النحوية واللغات. يمكن إنشاء الجداول يدويًا لطرق الأسبقية. أما بالنسبة لطرق الانحدار التكراري، فتُشتق الجداول المعقدة آليًا من القواعد النحوية بواسطة أداة توليد محلل مثل Bison . ^{[ 3 ]} عادةً ما تكون جداول المحلل أكبر بكثير من القواعد النحوية. في المحللات الأخرى غير المعتمدة على الجداول، مثل الانحدار التكراري ، يُحلل كل بناء لغوي بواسطة روتين فرعي مختلف، مُخصص لبنية ذلك البناء.

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

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

ينتظر محلل الإزاحة والاختزال حتى يُجري مسحًا وتحليلًا لجميع أجزاء بنية معينة قبل تحديد ماهية البنية المُدمجة. ثم يتصرف المحلل فورًا على هذه البنية المُدمجة دون مزيد من الانتظار. في مثال شجرة التحليل أعلاه، تُختزل العبارة B إلى Value، ثم إلى Products وSums في الخطوات من 3 إلى 6 بمجرد ظهور علامة الجمع (+) في التوقع المسبق، بدلًا من الانتظار لتنظيم هذه الأجزاء من شجرة التحليل. وتستند قرارات كيفية التعامل مع B فقط إلى ما رآه المحلل والماسح الضوئي بالفعل، دون النظر إلى العناصر التي تظهر لاحقًا على اليمين.

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

عندما تكون قاعدة نحوية مثل

المنتجات ← المنتجات * القيمة

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

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

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

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

• محلل أسبقية المعاملات ، وهو أسلوب عددي بسيط للغاية يعمل مع التعبيرات ولكنه لا يعمل مع بناء الجملة العام للبرنامج.
• محلل أسبقية بسيط ، يستخدم جدولًا واحدًا كبيرًا بحجم MxN للعثور على النهايات اليمنى واليسرى. يُستخدم في PL360 . ^{[ 5 ]} لا يدعم لغات البرمجة الشائعة.
• محلل أسبقية ضعيف، يستخدم جدول الأسبقية فقط للعثور على النهايات اليمنى للمقابض. يتعامل مع قواعد نحوية أكثر من الأسبقية البسيطة. ^{[ 6 ]}
• محلل الأسبقية الموسع.

• محلل أسبقية الاستراتيجية المختلطة، المستخدم في الإصدار الأصلي من لغة XPL . يوسع هذا المحلل مفهوم "الثنائيات"، المتأصل في أي محلل أسبقية، ليشمل "الثلاثيات". وهو أقل قوة من محلل الأسبقية أحادي الاستراتيجية (SLR). يحتوي عمومًا على جداول بيانات ضخمة جدًا حتى بالنسبة للغات صغيرة نسبيًا مثل XPL نفسها، وذلك بسبب العدد الكبير من "الثلاثيات" المطلوبة للتعرف على القواعد النحوية خارج الحدود التي تفرضها طرق الأسبقية. ^{[ 7 ]}

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

تُعد محللات LR شكلاً أكثر مرونة من تحليل الإزاحة والاختزال، حيث تتعامل مع عدد أكبر بكثير من القواعد النحوية. ^{[ 8 ]}

تعمل محللات LR كآلة حالة ، حيث تُجري انتقالًا بين الحالات لكل عملية إزاحة أو اختزال. وتستخدم هذه المحللات مكدسًا تُدفع فيه الحالة الحالية (إلى الأسفل) بواسطة عمليات الإزاحة. ثم يُسحب هذا المكدس (إلى الأعلى) بواسطة عمليات الاختزال (التي تُراكم في الوقت نفسه حالة جديدة). تُمكّن هذه الآلية محلل LR من التعامل مع جميع القواعد النحوية الحتمية الخالية من السياق، وهي مجموعة فرعية من قواعد الأسبقية. يُنفذ محلل LR بشكل كامل بواسطة محلل LR الكلاسيكي . أما محللا Look-Ahead LR و Simple LR فيُنفذان نسخًا مُبسطة منه ذات متطلبات ذاكرة مُخفضة بشكل كبير. ^{[ 9 ] [ 10 ]} وقد حددت الأبحاث الحديثة طرقًا يُمكن من خلالها تنفيذ محللات LR الكلاسيكية بمتطلبات جداول مُخفضة بشكل كبير مقارنةً بخوارزمية بناء الجداول الخاصة بـ Knuth. ^{[ 11 ]}

سواءً كان التحليل LR أو LALR أو SLR، فإن آلة الحالة الأساسية واحدة؛ الاختلاف يكمن فقط في الجداول، والتي تُولّد آليًا في أغلب الأحيان. إضافةً إلى ذلك، تُنفّذ هذه الجداول عادةً بحيث ينتج عن عملية REDUCE استدعاءٌ لروتين فرعي مغلق خارجي لآلة الحالة، يؤدي وظيفةً تُستنتج من دلالات قاعدة النحو التي يتم اختزالها. لذا، يُقسّم المحلل إلى جزءٍ ثابت لآلة الحالة، وجزءٍ متغير للدلالات. هذا التمييز الجوهري يُشجع على تطوير محللات عالية الجودة تتميز بموثوقية استثنائية.

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

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

00 b يمثل خطأ

01 b يمثل SHIFT

يمثل الرقم 10 ب رمز التخفيض

11 ب تعني التوقف

(يُعتبر STOP حالة خاصة من SHIFT). تتضمن المصفوفة بأكملها بشكل عام معظم تكوينات ERROR، وعددًا محددًا من تكوينات SHIFT وREDUCE وفقًا للقواعد، وتكوين STOP واحد.

في أنظمة البرمجة التي تدعم تحديد القيم في نظام الأرقام الرباعي (الأساس 4، بتان لكل رقم رباعي)، مثل XPL، يتم ترميزها على سبيل المثال:

"(2)… 0 …" يمثل خطأ

"(2)… 1 …" يمثل SHIFT

"(2)… 2 …" يمثل REDUCE

"(2)… 3 …" تعني التوقف

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

تُعدّ تكوينات SHIFT و REDUCE واضحة، من التعريف الأساسي لمحلل SHIFT-REDUCE.

إذن، يمثل STOP تكوينًا تكون فيه الحالة الموجودة في أعلى المكدس ورمز طرفية التطلع ضمن قواعد الموضوع، ويمثل نهاية البرنامج:

⊥ <البرنامج> • ⊥

من المستحيل الانتقال إلى ما بعد علامة ⊥ الأخيرة للوصول، من الناحية المفاهيمية

⊥ <البرنامج> ⊥ •

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

⊥ <البرنامج> • ⊥

حيث يتكون <البرنامج> فقط من "عبارة فارغة" ).

في معظم الحالات، يتم تحميل المكدس مسبقًا عن قصد، أي تهيئته، بـ

⊥ • <البرنامج> ⊥

حيث يُفترض أن الرمز ⊥ الأولي قد تم التعرف عليه بالفعل. وهذا يمثل بداية البرنامج، وبالتالي، يتجنب وجود إعداد بدء منفصل، وهو مفهوميًا

• ⊥ <البرنامج> ⊥

⊥ هو رمز طرفي زائف خاص يُضاف آليًا إلى القواعد النحوية، تمامًا كما أن <program> هو رمز غير طرفي زائف خاص يُضاف آليًا إلى القواعد النحوية (إذا لم يقم المبرمج بتضمين <program> صراحةً في القواعد النحوية، فسيتم إضافة <program> تلقائيًا إلى القواعد النحوية نيابةً عن المبرمج).

من الواضح أن مثل هذا المحلل اللغوي لديه تكوين بدء واحد (ضمني) وتكوين إيقاف واحد (صريح)، ولكنه يمكن أن يحتوي، وعادة ما يحتوي، على مئات من تكوينات SHIFT و REDUCE، وربما آلاف من تكوينات ERROR.