I’ve worked on several new and different things since July, and all thanks to my new job. Say “hooray” with me… Hooray! Luckily I recently got to do some compiler-style expression parsing. Not sure whether it’s my 100% favorite brand of problem to solve, but anything compiler-related is very, very near the top of my list.
We’re working on a jQuery plugin that I won’t share the details of yet, but the API contains a way to filter data using string matching expressions. It supports the normal comparison operations like “starts with”, “equals”, “matches regex”. Those are simple. Tack on logical operators like AND, OR and NOT, and you’ve now got some fancy parsing footwork to do. Imagine something like “Title^=Jimbo AND ID<45 OR Category IN 45,56,67”.
Once I realized the solution wasn’t going to be straightforward, I started thinking back to my Computer Science courses. The concept of operator precedence came to mind, but I couldn’t remember how it exactly worked. What I did know, is that I should probably convert the string expression to an expression tree, so I could traverse the tree later, evaluating it bottom-up. I like intermediate data structures, after all.
I probably could have accomplished this with a recursive descent parser, but it was the operator precedence that stumped me. Finally I decided to do yet-another google search, and this time I knew what to look for. I found an algorithm at the bottom of this page, which turned out to be exactly what I needed. It was recursive, makes used of a precedence table, and could be condensed into a few short functions.
You know the ending: it worked, I felt accomplished, I now better understand the problem, and I now have an elegant algorithm to solve it with.