Εργασία του μαθήματος - H γλώσσα Aegean-C

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Τελευταία νέα

15-12-1999
Νέα ενότητα: απαντήσεις σε συχνές ερωτήσεις.
15-12-1999
Νέα ενότητα: δημιουργία κώδικα για συμβολοσειρές.
15-12-1999
Νέα ενότητα: εκτέλεση και σύνδεση του μεταγλωττιστή.
14-12-1999
Καλύτερη τεκμηριώση για τη χρήση της εντολής div στις σημειώσεις για τις αριθμητικές εντολές.
8-12-1999
Αναλυτικές οδηγίες δημιουργίας κώδικα για βρόχους, μεταβλητές, κ.λπ.

Η άσκηση

Εισαγωγή

Η γλώσσα Aegean-C είναι ένα υποσύνολο της γλώσσας C. Δε διαθέτει πολλούς τύπους, δομές, δείκτες, αρκετούς τελεστές, τις περισσότερες συναρτήσεις της βιβλιοθήκης και ορισμένες εντολές. Παρόλ' αυτά περιλαμβάνει αρκετές δυνατότητες έτσι ώστε να μπορεί κανείς να γράψει ένα παιγνίδι όπως την προσγείωση στο φεγγάρι (Lunar Lander). Η παρακάτω συνοπτική περιγραφή της γλώσσας περιλαμβάνει μόνο τα στοιχεία που πρέπει να περιλαμβάνονται υποχρεωτικά στη γλώσσα. Η υλοποίηση της γλώσσας επιτρέπεται να προσθέσει δυνατότητες αρκεί να μην την κάνει ασύμβατη με τη βασική γλώσσα. Η σημασία όλων των στοιχείων της γλώσσας όπου δεν περιγράφεται διαφορετικά είναι ίδια με αυτή της C.

Λεκτικά στοιχεία

Η λεκτική δομή της Aegean-C είναι αρκετά απλή:

Μεταβλητές

Εντολές

Κάθε εντολή της Aegean-C τερματίζεται με ";". Πρέπει να υποστηρίζονται οι παρακάτω εντολές:

Εκφράσεις

Συναρτήσεις χρήστη

Ο χρήστης μπορεί να ορίσει νέες συναρτήσεις με την παρακάτω σύνταξη: 
όνομα_συνάρτησης()
{
	εντολές
}
Η συνάρτηση με το όνομα aegean αποτελεί την είσοδο του προγράμματος.

Ορισμένες συναρτήσεις

Στη βιβλιοθήκη της Aegean-C ορίζονται οι παρακάτω συναρτήσεις:
putstring(string)
Εμφανίζει τη συμβολοσειρά string στην έξοδο. Παράδειγμα putstring("hello, world\n").
putint(integer-expression)
Εμφανίζει την τιμή της έκφρασης στην έξοδο. Για παράδειγμα putint(3+5) εμφανίζει 7.
getint(variable)
Διαβάζει έναν ακέραιο από την είσοδο του προγράμματος και θέτει την τιμή της μεταβλητής.
getint()
Διαβάζει έναν ακέραιο από την είσοδο του προγράμματος και τον επιστρέφει (εναλλακτική δυνατότητα υλοποίησης).

Παράδειγμα

Το παρακάτω παράδειγμα τυπώνει ένα ορθογώνιο τρίγωνο από αστεράκια:
// A simple program in Aegean-C

int numstars;
int i;
int j;

// Print numstars stars
stars()
{
        i = 0;
        while (i < numstars) {
                putstring("*");
                i = i + 1;
        }
        putstring("\n");
}

// Program entry point
aegean()
{
        j = 0;

        while (j < 10) {
                numstars = j;
                stars();
                j = j + 1;
        }
}
Παράδειγμα εξόδου: 

*
**
***
****
*****
******
*******
********
*********

Το παράδειγμα μεταγλωττισμένο

Ο παρακάτω κώδικας είναι απλοποιημένη μορφή του κώδικα που παράγει ο μεταγλωττιστής της C (cc -S) για το αντίστοιχο παράδειγμα σε C.
.section        .rodata
.LC0:
        .string "*"
.LC1:
        .string "\n"
.text
        .align 4
.globl stars
        .type    stars,@function
stars:
        movl $0,i
.L2:
        movl i,%eax
        cmpl numstars,%eax
        jl .L4
        jmp .L3
.L4:
        pushl $.LC0
        call putstring
        addl $4,%esp
        incl i
        jmp .L2
.L3:
        pushl $.LC1
        call putstring
        addl $4,%esp
.L1:
        ret

.globl aegean
        .type    aegean,@function
aegean:
        movl $0,j
.L6:
        cmpl $9,j
        jle .L8
        jmp .L7
.L8:
        movl j,%eax
        movl %eax,numstars
        call stars
        incl j
        jmp .L6
.L7:
.L5:
        ret

        .comm   numstars,4,4
        .comm   i,4,4
        .comm   j,4,4

Προσθήκες

Η γλώσσα Aegean-C μπορεί να επεκταθεί με πολλούς και διαφορετικούς τρόπους. Ιδιαίτερα σημαντικές θεωρούνται επεκτάσεις με δυνατότητες που δεν υπάρχουν στη γλώσσα C. Μερικές ιδέες για επεκτάσεις είναι οι παρακάτω:

Αναφορά υλοποίησης

Κάθε υλοποίηση της γλώσσας Aegean-C πρέπει να συνοδεύεται από μια αναφορά υλοποίησης. Αυτή πρέπει να περιέχει τις παρακάτω ενότητες:

Πρόγραμμα εργασίας

Εβδομάδα 1

Τα παρακάτω πρέπει να έχουν ολοκληρωθεί από κάθε ομάδα:

Εβδομάδα 2

Τα παρακάτω πρέπει να έχουν ολοκληρωθεί από κάθε ομάδα:

Εβδομάδα 3

Τα παρακάτω πρέπει να έχουν ολοκληρωθεί από κάθε ομάδα:

Εβδομάδα 4

Απλές στρατηγικές παραγωγής κώδικα

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

Η παραγωγή κώδικα γίνεται αναδρομικά. Ο κανόνας της συντακτικής ανάλυσης που αναγνωρίζει ολόκληρο το πρόγραμμα μπορεί να καλεί τη συνάρτηση που παράγει τον κώδικα:

prog    : dec_seq               { codegen($1); }
        ;

dec_seq : /* ... */
Η συνάρτηση αυτή καλεί αναδρομικά άλλες συναρτήσεις ανάλογα με το είδος του κόμβου του δένδρου.

Εκφράσεις

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

Η υλοποίηση αυτή είναι κατάλληλη για αρχιτεκτονικές επεξεργαστών που βασίζονται σε στοίβα όπως η Java Virtual Machine και ο επεξεργαστής αριθμών κινητής υποδιαστολής της σειράς Intel Pentium, αλλά μπορεί να χρησιμοποιηθεί και σε αρχιτεκτονικές που βασίζονται σε καταχωρητές. Έτσι η έκφραση b + d υλοποιείται με τη σειρά:

        pushl   b               // Push operands
        pushl   d
        pop     %eax            // Retrieve operand 1
        pop     %ebx            // Retrieve operand 2
        add     %ebx, %eax      // Perform operation
        push    %eax            // Push back result
από κώδικα της μορφής:
void
codegen_add(struct s_tree *left, struct s_tree *right)
{
        codegen(left);
        codegen(right);
        printf("\tpop %%eax\n");
        printf("\tpop %%ebx\n");
        printf("\tadd %%ebx, %%eax\n");
        printf("\tpush %%eax\n");
}

Παράδειγμα:

a = b + c * d;
Δένδρο: 
    =
 a      +
     b    *
         c  d
Κώδικας:
        pushl   a
        pushl   b
        pushl   c
        pushl   d
        pop     %eax            // c *  d
        pop     %ebx
        mul     %ebx
        push    %eax
        pop     %eax            // b + (c * d)
        pop     %ebx
        add     %ebx, %eax
        push    %eax
        pop     %esi            // a = ...
        pop     %eax
        mov     %eax, (%esi)

Βρόχοι και αποφάσεις

Ο κώδικας για του βρόχους και τις αποφάσεις βασίζεται σε άλματα σε συγκεκριμένες ετικέτες. Τη δημιουργία του κώδικα διευκολύνει η υλοποίηση συνάρτησης new_label που επιστρέφει νέα ονόματα ετικετών (πιθανώς με τη χρήση των συναρτήσεων sprintf και malloc για την αποθήκευση του αποτελέσματος). Έτσι για παράδειγμα ο κώδικας για την εντολή while μπορεί να είναι της μορφής:
void
codegen_while(struct s_tree *expr, struct s_tree *stmt)
{
        char *loop = new_label();
        char *end = new_label();

        printf("%s:\n", loop);
        codegen(expr);
        printf("\tpop %%eax\n");
        printf("\tcmp %%eax, 0\n");
        printf("\tje %s\n", end);
        codegen(stmt);
        printf("\tjmp %s\n", loop);
        printf("%s:\n", end);
}
για να παράγει κώδικα όπως τον παρακάτω:
.L0053:
        pushl a
        pop %eax
        cmp %eax, 0
        je .L0054
        // code for the loop body
        jmp .L0053
.L0054:

Συναρτήσεις

Ο κώδικας για την υλοποίηση μιας συνάρτησης (π.χ. με όνομα fname) μπορεί να είναι της μορφής:
.globl fname
        .type    fname,@function
fname:
        // procedure body
        ret
Αντίστοιχα η κλήση σε μια συνάρτηση (π.χ. με όνομα fname) γίνεται με την ακολουθία call fname.

Μεταβλητές

Για κάθε ακέραια μεταβλητή αρκεί να υπάρχει στο αρχείο της συμβολικής γλώσσας (όχι ανάμεσα σε εντολές κώδικα) μια δήλωση της μορφής:
        .comm   varname,4,4
Η χρήση των μεταβλητών αυτών μπορεί να γίνει με απευθείας χρήση του ονόματος στις αντίστοιχες εντολές:
        movl %eax,varname
        // ...
        cmpl varname,%eax

Δημιουργία κώδικα για συμβολοσειρές

Αντίθετα με ό,τι αναφέρθηκε στο εργαστήριο, ο κώδικας για τη δημιουργία των συμβολοσειρών δεν είναι απαραίτητο να φτιαχτεί σε δεύτερη φάση μεταγλώττισης. Μπορεί μια συμβολοσειρά να περιληφθεί και μέσα στις εντολές του υπόλοιπου κώδικα αρκεί να προβλεφθεί μια εντολή jmp για να μην εκτελείται η συμβολοσειρά ως κώδικας. Οι ετικέτες για τη συμβολοσειρά και τον προορισμό της jmp θα δημιουργούνται από τη συνάρτηση new_label(). Παράδειγμα για την printf:
.globl main
        .type    main,@function
main:
        pushl %ebp
        movl %esp,%ebp
        jmp .LC2                // Skip the string data
.LC0:                           // Label for the string data
        .string "hello\n"       // String data
.LC2:                           // Label for skipping
        pushl $.LC0             // Push the address of the string data ...
        call printf             // ... for printf to print
        addl $4,%esp
.L1:
        leave
        ret
Στο παραπάνω παράδειγμα φαίνεται και ότι ο συμβολομεταφραστής μπορεί να χειριστεί τους κωδικούς διαφυγής όπως το \n χωρίς επέμβαση από το μεταγλωττιστή.

Εκτέλεση και σύνδεση του μεταγλωττιστή

Η εκτέλεση του μεταγλωττιστή της Aegean C (ac) μπορεί να γίνει με την παρακάτω διαδικασία: 
# Compile the source file lander.a to assembly file lander.s
ac <lander.a >lander.s
# Assemble lander.s; compile and link-in the Aegean runtime library (aegean.c)
cc -o lander lander.s aegean.c
Μπορεί ακόμα να αυτοματοποιηθεί με το παρακάτω Bourne shell script:
#!/bin/sh

# Names for the library and the compiler driver
LIB=aegean.c
COMP=acd

if [ "$1" = '' ]
then
        echo "Usage: $0 basename (e.g. $0 lander)" 1>&2
        echo "Will compile basename.a to basename via basename.s" 1>&2
        exit 1
fi
$COMP <$1.a >$1.s
cc -i $1 $1.s $LIB

Απαντήσεις σε συχνές ερωτήσεις

  1. Χρειάζεται τελικά δεύτερη φάση δημιουργίας κώδικα για τις μεταβλητές και τις συμβολοσειρές;
    Όχι, α) ο κώδικας για τις μεταβλητές δημιουργείται εκτός των εντολών αφού αυτές ορίζονται έξω από τις συναρτήσεις β) για τις συμβολοσειρές υπάρχει μέθοδος δημιουργίας κώδικα που δεν απαιτεί δεύτερο πέρασμα.
  2. Τι να κάνουμε με τα λάθη reduce/reduce του yacc.
    Ψάξτε στο αρχείο y.output για να δείτε τους κανόνες που δημιουργούν αυτά τα λάθη.
  3. Τι σημαίνει το λάθος X rules never reduced;
    Κάποια τερματικά σύμβολα έχουν οριστεί σε κανόνες, αλλά δεν έχουν χρησιμοποιηθεί σε κανέναν άλλο κανόνα. Ψάξτε στο αρχείο y.output (στο τέλος του) για να δείτε τα μη τερματικά σύμβολα που έχουν αυτό το πρόβλημα.
  4. Πως μπορούμε να βρούμε σφάλματα στο πρόγραμμά μας;
    Με τον απασφαλματωτή gdb.

    Εντολές

    break
    καθορίζει σημεία που θέλετε να σταματήσετε. π.χ. break main.c:22
    cont
    συνεχίζει την εκτέλεση μετά από break.
    step
    εκτελεί την επόμενη γραμμή κώδικα
    next
    εκτελεί την επόμενη γραμμή κώδικα χωρίς να μπαίνει μέσα στις συναρτήσεις
    where
    μετά από ένα segmentation fauls σας λέει σε ποιο σημείο έγινε.
    print expr
    τυπώνει την τιμή της έκφρασης expr
    help
    τυπώνει βοήθεια για τον gdb
    quit
    τερματίζει τη λειτουργία του gdb

Βιβλιογραφία

Creative Commons License  Τελευταία αλλαγή: Παρασκευή, 7 Νοεμβρίου 2003 3:38 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».