מחפש lex ו- yacc עבור Java? אתה לא מכיר את ג'ק

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

ייצור מנתח אוטומטי של המהדר

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

בעבודתי "האמיתית" הראשונה לאחר הלימודים בקולג 'קיבלתי שפה ליצירת שפת עיבוד גרפיקה חדשה להרכבה לפקודות עבור מעבד גרפי. התחלתי בדקדוק שהורכב טרי והתכונן לצאת לפרויקט רב השבועי של הרכבת מהדר. ואז חבר הראה לי את ה- lex ו- yacc של Unix . לקס בנה מנתחים לקסיקלים מביטויים רגולריים, ו- yacc הפחיתה מפרט דקדוק למהדר מונע טבלה שיכול לייצר קוד כאשר הוא ניתח בהצלחה הפקות מאותה דקדוק. השתמשתי ב- lex ו- yacc, ותוך פחות משבוע המהדר שלי התחיל לפעול! מאוחר יותר, פרויקט GNU של קרן התוכנה החופשית ייצר גרסאות "משופרות" של lex ו- yacc - המכונות flex and bison - לשימוש בפלטפורמות שלא הפעילו נגזרת של מערכת ההפעלה יוניקס.

העולם של ייצור המנתחים האוטומטי התקדם שוב כאשר טרנס פאר, אז סטודנט מאוניברסיטת פורדו, יצר את ערכת כלי הבנייה של Purdue Compiler או PCCTS. שני רכיבים של PCCTS - DFA ו- ANTLR - מספקים את אותן פונקציות כמו lex ו- yacc ; אולם הדקדוקים שמקבלים ANTLR הם דקדוקי LL (k) בניגוד לדקדוקי LALR המשמשים את yacc . יתר על כן, הקוד שמייצר PCCTS הוא הרבה יותר קריא מהקוד שנוצר על ידי yacc. על ידי יצירת קוד קל יותר לקריאה, PCCTS מקל על האדם הקורא את הקוד להבין מה החלקים השונים עושים. הבנה זו יכולה להיות חיונית כשמנסים לאבחן שגיאות במפרט הדקדוק. PCCTS פיתחה במהירות אנשים הבאים שמצאו את הקבצים שלה יותר קלים לשימוש מאשר yacc.

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

ג'ק עולה אל הצלחת

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

ג'ק (מתחרז עם yacc) הוא מחולל מנתחים, ברוח PCCTS, ש- Sun הוציאה בחינם לקהילת התכנות של Java. ג'ק הוא כלי קל במיוחד לתיאור: במילים פשוטות, אתה נותן לו סט כללים דקדוקיים ומשולבים בצורת קובץ .jack ומריץ את הכלי, והוא מחזיר לך מחלקת Java שתנתח את הדקדוק הזה. מה יכול להיות קל יותר?

השגת ג'ק היא גם די קלה. ראשית אתה מוריד עותק מדף הבית של ג'ק. זה מגיע אליך בצורה של מחלקת Java פריקה עצמית שנקראת install. כדי להתקין ג'ק אתה צריך להפעיל את זה installבכיתה, אשר, על מכונת 95 Windows נעשית באמצעות הפקודה: C:>java install.

הפקודה המוצגת לעיל מניחה כי javaהפקודה נמצאת בנתיב הפקודה שלך ושביל הכיתה הוגדר כראוי. אם הפקודה שלעיל לא פעלה, או אם אינך בטוח אם הדברים מוגדרים כהלכה או לא, פתח חלון MS-DOS על ידי חציית פריטי התפריט Start-> Programs-> MS-DOS Prompt. אם התקנת את Sun JDK, תוכל להקליד את הפקודות הבאות:

C:> נתיב C: \ java \ bin;% נתיב% C:> קבע CLASSPATH = .; c: \ java \ lib \ classes.zip 

אם מותקן סימנטק קפה גרסה 1.2 ואילך, תוכל להקליד את הפקודות הבאות:

C:> נתיב C: \ cafe \ java \ bin;% path% 

את נתיב הכיתה כבר צריך להגדיר בקובץ שנקרא sc.ini בספריית הפח של קפה.

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

באמצעות ג'ק

ג'ק כתוב כולו בג'אווה, ולכן קיום שיעורי הג'ק אומר שכלי זה זמין באופן מיידי בכל פלטפורמה התומכת במכונה הווירטואלית של ג'אווה. עם זאת, המשמעות היא שגם בתיבות Windows עליכם להריץ את ג'ק משורת הפקודה. נניח שבחרת בשם הספריה JavaTools כאשר התקנת את ג'ק במערכת שלך. כדי להשתמש בג'ק יהיה עליך להוסיף את השיעורים של ג'ק לנתיב הכיתה שלך. אתה יכול לעשות זאת בקובץ autoexec.bat או בקובץ .cshrc שלך אם אתה משתמש ב- Unix. הפקודה הקריטית דומה לשורה המוצגת להלן:

C:> הגדר CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ classes.zip 

שים לב שמשתמשי Symantec Cafe יכולים לערוך את קובץ sc.ini ולכלול שם את מחלקות ה- Jack, או שהם יכולים להגדיר CLASSPATHבמפורש כפי שמוצג לעיל.

הגדרת משתנה הסביבה כפי שמוצג לעיל מציבה את שיעורי הג'ק CLASSPATHבין "." (הספריה הנוכחית) ושיעורי המערכת הבסיסיים עבור Java. המעמד העיקרי עבור ג'ק הוא COM.sun.labs.jack.Main. היוון חשוב! יש בדיוק ארבע אותיות גדולות בפקודה ('C', 'O', 'M' ועוד 'M'). כדי להפעיל את ג'ק באופן ידני, הקלד את הפקודה:

C:> java COM.sun.labs.jack.Main -parser-input.jack

אם אין לך את קבצי ה- Jack בנתיב הכיתה שלך, תוכל להשתמש בפקודה זו:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ classes.zip COM.sun.labs.jack.Manager-input.jack 

כפי שאתה יכול לראות, זה נעשה קצת ארוך. כדי למזער את ההקלדה, הכנסתי את הקריאה לקובץ .bat בשם Jack.bat . בשלב כלשהו בעתיד, תכנית גלישת C פשוטה תהיה זמינה, אולי אפילו כשתקרא את זה. עיין בדף הבית של ג'ק לגבי הזמינות של תוכנות אלה ותוכניות אחרות.

כאשר ג'ק מופעל, הוא יוצר מספר קבצים בספרייה הנוכחית שאותם תחבר אחר כך למנתח שלך. לרוב קידומת שם המנתח שלך או שהם משותפים לכל המנתחים. אולם אחד מהם ASCII_CharStream.javaעשוי להתנגש בניתוחים אחרים, כך שככל הנראה רעיון טוב להתחיל בספריה המכילה רק את קובץ ה- jack שבו אתה הולך להשתמש כדי ליצור את המנתח.

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

C:> javac -d. ParserName.java

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

C:> javac * .java 

זה יקבץ את כל מה שבספריה. בשלב זה המנתח החדש שלך מוכן לשימוש.

תיאור מנתח ג'ק

לקבצי תיאור המנתח של ג'ק יש את הסיומת .jack והם מחולקים לשלושה חלקים בסיסיים: אפשרויות ומחלקת בסיס; אסימונים מילוניים; ולא מסופים. בואו נסתכל על תיאור מנתח פשוט (זה כלול בספריית הדוגמאות שמגיעה עם ג'ק).

אפשרויות {LOOKAHEAD = 1; } PARSER_BEGIN ( Simple1 ) מחלקה ציבורית Simple1 {public static void main (String args []) זורק ParseError { Simple1 parser = new Simple1 (System.in); parser.Input (); }} PARSER_END ( Simple1 )

השורות הראשונות לעיל מתארות אפשרויות לניתוח; במקרה זה LOOKAHEAD מוגדר ל- 1. ישנן אפשרויות אחרות, כגון אבחון, טיפול ב- Java Unicode, וכן הלאה, שגם ניתן להגדיר כאן. בעקבות האפשרויות מגיע מחלקת הבסיס של המנתח. שני התגים PARSER_BEGIN ו- PARSER_END סוגרים למחלקה שהופכת לקוד Java הבסיסי עבור המנתח שהתקבל. שים לב ששם הכיתה המשמש במפרט המנתח חייב להיות זהה בחלק ההתחלתי, האמצעי והסיום של סעיף זה. בדוגמה שלמעלה שמתי את שם הכיתה בפנים מודגשים כדי להבהיר זאת. כפי שניתן לראות בקוד לעיל, מחלקה זו מגדירה סטטיmainשיטה כך שניתן יהיה להפעיל את המחלקה על ידי מתורגמן Java בשורת הפקודה. mainהשיטה פשוט instantiates מנתח חדש עם זרם קלט (במקרה זה System.in) ולאחר מכן מפעילה את Inputהשיטה. Inputהשיטה היא מסוף-אי הדקדוק שלנו, והוא מוגדר בצורה של אלמנט EBNF. EBNF מייצג טופס Backus-Naur מורחב. צורת Backus-Naur היא שיטה לציון דקדוקים ללא הקשר. המפרט כולל מסוף בצד שמאל, סמל הפקה, שהוא בדרך כלל ":: =", והפקה אחת או יותר בצד ימין. הסימון המשמש הוא בדרך כלל משהו כזה:

מילת מפתח :: = " אם " | " ואז " | " אחר "

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

קלט ריק (): {} {MatchedBraces () "\ n"} voidBraces matched (): {} {"{" [MatchedBraces ()] "}"} 

מנתח פשוט זה מנתח את הדקדוק המוצג להלן:

קֶלֶט :: = בריסים מותאמים " \ n "
התאמת ברזלים :: = "{" [ MatchedBraces ] "}"

I've used italics to show the non-terminals on the right side of the productions and boldface to show literals. As you can see, the grammar simply parses matched sets of brace "{" and "}" characters. There are two productions in the Jack file to describe this grammar. The first terminal, Input, is defined by this definition to be three items in sequence: a MatchedBraces terminal, a newline character, and an end-of-file token. The token is defined by Jack so that you don't have to specify it for your platform.

When this grammar is generated, the left-hand sides of the productions are turned into methods inside the Simple1 class; when compiled, the Simple1 class reads characters from System.in and verifies that they contain a matching set of braces. This is accomplished by invoking the generated method Input, which is transformed by the generation process into a method that parses an Input non-terminal. If the parse fails, the method throws the exception ParseError, which the main routine can catch and then complain about if it so chooses.

Of course there's more. The block delineated by "{" and "}" after the terminal name -- which is empty in this example -- can contain arbitrary Java code that is inserted at the front of the generated method. Then, after each expansion, there is another optional block that can contain arbitrary Java code to be executed when the parser successfully matches that expansion.

A more complicated example

So how about an example that's a bit more complicated? Consider the following grammar, again broken down into pieces. This grammar is designed to interpret mathematical equations using the four basic operators -- addition, multiplication, subtraction, and division. The source can be found here:

options { LOOKAHEAD=1; } PARSER_BEGIN(Calc1) public class Calc1 { public static void main(String args[]) throws ParseError { Calc1 parser = new Calc1(System.in); while (true) { System.out.print("Enter Expression: "); System.out.flush(); try { switch (parser.one_line()) { case -1: System.exit(0); default: break; } } catch (ParseError x) { System.out.println("Exiting."); throw x; } } } } PARSER_END(Calc1) 

The first part is nearly the same as Simple1, except that the main routine now calls the terminal one_line repeatedly until it fails to parse. Next comes the following code:

IGNORE_IN_BNF : {}  " "  TOKEN : { } {  } TOKEN : /* OPERATORS */ { }    TOKEN : { }    

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