"uche" <ur***********@hotmail.comwrote in message
news:1a**********************************@c19g2000 prf.googlegroups.com...
Guys,
I am trying to build a Parse Tree with the following grammar. I have
implemented my insertions using a standard binary tree inserting
algorithm. With the psuedocode below, can you guys provide any helpful
feedback to placing insert statements into building nodes of the tree.
Any suggestions on how to build the tree will be appreciated.
I hope to build the tree to look like that
5+4
I've put together the code below.
Whether it is any use to you, I don't know. It was an interesting Sunday
morning exercise.
Input is A*(B+5) (as a array of tokens). This is converted to a tree
(pointers to node structs).
Output is the tree linearised back into (A*(B+5)) (notice there are extra
parentheses here).
Output into your graphical form is fiddly but I don't think difficult (but I
haven't tried it). It's a lot easier if A+B for example can be shown like
this:
+
A
B
Then it's fairly trivial.
Hope this helps.
Bart.
/*
Convert tokenised expression into simple tree form.
Input is from array exprdata, containing the expression as a series of
tokens. (Converting from string to tokens is a separate exercise!).
printexprdata() is test function to ensure exprdata is valid.
printtree() converts tree back into linear form. Because parentheses are
not
stored in the tree (only implied), these are added here, more than
necessary however.
Printing the tree as a graph is also a separate (but simpler?) exercise.
Expressions can consist of: +, -, *, /, integer constant, (, ), and single
letter
identifiers. Also - can be used to negate (converted to own token negtoken
in tree).
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct snode {
int token; /* numtoken/idtoken mean terminal node */
int value;
struct snode *left, *right;
} node;
#define endcase break;
#define addtoken 1
#define subtoken 2
#define multoken 3
#define divtoken 4
#define leftbtoken 5
#define rightbtoken 6
#define numtoken 7
#define idtoken 8
#define endtoken 9
#define badtoken 10
#define negtoken 11
node* readexpr(void);
node* readfactor(void);
node* readterm(void);
void nexttoken(void);
node* newnode(int,int,node*, node*);
void printtree(node*);
void printexprdata(void);
int exprdata[] = /* A*(B+5) note: 1-based */
{0,idtoken, 'A', multoken, leftbtoken,idtoken, 'B', addtoken, numtoken, 5,
rightbtoken,endtoken};
int tokenno; /* index into exprdata */
int token; /* current token */
char *opnames = "?+-*/?????"; /* also 1-based */
/**** MAIN ****/
int main(void){
node* expr;
tokenno=1;
nexttoken();
expr=readexpr();
printf("Input = ");
printexprdata();
printf("Output = ");
printtree(expr);
puts("");
} /* END MAIN */
/* READEXPR */
node* readexpr() {
// term + term or term - term
node *lhs, *rhs;
int t;
lhs=readfactor();
while (token==addtoken || token==subtoken) {
t=token;
nexttoken();
rhs=readfactor();
lhs=newnode(t, 0, lhs, rhs);
};
return lhs;
}
/* READFACTOR */
node* readfactor() {
// factor * factor or factor/factor
node *lhs, *rhs;
int t;
lhs=readterm();
while (token==multoken || token==divtoken) {
t=token;
nexttoken();
rhs=readterm();
lhs=newnode(t, 0, lhs, rhs);
};
return lhs;
}
/* READTERM */
node* readterm() {
// number or -term or (expr)
node *term;
int t;
switch (token) {
case subtoken:
nexttoken();
return newnode(negtoken, 0, readterm(), NULL);
case leftbtoken:
nexttoken();
term=readexpr();
if (token!=rightbtoken)
return newnode(badtoken, 0, NULL, NULL);
nexttoken();
return term;
case numtoken: case idtoken:
t=token;
nexttoken();
term=newnode(t, token, NULL, NULL);
nexttoken();
return term;
default:
return newnode(badtoken, 0, NULL, NULL);
};
}
/* NEXTTOKEN */
void nexttoken() {
token=exprdata[tokenno];
if (token!=endtoken) ++tokenno;
}
/* NEWNODE */
node * newnode(int opc, int value, node* left, node *right) {
node* p;
p=malloc(sizeof(node));
if (p==NULL) {
puts("Expr too complex.");
exit(1);
};
p->token=opc;
p->value=value;
p->left=left;
p->right=right;
return p;
}
/* PRINTTREE */
void printtree(node *expr) {
switch (expr->token) {
case numtoken:
printf("%d",expr->value);
endcase
case idtoken:
printf("%c",expr->value);
endcase
case negtoken:
printf("-");
printtree(expr->left);
endcase
case badtoken:
printf("Error");
endcase
default:
printf("(");
printtree(expr->left);
printf("%c",opnames[expr->token]);
printtree(expr->right);
printf(")");
};
}
/* FOR TESTING EXPRDATA[] */
void printexprdata() {
int n;
n=1;
while (n<=(sizeof(exprdata)/sizeof(exprdata[0]))) {
switch(exprdata[n]) {
case numtoken:
printf("%d",exprdata[++n]);
endcase
case idtoken:
printf("%c",exprdata[++n]);
endcase
case addtoken: case subtoken: case multoken: case divtoken:
printf("%c",opnames[exprdata[n]]);
endcase
case leftbtoken:
printf("(");
endcase
case rightbtoken:
printf(")");
endcase
};
++n;
};
puts("");
}
