כל מתכנת מתחיל נתקל בצורך לפענח שפות פשוטות בשלב מאוד מוקדם בקריירה שלו, הנה כמה דוגמאות לשפות פשוטות:
key1=value1
key2=value2
key3=another value
הטקסט שלמעלה הוא טקסט בשפה של קבצי Properties בג'אווה.
לא קשה לכתוב קוד בסיסי שמפענח אותו (נעזוב לרגע את זה שלא צריך לכתוב כזה כי המחלקה Properties יודעת לקרוא את זה):
private static void parse(BufferedReader reader) throws IOException
{
String line = null;
while ((line = reader.readLine()) != null)
{
StringTokenizer tok = new StringTokenizer(line, "=");
String key = tok.nextToken();
String value = tok.nextToken();
System.err.println("Read: key = " + key + ", value = " + value);
}
}
פשוט מספיק, נכון?
אבל השפה מכילה גם הערות, שאפשר שאפשר לציין באמצעות סימן #. כל מה שאחרי ה# מוגדר כהערה.
הקוד הקודם לא מתמודד עם זה – ולמרות שזה לא מסובך במיוחד להוסיף את זה, זה טיפה יותר קשה ממה שזה נראה במבט ראשון כי יש כל מני מקרים:
* האם ההערה היא בתחילת השורה? (מתעלמים מכל השורה).
* האם ההערה היא בסוף השורה? (השורה מכילה זוג ערכים וגם הערה).
עוד דבר אפשרי הוא לשבור שורה באמצע:
key1=ABC\
DEFG
פה יש רק ערך אחד לפי החוקים של השפה.
וזה לא הכל, יש עוד כמה עיזים שמסבכים את הטיפול בקלט הזה.
הקוד שקורא את השפה הזו שבמחלקה Propertis הסטנדרטית בג'אווה הוא בערך באורך של 50 שורות.
יחסית ארוך בשביל משהו כל כך פשוט, לא?
כששפה מסתבכת יותר העסק נהיה הרבה יותר מורכב ועדין מזה, אם קריאה של שפה כל כך פשוטה צריכה 50 שורות קוד, מה יעשה מי שצריך לבנות קומפיילר או שפת שאילתות מורכבת?
יש תאוריה ענפה מסביב לניתוח תחבירי וסמנטי של שפות פורמליות, ויש כלים טובים שעוזרים לפתור את הבעיה.
בגדול הרעיון הוא להגדיר את התחביר בצורה פורמלית, ולייצר ממנו בצורה אוטומטית קוד שמשמש לקריאה של קלט בשפה.
העסק לא פשוט, ודורש רקע תאורטי באוטומטים ושפות פורמליות (שכלול בכל תואר במדעי המחשב), אבל למרות מחיר הכניסה הגבוה שצריך לשלם כדי לשלוט בכלים האלו, זה בהחלט שווה את זה.
בגדול, יש חלוקה כזו:
חלק ראשון הוא המנתח הלקסיקלי, שמקבל זרם תווים, ומוציא זרם של לקסמות, הידועים גם כאסימונים (Tokens). האסימונים מוגדרים באמצעות ביטויים רגולריים (שפה דומה לשפה שמשמשת את grep).
חלק שני הוא המנתח התחבירי, שמקבל זרם של אסימונים מהמנתח הלקסיקלי, ומוציא עץ תחביר אבסטרקטי (Abstract syntax tree).
יש כלים שיודעים לקבל הגדות לקסיקליות ותחבירות, ולייצר מזה בצורה אוטומטית קוד שיודע לפענח קלט בשםה הנתונה. למעשה, הטכניקה המקובלת לכתיבת קומפיילרים כבר עשרות שנים מתבססת על כלים אוטומטיים כאלו.
את הPreprocessor של אנטנה כתבתי תוך שימוש בantlr, שהוא כלי כזה שכתוב בג'אווה, אבל יודע לייצר קוד במגוון שפות, ובקורס קומפילציה שאני לוקח כרגע בפתוחה לומדים להשתמש בכלים הקלאסיים – flex וbison.
לדעתי antlr הרבה יותר סימפטי לעבודה.
אם תהיה דרישה אני ארחיב עוד בנושא.
זה נושא מעניין ביותר. אני מגיב לפני שקראתי את הפוסט לעומקו.
בסקריפטים שיצרתי מידי פעם גם אני הייתי צריך לפנעח דברים (קובץ קונפיגורציה).
הדרך הפשוטה לעשות את זה היא:
להגדיר תחביר בסיסי.
לפענח את התחביר הבסיסי.
לא להגדיר מה קורה במקרה של קובץ (קונפיגורציה נניח) שאינו תואם את התחביר הבסיסי…
כלומר, אם "המשתמש" (מי שיצר את הקונפיגורציה) רשם את התחביר בצורה לא נכונה, כל תוצאה עלולה להתקבל (אני פשוט לא בודק את זה).
ברור לי שזו לא שיטה, וקומפיירלים זה עולם אחר לחלוטין: שם אתה גם צריך לוודא שהתוצאה תואמת את ההגדרה של התחביר, וגם שהתחביר בקובץ תואם את כללי התחביר. וכמובן שהתחביר מורכב הרבה הרבה יותר (סי ++? ג'אווה? פרל???). מה גם שאתה צריך להגדיר תחביר גמיש (אפשור תוויים לבנים למשל).
טוב. זו הייתה בעיקרה הערה.
קריאה מומלצת
http://www.defmacro.org/ramblings/lisp-in-haskell.html
תודה, אני אעיף מבט.
עמרי, עוד משהו, אשמח לשמוע את דעתך ממש בקצרה:
לא קראתי עדיין את הקישור לכלים bisoni ו- flex. אעשה זאת. מעבר לכך ששמעתי את השם, אני לא יודע על הכלים האלה שום דבר.
אני רוצה לומר לך איך אני "תופס" אותם אחרי שקראתי את הפוסט המעניין שלך:
כמו שביטויים רגולריים/כלים לשימוש בביטויים רגולריים (שם עברי שאני מעדיף: ביטויי תבנית) משמשים לחילוץ/עיבוד תתי מחרוזות המתאימות לתבנית מסויימת, האם זה נכון לומר שהכלים האלה הם הרחבה של ב"ר המשמשים לחילוץ מחרוזות המתאימות לתבנית מורכבת יותר (תחביר) ולאיתור הערכים השונים המרכיבים אותן על פי תפקידם?
למשל: איתור הגדרת המשתנה הזו:
int a = 5;
ואיתור ערכי החלקים: "int" הטיפוס, "a" שם המשתנה, "5" ערך המשתנה (לא במקרה רשמתי כמחרוזות).
אם כן, מבחינתי הייתי יכול להשתמש בזה למשל כדי להגדיר ולפענח קבצי קונפיגורציה, או כדי לשמור מבני נתונים בקובץ טקסי. אם כי זה די מיותר: אם אני צריך קובץ קונפיקורציה או נתונים שאינו טריויאלי, אז אני יכול להשתמש ב- XML: כל שפת תיסרוט מודרנית תומכת בה, וגם כל שפת תיכנות.
(מה גם שלדעתי שווה לעבוד עם הכלי/ספרייה SQLite, שאני צריך להתחיל ללמוד. זה כלי מעולה שאתה בוודאי מכיר).
יהונתן, כן ולא.
בגדול הגדרות תחביר מאפשרות לעשות מה שאמרת, אבל הן יותר חזקות מזה.
בדוגמא שלך, אפשר להשתמש בביטוי רגולרי כדי לתפוס את כל ההגדרה של המשתנה, אבל יש דברים שפשוט אי אפשר לתפוס בעזרת ביטוי רגולרי (אוטומט סופי דטרמיניסטי).
הדוגמא הקלאסית היא ביטוי שבו הסוגריים תואמות, X סוגריים פותחות משמאל וX
סוגריים סוגרות מימין, אבל יש משפחה שלמה של ביטויים כאלו.
אז לשאלתך, כן – Parser generators בהחלט מתאימים ליצירת קוד שמפענח קבצי קונפיגורציה.
עמרי,
ראשית, תודה רבה על התשובה. שנית, לזה בדיוק התכוונתי: ברור לי שביטויים רגולריים אי אפשר לעשות הכל. אני מתייחס לביטויים הרגולריים כתת קבוצה של התחבירים (כל ביטוי רגולרי הוא גם תחביר, אבל לא בהכרך להיפך). אבל אני מסכים שהדוגמה לא הייתה טובה. היה עלי לבחור דוגמה אחרת, רק שאני לא יודע באופן פורמלי מה אפשרי עם ב"ר ומה עם כלי תחביר, אני רק יודע שתחביר רחב יותר. עם ביטויים רגולריים יש לי ניסיון מעשי רב, ואני יודע מה אי אפשר להשיג באמצעותם. ספציפית, אני מכיר ב"ר ברמה של VIM (וכמובן אחרים בשינויי תחביר קלים), אבל לפי מה שאמרו לי יש גם 'משוכללים' יותר, למשל כאלה המאפשרים שימוש בתנאים (conditionals).
מה שכן, התייחסתי יותר לצד המעשי, להשתמש ב- bson ו- flex ככלים (לא חשוב באיזו צורת מימוש). אח"כ נכנסתי גם למאמר שהצגת, ואני מבין שהכלים האלה פועלים רק על קוד של שפה אחרת. אני לא יודע אם הם כלים בפני עצמם, שאפשר להשתמש בהם כמו שמשתמשים בביטויים רגולריים. לדוגמה: האם כמו ש- Perl תומכת באופן מובנה בביטויים רגולריים, האם היא גם תומכת בכלים האלה? באופן אינטואיטיבי התשובה היא לא, ויתכן גם שהשימוש בהם מורכב מידי מכדי להיות כליי תיסרוט או פיתוח מהיר יעילים.
יונתן,
לא ידוע לי על שימוש בכלים האלו כמשהו זריז כמו גרפ.
השימוש בהם מורכב ומערב יצירת קוד אוטומטית.
אוקיי עמרי, תודה רבה.
לא לשכוח את JavaCC ונגזרותיו שעושים עבודה מצויינת בתחום הזה (הקלט הוא הגדרת השפה והפלט מחלקות JAVA שיודעות לפרסס אותה ומאפשרות גם hookingבכל שלב).
ויטלי, האמת היא שניסיתי את JavaCC ומצאתי את Antlr כהרבה יותר נוח.