القواعد (BNF) ورمز بولند العكسي
| English | العربية |
|---|---|
| postfix/ˈpəʊstfɪks/ | اللاحق |
| precedence/ˈpresɪdəns/ | أولوية |
| grammar/ˈɡræmə/ | النحو |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | مخطط القواعد |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | ترميز بولند العكسي |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | صيغة باكوس-ناور |
| production rules/prəˈdʌkʃn ruːlz/ | قواعد الإنتاج |
| terminal/ˈtɜːmɪnl/ | طرفي القائمة |
| non-terminal/nɒn ˈtɜːmɪnl/ | غير طرفي |
| infix/ˈɪnfɪks/ | وسطي |
الترميز بدون أقواس، وبلا غموض
- اكتب
3 + 4 * 2وأنت تعتمد على约定: أن الضرب يرتبط بقوة أكبر من الجمع. غيّر约定 وهذا التعبير يعني شيئاً آخر. - عالم رياضيات بولندي، جان لوكاسيفيتش، أثبت في 1920s أنه إذا وضعت العملية الحسابية قبل operands becomes unnecessary. عكس العملية، وضع العملية بعد، وتحصل على شكل يمكن للآلة تقييمه باستخدام فقط المكدس.
- لهذا السبب تعمل آلة Java الافتراضية ومعظم مفسرات الأوامر الثنائية بصيغة اللاحقة. لا جدول أولويات، لا أقواس، لا غموض.
- هذه الدرس هو كيف تُكتب قواعد لغة ما، في BNF كمخطط نحوي، وكيف يتم تحويل الترميز البولندي العكسي وتقييمه.
صيغة باكوس-ناور
- القاعدة تقول أي تسلسلات الرموز هي برامج صالحة. صيغة باكوس-ناور - (BNF) تكتبها كـ قواعد إنتاج:
<symbol> ::= alternative1 | alternative2 | ...
- الرمز الطرفي هو نص حرفي يظهر في البرنامج. الرمز غير الطرفي هو اسم قاعدة أخرى، مكتوب بين قوسين زاويين.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
في BNF، الرمز الطرفي هو:
المؤثرات الطرفية هي رموز حرفية؛ والمؤثرات غير الطرفية هي أسماء قواعد إنتاج أخرى.
التكرار هو كيف يكرر BNF
- BNF ليس لديه رمز "تكرار"، لذا تُكتب التكرارات بتعريف قاعدة بخصوص نفسها.
- اقرأ
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>كـ: المعرّف هو حرف واحد، أو معرّف متبوع بحرف، أو معرّف متبوع برقم. - مجتمعة، تعني هذه البدائل "حرف متبوع بأي عدد من الأحرف أو الأرقام"، وهو ما يفسر أيضاً لماذا لا يمكن للمعرّف أن يبدأ برقم: لا بديل يسمح بذلك.
- المخطط النحوي، أو مخطط السكك الحديدية، يعبر عن نفس القواعد بيانياً، مع حلقة حيث يستخدم BNF التكرار. الترميزان متكافئان.
الحلقة والتكرار يقولاان نفس الشيء
صل كل مصطلح لقاعدة/رمز دالة بمعناه.
تبني BNF القواعد من مؤثرات طرفية وغير طرفية (التكرار الذاتي يوفر التكرار)؛ بينما يعيد RPN ترتيب التعبير لإزالة الأقواس.
لماذا تشير القاعدة
الخيارات معًا تعني حرفًا متبوعًا بأي عدد من الأحرف أو الأرقام، ولا يسمح أي خيار بأن يبدأ برقم.
مثال محلول: اختبار سلسلة مقابل القاعدة
- باستخدام القواعد أعلاه، أي من
count2،2countوmy_varهي معرفات صالحة؟ count2: صالح. بنِها:cهي<letter>، لذا فهي<identifier>؛ أضفo،u،n،tبالبديل الثاني؛ أضف2بالثالث.2count: غير صحيح. كل بديل يبدأ من<letter>أو من<identifier>آخر، ولا يمكن لأي سلسلة أن تبدأ برقم.my_var: غير صحيح، لأن_ليس رمزاً طرفياً في أي قاعدة هنا. حدد القاعدة التي فشلت، وليس فقط "يبدو خاطئاً".
باستخدام هذه القواعد، أي السلاسل التالية تُعد معرّفًا صحيحًا؟ حدد كل الخيارات الصحيحة.
الحرف المفرد هو معرّف وفق الخيار الأول. لا يمكن لـ 2count أن يبدأ برقم، و _ ليس رمزًا طرفيًا في أي قاعدة هنا.
الصيغة الوسطى واللاحقة
- الصيغة الوسطى تضع العملية بين حجاجها،
3 + 4 * 2، وبالتالي تحتاج إلى قواعد أولوية وأقواس لتكون بلا غموض. - الترميز البولندي العكسي، أو اللاحق، يضع العملية بعد حجاجها:
3 4 2 * +. لا يحتاج إلى أي منهما. - ترتيب ظهور العمليات في الشكل اللاحق هو الترتيب الذي يتم تطبيقه، وهو بالضبط ما يحتاجه الجهاز ليخبر به.
تحويل الصيغة الوسطى إلى اللاحقة
- استخدم كومة عمليات. امسح من اليسار إلى اليمين: أرسل حاجاً مباشرة إلى المخرجات؛ بالنسبة لـ عملية، قم أولاً بإخراج أي عمليات مكدسة ذات أولوية أعلى أو مساوية إلى المخرجات، ثم ادخلها.
- أدخل قوس فتح. عند قوس إغلاق، أخرج إلى المخرجات حتى القوس المفتوح المقابل، ثم تخلص من الزوج.
- في النهاية، أخرج كل ما تبقى على الكومة إلى المخرجات.
أولوية العمليات — وهو ما يلغيه رمز بولند العكسي
في الرياضيات العادية بالترتيب الوسطي، ترتبط عمليات × و ÷ بقوة أكبر من + و −، لذا يجب تطبيق القواعد بالترتيب الصحيح. يكتب رمز بولند العكسي المؤثرات أولاً (3 4 2 × + 1 −)، مما يثبت الترتيب دون الحاجة لقواعد أولوية.
ما هو شكل بولند العكسي (ما بعد المؤثر) للتعبير بالترتيب الوسطي (3 + 4) * 2؟
تفرض الأقواس حساب 3+4 أولاً: 3 4 +، ثم الضرب في 2: 3 4 + 2 *.
حول (A + B) * (C - D) إلى رمز بولند العكسي، باستخدام * للضرب.
تُحوّل كل قوس على حدة، ويُستدعى الضرب أخيرًا، فيظهر في النهاية. لا تبقى أقواس.
مثال محلول: التحويل، ثم التقييم
- حول $(A + B) \times (C - D)$ إلى RPN. أدخل
(؛ أخرجA؛ أدخل+؛ أخرجB؛ عند)أخرج عائدًا إلى(المقابل، مما يعطيA B +. أدخل×. يتصرف القوس الثاني بشكل مماثل، مما يعطيC D -. في النهاية أخرج×. النتيجة:A B + C D - ×. - قيّم الآن لـ $A=3, B=4, C=5, D=2$. أدخل 3، أدخل 4؛
+يأخذ الاثنين ويدخل 7. أدخل 5، أدخل 2؛-يأخذ الاثنين ويدخل 3.×يأخذ 7 و 3 ويدخل 21. - تأخذ العملية دائمًا أعلى عنصرين، والعنصر الأول المأخوذ هو الحاج الأيمن. هذا مهم لـ
-و/، حيث يغير الترتيب الإجابة.
احسب تعبير بولند العكسي 3 4 2 * +.
ادفع 3، 4، 2؛ * يسحب 4 و 2 → 8؛ + يسحب 3 و 8 → 11.
لا يحتاج رمز بولند العكسي إلى أقواس أو قواعد أولوية، ويمكن حسابه مباشرة باستخدام المكدس.
ادفع المؤثرات؛ كل مؤثر يسحب مؤثراته ويدفع النتيجة — وهو بالضبط كيف تعمل آلة المكدس.
التقييم باستخدام الكومة، خطوة بخطوة
- امسح من اليسار إلى اليمين: ادخل كل حاج؛ عند عملية، أخرج أعلى عنصرين، طبقها، وادخل النتيجة. في النهاية تحتوي الكومة على قيمة واحدة: الإجابة.
| الرمز | الكومة بعد |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- هذه آلة كومة: لا أقواس، لا جدول أولويات، لا نظرة مستقبلية. هكذا تقوم JVM ومفسرات الأوامر الثنائية بتقييم كل تعبير.
عند الحساب، العنصر الأول المُسحب من المكدس هو المؤثر الأيسر للمؤثر.
الأول المُسحب هو المؤثر الأيمن. لا فرق بالنسبة لـ + و *، لكن قلبه يكسر الطرح والقسمة.
رتّب خطوات حساب 3 4 2 * + باستخدام مكدس.
تذهب المؤثرات إلى الأعلى، يستهلك كل مؤثر أعلى عنصرين ويترك نتيجته. لا حاجة لأقواس ولا جدول أولويات.
علامات ضائعة
- الطرفي هو نص حرفي؛ غير الطرفي يسمي قاعدة أخرى. لا تبديلهما.
- BNF يعبر عن التكرار عبر التكرار. إذا أشارت قاعدة إلى نفسها، فقل ذلك ووضح معناها.
- في التقييم تأخذ العملية أعلى عنصرين، والعنصر الأول المأخوذ هو الحاج الأيمن. الحصول على ذلك معكوس يكسر الطرح والقسمة.
- RPN لا تحتاج إلى أقواس. كتابة أقواس في إجابة اللاحق تفقد الدرجة التي كانت تختبرها.
لقد فهمت الأمر
- قواعد إنتاج BNF تجمع الطرفيات (النص الحرفي) وغير الطرفيات (أسماء القواعد)، وتعبر عن التكرار عبر التكرار؛ المخطط النحوي هو الشكل البياني المكافئ
- اختبر سلسلة عن طريق بناؤها من القواعد، وسمِّ القاعدة التي فشلت عندما تكون غير صحيحة
- infix يتطلب الأولوية والأقواس؛ أما RPN (postfix) فيضع المؤثر بعد مُعاملاته ولا يحتاج إلى أي منهما
- التحويل يتم باستخدام مكدس مؤثرات، والتقييم عن طريق دفع المُعاملات وتطبيق كل مؤثر على أعلى اثنين، حيث يكون أول مُعامل تم إزاحته هو المُعامل الأيمن