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

Για να κάνουμε έναν συντακτικό αναλυτή αναδρομικής καθόδου να δημιουργήσει το συντακτικό δένδρο, φροντίζουμε κάθε συνάρτηση του αναλυτή να επιστρέφει τον αντίστοιχο κλάδο του δένδρου. Το παρακάτω παράδειγμα δημιουργεί και τυπώνει ένα συντακτικό δένδρο για τη γραμματική που εξετάζουμε:
/*
 * 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

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