How do I parse this type of expressions?

Question

I don't have a compilers background so I am not sure if this is a commmon thing in that area. Are there any standard techniques to parse expressions like this? (Say, tab indicates the depth)

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

Should be parsed as:

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

I am not sure if I should resort to a stack based evaluation? I am currently trying out one and I'll post a working code if I can get it running.

Any suggestions on a simple way to achieve this?

Answer 1

Assuming you are asking about how to parse expressions built out of operators with varying precedences and associativities -- absolutely.

One effective approach is called "top down operator precedence", and maybe also "operator precedence", and "precedence climbing" parsing. Here are some nice sources explaining the approach in detail:

• Pratt parsing (also the original paper)

• Douglas Crockford's take on it

• a Pythonist's take on it

• a Java version

The really neat thing is how little code it actually takes.

Key concepts are:

• prefix vs infix vs mixfix

• precedence: is 3 + 4 * 5 parsed as (3 + 4) * 5 or 3 + (4 * 5)?

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

Coincidentally, I have just been learning this stuff recently and ended up writing a an article on my blog about a similar approach to operator parsing, which you can find here. In my approach, I deal with infix, prefix, postfix, and mixfix operators (i.e. ? :); precedences and associativities are all specified in tables; I use a stack to keep track of operators whose operands haven't yet been found. The parser then builds a parse tree, where each node is a subexpression.