Title: Letter to the Editor

Author: Martin Moene

Date: 04 July 2015 21:57:43 +01:00 or Sat, 04 July 2015 21:57:43 +01:00

Summary: 

Body: 

Dear Editor,

I liked the idea of Vassili Kaplan’s easy-to-code parser (‘Split and Merge – Another Algorithm for Parsing Mathematical Expressions’, C Vu 27.2, May 2015).

One small thing I think we should point out, though, is that the algorithm as described in that article treats the associativity of operators in a way we probably don’t want.

With the commutative, transitive operators + and *, associativity doesn’t matter: A*(B*C) = (A*B)*C and same goes with +. But things can be more subtle with - and /.

To take the example of 3+2*6-1 becoming 3+12-1 and then 3+11, what if that first + were changed into a -, so we have 3-2*6-1 becoming 3-12-1 and 3-11? That would give a result of -8, instead of the -10 you’d get if you did it as (3-2*6)-1 as we’d normally understand it.

Moreover, the Split and Merge algorithm, as described in the article, does not consistently treat operators as right-associative either. If the operator is preceded by another of the same or lower precedence level, then it will be left-associative: 3-12-1 would get -10. But if the operator is preceded by one of a higher precedence level, it will become right-associative with the operators before that: 3-2*6-1 would get -8. This is a bit inconsistent and I can’t think of a language where we’d actually want this behaviour, although there might perhaps be one out there somewhere.

To make the algorithm consistently left-associative, we’d have to change the parser by having it break out of the merge loop and going back to the beginning after any successful merge, although it doesn’t have to do this if it’s already dealing with the first thing in the expression, or if the next operator is + or * and therefore can be evaluated with either associativity.

Having to break out of the loop will of course increase the time complexity a little, and let’s hope we’re not coding a language in which some operators are left-associative whereas others are right-associative. When inventing a new way of parsing expressions, it might be a good idea to test the code with as many expressions as possible. Perhaps write a random expression generator and feed the resulting expressions both to your code and to an established parser (such as Python’s eval function) and have it alert you about any differences in the result, or at least any difference in the first 3 significant digits (as you can’t count on both floating point systems to be using the same precision).

Of course, a lot would depend on how thorough your random expression generator is, so perhaps test its thoroughness first by making sure it flags up the problem with the existing version of the code. That’s what Richard Feynmann would call an ‘A-1’ experiment: first check our observation methods by verifying we can observe what we have already, before changing things.

While such ‘fuzz testing’ does not provide a 100% solid guarantee of catching all cases (you’d have to use formal code-proving methods for that, preferably checked by automatic proof-checking tools and it’s still possible to slip up by using them incorrectly), at least ‘fuzz testing’ should catch most things: I hope a decent fuzz-tester would have drawn our attention to the inconsistent associativity.

Silas

Silas S Brown http://people.ds.cam.ac.uk/ssb22

Have a reputation for being reasonable
~ Philippians 4:5, Phillip’s

Notes: 

More fields may be available via dynamicdata ..