סימולטור דקדוק חופשי־הקשר

דקדוק חופשי־הקשר הוא דקדוק פורמלי עם כללי גזירה המחליפים משתנה יחיד במחרוזת של טרמינלים ומשתנים. CFG מתאר שפות חופשיות־הקשר ונמצא בשימוש נרחב להגדרת התחביר של שפות תכנות. הוא בעל כוח ביטוי רב יותר ממש מדקדוקים רגולריים (DFA/NFA).

הצורה הנורמלית של חומסקי היא צורה מוגבלת של CFG שבה כל כלל הוא או A → BC (שני משתנים) או A → a (טרמינל אחד). כל CFG ניתן להמרה ל־CNF בלי לשנות את השפה שהוא מייצר. CNF נדרש עבור אלגוריתם CYK המשמש בסימולטור זה.

אלגוריתם קוק–יאנגר–קסאמי (CYK) הוא אלגוריתם תכנון דינמי המכריע האם מחרוזת שייכת לשפה חופשית־הקשר. הוא ממלא טבלה משולשית בגודל n×n של תת־מחרוזות מלמטה למעלה ורץ בזמן O(n³ · |G|), כאשר n הוא אורך הקלט ו־|G| הוא גודל הדקדוק.

עץ גזירה (או עץ ניתוח) מראה כיצד מחרוזת נגזרת מסמל ההתחלה שלב אחר שלב. כל צומת פנימי הוא משתנה, כל עלה הוא תו טרמינל, וילדי כל צומת תואמים את הצד הימני של כלל הגזירה שהופעל באותו שלב. סימולטור זה משחזר עץ גזירה תקף אחד בכל פעם שהקלט מתקבל.

CFG מתאר שפות חופשיות־הקשר, המכילות ממש את כל השפות הרגולריות. דוגמאות קלאסיות שאינן רגולריות הן {aⁿbⁿ | n ≥ 1} (מספר שווה של a ו־b), סוגריים מאוזנים וביטויים אריתמטיים. עם זאת, שפות חופשיות־הקשר אינן יכולות לתאר את {aⁿbⁿcⁿ} — זה דורש מודל חזק יותר כמו מכונת טיורינג.