Parsing expressions

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

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)
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
Question by:marss

Accepted Solution

ovidiucraciun earned 400 total points
ID: 2816722
yes, there are algorithms for that

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;

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;


Expert Comment

ID: 2817287
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!


Author Comment

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 ;-)

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
The viewer will learn how to implement Singleton Design Pattern in Java.
Suggested Courses

624 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