473,372 Members | 1,037 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,372 software developers and data experts.

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 4408

"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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

303
by: mike420 | last post by:
In the context of LATEX, some Pythonista asked what the big successes of Lisp were. I think there were at least three *big* successes. a. orbitz.com web site uses Lisp for algorithms, etc. b....
2
by: Todd Moyer | last post by:
I would like to use Python to parse a *python-like* data description language. That is, it would have it's own keywords, but would have a syntax like Python. For instance: Ob1 ('A'): Ob2...
19
by: Alex Mizrahi | last post by:
Hello, All! i have 3mb long XML document with about 150000 lines (i think it has about 200000 elements there) which i want to parse to DOM to work with. first i thought there will be no...
4
by: Pushya | last post by:
Hello - I am trying to parse a .XSD file to obtain information about element name and type in the file. I have been trying to find some kind of documentation for Schema Parsing. All I come...
16
by: Terry | last post by:
Hi, This is a newbie's question. I want to preload 4 images and only when all 4 images has been loaded into browser's cache, I want to start a slideshow() function. If images are not completed...
22
by: Tony Johansson | last post by:
Hello Experts! I'm reading i a book about C++ and they mention infix with telling what it is. I hope you out there can do so. Many thanks! //Tony
5
by: gamehack | last post by:
Hi all, I was thinking about parsing equations but I can't think of any generic approach. Basically I have a struct called math_term which is something like: struct math_term { char sign; int...
3
by: Jon Slaughter | last post by:
Is there anything like yacc or spirit for C#? What is the "standard" method for parsing grammars in C#? The last few days I have been looking at boost spirit and really like how it works. What I...
2
by: nicky123 | last post by:
Hi everyone, This is a brief description that I have provided for parsing & displaying an XML document using DOM API. Please feel free to post your own comments & views regarding...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.