Ψάχνετε για lex και yacc για Java; Δεν ξέρεις τον Τζακ

Η Sun κυκλοφόρησε τον Jack, ένα νέο εργαλείο γραμμένο στην Java, το οποίο δημιουργεί αυτόματα προγράμματα ανάλυσης, καταρτίζοντας προδιαγραφές γραμματικής υψηλού επιπέδου που είναι αποθηκευμένες σε ένα αρχείο κειμένου. Αυτό το άρθρο θα χρησιμεύσει ως εισαγωγή σε αυτό το νέο εργαλείο. Το πρώτο μέρος του άρθρου καλύπτει μια σύντομη εισαγωγή στην αυτόματη δημιουργία αναλυτών και τις πρώτες μου εμπειρίες μαζί τους. Στη συνέχεια, το άρθρο θα επικεντρωθεί στον Jack και πώς μπορείτε να το χρησιμοποιήσετε για να δημιουργήσετε προγράμματα ανάλυσης και εφαρμογές που έχουν δημιουργηθεί με αυτούς τους αναλυτές, βάσει της γραμματικής σας υψηλού επιπέδου.

Αυτόματη δημιουργία αναλυτή μεταγλωττιστή

Ο αναλυτής είναι ένα από τα πιο κοινά στοιχεία μιας εφαρμογής υπολογιστή. Μετατρέπει κείμενο που μπορεί να διαβαστεί από τον άνθρωπο σε δομές δεδομένων γνωστές ως αναλυτικά δέντρα, τα οποία κατανοούνται από τον υπολογιστή. Θυμάμαι ξεκάθαρα την εισαγωγή μου στην αυτόματη παραγωγή αναλυτών: Στο κολέγιο είχα ολοκληρώσει ένα μάθημα για την κατασκευή μεταγλωττιστή. Με τη βοήθεια της συζύγου μου, είχα γράψει έναν απλό μεταγλωττιστή που θα μπορούσε να μετατρέψει προγράμματα γραμμένα σε μια γλώσσα που αποτελείται από την τάξη σε εκτελέσιμα προγράμματα. Θυμάμαι ότι είμαι πολύ πετυχημένος εκείνο το σημείο.

Στην πρώτη μου «πραγματική» δουλειά μετά το κολέγιο, πήρα τη δέσμευση να δημιουργήσω μια νέα γλώσσα επεξεργασίας γραφικών για να μεταγλωττίσω εντολές για έναν συνεπεξεργαστή γραφικών. Ξεκίνησα με μια φρέσκια γραμματική και ετοιμάστηκα να ξεκινήσω στο έργο πολλών εβδομάδων για τη δημιουργία ενός μεταγλωττιστή. Τότε ένας φίλος μου έδειξε τα βοηθητικά προγράμματα Unix lex και yacc. Λέξ χτίστηκε λεξικά αναλυτές από κανονικές εκφράσεις, και yacc μείωσε μια προδιαγραφή γραμματικής σε έναν μεταγλωττιστή βάσει πινάκων που θα μπορούσε να παράγει κώδικα όταν είχε αναλύσει επιτυχώς τις παραγωγές από αυτήν τη γραμματική. χρησιμοποίησα lex και yacc, και σε λιγότερο από μία εβδομάδα ο μεταγλωττιστής μου τέθηκε σε λειτουργία! Αργότερα, το έργο GNU του Free Software Foundation παρήγαγε "βελτιωμένες" εκδόσεις του lex και yacc - ονομάστηκε καλώδιο και βόνασος - για χρήση σε πλατφόρμες που δεν εκτελούσαν παράγωγο του λειτουργικού συστήματος Unix.

Ο κόσμος της αυτόματης δημιουργίας parser προχώρησε ξανά όταν ο Terrence Parr, τότε φοιτητής στο Πανεπιστήμιο Purdue, δημιούργησε το Purdue Compiler Construction Tool Set ή PCCTS. Δύο συστατικά PCCTS - DFA και ANTLR - παρέχουν τις ίδιες λειτουργίες με lex και yacc; Ωστόσο, οι γραμματικές που ANTLR δέχεται είναι γραμματικές LL (k) σε αντίθεση με τις γραμματικές LALR που χρησιμοποιούνται από yacc. Επιπλέον, ο κώδικας που δημιουργεί το PCCTS είναι πολύ πιο αναγνώσιμος από τον κώδικα που δημιουργείται από yacc. Δημιουργώντας έναν κώδικα που είναι ευκολότερο να διαβαστεί, το PCCTS διευκολύνει τον άνθρωπο να διαβάσει τον κώδικα να κατανοήσει τι κάνουν τα διάφορα κομμάτια. Αυτή η κατανόηση μπορεί να είναι απαραίτητη κατά την προσπάθεια διάγνωσης σφαλμάτων στις προδιαγραφές γραμματικής. Το PCCTS ανέπτυξε γρήγορα έναν αριθμό ατόμων που βρήκαν τα αρχεία του πιο εύκολο στη χρήση yacc.

Η ισχύς της αυτόματης δημιουργίας αναλυτών είναι ότι επιτρέπει στους χρήστες να επικεντρώνονται στη γραμματική και να μην ανησυχούν για την ορθότητα της εφαρμογής. Αυτό μπορεί να είναι μια τεράστια εξοικονόμηση χρόνου τόσο σε απλά όσο και σε πολύπλοκα έργα.

Ο Τζακ ανεβαίνει μέχρι το πιάτο

Βαθμολογώ τα εργαλεία βάσει της γενικότητας του προβλήματος που επιλύουν. Καθώς η απαίτηση ανάλυσης της εισαγωγής κειμένου εμφανίζεται ξανά και ξανά, η αυτόματη παραγωγή αναλυτών ρυθμίζει αρκετά στην εργαλειοθήκη μου. Σε συνδυασμό με τον γρήγορο κύκλο ανάπτυξης της Java, η αυτόματη δημιουργία αναλυτών παρέχει ένα εργαλείο για το σχεδιασμό μεταγλωττιστή που είναι δύσκολο να νικήσει.

Ο Jack (rhymes with yacc) είναι μια γεννήτρια ανάλυσης, στο πνεύμα των PCCTS, που η Sun κυκλοφόρησε δωρεάν στην κοινότητα προγραμματισμού Java. Ο Τζακ είναι ένα εξαιρετικά εύκολο εργαλείο για να το περιγράψετε: Με απλά λόγια, του δίνετε ένα σύνολο συνδυασμένων γραμματικών και λεξικών κανόνων με τη μορφή αρχείου .jack και εκτελείτε το εργαλείο και σας δίνει πίσω μια τάξη Java που θα αναλύσει αυτήν τη γραμματική. Τι θα μπορούσε να είναι ευκολότερο;

Η απόκτηση του Jack είναι επίσης πολύ εύκολη. Πρώτα κατεβάζετε ένα αντίγραφο από την αρχική σελίδα του Jack. Αυτό έρχεται σε εσάς με τη μορφή μιας αυτο-αποσυσκευασμένης κατηγορίας Java που ονομάζεται εγκαθιστώ. Για να εγκαταστήσετε το Jack πρέπει να το επικαλέσετε αυτό εγκαθιστώ κλάση, η οποία, σε έναν υπολογιστή Windows 95 γίνεται χρησιμοποιώντας την εντολή: C:> εγκατάσταση java.

Η παραπάνω εντολή προϋποθέτει ότι το Ιάβα Η εντολή βρίσκεται στη διαδρομή εντολών σας και ότι η διαδρομή κλάσης έχει ρυθμιστεί κατάλληλα. Εάν η παραπάνω εντολή δεν λειτούργησε ή εάν δεν είστε σίγουροι αν έχετε ρυθμίσει σωστά τα πράγματα, ανοίξτε ένα παράθυρο MS-DOS διασχίζοντας τα στοιχεία μενού Έναρξη-> Προγράμματα-> MS-DOS Prompt. Εάν έχετε εγκαταστήσει το Sun JDK, μπορείτε να πληκτρολογήσετε αυτές τις εντολές:

C:> διαδρομή C: \ java \ bin;% path% C:> set CLASSPATH = .; c: \ java \ lib \ class.zip 

Εάν είναι εγκατεστημένο το Symantec Cafe έκδοση 1.2 ή μεταγενέστερη, μπορείτε να πληκτρολογήσετε αυτές τις εντολές:

C:> διαδρομή C: \ cafe \ java \ bin;% διαδρομή% 

Η διαδρομή τάξης πρέπει να έχει ήδη ρυθμιστεί σε ένα αρχείο που ονομάζεται sc.ini στον κατάλογο δοχείων του Cafe.

Στη συνέχεια, πληκτρολογήστε το εγκατάσταση java εντολή από ψηλά. Το πρόγραμμα εγκατάστασης θα σας ρωτήσει σε ποιον κατάλογο θέλετε να εγκαταστήσετε και ο υποκατάλογος Jack θα δημιουργηθεί κάτω από αυτόν.

Χρησιμοποιώντας τον Τζακ

Το Jack είναι γραμμένο εξ ολοκλήρου στην Java, οπότε η ύπαρξη τάξεων Jack σημαίνει ότι αυτό το εργαλείο είναι άμεσα διαθέσιμο σε κάθε πλατφόρμα που υποστηρίζει την εικονική μηχανή Java. Ωστόσο, αυτό σημαίνει επίσης ότι στα παράθυρα των Windows πρέπει να εκτελέσετε τον Jack από τη γραμμή εντολών. Ας υποθέσουμε ότι επιλέξατε το όνομα καταλόγου JavaTools όταν εγκαταστήσατε το Jack στο σύστημά σας. Για να χρησιμοποιήσετε τον Τζακ θα πρέπει να προσθέσετε τα μαθήματα του Τζακ στη διαδρομή της τάξης σας. Μπορείτε να το κάνετε αυτό στο autoexec.bat αρχείο ή στο δικό σας .cshrc αρχείο εάν είστε χρήστης του Unix. Η κρίσιμη εντολή μοιάζει με τη γραμμή που φαίνεται παρακάτω:

C:> set CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ class.zip 

Σημειώστε ότι οι χρήστες του Symantec Cafe μπορούν να επεξεργαστούν το sc.ini αρχειοθετήστε και συμπεριλάβετε τις τάξεις Jack εκεί, ή μπορούν να ορίσουν CLASSPATH ρητά όπως φαίνεται παραπάνω.

Η ρύθμιση της μεταβλητής περιβάλλοντος όπως φαίνεται παραπάνω τοποθετεί τις τάξεις Jack στο CLASSPATH μεταξύ "." (ο τρέχων κατάλογος) και οι βασικές κλάσεις συστήματος για Java. Η κύρια κατηγορία για τον Jack είναι COM.sun.labs.jack. Κύρια. Η κεφαλαιοποίηση είναι σημαντική! Υπάρχουν ακριβώς τέσσερα κεφαλαία γράμματα στην εντολή ("C", "O", "M" και ένα άλλο "M"). Για να εκτελέσετε χειροκίνητα τον Jack, πληκτρολογήστε την εντολή:

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

Εάν δεν έχετε τα αρχεία Jack στη διαδρομή της τάξης σας, μπορείτε να χρησιμοποιήσετε αυτήν την εντολή:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ class.zip COM.sun.labs.jack. Κύριο parser-input.jack 

Όπως μπορείτε να δείτε, αυτό καθυστερεί λίγο. Για να ελαχιστοποιήσω την πληκτρολόγηση, έβαλα την επίκληση σε ένα .νυχτερίδα όνομα αρχείου Jack.bat. Σε κάποιο σημείο στο μέλλον, ένα απλό πρόγραμμα περιτύλιξης C θα είναι διαθέσιμο, ίσως ακόμη και όταν το διαβάσετε. Ελέγξτε την αρχική σελίδα του Jack για τη διαθεσιμότητα αυτού και άλλων προγραμμάτων.

Όταν εκτελείται ο Jack, δημιουργεί πολλά αρχεία στον τρέχοντα κατάλογο που θα μεταγλωττίσετε αργότερα στον αναλυτή σας. Τα περισσότερα είτε προτίθενται με το όνομα του προγράμματος ανάλυσης είτε είναι κοινά για όλους τους αναλυτές. Ένα από αυτά, ωστόσο, ASCII_CharStream.java, μπορεί να συγκρουστεί με άλλους αναλυτές, οπότε είναι πιθανώς καλή ιδέα να ξεκινήσετε σε έναν κατάλογο που περιέχει μόνο το .γρύλος αρχείο που πρόκειται να χρησιμοποιήσετε για να δημιουργήσετε το πρόγραμμα ανάλυσης.

Μόλις εκτελέσετε τον Τζακ, εάν η γενιά έχει πάει ομαλά θα έχετε ένα σωρό .Ιάβα αρχεία στον τρέχοντα κατάλογο με διάφορα ενδιαφέροντα ονόματα. Αυτοί είναι οι αναλυτές σας. Σας ενθαρρύνω να τα ανοίξετε με έναν συντάκτη και να τα κοιτάξετε. Όταν είστε έτοιμοι μπορείτε να τους μεταγλωττίσετε με την εντολή

C:> javac -d. ParserName.java

όπου Όνομα Parser είναι το όνομα που δώσατε το πρόγραμμα ανάλυσης στο αρχείο εισαγωγής. Περισσότερα σχετικά με αυτό σε λίγο. Εάν όλα τα αρχεία του προγράμματος ανάλυσης δεν μεταγλωττιστούν, μπορείτε να χρησιμοποιήσετε τη μέθοδο πληκτρολόγησης brute force:

C:> javac * .java 

Αυτό θα συγκεντρώσει τα πάντα στον κατάλογο. Σε αυτό το σημείο ο νέος αναλυτής σας είναι έτοιμος για χρήση.

Περιγραφές αναλυτών Jack

Τα αρχεία περιγραφής Jack parser έχουν την επέκταση .γρύλος και χωρίζονται σε τρία βασικά μέρη: επιλογές και βασική κλάση. λεξικά κουπόνια; και μη τερματικά. Ας δούμε μια απλή περιγραφή αναλυτή (αυτό περιλαμβάνεται στο παραδείγματα κατάλογο που συνοδεύει τον Jack).

επιλογές {LOOKAHEAD = 1; } PARSER_BEGIN (Απλόδημόσια τάξη Απλό {public static void main (String args []) ρίχνει το ParseError { Απλό parser = νέο Απλό(System.in); parser.Input (); }} PARSER_END (Απλό) 

Οι πρώτες λίγες γραμμές παραπάνω περιγράφουν επιλογές για το πρόγραμμα ανάλυσης. σε αυτήν την περίπτωση ΚΟΙΤΑΞΟΥΜΕ ΜΠΡΟΣΤΑ έχει οριστεί σε 1. Υπάρχουν άλλες επιλογές, όπως διαγνωστικά, χειρισμός Java Unicode και ούτω καθεξής, που μπορούν επίσης να οριστούν εδώ. Ακολουθώντας τις επιλογές έρχεται η βασική κλάση του αναλυτή. Οι δύο ετικέτες PARSER_BEGIN και PARSER_END bracket την κλάση που γίνεται ο βασικός κώδικας Java για τον αναλυτή που προκύπτει. Σημειώστε ότι το όνομα κλάσης που χρησιμοποιείται στην προδιαγραφή αναλυτή πρέπει να είναι το ίδιο στην αρχή, στη μέση και στο τέλος αυτού του τμήματος. Στο παραπάνω παράδειγμα, έβαλα το όνομα της τάξης σε έντονα πρόσωπα για να το καταστήσω σαφές. Όπως μπορείτε να δείτε στον παραπάνω κώδικα, αυτή η τάξη ορίζει ένα στατικό κύριος μέθοδος έτσι ώστε η τάξη να μπορεί να καλείται από τον διερμηνέα Java στη γραμμή εντολών. ο κύριος Η μέθοδος απλώς δημιουργεί έναν νέο αναλυτή με μια ροή εισόδου (σε αυτήν την περίπτωση System.inκαι στη συνέχεια επικαλείται το Εισαγωγή μέθοδος. ο Εισαγωγή Η μέθοδος είναι μη τερματική στη γραμματική μας και ορίζεται με τη μορφή ενός στοιχείου EBNF. Το EBNF σημαίνει Extended Backus-Naur Form. Η φόρμα Backus-Naur είναι μια μέθοδος για τον καθορισμό γραμματικών χωρίς περιβάλλον. Η προδιαγραφή αποτελείται από ένα τερματικό στην αριστερή πλευρά, ένα σύμβολο παραγωγής, το οποίο είναι συνήθως ":: =" και ένα ή περισσότερα παραγωγές στη δεξιά πλευρά. Η σημειογραφία που χρησιμοποιείται είναι συνήθως κάτι σαν αυτό:

 Λέξη-κλειδί :: = "αν" | "έπειτα" | "αλλού" 

Αυτό θα διαβαστεί ως, "Το Λέξη-κλειδί Το τερματικό είναι μία από τις συμβολοσειρές συμβολοσειράς «εάν», «τότε» ή «αλλιώς». "Στο Τζακ, αυτή η φόρμα επεκτείνεται για να επιτρέπει στο αριστερό μέρος να αντιπροσωπεύεται από μια μέθοδο και οι εναλλακτικές επεκτάσεις μπορεί να αντιπροσωπεύονται από κανονικές εκφράσεις ή άλλα μη τερματικά. Συνεχίζοντας με το απλό μας παράδειγμα, το αρχείο περιέχει τους ακόλουθους ορισμούς:

void Input (): {} {MatchedBraces () "\ n"} void MatchedBraces (): {} {"{" [MatchedBraces ()] "}"} 

Αυτός ο απλός αναλυτής αναλύει τη γραμματική που φαίνεται παρακάτω:

Έχω χρησιμοποιήσει πλάγια γράμματα για να δείξω τα μη τερματικά στη δεξιά πλευρά των παραγωγών και το έντονο για να δείξω τα γράμματα. Όπως μπορείτε να δείτε, η γραμματική αναλύει απλά ταιριαστά σύνολα χαρακτήρων "{" και "}". Υπάρχουν δύο παραγωγές στο αρχείο Jack για την περιγραφή αυτής της γραμματικής. Το πρώτο τερματικό, Εισαγωγή, ορίζεται από αυτόν τον ορισμό ως τρία στοιχεία διαδοχικά: α Αντιστοιχισμένα στηρίγματα τερματικό, έναν χαρακτήρα νέας γραμμής και ένα διακριτικό στο τέλος του αρχείου. ο Το token ορίζεται από τον Jack έτσι ώστε να μην χρειάζεται να το καθορίσετε για την πλατφόρμα σας.

Όταν δημιουργείται αυτή η γραμματική, οι αριστερές πλευρές των παραγωγών μετατρέπονται σε μεθόδους μέσα στο Απλό τάξη; κατά τη σύνταξη, το Απλό τάξη διαβάζει χαρακτήρες από Σύστημα.σε και επαληθεύει ότι περιέχουν ένα αντίστοιχο σύνολο στηριγμάτων. Αυτό επιτυγχάνεται με την επίκληση της δημιουργούμενης μεθόδου Εισαγωγή, η οποία μετατρέπεται από τη διαδικασία δημιουργίας σε μια μέθοδο που αναλύει ένα Εισαγωγή μη τερματικό. Εάν η ανάλυση αποτύχει, η μέθοδος ρίχνει την εξαίρεση ParseError, την οποία μπορεί να πιάσει η κύρια ρουτίνα και μετά να διαμαρτύρεται αν το επιλέξει.

Φυσικά υπάρχουν περισσότερα. Το μπλοκ που οριοθετείται με "{" και "}" μετά το όνομα του τερματικού - το οποίο είναι κενό σε αυτό το παράδειγμα - μπορεί να περιέχει αυθαίρετο κώδικα Java που εισάγεται στο μπροστινό μέρος της δημιουργημένης μεθόδου. Στη συνέχεια, μετά από κάθε επέκταση, υπάρχει ένα άλλο προαιρετικό μπλοκ που μπορεί να περιέχει αυθαίρετο κώδικα Java που θα εκτελεστεί όταν ο αναλυτής ταιριάζει με επιτυχία με αυτήν την επέκταση.

Ένα πιο περίπλοκο παράδειγμα

Λοιπόν, τι γίνεται με ένα παράδειγμα που είναι λίγο πιο περίπλοκο; Σκεφτείτε την ακόλουθη γραμματική, και πάλι χωρισμένη σε κομμάτια. Αυτή η γραμματική έχει σχεδιαστεί για να ερμηνεύει μαθηματικές εξισώσεις χρησιμοποιώντας τους τέσσερις βασικούς τελεστές - προσθήκη, πολλαπλασιασμό, αφαίρεση και διαίρεση. Η πηγή μπορεί να βρεθεί εδώ:

επιλογές {LOOKAHEAD = 1; } PARSER_BEGIN (Calc1) δημόσια τάξη Calc1 {public static void main (String args []) ρίχνει ParseError {Calc1 parser = new Calc1 (System.in); ενώ (true) {System.out.print ("Enter Expression:"); System.out.flush (); δοκιμάστε το {switch (parser.one_line ()) {case -1: System.exit (0); προεπιλογή: break; }} catch (ParseError x) {System.out.println ("Έξοδος."); ρίξτε x; }}}} PARSER_END (Υπολογισμός 1) 

Το πρώτο μέρος είναι σχεδόν το ίδιο με Απλό, εκτός από το ότι η κύρια ρουτίνα καλεί τώρα το τερματικό μία γραμμή επανειλημμένα μέχρι να αποτύχει η ανάλυση. Στη συνέχεια έρχεται ο ακόλουθος κωδικός:

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

Αυτοί οι ορισμοί καλύπτουν τα βασικά τερματικά στα οποία καθορίζεται η γραμματική. Το πρώτο, που ονομάζεται IGNORE_IN_BNF, είναι ένα ειδικό διακριτικό. Τυχόν διακριτικά που διαβάζονται από τον αναλυτή που ταιριάζουν με τους χαρακτήρες που ορίζονται στο IGNORE_IN_BNF το διακριτικό απορρίπτεται σιωπηλά. Όπως μπορείτε να δείτε στο παράδειγμά μας, αυτό αναγκάζει τον αναλυτή να αγνοήσει χαρακτήρες διαστήματος, καρτέλες και χαρακτήρες επιστροφής μεταφοράς στην είσοδο.