Solved

Parsing expressions

Posted on 2000-05-17
3
217 Views
Last Modified: 2010-04-01
I've made a parser with javacc for a simple SQL select statement.

SELECT x FROM t
WHERE x=x1 AND (y=y1 OR z=z1)

in order to execute this statement i have to execute the expression in the parenthesis before applying that result to the first expression

r = (y=y1 OR z=z1)
then
x=x1 AND r

my parser is based on a standard EBNF grammar an work well.

what i need to know is:
how to construct a tree from the expressions, and if that is the soultion at all ;-)

is there an algorithm for this ?

best regards
marss
0
Comment
Question by:marss
3 Comments
 
LVL 3

Accepted Solution

by:
ovidiucraciun earned 200 total points
Comment Utility
yes, there are algorithms for that

1)
you must build a binary tree that has as leafs all the parameters from your expression and as internal nodes the operators (+,-,=,!); after you parsed the expression and built the tree just
pass the tree in pre-order ( root, left tree, right tree) and obtain the value of the expresion;

2)
u use a stack;
push the parameters (that can be 1 or two) and after that push the operator; and so on until you finish the experssion; from here just pop the first item from the stack, see if it needs 1 or 2 parameters and pop them(it) from the stack; evaluate the mini expression consisting from the parameter(s) and operator and the result push into the stack after previously poped out the next operator; and so on until the stack is empty;


0
 
LVL 1

Expert Comment

by:dotand
Comment Utility
Hi,
You are better off using a parser builder in Java (like YACC for Java).
The automatic parser generator will build the tree for you.

Be aware that building a BNF parser is very complex (I know this as I did a limited form parser in C++ some time back), even building a parser for GNF is not trivial.

My advice: seek a parser generator!

HTH,
Dotan
0
 

Author Comment

by:marss
Comment Utility
i have made my parser with javacc and it works well... that was not the issue

i needed to make a tree out of nested parenthesis, so i were able to execute the innermost expressions first.

the problem is solved now ;-)
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
The viewer will learn how to implement Singleton Design Pattern in Java.
This video teaches viewers about errors in exception handling.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now