?
Solved

Parsing expressions

Posted on 2000-05-17
3
Medium Priority
?
235 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 3

Accepted Solution

by:
ovidiucraciun earned 400 total points
ID: 2816722
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
ID: 2817287
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
ID: 2840702
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

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month10 days, 16 hours left to enroll

770 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