Το μεταεργαλείο yacc

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

Το μεταεργαλείο yacc

Το μεταεργαλείο yacc επιτρέπει την αυτόματη δημιουργία γλωσσικών επεξεργαστών και συντακτικών αναλυτών.
Ως είσοδο δέχεται μια γραμματική BNF σε μορφή κατάλληλη για μηχανική επεξεργασία καθώς και σημασιολογικούς κανόνες.
Ως έξοδο παράγει κώδικα που επεξεργάζεται τα τερματικά σύμβολα που δέχεται στην είσοδό του και εκτελεί του σημασιολογικούς κανόνες για τις γραμματικές προτάσεις που αναγνωρίζει.
Η λειτουργία του κώδικα που παράγει βασίζεται σε ένα πεπερασμένο αυτόματο στοίβας επαυξημένο με ειδικούς κανόνες για αιτιοκρατική λειτουργία.
Το μεταεργαλείο yacc συνεργάζεται άριστα με το μεταεργαλείο lex για τη λεκτική ανάλυση.

Διαδικασία χρήσης

Το αρχείο εισόδου για το εργαλείο yacc έχει κατάληξη .y
Το αρχείο εισόδου περιέχει δηλωτική περιγραφή της γραμματικής που θα αναγνωρίσει ο συντακτικός αναλυτής καθώς και σημασιολογικούς κανόνες.
Το εργαλείο yacc (με παραμέτρους -vd και το όνομα του αρχείου) διαβάζει το αρχείο αυτό και δημιουργεί:
- ένα αρχείο σε C με όνομα y.tab.c που υλοποιεί το συντακτικό αναλυτή που προδιαγράψαμε.
- ένα αρχείο επικεφαλίδας σε C με όνομα y.tab.h που ορίζει σταθερές για το λεκτικά (τερματικά) σύμβολα.
- ένα αρχείο κειμένου με όνομα y.output που επεξηγεί τις καταστάσεις και τις μεταπτώσεις του αυτομάτου.
Ο σαρωτής είναι υλοποιημένος στη συνάρτηση yyparse().
Κατά τη λειτουργία του ο συντακτικός αναλυτής καλεί τη συνάρτηση yylex() για να λάβει το επόμενο λεκτικό σύμβολο.
Για τη λειτουργία του συντακτικού αναλυτή τυπικά καλούμε τη συνάρτηση yyparse() μέσω της συνάρτησης main() την οποία υλοποιούμε εμείς.

Σημείωση

Στο εργαστήριο θα χρησιμοποιηθεί το πρόγραμμα bison που είναι συμβατό υπερσύνολο του yacc.

Αρχείο εισόδου

Το αρχείο εισόδου αποτελείται από τα παρακάτω τμήματα:
- δηλώσεις της C
- δηλώσεις του yacc
- κανόνες
- κώδικα χρήστη

Η δομή του αρχείου είναι η παρακάτω:

%{
C declarations
%}

Yacc declarations

%%
Grammar rules
%%
Additional C code

Οι δηλώσεις της C επιτρέπουν τη δήλωση συναρτήσεων και τύπων.
Οι δηλώσεις του yacc ορίζουν:
- τα ονόματα τερματικών και μη συμβόλων
- τους τύπους τερματικών και μη συμβόλων
- την προτεραιότητα των τελεστών
- την ένωση (union) της C που φυλάει όλα τα στοιχεία
- το σύμβολο αρχής
Οι κανόνες τις γραμματικής ορίζουν τη σύνταξη της γλώσσας που θα επεξεργάζεται ο αναλυτής καθώς και την αντίστοιχη σημασιολογική ενέργεια για κάθε κανόνα.
Ο κώδικας της C περιέχει συχνά τη συνάρτηση main και άλλες βοηθητικές συναρτήσεις.

Δηλώσεις του yacc

Οι δηλώσεις του yacc μας επιτρέπουν να ορίσουμε:

Συμβολικές τιμές για τα τερματικά σύμβολα με τη δήλωση %token:
%token tINC, tDEC, tFOR, tWHILE, tELSE
Την προτεραιότητα και την προσεταιριστικότητα των τελεστών με τις δηλώσεις:

%left τερματικό σύμβολο ...
προσεταιριστικότητα από αριστερά προς τα δεξιά. Α τελ Β τελ Γ είναι (Α τελ Β) τελ Γ.
%right τερματικό σύμβολο ...
προσεταιριστικότητα από δεξιά προς τα αριστερά. Α τελ Β τελ Γ είναι Α τελ (Β τελ Γ).
%nonassoc τερματικό σύμβολο ...
μη προσεταιριστικότητα. Α τελ Β τελ Γ εμφανίζει μήνυμα λάθους
Η προτεραιότητα ορίζεται από σειρά εμφάνισης με τους τελεστές στις πρώτες δηλώσεις να έχουν τη χαμηλότερη.
Παράδειγμα:
%left   '+' '-'
%left   '*' '/' '%'
%left   '.'
%right  '^'
%left   UMINUS
Τους τύπους των πιθανών σημασιολογικών τιμών που μπορούν να συσχετιστούν με τερματικά και μη σύμβολα με τη δήλωση %union.
Παράδειγμα:
%union {
        double d;
        struct s_vec {double x, y;} v;
        char *s;
        double (*f)(double);
        double (*f2)(double, double);
        double (*f2i)(int, double);
};
Τον τύπο των μη τερματικών συμβόλων με τη δήλωση %type . Ο τύπος typename πρέπει να είναι κάποιο μέλος της ένωσης %union.
Παράδειγμα:
%type <s>       optasg
%type <d>       scalar
%type <v>       vector
Τους τύπους των τερματικών συμβόλων με τη χρήση του στις δηλώσεις %token, %left, %right:
Παράδειγμα:
%token <d>      tNUM
%token <s>      tVAR
%token <v>      tVEC

%left <c>       '+' '-'
Το σύμβολο αρχής με τη δήλωση %start symbol.
Παράδειγμα:
%start program

Συντακτικοί κανόνες

Οι συντακτικοί κανόνες (syntax rules) γράφονται σε μορφή BNF με την παρακάτω σύνταξη:
name1   : symbol01 symbol02 symbol03 ...        /* Alternative 1 */
        | symbol11 symbol12 ...                 /* Alternative 2 */
        | symbol21 symbol22 symbol23 ...        /* Alternative 3 */
        ;

name2   : ...
Κάθε κανόνας ορίζει μια σειρά από παραγωγές για το αντίστοιχο μη τερματικό σύμβολο.
Τα σύμβολα δεξιά του κανόνα μπορεί να είναι τερματικά ή μη τερματικά.
Επιτρέπεται η διατύπωση εναλλακτικών κανόνων με το ίδιο όνομα ή ο χωρισμός των παραγωγών με το σύμβολο |.
Η επανάληψη ορίζεται με τη χρήση αναδρομής.
Καλό είναι, για να μη δημιουργείται κατά τη μεταγλώττιση μεγάλη στοίβα στο αυτόματο του yacc να χρησιμοποιούμε αριστερή αναδρομή και όχι δεξιά αναδρομή (ο κανόνας δηλαδή να εμφανίζεται αναδρομικά στο αριστερό μέρος της παραγωγής και όχι στο δεξιό).
Παράδειγμα αριστερής αναδρομής (ορθή χρήση):
expseq1:  exp
        | expseq1 ',' exp
        ;

Παράδειγμα δεξιάς αναδρομής (να αποφεύγεται):
expseq1:  exp
        | exp ',' expseq1

Τερματικά και μη τερματικά σύμβολα

Τα τερματικά σύμβολα του yacc πρέπει να οριστούν με τη χρήση της δήλωσης %token.
Επίσης είναι δυνατή η χρήση απλών χαρακτήρων ως τερματικά σύμβολα γράφοντάς τους σε μονά εισαγωγικά: 'c'
Για κάθε τερματικό σύμβολο που ορίζεται στο αρχείο .y ο yacc δημιουργεί μια δήλωση σταθεράς (#define) στο αρχείο y.tab.h για να μπορέσει ο λεκτικός αναλυτής να επιστρέψει την ίδια τιμή.
Παράδειγμα:
- Αρχείο gram.y:
  %token tWHILE
- Αρχείο y.tab.h
  #define tWHILE 257
- Αρχείο scan.l
  %{
  #include "y.tab.h"
  %}
  
  %%
  
  "while" { return tWHILE; }
Για να είναι δυνατός ο ορισμός παραγωγών με αμοιβαία αναδρομή τα μη τερματικά σύμβολα μπορούν να χρησιμοποιηθούν πριν οριστούν από κάποιο κανόνα.

Τιμές των συμβόλων

Κατά τη σημασιολογική ανάλυση μας ενδιαφέρει εκτός από το είδος ενός λεκτικού συμβόλου (μεταβλητή, ακέραιος, συμβολοσειρά) και η τιμή του (count, 45, "hello").
Η τιμή είναι απαραίτητη για την υλοποίηση του συντακτικού δένδρου και τη δημιουργία του κώδικα.
Το εργαλείο yacc συνδέει κανονικά με κάθε σύμβολο μια ακέραια τιμή.
Αν θέλουμε να συνδέσουμε άλλου είδους τιμή (π.χ. double) για κάθε σύμβολο μπορούμε να το κάνουμε με τον ορισμό της σταθεράς YYSTYPE στο τμήμα ορισμών της C στην αρχή του αρχείου:
Παράδειγμα:
%{
#define YYSTYPE double
%}
Ο λεκτικός αναλυτής (η συνάρτηση yylex()) πρέπει να θέτει κάθε φορά την καθολική μεταβλητή yylval που ορίζεται στο αρχείο y.tab.h στη σωστή τιμή (αν υπάρχει) για το αντίστοιχο σύμβολο.
Αν θέλουμε να ορίσουμε διαφορετικό τύπο τιμής για διαφορετικά σύμβολα μπορούμε να το κάνουμε με τις δηλώσεις %union, %type και %token.
Στην περίπτωση αυτή η μεταβλητή yylval ορίζεται από το yacc ως ένωση με πεδία αντίστοιχα με τα ονόματα των τύπων στην ένωση.
Ο λεκτικός αναλυτής στην περίπτωση αυτή πρέπει να θέτει το αντίστοιχο πεδίο της ένωσης yylval (π.χ. yylval.i = atoi(yytext)).

Σημασιολογικοί κανόνες

Κάθε παραγωγή μπορεί να έχει στο δεξί της μέρος, μέσα σε {}, έναν σημασιολογικό κανόνα γραμμένο σε C.
Ο σημασιολογικός κανόνας μπορεί να έχει πρόσβαση στις τιμές των συμβόλων στην αριστερή πλευρά του κανόνα με τα ονόματα των ειδικών μεταβλητών $1, $2, $3 ... όπου $1 είναι η τιμή του πρώτου συμβόλου, $2 η τιμή του δεύτερου, κ.λπ.
Ο σημασιολογικός κανόνας μπορεί να θέσει την τιμή του μη τερματικού συμβόλου στα αριστερά του κανόνα με ανάθεση στην ειδική μεταβλητή $$.
Παράδειγμα:
expr : expr + expr { $$ = $1 + $3; }
;
Οι τύποι των ειδικών μεταβλητών $$, $1, $2, ... είναι αντίστοιχοι με τον τύπο που έχει δηλωθεί για το σχετικό τερματικό ή μη τερματικό σύμβολο.
Τυπικές χρήσεις των σημασιολογικών κανόνων είναι:
- ο απευθείας υπολογισμός μιας τιμής:
  Παράδειγμα:
  expr : expr + expr { $$ = $1 + $3; }
  ;
- η δημιουργία ενός κόμβου για το συντακτικό δένδρο:
  Παράδειγμα:
  expr : expr + expr { $$ = mkbinop($1, $2, $3); }
  ;
- η εκτέλεση κάποιου κώδικα:
  Παράδειγμα (μετασχηματίζει αριθμητική με τελεστές σε κώδικα για κλήση συνάρτησης):
  expr : expr + expr { printf("plus(%d, %d)", $1, $3); }
  ;

Απλό παράδειγμα

Το παρακάτω πρόγραμμα υλοποιεί μια απλή αριθμομηχανή.

/* Infix notation calculator--calc */

%{
#define YYSTYPE double
#include <math.h>               /* Needed for pow */
%}

/* YACC Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* negation--unary minus */
%right '^'    /* exponentiation        */

/* Grammar follows */
%%
input:    /* empty string */
        | input line
;

line:     '\n'
        | exp '\n'  { printf ("\t%.10g\n", $1); }
;

exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1, $3); }
        | '(' exp ')'        { $$ = $2;         }
;
%%
#include <ctype.h>
#include <stdio.h>

/* Lexical analyzer */
int
yylex ()
{
        int c;

        /* skip white space  */
        while ((c = getchar ()) == ' ' || c == '\t')
                ;
        /* process numbers   */
        if (c == '.' || isdigit (c)) {
                ungetc (c, stdin);
                scanf ("%lf", &yylval);
                return NUM;
        }
        /* return end-of-file  */
        if (c == EOF)
                return 0;
        /* return single chars */
        return c;
}

main ()
{
        yyparse();
}

/* error function */
void
yyerror (char *s)  /* Called by yyparse on error */
{
        printf("%s\n", s);
}

Μεταγλώττιση και χρήση

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

$ yacc -vd calc.y
$ ls -rtl
total 23
-rw-r--r--   1 dspin    users        1304 Nov 16 22:51 calc.y
-rw-r--r--   1 dspin    users          32 Nov 16 22:51 y.tab.h
-rw-r--r--   1 dspin    users       12078 Nov 16 22:51 y.tab.c
-rw-r--r--   1 dspin    users        3773 Nov 16 22:51 y.output
$ cc -o calc y.tab.c -lm
$ ./calc
1+2*3
        7
3*(1+2)
        9
sdkjfh
syntax error
$

Τρόπος λειτουργίας

Η λειτουργία του yacc βασίζεται σε ένα ΝΠΑ στοίβας.
Κατά τη λειτοyργία του o yacc διαβάζει σύμβολα και τα προσθέτει τη στοίβα. Η λειτουργία αυτή καλείται πράξη ολίσθησης (shift action).
Κατά την ανάγνωση των λεκτικών συμβόλων o yacc κρατάει ένα σύμβολο προεξέτασης (lookahead token) εκτός της στοίβας για να μπορεί να διαλέξει ανάμεσα σε ισοδύναμους κανόνες της γραμματικής. (Οι γραμματικές που αναγνωρίζει ο yacc μπορούν να αναγνωριστούν με τη χρήση ενός μόνο συμβόλου προεξέτασης).
Όταν κάποια σύμβολα στη στοίβα ταιριάζουν με το δεξί τμήμα ενός κανόνα ο yacc αντικαθιστά τα σύμβολα αυτά από το αριστερό σύμβολο στον κανόνα. Η λειτουργία αυτή καλείται πράξη ελάττωσης (reduce action). Για την επιλογή ανάμεσα σε πολλούς υποψήφιους κανόνες o yacc χρησιμοποιεί το σύμβολο προεξέτασης.
Υπάρχει περίπτωση για έναν κανόνα να ταιριάζει ολίσθηση και ελάττωση:
if_stmt : IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
;

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

Το παρακάτω απόσπασμα από το αρχείο y.output απεικονίζει μια κατάσταση, τους κανόνες που είναι υποψήφιοι για αναγνώριση (τι βρίσκεται στη στοίβα), και τις ενέργειες ανάλογα με το σύμβολο που θα διαβαστεί:

state 17
        exp : exp . '+' exp  (6)
        exp : exp . '-' exp  (7)
        exp : exp '-' exp .  (7)
        exp : exp . '*' exp  (8)
        exp : exp . '/' exp  (9)
        exp : exp . '^' exp  (11)

        '*'  shift 12
        '/'  shift 13
        '^'  shift 14
        '-'  reduce 7
        '+'  reduce 7
        '\n'  reduce 7
        ')'  reduce 7

Ασκήσεις

Να υλοποιήσετε με το μεταεργαλείο yacc έναν υπολογιστή που να επεξεργάζεται διανύσματα (δύο διαστάσεων) με:
1. τους δυαδικούς τελεστές σε διανύσματα + -
2. το μοναδικό τελεστή -
3. τους τελεστές μεταξύ διανύσματος και σταθεράς * /
4. παρενθέσεις
Το κάθε διάνυσμα θα μπορεί να γράφεται ως [χ, ψ]. Κάθε γραμμή εισόδου θα αποτελεί μια εντολή για πράξη. Παράδειγμα:
```
[1, 2]
Result = [1, 2]
[1, 1] + [1, 2]
Result = [2, 2]
-([1, 2] * 2 + [1, 1])
Result = [-3, -5]
```

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

Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 235-244. Συμμετρία 1993.

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 257–267. Addison-Wesley, 1985.
Free Software Foundation. Bison — the YACC-compatible parser generator. Available online: http://www.gnu.org/manual/flex-2.5.4/flex.html, November 1995.
Stephen C. Johnson and Michael E. Lesk. Language development tools. Bell System Technical Journal, 56(6):2155–2176, July-August 1987.
Stephen C. Johnson. Yacc — yet another compiler-compiler. Computer Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, USA, July 1975.
John Levine, Tony Mason, and Doug Brown. Lex and Yacc. O'Reilly & Associates, second edition, 1992.

Περιεχόμενα