Last update: 04/06/2017
Εισοδος:
23 5.5
myvariable
32s
"Hello\nExample"
Θα αναγνωριστούν τα εξής tokens:
| line- | numOfToken- | Περιεχόμενο- | Κατηγορία |
|---|---|---|---|
| 1 | #1 | 23 | INTCONST |
| 1 | #2 | 5.5 | REALCONST |
| 2 | #3 | myvariable | IDENT |
| 3 | #4 | 32 | INTCONST |
| 3 | #5 | s | IDENT |
| 4 | #6 | "Hello |
Example" STRING
Όχι αυτο θα ελεγχθεί στην επόμενη φάση που είναι η συνακτική ανάλυση. Για αυτη τη φάση μαζεύετε τα Tokens χωρίς να ελένχετε τίποτα άλλο.
Οι βασικοί είναι αυτοι που είπες, συν το \" για να τυπώσεις " μεσα σε string. Αν θέλεις μπορείς να βρείς όλους τους escape characters πχ για τη γλώσσα C εδω: https://en.wikipedia.org/wiki/Escape_sequences_in_C
Τα strings που περιέχουν escaped χαρακτήρες, θα πρέπει να τους αναγνωρίζουν ως ειδικούς χαρακτήρες, δηλαδή το string “hello world\n”, θα περιέχει τους χαρακτήρες h, e, l, l, ..., d, newline και όχι τους χαρακτήρες h, e, l, l, ..., d, \, n. Το ίδιο βέβαια ισχύει και για τους άλλους escaped χαρακτήρες. Από εκεί και πέρα ένα string μπορεί να περιέχει έναν πραγματικό χαρακτήρα tab αντί για τον escaped \t, αλλά η χρήση ενός πραγματικού χαρακτήρα newline είναι προαιρετική. Η χρήση ενός πραγματικού χαρακτήρα newline μέσα σε strings, επιτρέπει στους χρήστες να δημιουργούν μεμονωμένα strings που καταλαμβάνουν παραπάνω από μία γραμμές (multi-line strings) εξυπηρετώντας μόνο αισθητικούς “σκοπούς”.
Πετάς και το \ και το n και βάζεις στη θέση τους τον χαρακτήρα '\n'. Αντικαθιστάς δηλαδή τους 2 χαρακτήρες με τον έναν που τους αντιστοιχεί.
" \b
abcdef"
Το \ είναι ειδικός χαρακτήρας μέσα στο string. Σημαίνει, οτι θα το χειριστούμε παρέα με τον χαρακτήρα που ακολουθεί για να τυπώσουμε κάτι ειδικό - πχ newline, tab, " (χωρίς να κλείσει το string) κτλ... Σε περίπτωση που ακολουθεί διαφορετικός χαρακτήρας απο αυτούς που περιμένουμε, τότε πρέπει να το χειριστούμε με έναν απο τους παρακάτω τρόπους:
1.το αφήνουμε μέσα στο string, όπως έκανες στο παράδειγμά σου, είτε με το \ είτε χωρίς, ΒΓΑΖΟΝΤΑΣ ΟΜΩΣ ενα μήνυμα warning ότι αυτό το string περιέχει τον invalid escape character b
2.Πετάμε μήνυμα λάθους και δε δεχόμαστε καθόλου το string.
Αυτό που θα πρέπει να σου βγάλει σαν output file είναι το lex.yy.c που θα είναι ο λεξικογραφικός αναλυτής σου. Αν δεν σου βγάζει κάτι τότε κάτι κάνεις λάθος από τα παραπάνω βήματα, διότι το δοκιμάσαμε και δουλεύει, οπότε η ξαναπροσπάθησε, ή στην χειρότερη ανέβασε το στην περιοχή σου και κάνε αυτά που λέει το front1 για linux.
Αν κατά την λεξικογραφική ανάλυση συναντήσετε undefined chars η γενικότερα είσοδο που δεν κάνει match σε κάποιο από τους κανόνες σας, θα πρέπει να έχετε έναν επιπλέον κανόνα μέσα από τον οποίο το action που θα κάνετε είναι να πετάτε ένα σχετικό μήνυμα λάθους (undefined input x in line y).
Παράδειγμα
!asdasd //asdasda
To ! είναι ένας undefined char οπότε θα πρέπει να τυπώσετε μήνυμα λάθους και είτε συνεχίζετε με την αναγνώριση του υπόλοιπου input (asdasd //asdasda), είτε να σταματήσετε την συντακτική ανάλυση εκεί.
Η alphayylex είναι στην ουσία η συνάρτηση μέσα από την οποία καλείται ο lex.
Είναι το ίδιο πράγμα με την yylex απλά στην εκφώνηση έχει διαφορετική ονομασία με το
prefix *"alpha"*.
Στην ουσία είναι το όνομα της συνάρτησης που θα πεταχθεί απο τον lex και θα καλείται εσείς
απο την main σας ώστε να γίνεται η λεξικογραφική ανάλυση.
By default το όνομα της συνάρτησης που παράγει το εργαλείο είναι το yylex, για να αλλάξετε το
όνομα αυτής αρκεί, όπως φαίνεται και στο φροντιστήριομ να κάνετε define το YY_DECL την υπογραφή
της συνάρτησης πχ. int alpha_yylex (...)
Θα πρέπει να ορίσετε εσείς ένα alpha_token_t το οποίο θα περιέχει τα στοιχεία που σας ζητάει
να κρατάει η εκφώνηση και μπορεί να είναι κάπως έτσι (δεν υπάρχει περιορισμός μπορεί να είναι
όπως θέλετε αρκεί να κρατάει ότι είναι απαραίτητο):
struct alpha_token_t {
unsigned int numline;
unsigned int numToken;
char *content;
char *type;
struct alpha_token_t *alpha_yylex;
}
Ο aplha_yylex παίρνει μια παράμετρο pointer στη μνήμη μίας μεταβλητής τύπου alpha_token_t,
στην οποία και θα αποθηκεύετε τα χαρακτηριστικά γνωρίσματα του εκάστοτε αναγνωρισμένου token. Αρα ο alpha_yylex
γεμίζει ένα token struct και έπειτα επιστρέφει. Αυτό το struct θα το βάζετε στη λίστα με τα Tokens.
Επομένως η παράμετρος είναι απαραίτητη.
/*aaaa
/*aa*/
Αν δεν βρεθεί κάτι τέτοιο έως το τέλος του αρχείου θα πρέπει να πετάξετε error για σχόλιο που δεν έχουν κλείσει.
// assafa /dsadsa/?Το αγνοείτε κανονικά αφού το // είναι Line comment και οτιδήποτε υπάρχει στην γραμμή από το // και μετά ανήκει σε αυτό.
παράδειγμα
/* mpla
/*aaa*/
*/
Δεν θα πρέπει να κρατάτε το περιεχόμενο των σχολίων, απλά μόνο το τι σχόλιο αναγνωρίσατε (καθώς και το πλήθος του), οπότε αυτό που τυπώνετε για το παράδειγμα είναι:
//kati edw/*kati allo
pame katwme enter */
Θα πρέπει να αναγνωριστεί ένα one line comment, 3 IDENT (pame, katwme και enter), ο OPERATOR * και ο OPERATOR /
/*kati//kati allo*/
Θα πρέπει να αναγνωριστεί ένα multiline comment.
Ξεκινάει να αναγνωρίζει string, επομένως αν δεν κλείνει έως το τέλος του αρχείου θα πρέπει να πετάει σχετικό error.
Όταν ένα string περιέχει enters ή tabs, ουσιαστικά περιέχει τους χαρακτήρες '\n' και '\t' αντίστοιχα.Απλά τους κρατάς ως έχουν στο δικό σου string.
Προκειμένου να βρεθεί (να γίνει resolve) ένα σύμβολο που εμφανίζεται σε μία συνάρτηση, θα πρέπει η διαδικασία της αναζήτησης να περάσει από τα εξής στάδια (η διαδικασία σταματάει σε οποιοδήποτε στάδιο μόλις βρεθεί το σύμβολο):
Η υλοποίηση είναι δική σας επιλογή.
Σε περιπτώσεις λάθους το ιδανικό είναι να βγάζετε κατάλληλο μήνυμα και να συνεχίζετε τη συντακτική ανάλυση στο υπόλοιπο κείμενο (όπως κάνουν δηλαδή οι πραγματικοί compilers). Πάντως στην περίπτωση που σας δυσκολεύει μια τέτοια συμπεριφορά, αρκεί να βγάλετε σχετικό μήνυμα λάθους και να τερματίζετε το compilation επιτόπου.
Παράδειγμα:
f=1;
function f(a,b)
{
x=5;
}
Θα μπορούσες να συνεχίσεις κανονικά με τη συντακτική ανάλυση και έτσι να αναλύσεις τα arguments και το body, απλά χωρίς να βάλεις τη συνάρτηση f στο symboltable (καθώς προκαλεί λάθος).
x=9;
function foo(x,y){}
Ακολουθώντας τους τους κανόνες στις τελευταίες διαφάνειες του φροντιστηρίου 3 προκύπτει:
{ { function x(){} function y(){ x();} } }
Με βάση τους κανόνες στις **τελευταίες διαφάνειες του φροντιστηρίου 3** το παραπάνω παράδειγμα είναι οκ.
Έστω οτι ειμαι στο scope 1 και εχει μια μεταβλητη y. Εχω μετά μια συνάρτηση μέσα στο ιδιο scope και βαζω και εκεί την μεταβλητή y ως lvalue.Τοτε πετάω error επειδη είναι εκτός της function το y ή φτιάχνω την μεταβλητη y μέσα στη function;
Ακολουθήστε τις οδηγίες των τελευταίων 4 slides του φροντιστηρίου 3 όπου καλύπτονται όλες οι περιπτώσεις!
Για το συγκεκριμένο παράδειγμα που αναφέρεις εξαρτάται από τον κώδικα:
{
y = 1;
function ex (a) {
y = 3; // error variable y in line 2 is not accessible in function ex
}
}
{
y = 1;
function ex (a) {
local y = 3; // define new local variable in scope 2 in line 4
}
}
{
y = 1;
function ex (a) {
::y = 3; // error, undefined global variable y in line 4
}
}
για να checkaroyme το x στην γραμμή 5 αν είναι valid, θα βρει το 3 πρώτα στην γραμμή 3, το οποιο είναι global από την γραμμή 1, σωστά?
1 x = 5
2 function foo{
3 ::x = 3;
4 function g(){
5 x = 9;
6 }
7 }
Όπως έχουμε πει αρκετές φορές δεν θα πρέπει να αντιμετωπίζουμε την κάθε περίπτωση ξεχωριστά. Οι περιπτώσεις έχουν ομαδοποιηθεί και είναι μαζεμένες στα 3-4 τελευταία slides του φροντ 3.
Το συγκεκριμένο ανήκει στην τελευταία περίπτωση (slide 20) όπου το variable είναι "σκετο" δηλ δεν συνοδεύται από :: ή local. Σε αυτή την περίπτωση κάνουμε lookup πρώτα στο current scope και στην συνέχεια σε πιο έξω scope εως ότου φτάσουμε στο global scope. Εαν σε οποιοδήποτε scope το βρούμε τότε σταματάμε την αναζήτηση και αναφερόμαστε σε αυτό το σύμβολο. Αυτό που μένει τώρα να δούμε είναι αν έχει δικαιώματα πρόσβασης. Αν δεν αναφέρεται σε global scope ή στο current scope και είναι μεσολαβεί συνάρτηση τότε πρέπει να πετάτε error.
Στο συγκεκριμένο παράδειγμα που αναφέρεις ψάχνει την μεταβλητή αρχικά στο current scope (i.e. 2) δεν τη βρίσκει. Στην συνέχεια ψάχνει την μεταβλητή στο αμέσως πιο πάνω scope (i.e. 1) δεν τη βρίσκει (::x δεν εισάγει κάποιο συμβολο στο symbol table απλά κάνουμε lookup στο scope 0). Τέλος, κάνουμε lookup στο πιο πάνω scope (i.e. 0) και εκεί αναφερόμαστε. Επειδή είμαστε σε global τότε η μεταβλητή είναι ορατή από στο scope 2 που προσπαθούμε να την κάνουμε access οπότε όλα καλά δεν υπάρχει κάποιο λάθος.
Οπωσδήποτε ως formals στο symboltable (ώστε να γίνεται σωστά το lookup μέσα στη συνάρτηση), και προαιρετικά ως extra πεδίο του struct function (μόνο και μόνο για να ξέρετε τα ορίσματα που παίρνει η εκάστοτε συνάρτηση).
Ακολουθόντας πάντα τους κανόνες στο τέλος του 3ου φροντιστηρίου . Αν δηλώνεις κάτι, τότε είναι ανάλογα με το τι δηλώνεις: το funcdef δηλώνει συνάρτηση, όλα τα υπόλοιπα δηλώνουν μεταβλητές. Όλες οι υπόλοιπες περιπτώσεις που απλά αναφέρεσαι σε κάτι (γιατι έκανες lookup και βρήκες κάτι) είναι ανάλογα με το τι βρήκες, δηλαδή μπορεί να είναι είτε μεταβλητή είτε συνάρτηση.
something.id πως διαχειρίζομαι το idΣε αυτήν την περίπτωση το id δε μας ενδιαφέρει, δε μπαίνει στο symboltable, δεν το κάνουμε lookup, δεν ασχολούμαστε μαζί του καθόλου.
f = 5;
f.x = 1;
Σε αυτή τη φάση αυτό δε χρειάζεται να πετάξει λάθος.Στη γενική περίπτωση όμως, δε μπορούμε να το ξέρουμε αυτό στατικά αλλά μόνο κατά την εκτέλεση, οπότε η πιο απλή πρακτική είναι να το αφήσουμε ως έχει κατά το compilation και να διαγνώσουμε τέτοια τυχόν λάθη κατά την εκτέλεση.
for(;;)
Εφόσον για το for έχουμε τον κανόνα forstmt -> for (elist; expr; elist) stmt ουσιαστικά η ερώτηση ανάγεται στο αν επιτρέπεται κάποιο από τα elist και expr να είναι κενά.
Βλέποντας και πάλι τη γραμματική, το expr δε μπορεί να είναι κενό συνεπώς το παράδειγμά δεν είναι συντακτικά ορθό.
1)t = [{x:a},{y:b}] ;
2)t["x"]=a;
t["y"]=b;
Δεν είναι ισοδύναμα. Τα x, y που έχεις στο πρώτο είναι μεταβλητές και όχι strings αρα δεν έχουν απαραίτητα τις τιμές "x" και "y" αντίστοιχα. Περίπου ισοδύναμα θα ήταν αν το πρώτο παράδειγμά σου ήταν: t = [ {"x" : a}, {"y": b} ]; Με αυτό το δεδομένο και στα δύο παραδείγματα θα μπούν μόνο τα t, a, b στο SymbolTable, όπως ακριβώς πρέπει. Ο λόγος που παραπάνω είπα "περίπου" ισοδύναμα, που έτσι κι αλλιώς δε μας ενδιαφέρει σε αυτή τη φάση, είναι οτι ακόμα και με την αλλαγμένη έκδοση, τα δύο κομμάτια κώδικα έχουν διαφορετική σημασιολογία. Το πρώτο (t = [...]) δημιουργεί ένα νέο δυναμικό πίνακα και τον εκχωρεί στη μεταβλητή t, ενώ το δεύτερο υποθέτει οτι η μεταβλητή t έχει τιμή πίνακα και του αναθέτει τιμές για κάποια indices. Σχετικά με τη χρήση πινάκων, οι δύο μορφές που είναι ισοδύναμες είναι οι t["x"] = a; και t.x = a; Στη δεύτερη περίπτωση το id x δε μας ενδιαφέρει και δεν μπαίνει στο SymbolTable, οπότε τα δύο παραπάνω αντιμετωπίζονται ακριβώς με τον ίδιο τρόπο.
Στην περίπτωση που δηλώνουν τι συνάρτηση χωρίς όνομα, μας ενδιαφέρει να κρατάμε τις παραμέτρους τις ή απλά τις αγνοούμε (αφού δεν έχουμε τρόπο να την καλέσουμε υποθετικά) πχ function(a,b,c){}
Οι συναρτήσεις χωρίς όνομα χρειάζονται τον ίδιο χειρισμό με τις συναρτήσεις που έχουν όνομα απλά θα πρέπει να τους δίνετε εσείς όνομα όπως αναφέρεται στο 3ο φροντ.
Ένας από τους τρόπους που μπορεί να γίνει κλήση της συνάρτησης για την γλώσσα alpha ως εξής:
example = function (a,b) { return a + b; }
example (3, 4);
Ένας άλλος τρόπος είναι:
example2 = ( function (a,b) { return a + b; } ) (3, 4);
Θα τα δούμε στην επόμενη φάση, αν θέλετε πάντως μπορείτε να τα φτιάξετε και από τώρα, δεν υπάρχει πρόβλημα.
Θα πρέπει να κάνετε όλες τις απαραίτητες αλλαγές στην γραμματική ώστε να μην έχετε conflicts (με εξαίρεση το conflict του ifelse) και δεν θα χαλάει την περιγραφή της γραμματικής της γλώσσας alpha που σας ζητάτε στην εκφώνηση.
Στην περίπτωση που έχουμε if(statement) semicolon , η έκφραση είναι αποδεκτη?
πχ: if(5) ;
Την απάντηση σε οποιαδήποτε τέτοιου είδους απορία την απάντηση μας την δίνει η γραμματική που περιγράφεται στην εκφώνηση.
Συγκεκριμένα για το παράδειγμα που αναφέρεις αντιστοιχεί στον κανόνα του if:
ifstmt -> if (expr ) stmt
οπότε το θέμα είναι αν το 5 μπορεί να αναχθεί σε expr και το ; σε stmt,
5 -> NUMBER -> const -> primary -> term -> expr ΟΚ
stmt -> ; ΟΚ
Οπότε ναι η έκφραση είναι αποδεκτή.
Όχι. Δεν είναι δυνατόν να ξέρουμε το reference count ενός πίνακα at compile time. Αυτό θα γίνει at run-time.
Όχι. Δεν είναι δυνατόν να ξέρουμε at compile time αν ένας πίνακας είναι null. Αυτό θα γίνει at run-time.
Το specification της γλώσσας λέει ότι ο τελεστής %, μπορεί να εφαρμοστεί σε αντικείμενα τύπου number. Επομένως θα μπορεί ο τελευταίος να εφαρμόζεται και σε μη ακέραιους αριθμούς, αρκεί αυτοί να μετατρέπονται πρώτα σε ακέραιους. Έτσι, για να υπολογιστεί το αποτέλεσμα της πράξης r = x % y, θα πρέπει να μετατραπούν πρώτα οι x, y σε ακέραιους και το τελικό αποτέλεσμα σε double, δηλαδή:
double r = ((int) x) % ((int) y);
Στο πεδίο label του struct quad, αποθηκεύουμε μόνο το index (στον πίνακα των quads), στο οποίο θα κάνει (ενδεχομένως) jump μία εντολή διακλάδωσης. Σε όλες τις άλλου τύπου εντολές το πεδίο index δεν χρησιμοποιείται. Φυσικά το index μιας συγκεκριμένης εντολής ενδιάμεσου κώδικα, ορίζεται εμμέσως από την θέση της στον πίνακα των quads.
Ο pointer expr* next, υπάρχει στο struct expr, ώστε να μπορούμε να φτιάχνουμε άμεσα απλές λίστες από αντικείμενα τύπου expr. Αυτό είναι χρήσιμο γιατί μπορούμε να χρησιμοποιήσουμε τον ίδιο τύπο (expr) και για το μη τερματικό σύμβολο elist (expression list) που εμφανίζεται και χρησιμοποιείται στους κανόνες call και tablemake.
Αυτή η επιπλέον εντολή ανάθεσης τιμής στους παραπάνω κανόνες, ενώ Δεν φαίνεται εκ πρώτης όψεως να συμβάλλει στην λειτουργικότητα του προγράμματος, είναι απαραίτητη για την διατήρηση της ορθής σημασιολογίας της γλώσσας σε περίπτωση που ο προγραμματιστής χρησιμοποιήσει το ίδιο l-value, αλλάζοντάς το, σε δύο ή περισσότερα σημεία ενός expression list. πχ.
i = 0;
t = [ ++i, i = 1821, --i, i = 8 ];
έτσι ο πίνακας t, για να είναι “σωστός”, σύμφωνα πάντα με την σημασιολογία της γλώσσας, θα πρέπει να είναι ισοδύναμος με τον:
t_correct = [ 1, 1821, 1820, 8 ];
αφού σύμφωνα με τη γλώσσα, τα expression lists γίνονται evaluate από τα αριστερά προς τα δεξιά. Είναι προφανές ότι εάν Δεν υπήρχε αυτή η τελευταία εντολή ανάθεσης τιμής στους παραπάνω γραμματικούς κανόνες, ο ενδιάμεσος κώδικας που θα παραγόταν, θα ανάγκαζε τον t να αρχικοποιηθεί τελικά με τις τιμές:
t_wrong = [ 8, 8, 8, 8 ];
αφού, σύμφωνα με την syntax-directed παραγωγή ενδιάμεσου κώδικα, πρώτα γίνεται η αποτίμηση όλων των εκφράσεων στο expression list και μετά γίνεται η ανάθεσή τους με tablesetelem.
Όντος σε αυτήν την περίπτωση το δεύτερο στοιχείο του πίνακα θα αρχικοποιηθεί στην τιμή “8”, που σίγουρα δεν είναι κάτι που θα περίμενε ο προγραμματιστής σε αυτήν την περίπτωση. Όμως, θα μπορούσε κάποιος να διαφωνήσει σχετικά με το εάν σε ένα l-value που εμφανίζεται στο initialization list ενός πίνακα (ή των παραμέτρων μιας συνάρτησης) θα πρέπει να αποδίδεται η τελική του τιμή μετά από ολόκληρη την αποτίμηση των εκφράσεων ή η τιμή που έχει εκείνη τη στιγμή. Έτσι, δεδομένης της συγκεκριμένης ασάφειας και δεδομένου ότι είναι πιο “καθαρή” η λύση της ανάθεσης της τιμής ενός l-value όταν αποτιμηθούν όλες οι εκφράσεις που το περιέχουν, είναι αποδεκτές και οι δύο προσεγγίσεις στην υλοποίηση της γλώσσας.
Πρόβλημα: Δημιουργία expr από το struct expr και επιστρέφει ενός pointer σε αυτό. Στον parser, όταν γίνεται η εκχώρηση της τιμής του στο $$ πετάει illegal cast από expr σε char.
Λύση: Στο μη τερματικό κανόνα που είναι το $$, θα πρέπει να αλλάξετε απάνω τη δήλωση και αντί για strValue να έχει exprValue για αυτό το λόγο πετάει και το error.
Αναφέρεται στο SymbolTableEntry του SymTable.
Ερώτηση: σε πιο στοιχειο εκχωρείται η τιμή?
στο ASSIGN _t1 TRUE η τιμή TRUE περνιέται στο _t1 (Εκχωρεί στο πρώτο στοιχείο)
sto ASSIGN _t1 a η τιμή του _t1 περνιέται στο a(Εκχωρεί στο δεύτερο στοιχείο)
το κάθε opcode έχει μια σύνταξη και δεν μπορεί να συμβαίνει αυτό που έχει το παράδειγμα.
Απάντηση: Ναι είναι λάθος στη διαφάνεια το ένα από τα 2, εξαρτάται από τη τακτική την οποια θα ακολουθήσετε εσείς. Αν είναι με τη σειρά opcode result arg1 arg2, τότε είναι λάθος το δεύτερο assign, αν είναι με τη σειρά opcode arg1 arg2 result. Είναι ok να ακολουθήσετε μια από τις 2, αρκεί να είναι η ίδια σε όλες τις περιπτώσεις.
Από όσο θυμάμαι, στις διαλέξεις δεν είναι μονο εκεί με ανάποδη σειρά τα args-results των quads, πρέπει για πχ να έχει και στα tables. Σε κάθε περίπτωση να είστε προσεκτικοί ώστε η σειρά να είναι συνεπής στα quads τα οποια θα παράγεται.
Σε όποιο scopespace και να είστε (είτε μέσα σε συνάρτηση είτε σε global scope) οι tmp μεταβλητές μετράνε κανονικά στα offset.
Παράδειγμα:
function f (a,b,c) { // τα offsets για τα formal args είναι 0,1,2
function l (d,e,f) { // τα offsets για τα formal args είναι 0,1,2 αντίστοιχα
}
function (h, i, j) { // τα offsets για τα formal args είναι 0,1,2 αντίστοιχα
}
}
Τα offsets για τα formal args είναι ίδια, αλλα αυτό είναι ok, διότι τα args είναι ξεχωριστά για τη κάθε συνάρτηση.
Παράδειγμα:
Το offset για τα program variables ΔΕΝ γίνεται reset. Το scopespace αλλάζει όταν ορίζεται νέα συνάρτηση και γίνεται reset το offset για τα formal args και τα local args. To offset για κάθε μεταβλητή βρίσκεται στα σχόλια
a; //0
b; //1
c; //2
{
d; //3
e; //4
{
f; //5
g; //6
}
h; //7
i; //8
while(true){
j; //9
k;//10
}
l; //11
for(m=0;n<2;o++){ //m=12 (_t0 = 13) n=14 (και άλλα temp)...
p; //15
q; //16
if (r==false){ //17
s; //18
t; //19
}
}
u; //20
v; //21
function f(w,x,y){ //w=0 x=1 y=2
z; //0
while(true){
aa; //1
}
}
ab; //22
(Στη διάλεξη 10 slide 5)
Η εντολή αυτή χρειάζεται για να κρατάμε τη διεύθυνση της κάθε συνάρτησης που ορίζεται, δηλαδή τον αριθμό στον οποιο antitoixei το quad της funcstart.
Ο λόγος που γίνεται αυτό είναι διότι, στη επομενη φάση (phase 4-5) στην στην εικονική μηχανή όταν θα θέλουμε να κάνουμε κλήση της κάθε συνάρτησης θα πρέπει να γνωρίζουμε σε ποια εντολή να πάμε έτσι ώστε να καλέσουμε τη συνάρτηση.
Σε κάθε assign πρέπει να παράγεται επιπλέον ένα assign σε tmp μεταβλητή, πχ. για το x = 1; θα παραχθούν τα quads:
assign 1 x
assign x _t0
Γιατι παράγονται 2 assign quads
Το 2o assign έχει χρησιμότητα σε περιπτώσεις όπως για παράδειγμα
f (x=1, x=2);
όπου αν απουσίαζε απο τα quads το 2ο assign τότε θα είχαμε ως αποτέλεσμα να περνάει σαν τιμές το f(2,2) αντί του f(1,2).
Για το -> t.a.b = c.d.e=f.g.h παράγουμε:
0: TABLEGETELEM t "a" _t0
1: TABLEGETELEM c "d" _t1
2: TABLEGETELEM f "g" _t2
3: TABLEGETELEM _t2 "h" _t3
4: TABLESETELEM _t1 "e" _t3
5: TABLEGETELEM _t1 "e" _t4
6: TABLESETELEM _t0 "b" _t4
7: TABLEGETELEM _t0 "b" _t5
Στην περιπτωση που το lvalue ειναι tableitem η παραγωγη του ενδιαμεσου κωδικα δεν γινεται στην αναγωγη του lvalue.
Πρεπει να "περιμενουμε" λιγο την αναλυση ωστε να δουμε με ποιο τροπο χρησιμοποιειτε το tableitem. Μια απο τις περιπτωσεις (slide 20-22 διάλεξη 10) ειναι το tableitem να χρησιμοποιειται ως rvalue κατι που το γνωρίζουμε μονο οταν φτασουμε στον κανονα primary<-lvalue.
Για το -> function foo (a,b) { }
funcstart foo
funcend foo
Για το -> f(1,2);
PARAM 2
PARAM 1
CALL f
Για το -> f(a(1), b(2, 3));
0: PARAM 1 // Η παράμετρος της συνάρτησης a().
1: CALL a
2: GETRETVAL _r0
3: PARAM 3
4: PARAM 2
5: CALL b
6: GETRETVAL _r1
7: PARAM _r1
8: PARAM _r0
9: CALL f
10:GETRETVAL _r2
Παράδειγμα
test().x = 1;
print(y.z.x, "-");
QUADS:
Για το -> test().x = 1; τα quads είναι:
1: call test
2: getretval _t0
3: tablesetelem _t0 "x" 1
Για το -> print (y.z.x, "-"); τα quads είναι:
4: tablegetelem y "z" _t1
5: tablegetelem _t1 "x" _t2
6: param "-"
7: param _t2
8: call print
9: getreval _t3
Για το παράδειγμα:
if (1>2)
x = 1;
θα παράχθούν τα εξής quads:
Για το παράδειγμα:
while(1) {
x = 1;
}
θα παράχθούν τα εξής quads:
Undefined ειναι οι μεταβλητές στις οποίες δεν εχουν γινει defined ο τυπος και η τιμη τους.
x=2; // x -> type: Number, value:2
x=y; // y δημιουργειτε αλλα δεν εχει ανατεθει σε αυτον τυπος και τιμη
Το αποτελεσμα ειναι τα x, y να ειναι undefined
Προσοχή: Πρόκειται για την σημασιολογία της γλώσσας και αφορά το runtime(i.e. Virtual Machine) και όχι το compile time!
Τα επιπλέον quads που θα πρέπει να παραχθούν φαίνεται από το φροντιστήριο στο slide 39 και 40 απλά είναι λίγο κρυμμένο :) Στην ουσία αν δείτε προσεκτικά για παράδειγμα στο slide 39:
Για το x = a < b or c<d and e < f;
Τα quads που παράγονται μέχρι και το 6 είναι αυτά που παράγονται για τα
a<b, c<d και e<f. Την στιγμή που παράγονται τα labels μένουν incomplete..
Όταν βρισκόμαστε τον κανόνα and και or αντίστοιχα εκεί έχουμε την γνώση και κάνουμε backpatch για την falselist (όταν είμαστε στην or) και για την truelist όταν είμαστε στη and, τα υπόλοιπα μένουν incomplete και απλά τα περνάμε στους πιο "πάνω" κανόνες (slide 37). Στην συνεχεια για το συγκεκριμένο πχ πιο πάνω κανόνας είναι το assignexpr.
Εκεί θα πρέπει να παραχθούν τα quads 7-9, όπου αυτά είναι και τα extra quads που θα πρέπει να παραχθούν για τη μερική αποτίμηση.
Επομένως τα quads που θα πρέπει να παράγεται είναι:
label QUAD
N : assign TRUE _t0
N+1 : jump N+3
N+2 : assign FALSE _t0
!!! Εκεί έχετε τη γνώση για τα labels και εκεί είναι είναι που θα γίνει και το backpatch για τις truelist - falselist Η truelist θα γίνει backpatch με το label Η και η falselist θα γίνει backpatch με το label Η+2.
Για το συγκεκριμένο παράδειγμα στο slide 39, η truelist θα γίνει backpatch με το label 7 και η falselist θα γίνει backpatch με το label 9.
Η περίπτωση της assignexpr είναι ένα παράδειγμα κανόνα που χρειάζεται αλλαγή.
Expr2.truelist, Expr2.falselist) στο Expr (i.e. $$) ώστε να διατηρήσουμε την πληροφορία των incomplete labels έως ότου έχουμε την γνώση για το καθένα ώστε να γίνει το backpatch.>,>=, etc.)
N : IF_RELOP id1 id2 _
N+1: JUMP _
Ν+1)N : ASSIGN TRUE _t0 // κάνουμε backpatch την truelist, i.e. backpatch (truelist, N)
N+1: JUMP N+3
N+2: ASSIGN FALSE _t0 // κάνουμε backpatch την falselist, i.e. backpatch (falselist, N+2)
x = a and b;
Το a, b θα πρέπει να αναχθούν σε Boolean. Για να το καταφέρουμε αυτό θα πρέπει να προσθέσουμε 2 επιπλέον quads.
Για το a:
IF_EQ a TRUE _
JUMP _
Η προσθήκη των quads γίνεται όταν έχουμε την γνώση ότι βρισκόμαστε σε λογική έκφραση (i.e. and, or, not), όπου εξετάζουμε τα expr1, expr2 τι τύπου είναι και αν δεν πρόκειται για boolean operand τότε θα κάνουμε emit τα 2 αυτά quads. Προφανώς, από τη στιγμή που έχουμε 2 incomplete labels θα πρέπει να τα εισάγουμε στις λίστες των falselist και truelist αντίστοιχα.
Ο τύπος των methodcall, normcall και callsuffix δεν ορίζεται με κάποιο από τα υπάρχοντα struct που βρίσκονται στις διαλέξεις. Αντιθέτως, θα πρέπει να ορίσεται εκ νέου κάποιο struct..
Καταρχήν μια τέτοια έκφραση για την σημασιολογία της Aplha είναι λάθος. Το not a θα έχει αποτέλεσμα bool ενώ επιτρέπονται μόνο arithexpressions. Μπορείτε προαιρετικά να το πετάτε ως error compile time, αλλιώς θα χτυπάει ως run-time error.
Τώρα για τα quads που θα παραχθούν έχει να κάνει με τη προτεραιότητα που έχουμε ορίσει από τη 2η φάση. Το not έχει πιο υψηλή προτεραιότητα από το < επομένως τα quads που παραχθούν είναι:
0: IF_EQ a true 4
1: JUMP 2
2: ASSIGN true _t1
3: JUMP 5
4: ASSIGN false _t1
5: IF_GREATER _t1 b 7
6: JUMP 9
7: ASSIGN true _t2
8: JUMP 10
9: ASSIGN false _t2
Ερώτηση
Εστω το σενάριο
function foo(b,a){
k=2*a + 3*b;
return k;
}
foo(y,x);
τα quads που παραγονται ειναι
funcstart foo
//ενδιαμεσα quads εκφρασης της k=2*a + 3*b; και return
funcend foo
param x
param y
call foo
getretval _t0
πως ξέρουμε εμείς μετά στο virtual machine να αντικαταστησουμε το b με y και το a με x εφοσων δεν γραφουμε σε κανένα quad αυτες τις 2(a,b) μεταβλητες.
Απάντηση
Έχει να κάνει με τα offsets που έχει κάθε σύμβολο. Το a,b που αναφέρεσαι σαν ονόματα δεν λένε τίποτα στην εικονική μηχανή. Η μηχανή γνωρίζει τα offsets του καθενός και τα ψάχνει μέσα στην στοίβα.
Όντος, αυτό ισχύει και μάλιστα όταν ο πίνακας βρίσκεται στο global scope, υπάρχει περίπτωση να κρατηθεί ζωντανός σε όλη τη ζωή του προγράμματος (στο τέλος του προγράμματος θα γίνει σίγουρα collect) ακόμα κι αν ο χρήστης του θέσει ρητά την τιμή nil. Όμως αυτή η συμπεριφορά δεν αλλάζει καθόλου τη σημασιολογία του reference counting των πινάκων, αφού έτσι κι αλλιώς ο χρήστης (προγραμματιστής της γλώσσας), δεν μπορεί να βασίσει την ορθότητα του προγράμματος του στην γνώση καταστροφής ενός πίνακα σε συγκεκριμένη χρονική στιγμή. Έτσι αυτή η συμπεριφορά, είναι απόλυτα αποδεκτή. Ένας “νεκρός” -για τον χρήστη- πίνακας μπορεί να μην καταστραφεί από το runtime σύστημα άμεσα, όμως δεδομένου ότι
Kάποιες από τις συναρτήσεις δεν χρειάζονται εξαρτάται από το ρεπερτόριο των εντολών που έχετε ορίσει. Το ρεπερτόριο των εντολών θα πρέπει να είναι ένα προς ένα με των πίνακα των function addresses των generate για να δουλεύει σωστά o dispatcher, αυτός είναι και ο λόγος που φαίνονται τα generate functions. Επομένως, ανάλογα με την υλοποίηση σας θα πρέπει να κάνετε κατάλληλες τροποποιήσεις.
Ο τελικός κώδικας αναφέρεται στους πίνακες σταθερών τιμών. ΔΕΝ περιέχονται ονόματα μεταβλητών μέσα στους πίνακες. Οι πίνακες είναι strings, numbers, userfunctions και libfunctions που συναντήθηκαν μέσα στο alpha πρόγραμμα που γίνεται compile.
Στο binary file καταγράφετε τους πίνακες και τα instruction (τελικός κώδικας) που αντιστοιχούν στο πρόγραμμα που γίνεται compile. Η VM κάνει load το binary file με τους ΄πίνακες και τα instructions και τα εκτελεί.
Επίσης είστε ελεύθεροι να περνάτε την πληροφορία με το τρόπο που θέλετε, δεν είναι υποχρεωτική η μορφή που σας δόθηκε απλά είναι προτεινόμενη και να έχετε ότι κατάληξη θέλετε στο binary file.
Δεν χρειάζεται να μεταφράσετε σε 0 και 1 τις πληροφορίες. Δείτε πως γράφουμε-διαβάζουμε binary files σε C/C++. Σε περίπτωση που δυσκολεύεστε είναι οκ να κάνετε ένα απλό read και write. Σε κάθε περίπτωση έτσι και αλλιώς για λόγους debug βολεύει να τα γράφετε σε αρχεία στην αρχή ώστε να δείτε ότι είναι αυτά που θέλετε να γράψετε.
Η κατασκευή ενός binary file για να προχωρήσετε στην 5η φάση είναι υποχρεωτική.
Χρειάζεται να προσθέσετε μια επιπλέον εντολή jump στην αρχή της Funcstart έτσι ώστε να κάνει skip τον τελικό κώδικά που αντιστοιχεί σε κάθε συνάρτηση.
funcstart:
jump labelNextFuncend
funcenter
return result:
assign result
jump labelFuncend
and, or, not:
Βλέπε διάλεξη 14 διαφάνειες 19-21
uminus:
mul -1
Σε οποιοδήποτε περίπτωση έχετε ορίσματα που δεν υποστηρίζονται βγάζετε runtime error με κατάλληλο διαγνωστικό μήνυμα.
Για τα strings συγκεκριμένα, θα είχε νόημα οι τελεστές σύγκρισης να κάνουν λεξικογραφική σύγκριση και το συν string concatenation, αλλά δεν είναι υποχρεωτικό.
Οι επιπλέον παράμετροι που περνάει ο χρήστης, απλώς αγνοούνται. Το runtime σύστημα, αντιστοιχίζει πάντα τις πραγματικές παραμέτρους της συνάρτησης στις αντίστοιχες πρώτες παραμέτρους που περνάει ο χρήστης και έτσι οι υπόλοιπες αγνοούνται με ασφάλεια.
Τότε υπάρχει πρόβλημα. Δεδομένου του τρόπου αντιστοίχησης, από το runtime σύστημα, των πραγματικών παραμέτρων μιας συνάρτησης με τις παραμέτρους που περνάει ο χρήστης, υπάρχει το ενδεχόμενο είτε μία παράμετρος να περιέχει "σκουπίδια", είτε να γίνει corrupt το runtime stack εάν ο χρήστης προσπαθήσει να αναθέσει τιμή σε μία "ανύπαρκτη" μεταβλητή. Όμως προκειμένου, αφενός να είναι πιο εύκολη η υλοποίηση και αφετέρου να είναι πιο γρήγορη η λειτουργία της εικονικής μηχανής, η υλοποίηση της γλώσσας δεν χρειάζεται να "προστατεύει" τον χρήστη (προγραμματιστή της γλώσσας) από αυτήν την "παγίδα".
Οι συναρτήσεις βιβλιοθήκης που θα πρέπει να υλοποιηθούν, είναι οι εξής:
value = false
foo = nil
t = [ { "foo" : 32 }, { "lala" : [ "inner", value, foo, 3.14 ] } ];
print("the contents of t are - ", t);
>> the contents of t are - [ { foo : 32 }, { lala : [ inner, false, nil, 3.140 ] }
a = input();
<< 3.1415
>> 3.1415 // number
<< "3.1415"
>> "3.1415" // string
<< 4.4a
>> "4.4a" // string
<< true
>> true // boolean
t = [ { "foo" : 34 }, { "lala" : [ 3, 4, 5 ] } ];
objectmemberkeys(t);
>> [ "foo", "lala" ]
t = [ 1, 2, 3, 4, 5 ];
objecttotalmembers(t);
>> 5
strtonum("1821.22");
>> 1821.220
strtonum("foo");
>> nil
sqrt(-1);
>> nil
cos(90);
>> 0
sin(270);
>> -1
Ερώτηση:
Κάθε φορά που έχουμε κλήση μιας συνάρτησης βιβλιοθήκης θα πρέπει να εισάγεται στον αντίστοιχο πίνακα σταθερών τιμών ανεξαρτήτως αν έχει κληθεί ξανά πιο πριν ή πρέπει να γίνεται lookup μέσα στον πίνακα και αν υπάρχει να μην την εκχωρούμε;
Απάντηση:
Στους πίνακες σταθερών (όχι μόνο στις συναρτήσεις αλλά σε όλους) οι τιμές θα πρέπει να είναι μοναδικές. Όταν πάτε να κάνετε insert, κάνετε πρώτα lookup και αν βρείτε το entry επιστρέφετε το αντίστοιχο index του, αλλιώς το εισάγετε και επιστρέφετε το index αυτού που μόλις βάλατε.
Δεν περνάτε ονόματα formals. Καταρχάς στον τελικό κώδικα δεν υπάρχουν ονόματα, περνάτε τύπο και offset. Οπότε τύπος όταν έχουμε formals είναι formal + το offset είναι ο τρόπος που θα το βρούμε μέσα στη στοίβα - περιβάλλον εκτέλεσης.
Τα strings του πίνακα σταθερών τιμών δε χρειάζεται να τα απελευθερώσετε ακόμα κι αν δεν αναφέρεται πλέον κανείς σε αυτά.
Το string value που μπορεί να έχει το κάθε memcell απελευθερώνεται όταν χρειάζεται με τη avm_memcellclear.
refcount γίνει 0 άσχετα με το αν το τελευταίο ref ήταν global, formal ή local, τότε κάνετε collect.Πίνακας με όρισμα πίνακα
t=[];
t[t]=3;
Οι πίνακες είναι hashtables που θεωρητικά μπορούν να υποστηρίξουν κλειδιά οποιοδήποτε τύπου. Σημασιολογικά το t[t] = 3; σημαίνει οτι στον πίνακα t στο κλειδί t βάζουμε την τιμή 3. Εφόσον κατά το runtime ο πίνακας t είναι ένας δυναμικός πίνακα με μοναδική διευθυνση στη μνήμη, μπορούμε κάλλιστα να χρησιμοποιήσουμε τη διεύθυνσή του για να κάνουμε ως index στο hashing. Ως index δεν επιτρέπεται ούτε το nil ούτε το undefined, άρα θα βγάζετε κατάλληλο μήνυμα λάθους. Πάντως για το project υποχρεωτικά είναι μόνο τα αριθμητικά και string κλειδιά.
Refcounter σε πίνακα
x=[];
0: NEWTABLE_V (global)1
1: ASSIGN (global)1 (global)0
2: ASSIGN (global)0 (global)2
Στην παραπάνω περίπτωση το refcounter είναι 3 (3 αναφορές).
Undefined και nil τιμή σε πίνακα
t = [];
t[0] = x; //x is undefined, so t[0] becomes undefined
print(t[0]); //prints undefined
t = [];
print(t[0]); //prints nil
t = ["an entry"];
t[0] = nil;
print(t[0]); //prints nil
print(objecttotalmembers(t)); //prints 0
Αρχικοποίηση top και topsp:
Στην κορυφή μπαίνουν τα globals, οπότε αρχικοποιείτε τους top και topsp τόσες θέσεις κάτω από την κορυφή. Από την 3η φάση είπαμε οτι οι temp μεταβλητές είναι κανονικές μεταβλητές που παίρνουν offset και μετράνε κανονικά στο εκάστοτε scope space. Άρα τις μετράμε και για το χώρο των globals, και των locals στις συναρτήσεις.
Γενικά συγκεκριμένο νούμερο για τα globals είναι δύσκολο να πεις καθώς εξαρτάται από το πόσα temps παράγονται που με τη σειρά του εξαρτάται από τον ακριβή κώδικα (π.χ. μερική vs ολική) καθώς και το αν κάνετε temp reuse.
x = 10;
y = "hello";
function f(x,y){return x+y;}
z = "word";
w = cos(3.14);
print(x,y,z,w);
Χωρίς temp reuse, έχουμε: