Αγγλική Εισαγωγή- English Introduction



Εισαγωγικές Έννοιες 

Οι γραμματικές τις οποίες χειρίζεται το παρόν εργαλείο ακολουθούν την BNF τυποποίηση με τη διαφορά ότι, για λόγους τόσο απλότητας όσο και συμβατότητας με περαιτέρω επεκτάσεις του, προτιμήθηκε η χρήση της σημειολογίας του μέτα-μεταγλωττιστή YACC (Yet Another Compiler-Compiler). Αυτή η απόφαση οφείλεται στην καθολική αποδοχή του YACC στο χώρο της Πληροφορικής.

Τα σύμβολα μιας γραμματικής διακρίνονται σε τερματικά και μη ως εξής:

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

E : E + T | T 

T : T * F | F 

F : ( E ) | id 

E : E + T 

E : T 

T : T * F 

T : F 

F : ( E ) 

F : id 

Στο παράδειγμα αυτό, τα τερματικά σύμβολα είναι τα: {+, *, (, ), id}. Τα μη τερματικά σύμβολα είναι τα: {E, T, F}, ενώ το αρχικό σύμβολο είναι το E (δηλαδή το αρχικό σύμβολο είναι το αριστερό μέρος του πρώτου κανόνα).

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

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

Υπάρχει η γενική αρχή ότι σύμβολα που εμφανίζονται στο αριστερό μέρος ενός κανόνα γίνονται αποδεκτά μόνον εφόσον έχουν παρουσιαστεί στο δεξί μέρος προηγούμενου κανόνα.

Για πρακτικούς λόγους, επιβάλλεται ο διαχωρισμός των συμβόλων με ένα τουλάχιστον κενό. Αυτό γίνεται προκειμένου το εργαλείο να είναι σε θέση να διακρίνει τα σύμβολα της γραμματικής. Εξάλλου, οι παραγωγές μιας γραμματικής γίνονται αποδεκτές για περαιτέρω διερεύνηση μόνον εφόσον είναι ομαδοποιημένες σε κανόνες. Η κενή συμβολοσειρά συμβολίζεται με το null.

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

Grammar Symbols Recognition-Syntax Tree-Left Productions

Ιδιότητες και Μετατροπές μιας Γραμματικής  

Μια γραμματική είναι αριστερά αναδρομική όταν έχει ένα μη τερματικό A τέτοιο ώστε να μπορεί να παραχθεί μέσω μίας (άμεση αναδρομή) ή περισσοτέρων (έμμεση αναδρομή) παραγωγών η συμβολοσειρά Α α, με α μια οποιαδήποτε συμβολοσειρά. Αν α είναι η κενή συμβολοσειρά, τότε η αναδρομή λέγεται κύκλος. Στην περίπτωση γραμματικών χωρίς κύκλους υπάρχει η δυνατότητα απαλοιφής των αναδρομών.

Η αριστερή παραγοντοποίηση είναι μια μετατροπή χρήσιμη για τη δημιουργία μιας γραμματικής κατάλληλης για συντακτική ανάλυση.

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

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

Grammar Properties & Transformations

Λειτουργία Συντακτικού Αναλυτή με Πρόβλεψη  

Αφού αναγνωριστούν οι παραπάνω ιδιότητες και εφαρμοστούν οι αντίστοιχες μετατροπές στη γραμματική που εξετάζουμε, είναι δυνατό να εξεταστεί αν μία συμβολοσειρά μπορεί να παραχθεί από τη γραμματική. Αυτόν το σκοπό αναλαμβάνει να υπηρετήσει ο συντακτικός αναλυτής με πρόβλεψη με τη βοήθεια του πίνακα συντακτικής ανάλυσης, ενός διδιάστατου πίνακα M[A,α] (A μη τερματικό, α τερματικό).

Το εργαλείο δίνει στο χρήστη τη δυνατότητα να εξετάσει αν μία συμβολοσειρά μπορεί να παραχθεί από την εξεταζόμενη γραμματική, αν δηλαδή ανήκει στη γλώσσα που η γραμματική αυτή περιγράφει.

Predictive Parser Operation

Δημιουργία Πίνακα Συντακτικής Ανάλυσης  

Ο πίνακας συντακτικής ανάλυσης M κατασκευάζεται βάσει των τιμών δύο συναρτήσεων, της FIRST και της FOLLOW.

Aν α είναι μια σειρά συμβόλων της γραμματικής, τότε η FIRST(α) είναι το σύνολο των τερματικών με τα οποία αρχίζουν οι συμβολοσειρές που προκύπτουν από το α. Αν από το α μπορεί να προκύψει η κενή συμβολοσειρά, τότε και αυτή ανήκει στη FIRST(α).

Η FOLLOW(A), για A μη τερματικό, είναι το σύνολο των τερματικών που μπορούν να εμφανιστούν αμέσως δεξιά του A, δηλαδή το σύνολο των τερματικών α για το οποίο μπορεί μια σειρά παραγωγών με αρχή το αρχικό σύμβολο να καταλήγει σε συμβολοσειρά της μορφής α A α β, για κάποια α και β. Αν είναι δυνατό το A να είναι το δεξιότερο σύμβολο σε κάποια προτασιακή μορφή, τότε το σύμβολο $ ανήκει στη FOLLOW(A).

Τόσο ο υπολογισμός των τιμών των δύο συναρτήσεων FIRST και FOLLOW όσο και η κατασκευή του πίνακα M μέσω αυτών περιγράφονται διεξοδικά από το εργαλείο.

Daveloping & Exploring Grammars

Βασίλης Αποστολόπουλος - Θάνος Βαρειάς - Νικόλαος Θεοχάρης 
Νοέμβριος 1998

Τα παραπάνω στοιχεία αντλήθηκαν από το βιβλίο "Compilers: Principles, Techniques and Tools" των Aho, Sethi και Ullman, γνωστό στους "μυημένους" και σαν dragonbook. 
Το εργαλείο που περιγράφεται δημιουργήθηκε από τους τρις υπογράφοντες από τον Οκτώβριο του 1996 ως  τον Νοέμβριο του 1998, στα πλαίσια πτυχιακής εργασίας υπό την επίβλεψη και (κυρίως) συνεργασία του Επίκουρου Καθηγητή του Πανεπιστημίου Αθηνών κυρίου Γιάννη Κοτρώνη και την ανεκτίμητη τεχνική συμβολή και συμπαράσταση του Υποψήφιου Διδάκτορα Πανεπιστημίου Αθηνών Δημήτρη Θεοτόκη .