חודש: יוני 2007

כל מתכנת מתחיל נתקל בצורך לפענח שפות פשוטות בשלב מאוד מוקדם בקריירה שלו, הנה כמה דוגמאות לשפות פשוטות:

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 הרבה יותר סימפטי לעבודה.

אם תהיה דרישה אני ארחיב עוד בנושא.