Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!gould9!ncr-sd!sdcsvax!darrell
From: darrell@sdcsvax.UUCP
Newsgroups: net.sources
Subject: Parse tree program
Message-ID: <1692@sdcsvax.UUCP>
Date: Mon, 21-Apr-86 03:04:18 EST
Article-I.D.: sdcsvax.1692
Posted: Mon Apr 21 03:04:18 1986
Date-Received: Wed, 23-Apr-86 22:39:14 EST
Organization: EECS Dept. U.C. San Diego
Lines: 180
Keywords: undergraduate systems course, parsing
Summary: A pedagogical aid for an undergraduate systems course.

I have used the following program in an undergraduate systems course
as a teaching aid.   It takes as input infix expressions composed of
single letters,  {+,  -,  *, /} and parentheses and produces a parse
tree on the screen.   Error handling is not spectacular;  neither is
the  input  format since it does not accept identifiers of arbitrary
length nor does it hand leading blanks.  But,  perhaps it will be of
use to someone teaching a similar course.

Flames to your favorite member of net.thought.police.

DL
Darrell Long
Department of Electrical Engineering and Computer Science
University of California, San Diego

UUCP: sdcsvax!darrell
ARPA: darrell@sdcsvax
------------------------------------------------------------------------
# include	<stdio.h>
# include	<curses.h>

/*
** PARSE TREE
**
** DDEL
** Sun Apr 13 13:13:11 PST 1986
*/

enum selector { operator, operand };

struct node {
    enum selector tag;
    char    op;
    struct node *left,
		*right;
};

static char input;

/*
** E -> T { + T } | T { - T }
*/

struct node *E () {
    char    save;
    struct node *p,
                *q,
                *r,
                *T();

    p = T ();
    q = (struct node *) NULL;
    r = (struct node *) NULL;

    while (input == '+' || input == '-') {
	save       = input;
	input      = getchar ();
	q          = T ();
	r          = (struct node *) malloc (sizeof (struct node));
	r -> tag   = operator;
	r -> op    = save;
	r -> left  = p;
	r -> right = q;
	p          = r;
    }
    if (r == (struct node *) NULL)
	return p;
    else
	return r;
}

/*
** T -> F { * F } | F { / F }
*/

struct node *T () {
    char    save;
    struct node *p,
                *q,
                *r,
                *F();

    p = F ();
    q = (struct node *) NULL;
    r = (struct node *) NULL;

    while (input == '*' || input == '/') {
	save       = input;
	input      = getchar ();
	q          = F ();
	r          = (struct node *) malloc (sizeof (struct node));
	r -> tag   = operator;
	r -> op    = save;
	r -> left  = p;
	r -> right = q;
	p          = r;
    }

    if (r == (struct node *) NULL)
	return p;
    else
	return r;
}

/*
** F -> letter | ( E )
*/

struct node *F () {
    struct node *p,
                *E();

    if (((input >= 'A') && (input <= 'Z')) ||
        ((input >= 'a') && (input <= 'z'))) {
	p        = (struct node *) malloc (sizeof (struct node));
	p -> tag = operand;
	p -> op  = input;
	input    = getchar ();
	return p;
    }
    else
	if (input == '(') {
	    input = getchar();
	    p     = E ();
	    if (input == ')')
		input = getchar ();
	    else {
                move   (23, 37);
		addstr (") expected.");
            }
            return p;
	}
	else {
            move   (23, 10);
	    addstr ("factor expected.");
	    return (struct node *) NULL;
	}
}

void tree (p, position, width, depth)
struct node *p;
int     position,
        width,
        depth;
{
    int     i;

    if (p != (struct node *) NULL)
	switch (p -> tag) {
	    case operator: 
		{
                    move  (depth, position);
		    addch (p -> op);
		    tree (p -> left,  position - width / 2, width / 2, depth + 3);
		    tree (p -> right, position + width / 2, width / 2, depth + 3);
		    break;
		}
	    case operand: 
		{
                    move  (depth, position);
		    addch (p -> op);
		    break;
		}
	}
}

main () {
    input = getchar();
    initscr();
    tree   (E (), 39, 40, 0);
    move   (23, 0);
    refresh();
}
-- 
Darrell Long
Department of Electrical Engineering and Computer Science
University of California, San Diego

UUCP: sdcsvax!darrell
ARPA: darrell@sdcsvax