|
Εθνικό Μετσόβιο Πολυτεχνείο
Τμήμα
Ηλεκτρολόγων Μηχανικών
|
Μεταγλωττιστές 2003
Θέμα εργασίας
Η γλώσσα Calvin
|
Μεταγλωττιστές http://www.sofltab.ntua.gr/~nickie/Compilers Καθηγητής: Νίκος Παπασπύρου Επιμέλεια: Κώστας Ταβερναράκης |
Η γλώσσα Calvin είναι μια απλή διαδικασιακή γλώσσα
προγραμματισμού. Τα χαρακτηριστικά της εν συντομία είναι τα εξής:
· σύνταξη εντολών παρόμοια με αυτή της γλώσσας C
· δομημένες συναρτήσεις με τους κανόνες εμβέλειας
της Pascal
· βασικοί τύποι δεδομένων για ακέραιους και
χαρακτήρες
· μονοδιάστατοι πίνακες με περιορισμένη
λειτουργικότητα
· βιβλιοθήκη συναρτήσεων εισόδου/εξόδου
Περισσότερες λεπτομέρειες
της γλώσσας δίνονται στις παραγράφους που ακολουθούν.
Τα αναγνωριστικά
(identifiers) της γλώσσας Calvin απαρτίζονται από γράμματα (A..Z, a..z),
ψηφία (0..9) και τον ειδικό χαρακτήρα _ (underscore). Ένα αναγνωριστικό δεν μπορεί να
αρχίζει από ψηφίο. Τα πεζά γράμματα διαφέρουν από τα αντίστοιχα κεφαλαία. Τα
παρακάτω αναγνωριστικά είναι δεσμευμένα και δεν επιτρέπεται να χρησιμοποιούνται
ως κοινά αναγνωριστικά. Η σημασία τους εξηγείται σε επόμενες παραγράφους.
char, else, if, integer, main, return, void, while
Τα αναγνωριστικά που αντιστοιχούν σε προκαθορισμένες διαδικασίες και
συναρτήσεις (ενότητα 6) είναι προκαθορισμένα, αλλά επιτρέπεται να
χρησιμοποιηθούν ως κοινά αναγνωριστικά, χάνοντας την ειδική σημασία τους.
Οι βασικοί τύποι δεδομένων που υποστηρίζει η γλώσσα Calvin είναι οι εξής:
Τύπος |
Περιγραφή |
integer |
ακέραιοι αριθμοί των 16 bit
σε παράσταση συμπληρώματος ως προς δύο (-32768 ως 32767) |
char |
χαρακτήρες των 8 bit σε
συμβολισμό ASCII. |
Οι ακέραιες σταθερές αποτελούνται από ένα προαιρετικό πρόσημο ακολουθούμενο
από ένα ή περισσότερα δεκαδικά ψηφία. Παραδείγματα ακέραιων σταθερών είναι τα
εξής:
0 5 -10 7483 -25983
Οι σταθερές τύπου χαρακτήρα αποτελούνται από έναν απλό ή ειδικό χαρακτήρα
που περικλείεται από απλά εισαγωγικά. Ως απλοί χαρακτήρες θεωρούνται όλοι οι
εκτυπώσιμοι χαρακτήρες πλην των εισαγωγικών (απλών και διπλών) και της
ανάστροφης καθέτου \ (backslash). Οι ειδικοί
χαρακτήρες χρησιμοποιούνται όπως στη γλώσσα C. Παριστάνονται ως ζεύγη
χαρακτήρων, με πρώτο την ανάστροφη κάθετο. Οι επιτρεπόμενοι ειδικοί χαρακτήρες
είναι οι εξής:
Χαρακτήρας |
Περιγραφή |
\n |
χαρακτήρας νέας γραμμής (new line) |
\" |
χαρακτήρας " (διπλό εισαγωγικό) |
\' |
χαρακτήρας ' (απλό εισαγωγικό) |
\0 |
χαρακτήρας με ASCII κωδικό 0 |
\t |
χαρακτήρας αλλαγής στήλης (TAB) |
\\ |
χαρακτήρας \ (backslash) |
Εκτός από τους βασικούς
τύπους δεδομένων, η γλώσσα Calvin υποστηρίζει πίνακες (arrays) αποτελούμενους από
στοιχεία των βασικών τύπων. Οι πίνακες όμως έχουν περιορισμένη λειτουργικότητα,
όπως θα εξηγηθεί στις επόμενες παραγράφους.
Κατά τον ορισμό μιας
μεταβλητής τύπου πίνακα, πρέπει να ορίζεται το μήκος του, δηλαδή το πλήθος των
στοιχείων που τον αποτελούν. Ένας πίνακας π.χ. 20 χαρακτήρων με όνομα name ορίζεται ως εξής:
char name [20];
Τα στοιχεία του πίνακα
μπορούν να προσπελαύνονται τοποθετώντας ένα δείκτη (έκφραση που επιστρέφει
ακέραιο αριθμό) ανάμεσα σε αγκύλες, π.χ.
name[5]
Το πρώτο στοιχείο κάθε
πίνακα αντιστοιχεί σε δείκτη 0, ενώ
το τελευταίο σε δείκτη ίσο με το μήκος του μείον ένα. Για τον πίνακα που
ορίστηκε πιο πάνω, οι επιτρεπτές τιμές του δείκτη είναι οι ακέραιοι αριθμοί
μεταξύ 0 και 19.
Το μέγιστο επιτρεπόμενο
μήκος πινάκων εξαρτάται από την υλοποίηση και μπορεί να καθοριστεί ελεύθερα από
κάθε ομάδα.
Όπως σε κάθε γλώσσα
προγραμματισμού, έτσι και στη γλώσσα Calvin ιδιαίτερα χρήσιμοι είναι οι πίνακες χαρακτήρων,
που χρησιμοποιούνται για την αποθήκευση συμβολοσειρών (strings). Η Calvin επιτρέπει τη χρήση
σταθερών συμβολοσειρών, δηλαδή σταθερών πινάκων αποτελούμενων από χαρακτήρες.
Οι συμβολοσειρές είναι ακολουθίες απλών και ειδικών χαρακτήρων που περικλείονται
από διπλά εισαγωγικά. Παραδείγματα συμβολοσειρών είναι τα εξής:
"This is a
string!"
"Hello world!\n"
"My phone number is: 1234567."
Για την παράσταση των
συμβολοσειρών, η γλώσσα Calvin χρησιμοποιεί την ίδια σύμβαση με τη C, δηλαδή οι
συμβολοσειρές είναι ακολουθίες χαρακτήρων που τερματίζονται με τον ειδικό
χαρακτήρα \0. Κατ’ αυτό τον τρόπο το
πραγματικό μήκος μιας συμβολοσειράς είναι κατά ένα μεγαλύτερο από το πλήθος των
χαρακτήρων που την αποτελούν και πρέπει να γίνεται πρόβλεψη για τον επιπλέον
χαρακτήρα.
Η Calvin είναι μια δομημένη
(block structured) γλώσσα. Οι διαδικασίες και οι συναρτήσεις μπορούν να είναι
φωλιασμένες (nested) η μια μέσα στην άλλη. Οι κανόνες εμβέλειας είναι ίδιοι με
αυτούς της Pascal.
Ένα πρόγραμμα της γλώσσας
Calvin έχει
τη δομή ενός προγράμματος Pascal. Η γλώσσα Calvin δε διαφοροποιεί τις μονάδες προγράμματος: το
κυρίως πρόγραμμα, οι διαδικασίες και οι συναρτήσεις αντιμετωπίζονται από
κοινού ως συναρτήσεις, και ως τέτοιες δηλώνονται. Σε περίπτωση που κάποια
μονάδα προγράμματος δεν επιστρέφει αποτέλεσμα, τότε δηλώνεται με τύπο void. Επισημαίνεται ότι μια συνάρτηση δεν μπορεί να
επιστρέφει αποτέλεσμα τύπου πίνακα.
Οι συναρτήσεις
κατατάσσονται σε δυο κατηγορίες: τις κοινές συναρτήσεις, που ορίζονται
μέσα στο πρόγραμμα, και τις εξωτερικές συναρτήσεις, που
δηλώνονται απλώς στην αρχή του προγράμματος και ορίζονται έξω από το πρόγραμμα
(π.χ. στη run-time βιβλιοθήκη που θα περιγραφεί αργότερα).
Οι συναρτήσεις (όπως άλλωστε και οι μεταβλητές) πρέπει να έχουν δηλωθεί
πριν χρησιμοποιηθούν. Η δήλωση αυτή μπορεί να γίνει με δυο τρόπους:
· με πλήρη ορισμό (επικεφαλίδα και κώδικας)
· με απλή δήλωση (επικεφαλίδα μόνο)
Οι εξωτερικές συναρτήσεις
δηλώνονται μόνο με το δεύτερο τρόπο. Επίσης, η δήλωσή τους γίνεται υποχρεωτικά
στην αρχή του προγράμματος (πριν την επικεφαλίδα του). Οι κοινές συναρτήσεις
που δηλώνονται με το δεύτερο τρόπο πρέπει αργότερα να οριστούν πλήρως, και
μάλιστα στην ίδια περιοχή εμβέλειας (scope). Ο μηχανισμός αυτός είναι ο ίδιος
με το μηχανισμό δήλωσης υποπρογραμμάτων της Pascal με την οδηγία forward.
Οι παράμετροι των
συναρτήσεων μπορούν να περνούν με δύο τρόπους: κατ’ αξία ή κατ’ αναφορά.
Το πέρασμα κατ’ αναφορά δηλώνεται με το σύμβολο & που προηγείται του ονόματος της τυπικής
παραμέτρου στην επικεφαλίδα της συνάρτησης, π.χ.
void f (integer by_value, integer &
by_reference)
Στην περίπτωση που κάποια
τυπική παράμετρος μιας συνάρτησης είναι πίνακας, στην επικεφαλίδα της
συνάρτησης δεν αναγράφεται το μήκος του πίνακα. Αν είναι απαραίτητο αυτό να
είναι γνωστό στη συνάρτηση, πρέπει να περνάει ως ανεξάρτητη παράμετρος. Πίνακες
μπορούν να περνούν και με τους δύο τρόπους (αξία και αναφορά). Παραδείγματα
συναρτήσεων με τυπικές παραμέτρους τύπου πίνακα είναι οι εξής:
void print (char s[])
integer sum
(integer & values[], integer size)
Οι εντολές της γλώσσας Calvin έχουν ακριβώς την ίδια
μορφή με τις αντίστοιχες εντολές της γλώσσας C. Με εξαίρεση τη σύνθετη εντολή
(compound statement), πρέπει να τερματίζονται υποχρεωτικά με το χαρακτήρα ; (semicolon).
Η εντολή εκχώρησης έχει
την ίδια σύνταξη και σημασιολογία με την αντίστοιχη εντολή της C. Επιτρέπεται
μόνο η εκχώρηση απλών τύπων: απαγορεύεται η εκχώρηση ολόκληρων πινάκων, αλλά
επιτρέπεται η εκχώρηση σε στοιχεία πίνακα.
Οι εντολές ελέγχου που
επιτρέπει η γλώσσα είναι οι εξής :
if ( λογική-έκφραση ) εντολή [ else εντολή ]
while (
λογική-έκφραση ) εντολή
Η σημασιολογία των
εντολών αυτών είναι η ίδια όπως στη γλώσσα C.
Η εντολή κλήσης
συνάρτησης έχει την ίδια σύνταξη και σημασιολογία με την αντίστοιχη εντολή της
γλώσσας C. Για να κληθεί όμως μια συνάρτηση ως εντολή, θα πρέπει αυτή η
συνάρτηση να έχει δηλωθεί ως void,
δηλαδή να μην επιστρέφει τύπο.
Η εντολή return χρησιμοποιείται για την επιστροφή από συνάρτηση.
Όταν πρόκειται για συνάρτηση που επιστρέφει κάποιο τύπο, πρέπει να ακολουθείται
από έκφραση του ίδιου τύπου με αυτόν που επιστρέφει η συνάρτηση.
Οι τελεστές της γλώσσας Calvin δίνονται παρακάτω. Η προτεραιότητα
(precedence) και η προσεταιριστικότητα (associativity) των τελεστών αυτών είναι η
ίδια με αυτή των τελεστών της γλώσσας C. Δεν υπάρχουν τελεστές που να
επιστρέφουν αποτέλεσμα τύπου χαρακτήρα ή πίνακα.
Οι αριθμητικοί τελεστές με ένα τελούμενο της γλώσσας Calvin είναι οι εξής:
Τελεστής |
Σημασία |
+ |
Θετικό πρόσημο (ταυτότητα) |
- |
Αρνητικό πρόσημο (αντίθετος) |
Οι δυαδικοί
αριθμητικοί τελεστές της γλώσσας είναι οι εξής:
Τελεστής |
Σημασία |
+ |
Πρόσθεση ακεραίων |
- |
Αφαίρεση ακεραίων |
* |
Πολλαπλασιασμός ακεραίων |
/ |
Πηλίκο ακέραιας διαίρεσης |
% |
Υπόλοιπο ακέραιας διαίρεσης |
Τα τελούμενα των αριθμητικών τελεστών πρέπει να είναι έγκυρες ακέραιες
εκφράσεις. Το αποτέλεσμά τους είναι ακέραιου τύπου.
Οι σχεσιακοί τελεστές της γλώσσας Calvin φαίνονται στον παρακάτω πίνακα. Τα τελούμενά τους
πρέπει να είναι έγκυρες ακέραιες εκφράσεις ή χαρακτήρες, του ίδιου όμως τύπου.
Απαγορεύονται συγκρίσεις ολόκληρων πινάκων, επιτρέπονται όμως οι συγκρίσεις
στοιχείων πινάκων. Συγκρίσεις μεταξύ χαρακτήρων γίνονται με βάση τους
αντίστοιχους κωδικούς ASCII (ακέραιοι από 0 ως 255).
Τελεστής |
Σημασία |
== |
ίσο |
!= |
διάφορο |
> |
μεγαλύτερο |
< |
μικρότερο |
>= |
μεγαλύτερο ή ίσο |
<= |
μικρότερο ή ίσο |
Τα αποτελέσματα των σχεσιακών τελεστών είναι λογικές εκφράσεις. Οι
εκφράσεις αυτές μπορούν να χρησιμοποιηθούν μόνο σε εντολές if και while.
Δεν μπορούν να εκχωρηθούν σε μεταβλητές, να περάσουν ως παράμετροι ούτε να
επιστραφούν ως αποτελέσματα συναρτήσεων.
Οι λογικοί τελεστές της γλώσσας Calvin είναι τρεις:
Τελεστής |
Σημασία |
|| |
Λογική διάζευξη (ή) |
&& |
Λογική σύζευξη (και) |
! |
Λογική άρνηση (όχι) |
Οι τελεστές || και && είναι δυαδικοί, ενώ ο τελεστής ! δέχεται ένα τελούμενο. Τα τελούμενα πρέπει να
είναι έγκυρες λογικές εκφράσεις. Το αποτέλεσμα είναι επίσης λογική έκφραση.
Τα σχόλια στη γλώσσα Calvin είναι δυο ειδών. Τα
κοινά σχόλια είναι ίδια με αυτά της γλώσσας C. Περικλείονται από τις ακολουθίες
χαρακτήρων /* και */ και δεν μπορούν να είναι φωλιασμένα (nested). Η
γλώσσα Calvin όμως
υποστηρίζει και ένα δεύτερο τύπο σχολίων, που αρχίζουν με την ακολουθία χαρακτήρων
// και εκτείνονται ως το τέλος της γραμμής (όπως στη
γλώσσα C++).
Η μοναδική οδηγία, που
επιτρέπει ο μεταγλωττιστής της γλώσσας Calvin είναι η οδηγία #include. Η οδηγία αυτή έχει την ίδια σημασιολογία όπως και στη γλώσσα C, δηλαδή
επιτρέπει την ανάγνωση ενός εξωτερικού αρχείου σαν αυτό να ήταν τμήμα του
προγράμματος. Πρέπει να βρίσκεται υποχρεωτικά στην αρχή της γραμμής (να μην
προηγούνται κενά διαστήματα). Η σύνταξή της είναι η εξής:
#include "όνομα αρχείου"
Η οδηγία αυτή απευθύνεται
ουσιαστικά στο λεκτικό αναλυτή. Σε περίπτωση που αυτός συναντήσει αυτή την
οδηγία, θα πρέπει να σταματήσει την ανάγνωση του αρχείου προγράμματος, και να
συνεχίσει με την επεξεργασία του αρχείου που ζητείται να συμπεριληφθεί. Μετά το
τέλος αυτού του αρχείου, ο λεκτικός αναλυτής πρέπει να συνεχίσει από το σημείο
του αρχείου προγράμματος, στο οποίο είχε σταματήσει. Τα αρχεία που διαβάζονται
με την οδηγία #include μπορούν να
περιέχουν και αυτά τέτοιες οδηγίες. Φυσικά μεμονωμένες λεκτικές μονάδες καθώς
και σχόλια πρέπει να περιέχονται πλήρως σε ένα αρχείο προγράμματος (δεν
επιτρέπεται να αρχίζουν σε ένα αρχείο προγράμματος και να τελειώνουν σε κάποιο
άλλο).
Η υλοποίηση της οδηγίας #include δεν είναι υποχρεωτική, αλλά η σωστή
και πλήρης υλοποίησή της προσθέτει μισή μονάδα στο λεκτικό αναλυτή. Στις ομάδες
που δε θα την υλοποιήσουν θα δοθεί κατάλληλος προεπεξεργαστής (preprocessor)
για τη σωστή μεταγλώττιση όλων των προγραμμάτων Calvin.
Παρακάτω δίνεται η γραμματική της γλώσσας Calvin σε μορφή extended BNF. Τα τερματικά σύμβολα
αναγράφονται με έντονους χαρακτήρες και μέσα σε διπλά εισαγωγικά. Μέσα σε
γωνιακές αγκύλες αναγράφονται τα μη τερματικά σύμβολα και κατ’ εξαίρεση οι
λεκτικές μονάδες:
<integer-constant> : ακέραια σταθερά (χωρίς πρόσημο)
<char-constant> : σταθερή τύπου χαρακτήρα
<string-constant> : σταθερή συμβολοσειρά
<id> : αναγνωριστικό
Ακολουθεί η
γραμματική της γλώσσας.
<program> ::= <external-functions>
<program-header>
(<local-definition>)*
<compound-statement>
<external-functions> ::= (<function-prototype>)*
<program-header> ::= “void” “main” “(” “)”
<local-definition> ::= <function-prototype>
| <function-definition>
| <variable-definition>
<function-prototype> ::= <function-header>
“;”
<function-definition> ::= <function-header>
(<local-definition>)*
<compound-statement>
<function-header> ::= <return-type>
<id>
“(” [<formal-params>] “)”
<return-type> ::= <data-type>
| “void”
<formal-params> ::= <formal-parameter>
(“,” <formal-parameter>)*
<formal-parameter> ::= <data-type>
[“&”] <id> [“[” “]”]
<data-type> ::= “integer” | “char”
<variable-definition> ::= <data-type>
<def-one-variable>
(“,” <def-one-variable>)* “;”
<def-one-variable> ::= <id>
[“[” <integer-constant> “]”]
<statement> ::= <assignment>
| <if-statement>
| <while-statement>
| <void-function-call>
| <return-statement>
| <compound-statement>
| <empty-statement>
<assignment> ::= <l-value>
“=” <expression> “;”
<l-value> ::= <id>
[“[” <expression> “]”]
<if-statement> ::= “if” “(” <b-expression> “)”
<statement>
[“else” <statement>]
<while-statement> ::= “while” “(” <b-expression> “)”
<statement>
<void-function-call> ::= <function-call>
“;”
<function-call> ::= <id> “(” [ <actual-params> ] “)”
<actual-params> ::= <actual-parameter>
(“,”
<actual-parameter>)*
<actual-parameter> ::= <expression>
| <array-as-parameter>
| <string-constant>
<array-as-parameter> ::= <id>
<return-statement> ::= “return” [ <expression> ] “;”
<empty-statement> ::= “;”
<compound-statement> ::= “{” (<statement>)* “}”
<b-expression> ::= <b-expression>
“||” <b-expression>
| <b-expression> “&&” <b-expression>
| “!”
<b-expression>
| “(”
<b-expression> “)”
| <expression> “==” <expression>
| <expression> “!=” <expression>
| <expression> “>” <expression>
| <expression> “<” <expression>
| <expression> “>=” <expression>
| <expression> “<=” <expression>
<expression> ::= <expression>
“+” <expression>
| <expression> “-” <expression>
| <expression> “*” <expression>
| <expression>
“/” <expression>
| <expression> “%”
<expression>
| “+”
<expression>
| “-”
<expression>
| <l-value>
| <integer-constant>
| <char-constant>
| <function-call>
| “(”
<expression> “)”
Προκειμένου
να υλοποιηθούν λειτουργίες που δεν υποστηρίζονται άμεσα από τη γλώσσα Calvin, έχει υλοποιηθεί μια
βιβλιοθήκη έτοιμων συναρτήσεων (run-time library). Η βιβλιοθήκη αυτή έχει
γραφεί σε 8086 assembly και πρέπει να χρησιμοποιηθεί κατά τη συνένωση (linking)
του τελικού κώδικα των προγραμμάτων σε γλώσσα Calvin.
Οι
δηλώσεις (επικεφαλίδες) των συναρτήσεων που περιέχονται στη βιβλιοθήκη
συμπεριλαμβάνονται σε αρχεία επικεφαλίδας (header files), που δίνονται μαζί με
τη βιβλιοθήκη. Οι συναρτήσεις που ορίζονται σε δύο από αυτά τα αρχεία
περιγράφονται στις επόμενες παραγράφους. Για την περιγραφή των υπόλοιπων
συναρτήσεων της βιβλιοθήκης, βλέπε την on-line τεκμηρίωση που θα δοθεί μαζί με
τη βιβλιοθήκη.
Το
αρχείο αυτό περιέχει τις εξής συναρτήσεις, που υλοποιούν τις λειτουργίες
εισόδου και εξόδου (I/O) για τους τύπους δεδομένων της γλώσσας Calvin:
void PutChar (char c)
Εκτυπώνει
το χαρακτήρα c στο τρέχον αρχείο
εξόδου.
void PutInteger (integer i)