نريد برنامجاً يأخذ صيغة رياضية ويرسمها!
وإمعاناً في التحدي، نريد أن نكتب هذا البرنامج في مائة سطر من الكود أو أقل. هل سنقدر يا ترى؟ أعتقد أنك ستستمتع كثيراً بهذا المقال عزيزي القاري.
هذه الرسمة اسمها "شجرة الإعراب" أو parse tree، وهي تشبه الشجرة لأن لها جذراً وفروعاً. كيف نعبر عن هذه الشجرة بقيمة في لغة كلمات؟ هناك طرق كثيرة: يمكن أن نستخدم الفصائل والكائنات، أو المصفوفات، أو القواميس...فلنستخدم طريقة بسيطة: سوف تكون كل شجرة عبارة من مصفوفة من ثلاثة عناصر: العملية الحسابية نفسها، والقيمتان التي تجري عليهما العملية. مثلاً إن قمنا بإعراب التعبير "4+5" سوف نحصل على المصفوفة ["+"، 4، 5]. لو أعربنا القيمة النصية "(4+5)×2" سوف نحصل على ["×"، ["+"، 4، 5]، 2]. أي أن الشجرة هي عملية ضرب بين ["+"، 4، 5] وبين 2.
لو افترضنا أننا - بطريقة ما - لدينا دالة تأخذ نصاً من المستخدم وتعود لنا بهذه الشجرة، فإنه من السهل أن نحسب القيمة المطلوبة من الشجرة: نحسب الفرع الأيمن، ثم نحسب الفرع الأيسر، ثم نقوم بتطبيق العملية الحسابية.
لاحظ أن الإعراب لا يعود دائماً بمصفوفات..لو أعربنا مثلاً التعبير 12 فإن "الشجرة" ما هي إلا العدد 12 نفسه.
رائع. الآن علينا أن نفكر: مم تتكون الصيغ الرياضية؟ سوف نسمي الصيغة في صورتها النهائية "تعبير حسابي"، وهذا التعبير مكون من حد واحد أو أكثر. ما الذي يفصل بين الحدود في التعبير الواحد؟ علامات الجمع والطرح. أي أن التعبير يكون في صيغة حد1 + حد2 - حد3....الخ، أو مكون من حد واحد.
في السطر الأخير نجرب القواعد الجديدة. سوف يطبع مفسر كلمات لك القيمة......لاشيء :(
لماذا؟ في الواقع سوف تقوم كلمات بإعراب التعبير، لكننا لم نطلب منها أن تعطينا شجرة إعراب، لذلك سوف تعود لنا بالقيمة لاشيء. هيا نغير ذلك الموقف! فلنبدأ بشيء بسيط كالأرقام:
لاحظ شيئين:
في السطر الأول قلنا خانة:أ رقم:ب ، هذه طريقتنا في إعطاء أسماء للمكونات التي نعربها.
أننا قلنا في أخر السطر => أ + ب ، وهذه طريقتنا في أن نعود بقيم أثناء الإعراب
يمكن أن نقرأ السطر كله كالآتي: الرقم مكون من خانة هي أ، ورقم أصغر هو ب، وحين نجدهما نعود بالقيمة أ + ب.
لاحظ أن أ و ب هما نصان، فلو أعربنا الرقم "123" فسيكون أ = "1" و ب يساوي "23" (الأرقام تقرأ من اليسار) وبهذا يكون الرقم كله هو أ + ب = "123"
ماذا عن السطر الثاني الذي يقول أو خانة؟ نحن لم نخبره بأي قيمة يعود، لكن لو رأى مفسر كلمات قاعدة ما هي الا استدعاء قاعدة أخرى (نحن لم نفعل سوى استدعاء "خانة") فسيعود بنفس القيمة الآتية من القاعدة المستدعاه. كأني بالضبط قلت أو خانة:أ => أ
ماذا عن السطر خانة = من "0" إلى "9"؟ حين تكون القاعدة ما هي إلا قيمة نصية فالقيمة العائدة منها هي نفس القيمة النصية.
إذاً قد عرفنا ماذا يرجع من رقم. ماذا عن شيء مثل تعبير؟
باللغة البشرية:
التعبير هو حد اسمه أ، ثم علامة "+"، ثم تعبير أصغر اسمه ب ، وفي تلك الحالة ارجع بالمصفوفة ["+"، أ، ب]
أو هو حد اسمه أ، ثم علامة "-"، ثم تعبير أصغر اسمه ب، وهنا ارجع بالمصفوفة ["-"، أ، ب]
أو هو مجرد حد اسمه أ، وفي تلك الحالة ارجع بذلك الحد.
سهل، أليس كذلك؟ بنفس الطريقة نعدل "حد" و "أس" و"أولي" ليكون لدينا القواعد كلها:
لاحظ أننا في هذا الجزء التالي قد حولنا الرقم من قيمة نصية إلى قيمة عددية:
سوف تصنع لنا كلمات دالة اسمها "تعبير" (لأننا قد سمينا القواعد "تعبير")، وهذه الدالة إن أعطيناها نصاً فستعطينا شجرة إعراب. جرب أن تضيف هذا السطر في آخر البرنامج:
اطبع تعبير("12+13×14")
سوف يظهر المخرج التالي:
["+"، 12، ["×"، 13، 14]]
في الواقع الكود السابقة ليست دقيقة لأن العمليات الرياضية + - ÷ × بها خاصية left associativity. أي أن تعبير مثل 1-2-5 المفروض أن يكون (1-2)-5، لكن برنامجنا يعتبره 1-(2-5)، أي أنه يعود بالشجرة ["-"، 1، ["-"، 2، 5] بدلاً من الشجرة الصحيحة وهي ["-"، ["-"، 1، 2]، 5]
سبب المشكلة هو أنه كان المفروض في القواعد أن نقول:
تعبير = تعبير + حد
ولكننا قلنا
تعبير = حد + تعبير
للأسف لا يمكن استخدام الطريقة الصحيحة في هذا الإصدار من كلمات بسبب مشكلة اسمها left recursion (هناك طرق لحل تلك المشكلة لكنها لم تطبق في كلمات بعد). لذلك علينا الحذر: البرنامج سيعطي نتائجاً خاطئة في المدخلات أ-ب-ج أو أ÷ب÷ج، ولكن يمكننا استخدام الأقواس في تلك الحالات.
على العموم قد أنهينا جزء إعراب الصيغ الرياضية، ومازال لدينا 70 سطراً أيضاً!
وإمعاناً في التحدي، نريد أن نكتب هذا البرنامج في مائة سطر من الكود أو أقل. هل سنقدر يا ترى؟ أعتقد أنك ستستمتع كثيراً بهذا المقال عزيزي القاري.
الجزء الأول: كيف نفهم الصيغة الرياضية؟
يوجد في علوم الحاسب ما يسمى parsing (الإعراب). لو أعربنا التعبير الحسابي س^2+5 فسيكون لنا النتيجة التالية:
لو افترضنا أننا - بطريقة ما - لدينا دالة تأخذ نصاً من المستخدم وتعود لنا بهذه الشجرة، فإنه من السهل أن نحسب القيمة المطلوبة من الشجرة: نحسب الفرع الأيمن، ثم نحسب الفرع الأيسر، ثم نقوم بتطبيق العملية الحسابية.
لاحظ أن الإعراب لا يعود دائماً بمصفوفات..لو أعربنا مثلاً التعبير 12 فإن "الشجرة" ما هي إلا العدد 12 نفسه.
رائع. الآن علينا أن نفكر: مم تتكون الصيغ الرياضية؟ سوف نسمي الصيغة في صورتها النهائية "تعبير حسابي"، وهذا التعبير مكون من حد واحد أو أكثر. ما الذي يفصل بين الحدود في التعبير الواحد؟ علامات الجمع والطرح. أي أن التعبير يكون في صيغة حد1 + حد2 - حد3....الخ، أو مكون من حد واحد.
كيف نعبر عن هذا رياضياً؟ هناك طريقة اسمها Parse Expression Grammar أو PEG تسمح لنا أن نكتب القاعدة بهذه الطريقة:
تعبير = حد "+" تعبير (هذه قاعدة 1#)
أو حد "-" تعبير (قاعدة 2#)
أو حد (قاعدة 3#)
ما معنى هذا الوصف؟ معناه أن التعبير يمكن أن يكون حداً واحداً أو مجموعة من الحدود يفصل بينها + و -. مثلاً يمكن أن نبدأ بالحد "2×3". نحن نعرف أن هذا تعبير من قاعدة #3 من التعريف. ماذا عن 1 + 2×3؟ نعرف أن هذا أيضاً تعبير (من قاعدة #1 التي تقول أن حد + تعبير = تعبير، وبالتالي سمحت لنا بإضافة حد في المقدمة). ماذا عن 5 - 1 + 2×3؟ هذا أيضاً تعبير من جزء 2# من التعريف
لو شعرت أن الأمر صعب فلا تقلق: الموضوع ببساطة هو recursion مثلما تعلمت في البرمجة. المسألة هي أن التعبير يمكن أن يكون حداً أو يكون حد + حد + حد ....، أو حد + حد - حد - حد ....الخ.
ماذا عن الحدود نفسها؟ الحد هو "أس" واحد أو أكثر تفصل بينها علامات ×، ÷
هذه كلها حدود:
5^2 × 6
6 ÷ 3
18
6^س
كيف نكتبها بطريقة PEG؟ هكذا:
حد = أس "×" حد
أو أس "÷" حد
أو أس
وهي كما ترى نفس طريقة التعبيرات. لاحظ أن قيمة عادية مثل "18" نعتبرها أس رغم غياب علامة ^، مثلما اعتبرنا أن 12 هو تعبير رغم غياب علامة + أو -
ماذا عن الأسس؟ هي ببساطة مجموعة من واحد أو أكثر من التعبيرات الأولية يفصل بينها علامة ^. كل هذه أسس:
س^2
2^س
س^2^3
س
12
والقاعدة (كما خمنت) هي:
أس = أولي "^" أس
أو أولي
ولكن ما هو التعبير الأولي؟؟؟ إنه رقم، أو المتغير س، أو تعبير بين أقواس:
أولي = "س"
أو رقم
أو "(" تعبير ")"
لم يبق ما نعرّفه سوى الأرقام نفسها. الرقم هو خانة واحدة أو أكثر (الخانة هي الرمز 0، أو 1، أو 2...إلى 9).
رقم = خانة رقم
أو خانة
خانة = من "0" إلى "9"
الرقم هو خانات لا يفصل بينها شيء. لهذا لم نقل مثلاً رقم = خانة + رقم بل قلنا مباشرةً رقم = خانة رقم....
ولكن ما فائدة كل هذا؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
فائدة كل هذا أن لغة كلمات بها محرك إعراب جاهز. لو قدمت له قواعد في صورة PEG سوف يقدم لك إمكانية إعراب أي نص يتماشى مع هذه القواعد. مثلما نعرّف في كلمات دالة أو إجراء أو فصيلة، يمكننا أيضاً أن نعرّف قواعداً. انظر للكود الآتية:
قواعد تعبير : تعبير = حد "+" تعبير أو حد "-" تعبير أو حد حد = أس "×" حد أو أس "÷" حد أو أس أس = أولي "^" أس أو أولي أولي = رقم أو "س" أو "(" تعبير ")" رقم = خانة رقم أو خانة خانة = من "0" إلى "9" نهاية
اطبع تعبير ("1+2+3")
في السطر الأخير نجرب القواعد الجديدة. سوف يطبع مفسر كلمات لك القيمة......لاشيء :(
لماذا؟ في الواقع سوف تقوم كلمات بإعراب التعبير، لكننا لم نطلب منها أن تعطينا شجرة إعراب، لذلك سوف تعود لنا بالقيمة لاشيء. هيا نغير ذلك الموقف! فلنبدأ بشيء بسيط كالأرقام:
رقم = خانة:أ رقم:ب => أ + ب أو خانة خانة = من "0" إلى "9"
لاحظ شيئين:
في السطر الأول قلنا خانة:أ رقم:ب ، هذه طريقتنا في إعطاء أسماء للمكونات التي نعربها.
أننا قلنا في أخر السطر => أ + ب ، وهذه طريقتنا في أن نعود بقيم أثناء الإعراب
يمكن أن نقرأ السطر كله كالآتي: الرقم مكون من خانة هي أ، ورقم أصغر هو ب، وحين نجدهما نعود بالقيمة أ + ب.
لاحظ أن أ و ب هما نصان، فلو أعربنا الرقم "123" فسيكون أ = "1" و ب يساوي "23" (الأرقام تقرأ من اليسار) وبهذا يكون الرقم كله هو أ + ب = "123"
ماذا عن السطر الثاني الذي يقول أو خانة؟ نحن لم نخبره بأي قيمة يعود، لكن لو رأى مفسر كلمات قاعدة ما هي الا استدعاء قاعدة أخرى (نحن لم نفعل سوى استدعاء "خانة") فسيعود بنفس القيمة الآتية من القاعدة المستدعاه. كأني بالضبط قلت أو خانة:أ => أ
ماذا عن السطر خانة = من "0" إلى "9"؟ حين تكون القاعدة ما هي إلا قيمة نصية فالقيمة العائدة منها هي نفس القيمة النصية.
إذاً قد عرفنا ماذا يرجع من رقم. ماذا عن شيء مثل تعبير؟
تعبير = حد:أ "+" تعبير:ب => ["+"، أ، ب] أو حد:أ "-" تعبير:ب => ["-"، أ، ب] أو حد:أ => أ
باللغة البشرية:
التعبير هو حد اسمه أ، ثم علامة "+"، ثم تعبير أصغر اسمه ب ، وفي تلك الحالة ارجع بالمصفوفة ["+"، أ، ب]
أو هو حد اسمه أ، ثم علامة "-"، ثم تعبير أصغر اسمه ب، وهنا ارجع بالمصفوفة ["-"، أ، ب]
أو هو مجرد حد اسمه أ، وفي تلك الحالة ارجع بذلك الحد.
سهل، أليس كذلك؟ بنفس الطريقة نعدل "حد" و "أس" و"أولي" ليكون لدينا القواعد كلها:
قواعد تعبير : تعبير = حد : أ "+" تعبير : ب => ["+"، أ، ب] أو حد : أ "-" تعبير : ب => ["-"، أ، ب] أو حد : أ => أ حد = أس:أ "×" حد:ب => ["×"، أ، ب] أو أس:أ "÷" حد:ب => ["÷"، أ، ب] أو أس:أ => أ أس = عامل:أ "^" أس:ب => ["^"، أ، ب] أو عامل عامل = رقم:أ => كعدد (أ) أو "س" أو "(" تعبير : أ ")" => أ رقم = خانة : أ رقم : ب => أ + ب أو خانة خانة = من "0" إلى "9" نهاية
لاحظ أننا في هذا الجزء التالي قد حولنا الرقم من قيمة نصية إلى قيمة عددية:
عامل = رقم:أ => كعدد (أ)
قد يبدو الأمر صعباً، لكنه أسهل بكثير من كتابة برنامج يأخذ أي صيغة رياضية ويفهمها بطريقة يدوية. القواعد كلها أخذت 30 سطراً لكنها وفرت عشرات أو مئات السطور المطلوبة لعمل مثل هذا البرنامج في لغات أخرى.
سوف تصنع لنا كلمات دالة اسمها "تعبير" (لأننا قد سمينا القواعد "تعبير")، وهذه الدالة إن أعطيناها نصاً فستعطينا شجرة إعراب. جرب أن تضيف هذا السطر في آخر البرنامج:
اطبع تعبير("12+13×14")
سوف يظهر المخرج التالي:
["+"، 12، ["×"، 13، 14]]
في الواقع الكود السابقة ليست دقيقة لأن العمليات الرياضية + - ÷ × بها خاصية left associativity. أي أن تعبير مثل 1-2-5 المفروض أن يكون (1-2)-5، لكن برنامجنا يعتبره 1-(2-5)، أي أنه يعود بالشجرة ["-"، 1، ["-"، 2، 5] بدلاً من الشجرة الصحيحة وهي ["-"، ["-"، 1، 2]، 5]
سبب المشكلة هو أنه كان المفروض في القواعد أن نقول:
تعبير = تعبير + حد
ولكننا قلنا
تعبير = حد + تعبير
للأسف لا يمكن استخدام الطريقة الصحيحة في هذا الإصدار من كلمات بسبب مشكلة اسمها left recursion (هناك طرق لحل تلك المشكلة لكنها لم تطبق في كلمات بعد). لذلك علينا الحذر: البرنامج سيعطي نتائجاً خاطئة في المدخلات أ-ب-ج أو أ÷ب÷ج، ولكن يمكننا استخدام الأقواس في تلك الحالات.
على العموم قد أنهينا جزء إعراب الصيغ الرياضية، ومازال لدينا 70 سطراً أيضاً!
ليست هناك تعليقات:
إرسال تعليق