מהדרים: מה ההבדל בין מנתחי LL (0) ו- LR (0). האם יש דבר כמו מנתחי LL (0)?


תשובה 1:

נראה כי שאלה זו ממוקדת בנתחי LL (0), אז בואו נגדיר אותם. מנתח LL (0), מנתח משמאל לימין באמצעות 0 אסימונים בתחילת הייצור כדי לקבוע איזו ייצור יש להחיל. מה המשמעות של 0 סמלים זה אומר שהמנתח אינו יכול להשתמש בטקסט המנותח כדי לקבוע איזו ייצור יש להחיל. המשמעות היא שהנתח לא יכול לבצע בחירות. עליו לדעת לפני שהוא מתחיל לנתח בדיוק את רצף האסימונים שהוא ינתח. יש לתקן את רצף האסימונים, מה שאומר שיכול להיות רק רצף אחד שהנתח ינתח. לפיכך, ייתכן שיהיה לך מנתח שמקבל "שלום עולם!" עם דקדוק כזה:

המטרה: סימן קריאה "שלום" מרחב הלבן "העולם";

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

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

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

המטרה: שלום חלק חלק סוף סוף;

שלום חלק: hello1;

hello1: "שלום";

סוף-חלק: חלק אחר-עולם אחרון;

חלק עולמי: "עולם";

חלק אחרון: "!";

עם זאת, שימו לב כיצד לאף אחד מהכללים אין מפעילי "או" (|) ויש כלל אחד בלבד לכל טרמינל. זה מה שמאפשר לנתח לדעת להתאים לכל כלל מבלי להשתמש באסימונים מפלים (אסימונים הבוחרים לאיזה כיוון הולך המנתח), מה שהופך את הדקדוק LL (0).

עכשיו, האם ניתן להשתמש בהפקה רקורסיבית ועדיין יש לך דקדוק LL (0)? התשובה היא "לא". בוא נראה מה יקרה אם יש לנו כלל רקורסיבי.

המטרה: "x" המטרה "y";

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

לפיכך, דקדוק LL (0) חייב לנתח רשימה סופית של אסימונים, בדיוק רשימה סופית אחת (אותה רשימה בכל פעם).

שימו לב להבדל למשמעות LR (0). מנתח LR (k) רשאי להשתמש בכל אסימונים (רבים ככל שהוא אוהב) בתוך הפקה כדי להבחין, פלוס עד k אסימונים מההקשר כאשר הייצור מפחית כדי לקבוע אם עליו להפחית. במקרה של LR (0), הוא לא יכול להשתמש באסימונים נוספים כדי לקבוע אם עליו להפחית. עליו פשוט להחליט על סמך אסימוני הכלל המופחתים. להלן דקדוק LR (0):

המטרה: "x" | "(" מטרה ")";

דקדוק זה מנתח "x" המוקף במספר סוגריים של סוגריים. שים לב שהוא יכול להשתמש באסימון "x" ובאסימון "(" כדי להחליט איזה כלל להחיל. ה- 0 ב- LR (0) אינו מגביל את השימוש באסימונים בתוך כלל, כמו שה- 0 ב- LL (0) עושה. הדבר היחיד שהוא מגביל הוא השימוש באסימונים (של הקשר, אחרי הכלל בשימוש מסוים בלא הטרמינל) כאשר מחליטים לצמצם. הדקדוק הזה לא צריך שום הקשר בכדי להחליט לצמצם. "x" בשנייה שהוא מצמצם אחרי שראה ")". האסימונים בתוך כלל קובעים בדיוק מתי הכלל אמור לצמצם.


תשובה 2:

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

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