محلل Packrat

محلل Packrat هو نوع من المحللات اللغوية التي تتشابه مع محلل الانحدار التكراري في بنيتها. ومع ذلك، فهو يختلف عنها في أنه يأخذ قواعد التعبير التحليلي (PEGs) كمدخلات بدلاً من قواعد LL . ^{[ 1 ]}

في عام ١٩٧٠، وضع ألكسندر بيرمان الأساس لتحليل لغة باكرات من خلال تقديم "مخطط التعرف على لغة TMG" (TS) و"مخطط التعرف على لغة TMG المعمم" (gTS). استند مخطط التعرف على لغة TMG إلى مُجمِّع-مُجمِّع لغة TMG الخاص بروبرت إم. ماكلور، بينما استند مخطط التعرف على لغة TMG المعمم إلى مُجمِّع-مُجمِّع لغة META الخاص بديوي فال شور . لاحقًا، قام أهو وأولمان بتطوير عمل بيرمان، وأُعيدت تسميته إلى لغة التحليل من أعلى إلى أسفل (TDPL) ولغة التحليل من أعلى إلى أسفل المعممة (GTDPL) على التوالي. كانت هذه الخوارزميات الأولى من نوعها التي تستخدم التحليل الحتمي من أعلى إلى أسفل مع التراجع. ^{[ ٢ ] [ ٣ ]}

طوّر برايان فورد قواعد PEG كتوسيع لقواعد GTDPL وTS. على عكس قواعد CFG ، تتميز قواعد PEG بوضوحها التام وتوافقها الجيد مع اللغات الموجهة للآلة. كما تستطيع قواعد PEG، على غرار GTDPL وTS، التعبير عن جميع قواعد LL(k) و LR(k) . وقدّم فورد أيضًا Packrat كمحلل نحوي يستخدم تقنيات التخزين المؤقت فوق محلل PEG بسيط. وقد تم ذلك لأن قواعد PEG تتمتع بقدرة استشرافية غير محدودة ، مما ينتج عنه محلل نحوي ذو أداء زمني أُسّي في أسوأ الحالات. ^{[ 2 ] [ 3 ]}

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

يأخذ محلل packrat نفس بنية PEGs كمدخلات: يتكون PEG بسيط من رموز طرفية وغير طرفية، وربما متداخلة مع عوامل تشكل قاعدة اشتقاق واحدة أو أكثر. ^{[ 2 ]}

المشغلون

قواعد بناء الجملة

المشغل	علم الدلالة
تسلسل ${\displaystyle \alpha \beta }$	النجاح: إذا${\displaystyle \alpha }$و${\displaystyle \beta }$معترف بها الفشل: إذا${\displaystyle \alpha }$أو${\displaystyle \beta }$غير معترف بها تم استهلاكه:${\displaystyle \alpha }$و${\displaystyle \beta }$في حالة النجاح
الاختيار المرتب ${\displaystyle \alpha /\beta /\gamma }$	النجاح: إذا كان أي مما يلي${\displaystyle \{\alpha ,\beta ,\gamma \}}$يتم التعرف عليه بدءًا من اليسار الفشل: كل شيء${\displaystyle \{\alpha ,\beta ,\gamma \}}$لا تتطابق تم استهلاكه: التعبير الذري الذي حقق نجاحًا، لذا في حالة نجاح عدة تعبيرات، يتم دائمًا إرجاع أول تعبير ناجح.
والمسند ${\displaystyle \&\alpha }$	النجاح: إذا${\displaystyle \alpha }$معترف به الفشل: إذا${\displaystyle \alpha }$غير معترف به المستهلك: لم يتم استهلاك أي مدخلات
ليس مسندًا ${\displaystyle$ !\alpha }	النجاح: إذا${\displaystyle \alpha }$غير معترف به الفشل: إذا${\displaystyle \alpha }$معترف به المستهلك: لم يتم استهلاك أي مدخلات
واحد أو أكثر ${\displaystyle \alpha +}$	النجاح: حاول أن تتعرف${\displaystyle \alpha }$مرة واحدة أو عدة مرات الفشل: إذا${\displaystyle \alpha }$غير معترف به المستهلك: الحد الأقصى للعدد الذي${\displaystyle \alpha }$معترف به
صفر أو أكثر ${\displaystyle \alpha *}$	النجاح: حاول أن تتعرف${\displaystyle \alpha }$صفر أو عدة مرات الفشل: لا يمكن أن يفشل المستهلك: الحد الأقصى للعدد الذي${\displaystyle \alpha }$معترف به
صفر أو واحد ${\displaystyle \alpha$ ؟}	النجاح: حاول أن تتعرف${\displaystyle \alpha }$صفر أو واحد الفشل: لا يمكن أن يفشل تم استهلاكه:${\displaystyle \alpha }$إذا تم الاعتراف به
نطاق المحطة الطرفية [${\displaystyle ab}$]	نجاح: التعرف على أي طرفية${\displaystyle c}$التي تقع ضمن النطاق${\displaystyle [ab]}$في حالة${\displaystyle [{\textbf {'}}h{\textbf {'}}-{\textbf {'}}z{\textbf {'}}]}$،${\displaystyle c}$يمكن أن يكون أي حرف من h إلى z فشل: في حالة عدم وجود طرفية داخل${\displaystyle [ab]}$يمكن التعرف عليها تم استهلاكه:${\displaystyle c}$إذا تم الاعتراف به
أي شخصية ${\displaystyle .}$	نجاح: التعرف على أي حرف في المدخلات فشل: إذا لم يكن هناك حرف في المدخلات تم استهلاكه: أي حرف في المدخلات

المُجمِّع التكراري

المُركِّبات التكرارية${\displaystyle \alpha +}$و${\displaystyle \alpha *}$تتطلب هذه المجموعات عناية خاصة عند استخدامها في محلل Packrat: فهي تُدخل استدعاءً تكراريًا سريًا لا يُسجل النتائج الوسيطة في مصفوفة المخرجات، مما قد يؤدي إلى عمل المحلل بسلوك غير خطي. يمكن حل هذه المشكلة بتطبيق التحويل التالي: ^{[ 1 ]}

إبداعي	مترجم
${\displaystyle S\rightarrow \alpha +}$	${\displaystyle S\rightarrow \alpha S/\alpha }$
${\displaystyle S\rightarrow \alpha *}$	${\displaystyle S\rightarrow \alpha S/\epsilon }$

بفضل هذا التحويل، يمكن تخزين النتائج الوسيطة بشكل صحيح.

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

يخزن تحليل Packrat النتائج في مصفوفة أو بنية بيانات مشابهة تسمح بعمليات بحث وإدراج سريعة. عند مصادفة قاعدة إنتاج، يتم فحص المصفوفة لمعرفة ما إذا كانت قد ظهرت من قبل. إذا كانت موجودة، يتم استرجاع النتيجة من المصفوفة. وإذا لم تكن موجودة، يتم تقييم قاعدة الإنتاج، وإدراج النتيجة في المصفوفة، ثم إعادتها. ^{[ 9 ]} عند تقييم كامل${\displaystyle m*n}$في المصفوفة ضمن نهج جدولي، سيتطلب ذلك${\displaystyle \Theta (mn)}$^{[ 9 ]} هنا ،${\displaystyle m}$يمثل عدد الرموز غير الطرفية، و${\displaystyle n}$يمثل حجم سلسلة الإدخال.

في تطبيق بسيط، يمكن استخلاص الجدول بأكمله من سلسلة الإدخال بدءًا من نهاية السلسلة.

يمكن تحسين محلل Packrat لتحديث الخلايا الضرورية فقط في المصفوفة من خلال زيارة عميقة أولاً لكل شجرة تعبير فرعي. وبالتالي، باستخدام مصفوفة بأبعاد${\displaystyle m*n}$غالبًا ما يكون هذا الأسلوب مُهدرًا للذاكرة، إذ ستبقى معظم المدخلات فارغة. ^{[ 5 ]} ترتبط هذه الخلايا بسلسلة الإدخال، وليس بالرموز غير الطرفية للقواعد النحوية. هذا يعني أن زيادة حجم سلسلة الإدخال ستؤدي دائمًا إلى زيادة استهلاك الذاكرة، بينما لا يُغير عدد قواعد التحليل إلا أسوأ تعقيد للمساحة. ^{[ 1 ]}

عامل القطع

أُضيف عامل آخر يُسمى "cut" إلى Packrat لتقليل متوسط ​​تعقيد المساحة بشكل أكبر. يستفيد هذا العامل من البنى الرسمية للعديد من لغات البرمجة لاستبعاد الاشتقاقات غير الممكنة. على سبيل المثال، يكون تحليل عبارات التحكم في لغة برمجة قياسية حصريًا متبادلًا مع أول رمز مميز يتم التعرف عليه، على سبيل المثال،${\displaystyle \{{\mathtt {if,do,while,switch}}\}}$[ ^{10 ]​}

المشغل	علم الدلالة
يقطع ${\displaystyle {\begin{array}{l}\alpha \uparrow \beta /\gamma \\(\alpha \uparrow \beta )*\end{array}}}$	لو${\displaystyle \alpha }$معترف به ولكن${\displaystyle \beta }$إذا لم يكن الأمر كذلك، فتجاوز تقييم البديل. في الحالة الأولى، لا تقم بالتقييم${\displaystyle \gamma }$لو${\displaystyle \alpha }$تم الاعتراف بالقاعدة الثانية، ويمكن إعادة صياغتها على النحو التالي:${\displaystyle N\rightarrow \alpha \uparrow \beta N/\epsilon }$ويمكن تطبيق القواعد نفسها.

عندما يستخدم محلل Packrat عوامل القطع، فإنه يُفرغ فعليًا مكدس التراجع الخاص به. ويعود ذلك إلى أن عامل القطع يُقلل عدد البدائل الممكنة في الاختيار المُرتب. وبإضافة عوامل القطع في المواضع المناسبة في تعريف القواعد النحوية، لا يحتاج محلل Packrat الناتج إلا إلى مساحة ثابتة تقريبًا للتخزين المؤقت. ومع ذلك، لا تزال المشكلة الأساسية المتمثلة في أن محللات Packrat تتطلب مساحة O(n) قائمة. ^{[ 10 ]}

رسم تخطيطي لتنفيذ خوارزمية Packrat بلغة شبه كودية تشبه لغة Lua. ^{[ 5 ]}

إدخال ( ن ) -- إرجاع الحرف الموجود في الموضع نالقاعدة ( R : القاعدة ، P : الموضع )entry = GET_MEMO ( R , P ) -- إرجاع عدد العناصر التي تمت مطابقتها مسبقًا في القاعدة R عند الموضع Pإذا كانت قيمة المدخل تساوي nil ،return EVAL ( R , P );نهايةإرجاع المدخل ؛EVAL ( R : القاعدة , P : الموضع )البداية = P ;for choice in R . choices -- إرجاع قائمة بالخياراتacc = 0 ;for symbol in choice then -- أعد كل عنصر من عناصر القاعدة، طرفي وغير طرفيإذا كان الرمز طرفيًا ،إذا كان INPUT ( start + acc ) == symbol . terminal ثمacc = acc + 1 ; -- تم العثور على الطرفية الصحيحة، تجاوزهاآخراستراحة ؛نهايةآخرres = RULE ( symbol . nonterminal , start + acc ); -- محاولة التعرف على رمز غير طرفي في الموضع start+accSET_MEMO ( symbol . nonterminal , start + acc , res ); -- نقوم أيضًا بتخزين الفشل بالقيمة الخاصة failإذا كانت النتيجة تساوي فشلًا ،استراحة ؛نهايةacc = acc + res ;نهايةإذا كان الرمز يساوي آخر رمز في الاختيار ، فتحقق مما إذا كان قد تم مطابقة الرمز الأخير في الاختيار، وإذا كان الأمر كذلك، فأرجعإرجاع acc ;نهايةنهايةإرجاع فشل ؛ -- إذا لم يكن هناك تطابق في الاختيار، يتم إرجاع فشل

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

${\displaystyle {\begin{cases}S\rightarrow A\\A\rightarrow M\ {\texttt {'+'}}\ A\ /\ M\\M\rightarrow P\ {\texttt {'*'}}\ M\ /\ P\\P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ D\\D\rightarrow ({\texttt {'0'}}-{\texttt {'9'}})\end{cases}}}$

باستخدام الرمز ⊣ كفاصل للخط، يمكننا تطبيق خوارزمية باكرات

اشتقاق2*(3+4)⊣

شجرة بناء الجملة	فعل	طاولة باكرات
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle {\begin{array}{l}S\rightarrow A\\A\rightarrow M\ {\texttt {'+'}}\ A\\M\rightarrow P\ {\texttt {'*'}}\ M\\P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\end{array}}}$ ɛ ملحوظات المدخل الأيسر المدخلات لا تتطابق مع العنصر الأول في الاشتقاق. العودة إلى قاعدة النحو الأولى ذات البديل غير المستكشف${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 2*(3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م P د 2 * ( 3 + 4 ) لم يتم التحديث لعدم التعرف على أي طرفية
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle P\rightarrow D}$${\displaystyle D\rightarrow 2}$ 2 ملحوظات المدخل الأيسر قم بإزاحة المدخلات بمقدار واحد بعد استخراج الطرفية 2 *(3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م P 1 د 1 2 * ( 3 + 4 ) تحديث: D(1) = 1؛ P(1) = 1;
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*( ملحوظات المدخل الأيسر إزاحة الإدخال بمقدار طرفين${\displaystyle \{{\texttt {*}},{\texttt {(}}\}}$ 3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م P 1 د 1 2 * ( 3 + 4 ) لا يوجد تحديث لأنه لم يتم التعرف على أي طرفية غير طرفية بشكل كامل
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*( ملحوظات المدخل الأيسر المدخلات لا تتطابق مع العنصر الأول في الاشتقاق. العودة إلى قاعدة النحو الأولى ذات البديل غير المستكشف${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م P 1 د 1 2 * ( 3 + 4 ) لم يتم التحديث لعدم التعرف على أي طرفية
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle P\rightarrow D}$${\displaystyle D\rightarrow 3}$ 2*( ملحوظات المدخل الأيسر قم بإزاحة المدخلات بمقدار واحد بعد استخراج الطرفية 3 لكن المدخلات الجديدة لن تتطابق في الداخل${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$لذا فإن عملية الفتح ضرورية لـ${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ 3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م P 1 1 د 1 1 2 * ( 3 + 4 ) تحديث: D(4) = 1؛ P(4) = 1;
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle M\rightarrow P}$ 2*(3+ ملحوظات المدخل الأيسر العودة إلى${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ ولا نقوم بتوسيعها لأن لدينا نتيجة في جدول التخزين المؤقت P(4) ≠ 0، لذا نقوم بإزاحة المدخلات بمقدار P(4). ونقوم أيضًا بإزاحة${\displaystyle +}$من${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$ 4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م 1 P 1 1 د 1 1 2 * ( 3 + 4 ) ضربة على النقطة P(4) قم بتحديث M(4) = 1 حيث تم التعرف على M
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ 2*(3+ ملحوظات المدخل الأيسر المدخلات لا تتطابق مع العنصر الأول في الاشتقاق. العودة إلى قاعدة النحو الأولى ذات البديل غير المستكشف${\textstyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}\ /\ {\underline {D}}}$ 4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م 1 P 1 1 د 1 1 2 * ( 3 + 4 ) لم يتم التحديث لعدم التعرف على أي طرفية
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle P\rightarrow D}$${\displaystyle D\rightarrow 4}$ 2*(3+ ملحوظات المدخل الأيسر قم بإزاحة المدخلات بمقدار واحد بعد استخراج الطرفية 4 لكن المدخلات الجديدة لن تتطابق في الداخل${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M}$لذا فإن عملية الفتح ضرورية 4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م 1 P 1 1 1 د 1 1 1 2 * ( 3 + 4 ) تحديث: D(6) = 1؛ P(6) = 1;
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle M\rightarrow P}$ 2*(3+ ملحوظات المدخل الأيسر العودة إلى${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$ ولا نقوم بتوسيعها لأن لدينا ضربة في جدول التخزين المؤقت P(6) ≠ 0 لذلك نقوم بإزاحة المدخلات بمقدار P(6). لكن المدخلات الجديدة لن تتطابق${\displaystyle +}$داخل${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A}$لذا فإن عملية الفتح ضرورية 4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ م 1 1 P 1 1 1 د 1 1 1 2 * ( 3 + 4 ) ضربة على النقطة P(6) قم بتحديث M(6) = 1 حيث تم التعرف على M
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle A\rightarrow M}$ 2*(3+4) ملحوظات المدخل الأيسر العودة إلى${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A\ /\ {\underline {M}}}$ ولا نقوم بتوسيعها لأن لدينا ضربة في جدول التخزين المؤقت M(6) ≠ 0 لذلك نقوم بإزاحة المدخلات بمقدار M(6). قم أيضًا بتغيير الوضع${\displaystyle )}$من${\displaystyle P\rightarrow {\texttt {'('}}\ A\ {\texttt {')'}}}$ ⊣	فِهرِس 1 2 3 4 5 6 7 S أ 3 م 1 1 P 1 5 1 1 د 1 1 1 2 * ( 3 + 4 ) ضربة على M(6) قم بتحديث A(4) = 3 حيث تم التعرف على A قم بتحديث P(3) إلى 5 حيث تم التعرف على P
	قواعد الاشتقاق تم تحويل المدخلات 2* ملحوظات المدخل الأيسر العودة إلى${\displaystyle M\rightarrow P\ {\texttt {'*'}}\ M\ /\ {\underline {P}}}$كطرفية${\displaystyle *\neq \dashv }$ (3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ 3 م 1 1 P 1 5 1 1 د 1 1 1 2 * ( 3 + 4 ) لم يتم التحديث لعدم التعرف على أي طرفية
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle M\rightarrow P}$ 2*(3+4) ملحوظات المدخل الأيسر لا نقوم بتوسيعها لأن لدينا نتيجة في جدول التخزين المؤقت P(3) ≠ 0، لذلك نقوم بإزاحة المدخلات بمقدار P(3). ⊣	فِهرِس 1 2 3 4 5 6 7 S أ 3 م 7 1 1 P 1 5 1 1 د 1 1 1 2 * ( 3 + 4 ) ضربة على النقطة P(3) قم بتحديث M(1)=7 حيث تم التعرف على M
	قواعد الاشتقاق تم تحويل المدخلات ملحوظات المدخل الأيسر العودة إلى${\displaystyle A\rightarrow M\ {\texttt {'+'}}\ A\ /\ {\underline {M}}}$كطرفية${\displaystyle +\neq \dashv }$ 2*(3+4)⊣	فِهرِس 1 2 3 4 5 6 7 S أ 3 م 7 1 1 P 1 5 1 1 د 1 1 1 2 * ( 3 + 4 ) لم يتم التحديث لعدم التعرف على أي طرفية
	قواعد الاشتقاق تم تحويل المدخلات ${\displaystyle A\rightarrow M}$ 2*(3+4)⊣ ملحوظات المدخل الأيسر لا نقوم بتوسيعها لأن لدينا نتيجة في جدول التخزين المؤقت M(1) ≠ 0، لذلك نقوم بإزاحة المدخلات بمقدار M(1). تم اختزال S بالكامل، لذلك تم التعرف على سلسلة الإدخال.	فِهرِس 1 2 3 4 5 6 7 S 7 أ 7 3 م 7 1 1 P 1 5 1 1 د 1 1 1 2 * ( 3 + 4 ) ضربة على M(1) قم بتحديث A(1)=7 حيث تم التعرف على A قم بتحديث S(1)=7 حيث تم التعرف على S

• خوارزمية CYK
• قواعد اللغة الخالية من السياق
• خوارزميات التحليل
• محلل إيرلي

• تحليل Packrat: بسيط، قوي، كسول، وقت خطي
• قواعد تحليل التعبيرات: أساس نحوي قائم على التعرف