"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("");

}