דקדוק (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 ש אם מניחים את האופרטור לפני הארגומנטים שלו הסוגריים הופכים למיותרים. הפוך זאת, והנח את האופרטור אחרי, ותקבל צורה שמכונה יכולה לשאול באמצעות סטק בלבד.
- זוהי הסיבה ש-Machine הווירטואלי של 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, סימן טרמינלי הוא:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
טרמינלים הם טוקנים תיאוריים; לא-טרמינלים הם שמות של כללי ייצור אחרים.
רקורסיה היא אופן החזרה של BNF
- ל-BNF אין סמן "חזרה", לכן חזרה נכתבת על ידי הגדרת כלל במונחים של עצמו.
- קריאת
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>כפירושו: מזהה הוא אות בודדת, או מזהה העוקב בו אות, או מזהה העוקב בו דיגית. - יחד האפשרויות הללו פירושן "אות שאחריה מספר כלשהו של אותיות או ספרות", מה שמסביר גם מדוע מזהה אינו יכול להתחיל בספרה: אף אפשרות לא מאפשרת זאת.
- תרשים סינטקטי, או תרשים רכבת, מבטא את אותם כללים בגרפיקה, עם לולאה שבה BNF משתמש בריקורסיה. שתי הסימונים שווים ערך.
הלולאה והריקורסיה אומרות את אותו דבר
התאם כל שם מונח במדריך/סימון למשמעותו.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
BNB בונה כללים מתוך טרמינלים ולא-טרמינלים (רקורסיה נותנת חזרה); RPN מעצב מחדש ביטוי כדי לבטל סוגריים.
מדוע הכלל
Difficulty 1/5 · 100 coins + a small bonus on first completion today
האלטרנטיבות יחד מציינות אות שבעקבה כל מספר של אותיות או ספרות, ואף אלטרנטיבה אחת לא מאפשרת התחלה בספרה.
דוגמה פותרת: בדיקת מחרוזת מול הדקדוק
- באמצעות הכללים למעלה, אילו מ-
count2,2countו-my_varהם מזהים תקפים? count2: תקין. בנה אותו:cהוא<letter>, ולכן<identifier>; הוסףo,u,n,tלפי האלטרנטיבה השנייה; הוסף2לפי השלישית.2count: לא תקף. כל אפשרות מתחילה מ-<letter>או מ-<identifier>אחר, ואין שרשרת שיכולה להתחיל בספרה.my_var: לא תקף, כי_אינו טרמינל בכלל כאן. ציינו את הכלל הנכשל, לא רק "זה נראה שגוי".
באמצעות כללים אלו, אילו מחרוזות הן מזהים תקפים? בחר את כולם החלים.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
אות בודדת היא מזהה לפי האלטרנטיבה הראשונה. 2count אינו יכול להתחיל בספרה, ו- _ אינו תומך (terminal) בכל כלל כאן.
ביניים ואחורי
- ביניים מציב את הפועל בין המפעילים שלו,
3 + 4 * 2, ולכן דורש כללי עדיפות וסוגריים כדי להיות חד-משמעי. - סימון פולני הפוך, או אחורי, מציב את הפועל אחרי המפעילים שלו:
3 4 2 * +. הוא אינו זקוק לשום אחד מהם. - הסדר שבו הפועלים מופיעים בצורה האחורית הוא הסדר שבו הם מיושמים, בדיוק מה שהמכונה צריכה לקבל instruction.
המרת ביניים לאחורי
- השתמשו ב-ערימה של פועלים. סרו从左至右 (שמאל לימין): שלחו מפעיל ישירות לתוצאה; עבור פועל, קודם חלצו לתוצאה כל פועלים מעורמים בעלי עדיפות גבוהה או שווה, ולאחר מכן הדליקו אותו.
- הדליקו סוגר פתיחה. על סוגר סגירה, חלצו לתוצאה עד לסוגר הפתיחה המתאים, ולאחר מכן השליכו את הזוג.
- בסוף, חלצו הכל שנותר בערימה לתוצאה.
עדיפות מפעילים — מה ש-RPN מסיר
במתמטיקה אינפיקס רגילה, × ו-÷ בעלי עדיפות גבוהה יותר מ-+ ו-−, ולכן יש ליישם את הכללים בסדר הנכון. נקודת פולין ההפוכה כותבת את האופרנדים קודם (3 4 2 × + 1 −), מה שמקבע את הסדר כך שאין צורך בכללי עדיפות.
מהו הצורה RPN (הפוסטפיקס) של הביטוי האינפיקסי (3 + 4) * 2?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
הסוגריים מחייבים ביצוע 3+4 קודם: 3 4 +, ולאחר מכן הכפלה ב-2: 3 4 + 2 *.
מירוק את (A + B) * (C - D) לרעיון פולני הפוך, תוך שימוש ב- * להכפלה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
כל סוגריים ממוירים בהתאמה, והכפלה נשלפת אחרונה, כך שהיא מופיעה בסוף. אין סוגריים שנותרו.
דוגמה פותרת: המרה, ולאחר מכן חישוב
- המירו $(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. - המפעיל תמיד לוקח את שני הפריטים העליונים, והפריט הראשון שנפתח הוא האופרנד הימני. זה חשוב ב-
-וב-/, שבהם סדר משנה את התוצאה.
חשב את הביטוי RPN 3 4 2 * +.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
דחוס 3, 4, 2; * שולף 4 ו-2 → 8; + שולף 3 ו-8 → 11.
רעיון פולני הפוך אינו זקוק לסוגריים או לכללי עדיפות, וניתן לחשב אותו ישירות באמצעות אגרת נתונים (סטק).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
דחס את המפעילים; כל מפעיל שולף את המפעילים שלו ודחס את התוצאה — מה שמדויק הוא אופן פעולתו של מכונת אגרת נתונים.
ביצוע חישוב עם ערימה, צעד אחר צעד
- סרוק משמאל לימין: הכנס כל אופרנד; בעת מפעיל, פתח את שני הפריטים העליונים, יישם אותו, ו-הכנס את התוצאה. בסוף הערימה נותר ערך אחד: התשובה.
| סימן | הערימה לאחר |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- זוהי מכונת ערימה: אין סוגריים, אין טבלת עדיפויות, לא ישנן מבטי חזית. כך ה-JVM ופרשני בייטקוד רבים מחשבים כל ביטוי.
בעת חישוב RPN, הפריט הראשון שנשלף מאגרת הנתונים הוא המפעיל השמאלי של המפעיל.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
האופרנד הראשון שנפלט הוא האופרנד הימני. זה לא משנה עבור + ו-*, אך הפוך לסדר הופך את החיסור והחלקה למטעים.
סדרו את שלבי החישוב של 3 4 2 * + באמצעות סטק (ערימה).
Difficulty 3/5 · 200 coins + a small bonus on first completion today
האופרנדים נשארים בסטק, כל אופרציה צורכת שניים מהראש ומשאירה את התוצאה שלה. אין צורך בסוגריים או בטבלת עדיפויות.
סימונים נופלים מהיד
- סימול הוא טקסט מפורש; לא-סימול הוא שם של כלל אחר. אל תחליף אותם.
- BNF מבטא חזרה על ידי רקורסיה. אם כלל מתייחס לעצמו, ציין זאת ואמור מה המשמעות.
- בחישוב המפעיל לוקח את שני הפריטים העליונים, והפריט הראשון שנפתח הוא האופרנד הימני. הפיכת הסדר הזו גורמת לכשלון בחיסור וחלוקה.
- RPN אינו זקוק לסוגריים. כתיבת סוגריים בתשובה בפוסטפיקס תגרע נקודות מהבחינה שהיא נועדה לבדוק.
הבנתך מושלמת
- כללי BNF משלבים סימולים (טקסט מפורש) ולא-סימולים (שמות כללים), ומבטאים חזרה על ידי רקורסיה; תרשים סינטקסי הוא הצורה הגרפית המקבילה
- בדוק מחרוזת על ידי בניית אותה מהכללים, ושם את הכלל שנקלע לו קושי כאשר היא פסולה
- אינפיקס דורש עדיפויות וסוגריים; RPN (פוסטפיקס) מניח את המפעיל אחרי האופרנדים ואינו זקוק לאף אחד מהם
- ממיר באמצעות ערימת מפעילים, ובצע חישוב על ידי הכנסת אופרנדים ויישום כל מפעיל על שני הפריטים העליונים, כאשר הפריט הראשון שנפתח הוא האופרנד הימני