468,512 Members | 1,348 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

parsing tree help

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

Goal
|
|
|
Expr
|
|
Term
|
Factor
|
|
+
/ \
5 4

eprime()
/*Expr' -+ Term Expr' */
/* Expr' -- Term Expr'*/

if(word = t or word = -) then
word <-NextWord()
if(Term()=false)
then return false;
else return Eprime();
/*Expr' -Empty Set */
return true;
Term()
/*Term -Factor Term'*/
if(factor()=false)
then return false
else return Tprime()
Tprime ()
/* Term' -x factor Term' */
/*Term' -/ factor Term'*/
if (word = x or word = / )
Word=NextWord()
if(factor () = false)
then return false;
then return TPrime();
/*Term' -Empty Set */
return True;
Factor()
/*Factor -(Expr) */
if(word = '(' ) then
word<-Nextword();
if(Expr()-false)
then return false
else if (word != ')') then
return false;
/*Factor ->Num*/
/*Factor->ident*/

else if(word!= Num and word != ident) then
report syntax error
return false;

word <- Nextword()
return true;

Main()
/* goal-Expr */
Word <-Nextword()
if(expr() and word=eof)
then proceed to the next step
else return false

Expr()
/*Expr -Term Expr' */
if(Term ()= false)
then return false
else return Eprime()
Mar 30 '08 #1
2 4175

"uche" <ur***********@hotmail.comwrote in message
news:1a**********************************@c19g2000 prf.googlegroups.com..
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
expressions, terms and factors are parse level concepts.
The important step in the parser is that

1 + ? = 1 + expression

(?) = (expression)

Thus the code is mutually recursive.

To build a tree, define

typedef struct parsenode
{
struct parse node *left;
struct parsenode *right;
char operation; /* +, - * etc, including a code for "brackets" */
double val; /* only used for leaf nodes */
} PARSENODE;

Now make expression(), facor() and and term() all return PARSENODE *s.
--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Mar 30 '08 #2

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

Mar 30 '08 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

303 posts views Thread by mike420 | last post: by
2 posts views Thread by Todd Moyer | last post: by
19 posts views Thread by Alex Mizrahi | last post: by
4 posts views Thread by Pushya | last post: by
16 posts views Thread by Terry | last post: by
22 posts views Thread by Tony Johansson | last post: by
5 posts views Thread by gamehack | last post: by
3 posts views Thread by Jon Slaughter | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.