Solved

Parsing expressions

Posted on 2000-05-17
3
226 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
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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

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)
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

820 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