[Αυτό το κείμενο απευθυνόταν αρχικά στους σπουδαστές που παρακολουθούσαν το μάθημα "Μεταγλωττιστές" το ακαδημαϊκό έτος 2001-02.] ΠΟΛΛΑ SHIFT/REDUCE ΚΑΙ REDUCE/REDUCE CONFLICTS ΣΤΟ ΣΥΝΤΑΚΤΙΚΟ ΑΝΑΛΥΤΗ ΤΗΣ PCL Νίκος Παπασπύρου (nickie@softlab.ntua.gr) 30 Απριλίου 2002 Όπως αρκετές ομάδες παρατήρησαν, η απευθείας υλοποίηση της γραμματικής της PCL στο bison οδηγεί σε ένα μεγάλο αριθμό απο reduce/reduce conflicts (ή shift/reduce, στην καλύτερη περίπτωση). Το πρόβλημα εντοπίζεται στις εκφράσεις και πιο συγκεκριμένα στους τελεστές @ και ^ της γλώσσας. Παρακάτω περιγράφεται το πρόβλημα και μερικές δυνατές λύσεις του. ---------------------------------------- 1. Το πρόβλημα ---------------------------------------- Η ελάχιστη γραμματική που είναι υποσύνολο αυτής της PCL και παρουσιάζει το πρόβλημα είναι η εξής (σε bison): %token id %token integer_const %left '^' %left '@' %% expr : l_value | r_value ; l_value : id | expr '^' ; r_value : integer_const | '@' l_value ; %% που έχει ως αποτέλεσμα: foo.y contains 1 reduce/reduce conflict. και πιο συγκεκριμένα: state 7 expr -> l_value . (rule 1) r_value -> '@' l_value . (rule 6) $ reduce using rule 1 (expr) $ [reduce using rule 6 (r_value)] '^' reduce using rule 1 (expr) '^' [reduce using rule 6 (r_value)] $default reduce using rule 1 (expr) Ο αριθμός των conflicts πολλαπλασιάζεται αν προστεθούν και άλλοι τελεστές στη γραμματική. Νομίζω πως δεν μπορεί να θεωρηθεί σωστή μια τέτοια γραμματική αν δεν επιλυθούν τα conflicts. Στην προκειμένη περίπτωση, όταν έπεται '^' προτιμάται ο κανόνας 1 έναντι του 6, κάτι που είναι αντίθετο με τη δηλωμένη σειρά προτεραιότητας. Ακόμα όμως και αν αντιστραφεί η σειρά των κανόνων στη γραμματική, νομίζω πως δεν μπορεί να εξασφαλιστεί ότι θα επιλέγεται κάθε φορά ο σωστός κανόνας, αν υπάρχουν και άλλοι τελεστές στη γλώσσα με μικρότερες προτεραιότητες. Το πρόβλημα φαίνεται να οφείλεται σε αδυναμία του bison να υλοποιήσει σωστά την προτεραιότητα του τελεστή '^' που είναι επιθεματικός (postfix). Ο μηχανισμός δήλωσης προτεραιοτήτων στο bison εστιάζεται σε ενθεματικούς (infix) τελεστές, με ιδιαίτερη πρόβλεψη για προθεματικούς (prefix). Φαίνεται ότι δε δουλεύει καλά σε περίπλοκες γραμματικές όπου υπάρχει συνδυασμός αυτών με επιθεματικούς τελεστές. Ο ισχυρισμός ότι το πρόβλημα οφείλεται σε αδυναμία του bison ενισχύεται από το γεγονός ότι ο συντακτικός αναλυτής για την GNU Pascal που υλοποιείται με το bison ---επίσης της GNU--- δεν περιέχει δηλώσεις προτεραιοτήτων τελεστών. Αντίθετα, οι προτεραιότητες και οι προσεταιριστικότητες επιλύονται με επιπλέον κανόνες της γραμματικής. ---------------------------------------- 2. Μια πρώτη λύση ---------------------------------------- Το πρόβλημα στην παραπάνω γραμματική αποφεύγεται αν αντικαταστήσει κανείς το expr με τους δυο εναλλακτικούς κανόνες μέσα στον κανόνα για το l_value: %token id %token integer_const %left '^' %left '@' %% expr : l_value | r_value ; l_value : id | l_value '^' | r_value '^' ; r_value : integer_const | '@' l_value ; %% Όμως, το πρόβλημα επανέρχεται αν το expr χρησιμοποιείται και σε άλλα σημεία στους κανόνες για τα l_value και r_value, όπως συμβαίνει στην πλήρη γραμματική για την PCL. Η μόνη λύση είναι να αντικατασταθεί το expr σε όλα αυτά τα σημεία. Π.χ. ο κανόνας: r_value : expr '*' expr ; θα πρέπει να αντικατασταθεί με τέσσερις κανόνες: r_value : l_value '*' l_value ; r_value : l_value '*' r_value ; r_value : r_value '*' l_value ; r_value : r_value '*' r_value ; Η συνολική γραμματική που προκύπτει με αυτό τον τρόπο είναι αρκετά μεγάλη. ---------------------------------------- 3. Μια δεύτερη λύση ---------------------------------------- Ένας τρόπος για να επιλυθεί το πρόβλημα, ακολουθώντας το παράδειγμα του συντακτικού αναλυτή για την GNU Pascal, είναι να παρακάμψει κανείς το μηχανισμό των προτεραιοτήτων του bison. Η παραπάνω ελάχιστη γραμματική γίνεται: %token id %token integer_const %% expr : expr2 ; expr2 : l_value2 | r_value2 ; expr1 : l_value1 | r_value1 ; expr0 : l_value0 | r_value0 ; l_value2 : l_value1 | expr '^' ; l_value1 : l_value0 ; l_value0 : id ; r_value2 : r_value1 ; r_value1 : r_value0 | '@' l_value1 ; r_value0 : integer_const ; %% η οποία δεν έχει conflicts (το bison προειδοποιεί για κάποια μη τερματικά σύμβολα και κανόνες που δε χρησιμοποιούνται, ίσως όμως αυτά χρειαστούν στην πλήρη γραμματική της PCL). Στην παραπάνω γραμματική τα επίπεδα της προτεραιότητας των τελεστών έχουν οριστεί ρητά μέσα στη γραμματική. Στο επίπεδο 2 βρίσκεται ο τελεστής '^', στο επίπεδο 1 ο τελεστής '@' και στο επίπεδο 0 οι απλές εκφράσεις. (Έχει γίνει η παραδοχή ότι ο μικρότερος αριθμός επιπέδου αντιστοιχεί σε μεγαλύτερη προτεραιότητα τελεστών.) Με αυτό τον τρόπο μπορεί κανείς να οδηγηθεί σε μια πλήρη γραμματική για την PCL χωρίς conflicts (εκτός του dangling-else που και αυτό μπορεί να εξαλειφθεί). Η γραμματική αυτή όμως περιέχει πολλά επίπεδα εκφράσεων και δεν είναι ιδιαίτερα κομψή. ---------------------------------------- 4. Μια καλύτερη λύση ---------------------------------------- Μια πιο κομψή γραμματική που επίσης δεν περιέχει conflicts μπορεί να προκύψει από το συνδυασμό των δυο προηγούμενων προσεγγίσεων. Ο μηχανισμός των προτεραιοτήτων του bison δεν παρακάμπτεται εντελώς, παρά μόνο στο επίπεδο που προκαλεί το πρόβλημα. Η ελάχιστη γραμματική γίνεται τότε: %token id %token integer_const %left '^' %left '@' %% expr : l_value | r_value ; l_value : l_value_simple | l_value '^' | r_value_simple '^'; l_value_simple : id r_value : r_value_simple ; r_value_simple : integer_const | '@' l_value_simple ; %% Ας σημειωθεί ότι προστέθηκε μόνο ένα μη τερματικό σύμβολο (r_value_simple), που αντιστοιχεί σε κάθε r_value με τελεστές μεγαλύτερης προτεραιότητας από το '^'. Επίσης, ο κανόνας: l_value : expr '^' ; έχει αντικατασταθεί με δύο κανόνες: l_value : l_value '^' | r_value_simple '^'; (Ο πρώτος είναι αρκετός γιατί ο τελεστής '^' έχει τη μικρότερη δυνατή προτεραιότητα μεταξύ των τελεστών των l_values. Αν αυτό δε συνέβαινε, θα χρειαζόταν να προστεθεί ένα ακόμα μη τερματικό l_value_simple.) ---------------------------------------- 5. Συμπέρασμα ---------------------------------------- Νομίζω ότι η τελευταία γραμματική είναι η κομψότερη που αποφεύγει το πρόβλημα και μπορεί να επεκταθεί στην πλήρη γραμματική για την PCL. Σε κάποιες από τις παραπάνω λύσεις οδηγήθηκαν ανεξάρτητα από εμένα κάποιες από τις ομάδες, όπως παρατήρησα στους συντακτικούς αναλυτές που έχουν παραδώσει. Αξίζει λοιπόν να αποδοθούν τα εύσημα στις ομάδες 2 (Τσιάκουλης & Τζανής) και 8 (Ασημενός & Ανδρουλιδάκης) που βρήκαν και χρησιμοποιήσαν τη λύση της ενότητας 2. Οι άλλες ομάδες (όσες φυσικά παρέδωσαν συντακτικό αναλυτή) είτε αγνόησαν το πρόβλημα, είτε το επέλυσαν πρόβλημα αλλάζοντας τη γραμματική της PCL (αν δεν πάει το βουνό στο Μωάμεθ...), ή χρησιμοποίησαν τρόπους που δεν μου είναι εύκολο να διαπιστώσω αν είναι σωστοί. Το πιθανότερο είναι ότι, ακόμα και αν η συντακτική ανάλυση φαίνεται να γίνεται σωστά, η δομή του συντακτικού θα είναι λάθος, κάτι που θα φανεί στις επόμενες φάσεις της μεταγλώττισης. Επειδή η βαθμολόγηση θα γίνει ---ούτως ή άλλως--- βάσει της τελευταίας έκδοσης του μεταγλωττιστή σας, οψόμεθα... Εν κατακλείδι, συγχαρητήρια σε όλους για την καλή δουλειά σας, ακόμα και αν παιδευτήκατε αρκετά και δεν καταφέρατε να γλυτώσετε από τα 154 reduce/reduce errors. Όπως ίσως φάνηκε στα γραφόμενα παραπάνω, ούτε το πρόβλημα είναι προφανές ούτε και η λύση του. Αν θέλετε, μπορείτε να χρησιμοποιήσετε τη λύση της ενότητας 4 στη συνέχεια της εργασίας σας.