ה ההבדל העיקרי בין דקדוק לא חד משמעי הוא ש דקדוק דו -משמעי הוא דקדוק חופשי הקשר עבורו קיימת מחרוזת שיכולה להיות בעלת יותר מגזירה אחת השמאלית ביותר ואילו דקדוק חד -משמעי הוא דקדוק ללא הקשר שלכל מחרוזת תקפה יש גזירה ייחודית ביותר משמאל.

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

דקדוק דו משמעי, דקדוק חד משמעי

מהי דקדוק מעורפל

אומרים שדקדוק הוא דו -משמעי אם קיימות שתי נגזרות או יותר למחרוזת.

איור 1: דקדוק מעורפל

נניח כי יש דקדוק המוגדר כדלקמן.

G = ({S}, {a+b,+, *}, P, S}. כללי הייצור הם כדלקמן. S -> S+S | S *S | a | b. נניח כי נדרש צור את המחרוזת a+ a*b.

שקול, S -> S+S

החלפת 'א' ברוב S נותנת את הדברים הבאים.

S-> a +S

החלפת S*S ב- S היא כדלקמן.

S-> a + S*S

החלפת 'a' בשמאל S ביותר תיתן את הפלט שלהלן.

S -> a+ a*S

החלפת 'b' ב- S תיתן את הפלט הבא.

S -> a + a * b

זוהי המחרוזת הנדרשת ליצירה.

כאשר משתמשים בכלל הייצור האחר, זה ייתן

S -> S* S

החל S+S בצד שמאל ביותר S ייתן את הדברים הבאים.

S -> S+S * S

תחליף 'א' עבור רוב השמאליים S,

S -> a + S*S

החלפת 'א' עבור רוב השמאליים S,

S -> a + a * S

החלפת 'b' ב- S תיתן את הפלט הבא.

S -> a + a*b

שוב, הוא יצר את המחרוזת הנדרשת. לכן, יש יותר מנגזרת אחת ליצירת המחרוזת. לכן, מדובר בדקדוק לא ברור.

מהי דקדוק חד משמעי

בדקדוק דו -משמעי, למחרוזת מסוימת יש נגזרת ייחודית השמאלית ביותר. עיין בכללי הייצור הבאים.

S -> L | a, L -> LS | ס

שקול את חוק S -> L. תחליף LS במקום L.

S -> LS

מחליף S, הראשון של L.

S -> S S

החלפת 'a' ב- S השמאלית ביותר תיתן את הפלט שלהלן.

S -> א S

החלפת 'a' עבור S תתן את הדברים הבאים.

S -> א א

לכן, למחרוזת יש גזירה ייחודית השמאלית ביותר. אם כן, מדובר בדקדוק חד משמעי.

ההבדל בין דקדוק חד משמעי וחד משמעי

הַגדָרָה

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

מספר הגזרות השמאליות ביותר

בדקדוק דו -משמעי, למחרוזת יכולות להיות שתי נגזרות שמאלה או יותר, אך בדקדוק חד -משמעי, למחרוזת יש גזירה ייחודית השמאלית ביותר.

סיכום

דקדוק ללא הקשר יכול להיות דו -משמעי או חד -משמעי. ההבדל בין דקדוק דו -משמעי וחד משמעי הוא שהדקדוק הדו -משמעי הוא דקדוק חופשי שלקשר קיימת מחרוזת שיכולה להיות לה יותר מנגזרת אחת השמאלית ביותר ואילו דקדוק חד -משמעי הוא דקדוק ללא הקשר שלכל מחרוזת תקפה יש נגזרת ייחודית משמאל ביותר..

התייחסות:

1. "דקדוק מעורפל". ויקיפדיה, קרן ויקימדיה, 17 ביולי 2018, זמין כאן.2. “עיצוב מהדר | דקדוק מעורפל. " GeeksforGeeks, 10 בפברואר 2018, זמין כאן.3. "דקדוק מעורפל", האקדמיה של נסו, 29 במרץ 2017, זמין כאן.

באדיבות התמונה:

1. "Leftmostderivations jaredwf" מאת Jaredwf בויקיפדיה האנגלית - הועבר מ- en.wikipedia ל- Commons על ידי EdwardHades (Public Domain) באמצעות Commons Wikimedia