Parse tree program
darrell at sdcsvax.UUCP
darrell at sdcsvax.UUCP
Mon Apr 21 18:04:18 AEST 1986
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 at 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 at sdcsvax
More information about the Comp.sources.unix
mailing list