How to parse this type of expression?

Question

I have no background compilers, so I'm not sure if this is a post in this area. Are there standard methods for analyzing such expressions? (Say the tab indicates the depth)

And A + B = 1 C + D = 1 Or P + Q = 1 K = 1 And Q = 1 R = 2 

It should be analyzed as:

 ((A+B=1) AND (C+D=1) AND ((P+Q=1) OR (K=1)) AND ((Q=1) AND (R=2))) 

I'm not sure if I should resort to stack based evaluation? I am currently testing one and I will send working code if I can run it.

Any suggestions on a simple way to achieve this?

Answer 1

Assuming you are asking how to parse expressions built from operators with different priorities and associativity - absolutely.

One effective approach is called “top-down operator priority”, or maybe “operator priority” and parsing “priority”. Here are some good sources that explain the approach in detail:

• Pratt parsing (also original paper )

• Douglas Crockford take on it

• Pythonist take on it

• a version of Java

Actually very neat is how little code it really takes.

Key concepts:

• prefix vs infix vs mixfix

• priority: 3 + 4 * 5 analyzed as (3 + 4) * 5 or 3 + (4 * 5) ?

• associativity: x - y - z analyzed as x - (y - z) or (x - y) - z ?

By the way, I recently studied this material and eventually wrote an article on my blog about a similar approach to parsing operators, which you can find here . In my approach, I deal with the operations infix, prefix, postfix and mixfix (i.e. ? : ; priorities and associativity are indicated in the tables; I use the stack to track statements whose operands have not yet been found. The parser then creates a parse tree where each node is a subexpression.