Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Parsing expressions

Posted on 2000-05-17
Medium Priority
241 Views
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
0
[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

LVL 3

Accepted Solution

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

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

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

Question has a verified solution.

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

Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
###### Suggested Courses
Course of the Month9 days, 23 hours left to enroll