Συντακτική ανάλυση

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

Ο συντακτικός αναλυτής

Ο συντακτικός αναλυτής:

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

Τρόποι υλοποίησης

Διαχωρίζουμε δύο είδη συντακτικών αναλυτών ανάλογα με τον τρόπο που σχηματίζουν το δένδρο:

Συντακτικός αναλυτής από πάνω προς τα κάτω (top down parser): ο αναλυτής αυτός ξεκινά από τη ρίζα του δένδρου και αντικαθιστά μη τερματικά σύμβολα από το αριστερό τμήμα παραγωγών με τα αντίστοιχα δεξιά τους τμήματα μέχρι να αναγνωρίσει όλη την είσοδο. Το μη τερματικό σύμβολο που επιλέγεται για αντικατάσταση είναι κάθε φορά το αριστερότερο (leftmost) (L) μη τερματικό σύμβολο. Ακόμα, ο αναλυτής για να μπορέσει να υλοποιηθεί πρέπει να αρκεί να διαβάζει κάθε φορά ένα (1) μόνο σύμβολο από την είσοδο από αριστερά προς τα δεξιά (L). Έτσι ο αναλυτής και η αντίστοιχη γραμματική ονομάζονται LL(1).
Ο αναλυτής αυτός μπορεί να υλοποιηθεί είτε ως ένας συντακτικός αναλυτής αναδρομικής κατάβασης (recursive descent parser) ή ως ένα ειδικό αυτόματο στοίβας. Ο συντακτικός αναλυτής αναδρομικής κατάβασης αποτελείται από συναρτήσεις, μια για κάθε μη τερματικό σύμβολο, που καλούν η μια την άλλη. Το ρόλο της στοίβας παίζει η στοίβα κλήσεων των συναρτήσεων που υλοποιεί ο επεξεργαστής. Για το λόγο αυτό οι συντακτικοί αυτοί αναλυτές είναι συχνά γρηγορότεροι από αυτούς που υλοποιούνται με αυτόματα.
Συντακτικός αναλυτής από κάτω προς τα πάνω (bottom up parser): ο αναλυτής αυτός αντικαθιστά δεξιά τμήματα παραγωγών με τα αντίστοιχα αριστερά τους τμήματα.
Ο αναλυτής αυτός χρησιμοποιεί κάθε φορά τη δεξιότερη (rightmost) παραγωγή. Ανάλογα με το αν χρειάζεται να εξετάσει 0, 1 ή Κ σύμβολα εισόδου για να υλοποιήσει μια παραγωγή ονομάζεται LR(0), LR(1) ή LR(K). Η υλοποίηση του αναλυτή αυτού γίνεται από ειδικό αυτόματο στοίβας.

Και στις δύο περιπτώσεις οι γραμματικές πρέπει να εκπληρούν ορισμένους κανόνες για να μπορούν να σχηματίσουν τον αντίστοιχο συντακτικό αναλυτή και κατηγοριοποιούνται ανάλογα με το όνομα του αναλυτή (LL(1), LR(1), ...).

Αναλυτής αναδρομικής κατάβασης

Ο συντακτικός αναλυτής αναδρομικής κατάβασης υλοποιεί μια συνάρτηση για κάθε κανόνα της γραμματικής.
Η κάθε συνάρτηση:
- Για τα μη τερματικά σύμβολα του κανόνα καλεί την αντίστοιχη συνάρτηση.
- Διαβάζει τα τερματικά σύμβολα του κανόνα από το λεκτικό αναλυτή.
- Αν διαβάσει ένα τερματικό σύμβολο που δεν αντιστοιχεί στον κανόνα το σπρώχνει πίσω στην είσοδο (ungetch()) και επιστρέφει.
- Αν έχει να επιλέξει ανάμεσα σε διαφορετικές παραγωγές για έναν κανόνα, διαβάζει ένα σύμβολο εισόδου και αποφασίζει ανάλογα με αυτό.

Παράδειγμα

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

  expr		::= term ('+' term |'-' term) * 
  term		::= factor ('*' factor |'/' factor) * 
  factor	::= digit | '-' factor | '(' expr ')'  
  digit	::= 0 | 1 | 2 | 3 |4 | 5 | 6 | 7 | 8 | 9

και τυπώνει "Parse ok", ") expected" ή "Syntax error".

/*
* Recursive descent parser for the following expression grammar:
* expr         ::= term ('+' term |'-' term) *
* term         ::= factor ('*' factor |'/' factor) *
* factor       ::= digit | '-' factor | '(' expr ')'
* digit        ::= 0 | 1 | 2 | 3 |4 | 5 | 6 | 7 | 8 | 9
*
* D. Spinellis, November 1999
*
* $Id: parse0.c 1.1 1999/11/10 00:14:12 dds Exp dds $
*
*/

#include <stdio.h>

/* Forward declarations */
void term(void);
void factor(void);

/* expr ::= term ('+' term |'-' term) * */
void
expr(void)
{
        int c;

        term();
        for (;;) {
                switch (c = getchar()) {
                case '+':
                        term();
                        break;
                case '-':
                        term();
                        break;
                default:
                        ungetc(c, stdin);
                        return;
                }
        }
}

/* term ::= factor ('*' factor |'/' factor) * */
void
term(void)
{
        int c;

        factor();
        for (;;) {
                switch (c = getchar()) {
                case '*':
                        factor();
                        break;
                case '/':
                        factor();
                        break;
                default:
                        ungetc(c, stdin);
                        return;
                }
        }
}

/* factor ::= digit | '-' factor | '(' expr ')' */
void
factor(void)
{
        int c;

        switch (c = getchar()) {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
                return;
        case '-':
                factor();
                ;
        case '(':
                expr();
                c = getchar();
                if (c != ')') {
                        printf("Expected ')'\n");
                        exit(1);
                }
                return;
        default:
                printf("Syntax error\n");
                exit(1);
        }
}

/*
* Test harness
*/
main()
{
        expr();
        printf("Parse ok\n");
}

Χρήση του αναλυτή

% parse
1+2*4-7*(3-1)
Parse ok

% parse
3++3-3
Syntax error

% parse
3-2*(2+2
Expected ')'

% parse
2-
Syntax error

Παράσταση του συντακτικού δένδρου

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

Παράδειγμα ορισμού (tree.h)

/*
* Tree type and building function declarations
*
* D. Spinellis, November 1999
*
* $Id: tree.h 1.1 1999/11/09 23:32:12 dds Exp $
*
*/

enum e_nodetype {
        ent_binop,                              /* Binary operator expr */
        ent_unop,                               /* Unary operator expr */
        ent_digit                               /* Digit expr */
};

struct s_tree {
        enum e_nodetype nt;                     /* Expression type */
        union {
                struct s_binop {
                        struct s_tree *left, *right;
                        char op;
                } binop;                        /* Binary operator expr */
                struct s_unary {
                        struct s_tree *expr;
                        char op;
                } unop;                         /* Unary operator expr */
                int digit;                      /* Digit expression */
        } u;
};

struct s_tree * mk_binop(struct s_tree *left, char op, struct s_tree *right);
struct s_tree * mk_unop(char op, struct s_tree *expr);
struct s_tree * mk_digit(char c);

Παράδειγμα συναρτήσεων δημιουργία και εκτύπωσης (tree.c)

/*
* Tree building functions
*
* D. Spinellis, November 1999
*
* $Id: tree.c 1.2 1999/11/10 09:15:35 dds Exp $
*
*/

#include <stdlib.h>
#include "tree.h"

struct s_tree *
mk_binop(struct s_tree *left, char op, struct s_tree *right)
{
        struct s_tree *t = malloc(sizeof(struct s_tree));

        t->nt = ent_binop;
        t->u.binop.left = left;
        t->u.binop.op = op;
        t->u.binop.right = right;
        return (t);
}

struct s_tree *
mk_unop(char op, struct s_tree *expr)
{
        struct s_tree *t = malloc(sizeof(struct s_tree));

        t->nt = ent_unop;
        t->u.unop.op = op;
        t->u.unop.expr = expr;
        return (t);
}

struct s_tree *
mk_digit(char c)
{
        struct s_tree *t = malloc(sizeof(struct s_tree));

        t->nt = ent_digit;
        t->u.digit = c -'0';
        return (t);
}

/*
* Indent output by the indent ammount given
*/
static void
indent(int level)
{
        int i;

        for (i = 0; i < level; i++)
                printf("    ");
}

/*
* Dump an expression tree to the standard output
*/
void
dumptree(struct s_tree *t)
{
        static int il = 0;              /* Indent level */

        il++;
        switch (t->nt) {
        case ent_binop:
                dumptree(t->u.binop.left);
                indent(il); printf("%c\n", t->u.binop.op);
                dumptree(t->u.binop.right);
                break;
        case ent_unop:
                indent(il); printf("%c\n", t->u.unop.op);
                dumptree(t->u.unop.expr);
                break;
        case ent_digit:
                indent(il); printf("%d\n", t->u.digit);
                break;
        }
        il--;
}

Δημιουργία συντακτικού δένδρου

Για να κάνουμε έναν συντακτικό αναλυτή αναδρομικής καθόδου να δημιουργήσει το συντακτικό δένδρο, φροντίζουμε κάθε συνάρτηση του αναλυτή να επιστρέφει τον αντίστοιχο κλάδο του δένδρου. Το παρακάτω παράδειγμα δημιουργεί και τυπώνει ένα συντακτικό δένδρο για τη γραμματική που εξετάζουμε:

/*
* Recursive descent parser for the following expression grammar:
* expr         ::= term ('+' term |'-' term) *
* term         ::= factor ('*' factor |'/' factor) *
* factor       ::= digit | '-' factor | '(' expr ')'
* digit        ::= 0 | 1 | 2 | 3 |4 | 5 | 6 | 7 | 8 | 9
*
* D. Spinellis, November 1999
*
* $Id: parse.c 1.1 1999/11/09 23:32:12 dds Exp $
*
*/

#include <stdio.h>
#include "tree.h"

/* Forward declarations */
struct s_tree *term(void);
struct s_tree *factor(void);

/* expr ::= term ('+' term |'-' term) * */
struct s_tree *
expr(void)
{
        struct s_tree *e1, *e2;
        int c;

        e1 = term();
        for (;;) {
                switch (c = getchar()) {
                case '+':
                        e2 = term();
                        e1 = mk_binop(e1, '+', e2);
                        break;
                case '-':
                        e2 = term();
                        e1 = mk_binop(e1, '-', e2);
                        break;
                default:
                        ungetc(c, stdin);
                        return (e1);
                }
        }
}

/* term ::= factor ('*' factor |'/' factor) * */
struct s_tree *
term(void)
{
        struct s_tree *t1, *t2;
        int c;

        t1 = factor();
        for (;;) {
                switch (c = getchar()) {
                case '*':
                        t2 = factor();
                        t1 = mk_binop(t1, '*', t2);
                        break;
                case '/':
                        t2 = factor();
                        t1 = mk_binop(t1, '/', t2);
                        break;
                default:
                        ungetc(c, stdin);
                        return (t1);
                }
        }
}

/* factor ::= digit | '-' factor | '(' expr ')' */
struct s_tree *
factor(void)
{
        struct s_tree *f;
        int c;

        switch (c = getchar()) {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
                return (mk_digit((char)c));
        case '-':
                f = factor();
                return (mk_unop('-', f));
        case '(':
                f = expr();
                c = getchar();
                if (c != ')')
                        printf("Expected ')'\n");
                return (f);
        }
}

/*
* Test harness
*/
main()
{
        struct s_tree *t;

        t = expr();
        dumptree(t);
}

Παράδειγμα χρήσης

Με τις παρακάτω εντολές βλέπουμε το συντακτικό δένδρο της έκφρασης 1+2*(4-5)*-3 :

% echo 1+2*(4-5)*-3 | parse
        1
    +
                2
            *
                    4
                -
                    5
        *
            -
                3

Ασκήσεις

Να υλοποιήσετε σε C ένα συντακτικό αναλυτή που να αναγνωρίζει και να τυπώνει το συντακτικό δένδρο για αριθμητικές εκφράσεις που αποτελούνται από ψηφία, +, -, *, /, (, ), ^ (ύψωση σε δύναμη) σύμφωνα με τους συνηθισμένους κανόνες προτεραιότητας της αριθμητικής.

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

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

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques, and Tools, pages 159–246. Addison-Wesley, 1985.
Francis Giannesini and Jacques Cohen. Parser generation and grammar manipulation using Prolog's infinite trees. Journal of Logic Programming, 1(3):253–265, October 1984.
David H. D. Warren. Logic programming and compiler writing. Software: Practice & Experience, 10:97–125, 1980.

Περιεχόμενα