Σχεδίαση και υλοποίηση ενός μεταγλωττιστή για τη γλώσσα MiniJava (ένα μικρό υποσύνολο της Java)

Για την υλοποίηση του μεταγλωττιστή θα χρησιμοποιηθούν τα εργαλεία JavaCC και JTB

Η υλοποίηση όλων των επιπέδων του project (homework 2-6) θα γίνει σε Java με χρήση visitor pattern

Εργασία 6 - Παραγωγή τελικού κώδικα MIPS από Kanga

Σ'αυτό το στάδιο της εργασίας θα μεταφράσετε τον κώδικα Kanga σε κώδικα assembly της οικογένειας επεξεργαστών MIPS. Οι καταχωρητές του MIPS είναι ακριβώς αυτοί που χρησιμοποιεί η Kanga για τις μεταβλητές της. Πρακτικά θα πρέπει να μετονομάσετε τις εντολές της Kanga σε κανονικές εντολές του MIPS. Οι καταχωρητές του MIPS που σας ενδιαφέρουν μαζί με τις συμβάσεις χρήσεις τους είναι οι:

• $0 : Έχει πάντα την τιμή 0
• $t0 - $t9 : Δεν διατηρούνται μετά από call
• $s0 - $s7 : Διατηρούνται μετά από call
• $v0 : Χρησιμοποιείται για τιμή επιστροφής
• $v1 : Χρησιμοποιείστε το συμβατικά για αντιγραφή από ένα μέρος της στοίβας σε άλλο
• $a0 - $a3 : Χρησιμοποιούνται για πέρασμα ορισμάτων
• $sp : Δείκτης στην κορυφή της στοίβας
• $ra : Διεύθυνση επιστροφής

Εργασία 5 - Παραγωγή ενδιάμεσου κώδικα Kanga από Spiglet

Σ'αυτό το στάδιο της εργασίας θα μεταφράσετε τον κώδικα Spiglet σε μια ακόμα χαμηλότερου επιπέδου ενδιάμεση μορφή που θα την πούμε Kanga. Η Kanga είναι μια γλώσσα σαν τη Spiglet αλλά πιο κοντά στα συγκεκριμένα χαρακτηριστικά της αρχιτεκτονικής MIPS. Οι αλλαγές από τη Spiglet στην Kanga είναι οι εξής:

• Η Kanga υποστηρίζει σχόλια της μορφής της C
• Τα labels πλέον δουλεύουν σωστά σαν global και όχι μόνο σε local scope.
• Αντί για απεριόριστο αριθμό προσωρινών τοπικών μεταβλητών, η Kanga έχει 24 καταχωρητές ολικής εμβέλειας (global scope). Οι καταχωρητές s0-s7 και t0-t9 μπορούν να χρησιμοποιηθούν για οτιδήποτε. Οι καταχωρητές a0-a3 χρησιμοποιούνται μόνο για πέρασμα ορισμάτων κατά την κλήση συνάρτησης. Ο καταχωρητής v0 δεσμεύεται για επιστροφή αποτελέσματος από μια κλήση συνάρτησης, και οι v0 (επίσης) και v1 χρησιμοποιούνται σαν προσωρινοί καταχωρητές όταν χρειάζεται να γίνουν πράξεις μέσω τιμών που βρίσκονται στο stack.
• Οι τιμές φορτώνονται και γράφονται στο stack με τις εντολές ALOAD και ASTORE, όπου η έκφραση (SPILLEDARG i) αναφέρεται στην i-στη τιμή του stack, με την πρώτη τιμή στο (SPILLEDARG 0). Για παράδειγμα το "ALOAD s3 (SPILLEDARG 1)" φορτώνει τη δεύτερη τιμή από το stack στον καταχωρητή s3.
• Το σώμα μιας συνάρτησης δεν είναι πια StmtExp αλλά StmtList. Η τιμή επιστροφής πρέπει να μπει στον καταχωρητή v0.
• Το CALL είναι πια statement και όχι expression. Όπως είπαμε παραπάνω, οι καταχωρητές "a" χρησιμοποιούνται για ορίσματα. Αν υπάρχουν πάνω από 4 ορίσματα πρέπει να χρησιμοποιήσετε την εντολή PASSARG που σώζει επιπλέον ορίσματα στο stack. Η αρίθμηση του PASSARG ξεκινάει από το 1, ενώ του SPILLEDARG από το 0, άρα γενικά ένα όρισμα που περνάει σαν (PASSARG i) είναι ορατό στο σώμα της συνάρτησης σαν (SPILLEDARG i-1). Για παράδειγμα φανταστείτε ότι καλούμε μια συνάρτηση με label P, τιμές ορισμάτων στους καταχωρητές t1, t2, t3, t4 και t5, και θέλουμε η τιμή επιστροφής να μπει στον καταχωρητή t6:
  MOVE a0 t1 // πρώτα βάζουμε τις τιμές στους καταχωρητές ορισμάτων
  MOVE a1 t2
  MOVE a2 t3
  MOVE a3 t4
  PASSARG 1 t5 // πάνω από 4 ορίσματα μπαίνουν στο stack
  CALL P
  MOVE t6 v0 // τιμή επιστροφής
• Μια συνάρτηση έχει τρεις αριθμούς στην αρχή του ορισμού της, π.χ. "procA [5] [3] [4]". Ο πρώτος αριθμός έχει το ίδιο νόημα που είχε στη Spiglet, δηλαδή δίνει τον αριθμό ορισμάτων.
  Ο δεύτερος δίνει τον αριθμό θέσεων στο stack που χρειάζεται η συνάρτηση. Αυτός είναι συνολικός αριθμός και περιλαμβάνει χώρο για τα ορίσματα, αν χρειάζεται, για όποιες τοπικές μεταβλητές δεν αποθηκεύονται αποκλειστικά σε καταχωρητές και για όποιους καταχωρητές πρέπει να σωθούν.
  Ο τρίτος αριθμός είναι ο μέγιστος αριθμός ορισμάτων κλήσεων στο σώμα της procA. Αν π.χ. η procA καλεί την procB που παίρνει 3 ορίσματα, την procC που παίρνει 2 και την procD που παίρνει 4 ορίσματα, τότε αυτός ο αριθμός είναι 4.

Εδώ θα βρείτε τη γραμματική της Kanga (και σε μορφή javaCC), τα συνηθισμένα παραδείγματα προγραμμάτων σε μορφή Kanga και έναν interpreter για Kanga.

Εργασία 4 - Παραγωγή ενδιάμεσου κώδικα Spiglet από Piglet

Το επόμενο βήμα της εργασίας είναι να μεταφραστεί ο ενδιάμεσος κώδικας από τη μορφή Piglet σε κάτι ακόμα χαμηλότερου επιπέδου, που θα το ονομάσουμε Spiglet. Η Spiglet είναι γνήσιο υποσύνολο της Piglet. H γραμματική της Spiglet (σε μορφή javaCC εδώ) διαφέρει από αυτή της Piglet σε δύο σημεία:

• Το StmtExp δεν είναι Exp στη Spiglet.
• Σε πολλά σημεία αντί για Exp υπάρχει SimpleExp ή Temp.

Πρακτικά αυτό σημαίνει ότι πολλές εκφράσεις πρέπει να σπάσουν σε απλούστερη μορφή. Τα συνηθισμένα παραδείγματα προγραμμάτων σε Spiglet υπάρχουν εδώ (αντιστοιχούν στα παραδείγματα MiniJava). Μια και η Spiglet είναι υποσύνολο της Piglet, μπορείτε να χρησιμοποιήσετε τον ίδιο formatter και τον ίδιο interpreter όπως στην προηγούμενη εργασία. Αν θέλετε να επιβεβαιώσετε ότι ένα πρόγραμμα της Spiglet είναι πραγματικά νόμιμη Spiglet (και όχι απλά Piglet) μπορείτε να χρησιμοποιήσετε αυτόν τον parser γράφοντας "java -jar spp.jar < [Input-program]". Αν το πρόγραμμα είναι συντακτικά νόμιμη Spiglet, θα σας βγάλει το μήνυμα "Program parsed successfully".

Εργασία 3 - Παραγωγή ενδιάμεσου κώδικα Piglet από MiniJava

Σε αυτό το κομμάτι της εργασίας καλείστε να γράψετε visitors που να μετατρέπουν τον κώδικα MiniJava σε μια ενδιάμεση γλώσσα που θα ονομάσουμε Piglet. Τα περισσότερα στοιχεία της γλώσσας αυτής μπορείτε να τα καταλάβετε διαβάζοντας τη γραμματική της η οποία βρίσκεται σε μορφή BNF εδώ, σε μορφή javaCC βρίσκεται εδώ. Παρακάτω ακολουθούν μερικές επεξηγήσεις:

• Οι μέθοδοι ορίζονται ως "function_name [ arguments ]", έχουν ως ορίσματα τις προσωρινές μεταβλητές "TEMP 0", "TEMP 1" κλπ, και τα "TEMP x" χρησιμοποιούνται από εκεί και πέρα ως προσωρινές μεταβλητές, προσωρινές τιμές, υπολογισμό εκφράσεων κλπ.
• Η έκφραση "CALL expression ( expression_1 expression_2 ... expression_n )" καλεί τη συνάρτηση που βρίσκεται στη θέση μνήμης που είναι ίση με την τιμή του expression και της δίνει ως ορίσματα τις τιμές των expression_1, expression_2 κλπ. Κάθε κλήση συνάρτησης είναι δυναμική οπότε η θέση της συνάρτησης στη μνήμη είναι γνωστή μόνο κατά την ώρα της εκτέλεσης. Αποτέλεσμα της έκφρασης είναι και η τιμή που επιστρέφει η συνάρτηση.
• Η έκφραση "HALLOCATE expression" παίρνει ως αποτέλεσμα την (ακέραια) τιμή του expression και κάνει δυναμική δέσμευση μνήμης τόσων θέσεων. Τυπικά το expression θα έχει ως αποτέλεσμα κάποιο πολλαπλάσιο του 4, δεδομένου ότι και οι θέσεις μνήμης και οι ακέραιοι θεωρούμε ότι είναι 4 bytes. Κάθε φορά που δεσμεύετε ένα αντικείμενο θα πρέπει να δεσμεύσετε και το virtual table του, μπορείτε όμως να δεσμεύσετε από την αρχή στη main όσα virtual tables χρειάζονται και να τα αναθέτετε επιτόπου καθώς το virtual table είναι κοινό για όλες τα αντικείμενα (δυναμικά) ίδιας κλάσσης. Αποτέλεσμα της έκφρασης είναι η δεσμευμένη μνήμη.
• Η εντολή "MOVE temp expression" αποθηκεύει την τιμή της έκφρασης expression στην προσωρινή μεταβλητή temp (ένα "TEMP x").
• Η εντολή "HSTORE expression_1 integer_literal expression_2" αποθηκεύει στη θέση μνήμης expression_1 με offset integer_literal την τιμή του expression_2. Το offset χρησιμοποιείται και για να ορίσετε την τιμή σε ένα στοιχείο πίνακα αλλά και για να θέσετε τιμή σε οποιοδήποτε πεδίο κλάσσης.
• Η εντολή "HLOAD temp expression integer_literal" διαβάζει την τιμή της διεύθυνσης που δίνει η τιμή του expression με offset integer_literal στην προσωρινή μεταβλητή temp. Αυτό θα χρησιμοποιηθεί όχι μόνο για να διαβάζετε στοιχεία από πίνακες και πεδία κλάσσεων αλλά και για να καλείτε μεθόδους διαβάζοντας τη διεύθυνση τους από το virtual table.
• Η εντολή "JUMP label" κάνει άλμα στην ετικέτα label. Οι ετικέτες είναι μια θέση μνήμης πρακτικά και της θεωρούμε ακέραιες εκφράσεις με τιμή τη θέση μνήμης την οποία αφορούν.
• Η εντολή "CJUMP expression label" προχωράει στην επόμενη εντολή (branch not taken) μόνο αν η τιμή του expression είναι ακριβώς ίση με 1, αλλιώς κάνει άλμα στην ετικέτα label (branch taken).
• Η έκφραση "LT expression_1 expression_2" ελέγχει αν το expression_1 είναι μικρότερο του expression_2, και παρομοίως γράφονται τα PLUS, MINUS, TIMES που εκτελούν πρόσθεση αφαίρεση και πολλαπλασιαμό.
• Η γλώσσα επιτρέπει statement expression που είναι ένα σύνολο από εντολές που τελειώνουν με ένα return. Η συνολική τιμή του statement expression είναι και η τιμή της έκφρασης στο "RETURN expression". Τα statement expression ξεκινούν με "BEGIN" και τελειώνουν σε "END".
• Η εντολή "ERROR" τερματίζει το πρόγραμμα με κάποιο σφάλμα. Ένας πιθανός λόγος για να συμβεί αυτό είναι να ζητήσετε πρόσβαση σε αντικείμενο που δεν έχετε ακόμα δεσμεύσει. Στα πλαίσια της εργασίας είναι επιθυμητό να αρχικοποιείτε τις προσωρινές μεταβλητές που είναι αντικείμενα με το 0 (null) και στο access να γίνεται έλεγχος ότι το αντικείμενο είναι δεσμευμένο, όπως ο έλεγχος που κάνει η Java όταν πετάει NullException. Για να κάνετε τον έλεγχο ότι ένα αντικείμενο δεν είναι null θα χρησιμοποιήσετε την έκφραση "LT expression 1".
• Η εντολή "NOOP" δεν κάνει τίποτα.

Σε περίπτωση που δεν θυμάστε ή δεν έχετε δει πώς φτιάχνονται τα virtual tables, είναι μια δομή πίνακα στα πρώτα 4 bytes ενός αντικειμένου και ορίζει ένα offset για κάθε function. Η foo πχ. στο 0 και η bar στο 1 (με πραγματικό offset 4). Αν μια μέθοδος γίνει override μπαίνει στην ίδια θέση του virtual table με την προηγούμενη. Έτσι επιτυχάνεται η λειτουργικότητα του πολυμορφισμού. Αν θέλαμε να το παραστήσουμε σε C φανταστείτε ότι αν το αντικείμενο obj βρίσκεται στη θέση x και πάνω του καλούμε την foo που έχει virtual table offset ίσο με 3, θα καλεστεί η συνάρτηση που βρίσκεται στη θέση μνήμης x[0][12].

Πολλά πράγματα που ίσως παραλήφθηκαν μπορείτε να τα βρείτε διαβάζοντας τη γραμματική της piglet, είναι αρκετά μικρή και κατανοητή. Μπορείτε επίσης να κατανοήσετε τη μορφή της piglet βλέποντας τα παραδείγματα που δίνονται εδώ (αντιστοιχούν στα παραδείγματα MiniJava της προηγούμενης εργασίας). Μπορείτε να χρησιμοποιήσετε μαζί με τη javaCC γραμματική της Piglet αυτόν τον visitor για να δώσει "όμορφη" όψη στον κώδικα piglet που παράγετε. Πρακτικά θα βάλει tabs στον κώδικα piglet, ώστε να είναι πιο ευανάγωνστος. Επιπλέον μπορείτε να χρησιμοποιήσετε αυτό το πρόγραμμα για να "εκτελέσετε" την piglet και να δείτε αν παράγει σωστά αποτελέσματα. Τα σωστά αποτελέσματα μπορείτε να τα δείτε συγκρίνοντας την έξοδο που δίνει ο javac και η java με την έξοδο που βγάζει αφού το κάνετε piglet και το "περάσετε" μέσα από αυτό το piglet execute "platform".

Εργασία 2 - Σημασιολογικός έλεγχος MiniJava

Με τη δεύτερη εργασία ξεκινάει το project του εξαμήνου που είναι η κατασκευή ενός μεταγλωττιστή για τη MiniJava, ένα υποσύνολο της Java. Η MiniJava έχει σχεδιαστεί έτσι ώστε να μπορεί να μεταγλωττιστεί κανονικά από έναν java compiler όπως ο javac.

Ακολουθεί μερική περιγραφή της γλώσσας με λόγια που μπορείτε και να την αγνοήσετε (μια και όλα αυτά φαίνονται και στη γραμματική ή συνεπάγονται από την απαίτηση ότι κάθε πρόγραμμα MiniJava είναι και πρόγραμμα Java):

• Η MiniJava είναι πλήρως αντικειμενοστρεφής όπως η Java, δεν επιτρέπει global συναρτήσεις, μόνο κλάσεις, πεδία και μέθοδοι. Οι βασικοί τύποι είναι ο int, ο boolean και ο int[] που είναι ένας πίνακας από int. Έπειτα μπορείτε να χτίσετε κλάσεις που περιέχουν πεδία από αυτούς τους βασικούς τύπους ή άλλες κλάσεις. Οι κλάσεις περιέχουν μέσα μεθόδους με ορίσματα απλούς τύπους ή κλάσεις κλπ.
• Η MiniJava υποστηρίζει απλή κληρονομικότητα αλλά όχι interfaces. Επιπλέον δεν υποστηρίζει overloading που σημαίνει ότι κάθε όνομα μεθόδου πρέπει να είναι μοναδικό. Επιπλέον όλες οι μέθοδοι είναι εξ ορισμού πολυμορφικές, ή αλλιώς το γνωστό virtual από τη C++. Αυτό σημαίνει ότι η foo μπορεί να οριστεί στην υποκλάση αν έχει ίδια ορίσματα και τύπο επιστροφής με την γονική, αλλά αν υπάρχει στη γονική με άλλα ορίσματα ή τύπο επιστροφής, τότε είναι σφάλμα. Επίσης όλες οι μέθοδοι πρέπει να έχουν τύπο επιστροφής, δεν υπάρχουν void μέθοδοι. Τα πεδία μπορούν να έχουν ίδια ονόματα σε base και derived class και πρόκειται πρακτικά για διαφορετικά πεδία.
• Η MiniJava περιορίζει όλες τις μεθόδους σε public και όλα τα πεδία σε protected. Μια κλάση δε μπορεί σε καμία μέθοδο να δει πεδίο άλλης κλάσης, εκτός αν πρόκειται για υπερ-κλάση. Μπορεί να δει μόνο μεθόδους. Τις δικές τις μεθόδους τις καλεί με τη βοήθεια του this. Το this.foo(5) καλεί τη δική της foo, το a.foo(5) καλεί του αντικειμένου a. Οι τοπικές μεταβλητές ορίζονται μόνο στην αρχή μιας μεθόδου και όχι ενδιάμεσα. Απαγορεύεται να επαναμβάνεται ένα όνομα μεταξύ τοπικών μεταβλητών και απαγορεύεται να επαναλαμβάνεται μεταξύ πεδίων. Μια τοπική μεταβλητή x όμως έχει προτεραιότητα από ένα πεδίο x της κλάσης της μεθόδου και πρακτικά την επισκιάζει.
• Η MiniJava δεν ορίζει constructors και destructors, ορίζει τον τελεστή new να λειτουργεί σαν default void constructor. Επιπλέον δεν υπάρχουν inner classes και δεν υπάρχουν στατικές μέθοδοι ή δεδομένα. Κατ' εξαίρεση στατική θεωρείται η μέθοδος main για την οποία έχουμε ειδικό χειρισμό μέσω της γραμματικής. Τα προγράμματα MiniJava πρακτικά είναι ένα αρχείο που ξεκινά με ειδική κλάση που περιέχει τη μέθοδο main και συγκεκριμένα ορίσματα, τα οποία θα παραβλέπετε γιατί δεν υπάρχει τύπος String, ούτε String[], αφού δεν υπάρχουν πίνακες κλάσεων. Η κλάση αυτή δεν έχει πεδία. Μετά ορίζονται οι υπόλοιπες κλάσεις που μπορούν να έχουν ελεύθερα πεδία και μεθόδους.
• Μερικά σημεία που θα πρέπει να προσέξετε είναι ότι μια κλάση A μπορεί να περιέχει ένα πεδίου τύπου B, που το B είναι μια κλάση που ορίζεται αργότερα στο αρχείο. Όμως όταν έχουμε "class B extends A", τότε η A πρέπει να έχει οριστεί πριν τη B στο αρχείο. Όπως θα παρατηρήσετε από τη γραμματική της η MiniJava έχει πολύ απλούς τρόπους για να φτιάχνονται expressions και από τελεστές σύγκρισης επιτρέπει μόνο το <. Δεν υποστηρίζει λίστες πράξεων, πχ. 1+2+3 αλλά επιτρέπει προφανώς να καλούνται μέθοδοι αντικειμένων με ορίσματα, να χρησιμοποιούνται οι τύποι επιστροφής για άλλα expressions κλπ. Από λογικούς τελεστές επιτρέπει το λογικό and "&&" και το λογικό not "!". Επιτρέπεται η εκχώρηση και ο τελεστής [ ] για τους int πίνακες και η έκφραση a.length που επιστρέφει το μέγεθος του πίνακα a. Τέλος έχουμε προτάσεις while και if που ακολουθούνται αναγκαστικά από κάποιο else. Τέλος προφανώς η εκχώρηση "A a = new B();" όταν ισχύει B extends A είναι σωστή και το ίδιο ισχύει όταν μια μέθοδος περιμένει όρισμα τύπου A και της δίνεται στοιχείο τύπου B.

Η γραμματική της MiniJava σε BNF υπάρχει εδώ. Μπορείτε να κάνετε μικρές αλλαγές στη γραμματική, αν θέλετε να αναλύσετε παραπάνω κάποιους γραμματικούς κανόνες αλλά θα πρέπει να αναγνωρίζετε σωστά όσα αναγνωρίζει η MiniJava και να μην αναγνωρίζετε ως σωστό κάτι που αναγνωρίζει ως λάθος η κανονική java, αλλά κάτι τέτοιο δε σας το συνιστούμε, καθώς θα κάνετε τρομακτικά δυσκολότερη τη δουλειά σας στα επόμενα κομμάτια, αν θέλετε να κάνετε τον compiler σας καλύτερο από τον ζητούμενο. Κανονικά όμως δε χρειάζεται να πειράξετε τη γραμματική. Επιπλέον πολλά στοιχεία της γλώσσας που πιθανώς παραλείψαμε στην εκφώνηση, πρέπει να είστε σε θέση να τα εξάγετε διαβάζοντας τη γραμματική της γλώσσας. Κάποια πράγματα δίνονται έτοιμα, πχ. τα σχόλια αφαιρούνται κατά την λεκτική ανάλυση.

Σας δίνεται η γραμματική της MiniJava και σε μορφή JavaCC εδώ. Θα χρησιμοποιήσετε το εργαλείο JTB για να τη μετατρέψετε σε γραμματική που παράγει ιεραρχίες κλάσεων. Έπειτα θα γράψετε έναν ή περισσότερους visitors που θα κάνουν έλεγχο πάνω στο αρχείο MiniJava και θα λένε αν είναι σημασιολογικά σωστό, αλλιώς θα τυπώνουν error. Δε είναι απαραίτητο ο compiler να εξηγεί ακριβώς τι error συνάντησε και θα τερματίζει απευθείας στο πρώτο error, χωρίς να κοιτάει για άλλα. Το κυριότερο είναι να μην προσπερνάτε errors και να μην βγάζετε errors σε σωστά προγράμματα.

Οι visitors που θα φτιάξετε θα πρέπει να είναι subclasses των visitors που ορίζει το JTB, αλλά μπορούν να περιέχουν πεδία και μεθόδους, ώστε να κρατάτε πληροφορία κατά τη διάρκεια του ελέγχου, να μεταφέρετε πληροφορία από έναν visitor στον επόμενο κλπ. Τελικά θα έχετε μια Main κλάση που θα εκτελεί τη σημασιολογική ανάλυση ξεκινώντας, τον parser που παρήγαγε το JavaCC και τρέχοντας τους visitors που φτιάξατε. Παραδίδετε το αρχείο της γραμματικής, αν δεν κάνετε αλλαγές πάνω του, αλλιώς παραδίδετε τον κώδικα του project, αυτόν που παρήγαγε ο JavaCC και ο JTB και μαζί και τις δικές σας κλάσεις που υλοποιούν τους visitors κλπ. και μια Main. Η Main σας πρέπει να κάνει parse και semantic check σε όλα τα MiniJava αρχεία που δίνονται ως ορίσματα και να τυπώνει για καθένα αν ήταν σωστό ή όχι.

Θα υπάρξει tutorial για τη χρήση του JavaCC και του JTB καθώς και στην κατασκευή visitors στο lab. Επίσης μπορείτε να χρησιμοποιήσετε αυτά τα αρχεία για να τεστάρετε το πρόγραμμά σας. Προφανώς μπορείτε και είναι και θεμιτό να φτιάξετε και δικά σας αρχεία, η βαθμολογία της άσκησης θα κριθεί καθαρά και μόνο από το πώς τα πήγε ο compiler σας στο σύνολο αρχείων που θα τον δοκιμάσουμε, δηλαδή σε αυτά που σας δίνονται και πιθανώς σε κάποια άλλα δικά μας που δε θα σας δώσουμε. Μπορείτε να μοιραστείτε ιδέες και test files αν θέλετε, αλλά προφανώς δε μπορείτε να μοιραστείτε κώδικα. Οι αντιγραφές θα μηδενίζονται. Be righteous λοιπόν, καλή αρχή στη MiniJava και τον compiler and may the Force be with you!

Εργασία 1 - Calculator grammar

• exp -> num | exp op exp | (exp)
• op -> + | - | * | /
• num -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

1. Αρχικά θα πρέπει να φτιάξετε στο χαρτί (και να παραδώσετε σε ένα .txt ή .pdf αρχείο) σύνολα FIRST & FOLLOW για την LL(1) γραμματική του calculator, όπως την τροποποιήσατε. Στο τέλος θα τα συνοψίσετε σε έναν ενιαίο πίνακα lookahead.


2. Στη συνέχεια πρέπει να γράψετε έναν recursive descent parser σε Java που να διαβάζει εκφράσεις και να τις βγάζει στην έξοδο με μορφή postfix ή να τυπώνει "parse error" αν υπάρχει συντακτικό σφάλμα. Στα πλαίσια αυτού του προγράμματος δεν μας ενδιαφέρει να αναγνωρίζετε κενά ή διψήφιους και πάνω αριθμούς. Μπορείτε να θεωρήσετε ότι διαβάζετε τα σύμβολα ένα ένα (όπως μια getchar σε C). Η έκφραση θα πρέπει να τελειώνει με αλλαγή γραμμής ή EOF.


3. Για το τρίτο μέρος θα γράψετε μια LR γραμματική για έναν calculator στο εργαλείο sableCC. Ο calculator πρέπει να υποστηρίζει τις ίδιες 4 πράξεις αλλά εδώ θα πρέπει να κάνετε κανονική λεκτική ανάλυση, δηλαδή να αγνοείτε κενά και να δέχεστε (μη αρνητικούς ακέραιους) αριθμούς οποιουδήποτε μήκους. Το πρόγραμμα αυτό απλά θα αναγνωρίζει αν η έκφραση είναι σωστή, δεν θα την τυπώνει σε κάποια μορφή.