Re: String Processing Challenge

On Feb 4, 11:06 pm, "David BL" <davi..._at_iinet.net.au> wrote:
> In the recent thread "Objects and relations" Marshall and I had an
> interesting discussion about whether RM/RA is suitable for string
> processing. I feel that the examples we used for comparison were
> overly simple. For my own part I'm still left wondering how RM can be
> easily applied in more complex problems.
>
> I have chosen a practical example of string processing that allows for
> reasonably concise solutions in OO, FP and LP styles. The existence
> of concise FP and LP solutions show that the problem is well described
> declaratively or logically. ie it is not specifically suitable for
> procedural solutions.
>
> Problem specification: Given a string that is an infix expression
> using the binary operators *,/,+,-, unary operators +,- and literal
> integers in base 10, calculate the result as an integer following
> BIMDAS / PEMDAS (or whatever you call it). Assume "/" designates
> integer division. For simplicity assume that the expression is well
> formed, there is no exponentiation, there is no division by zero and
> ignore overflow when using a native integer type.
>
> The following EBNF grammar is assumed
>
> Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
>
> LiteralInteger =
> Digit |
> LiteralInteger Digit;
>
> Expr = AdditiveExpr;
>
> AdditiveExpr = MultiplicativeExpr { ("+" | "-") MultiplicativeExpr };
>
> MultiplicativeExpr = PrimExpr { ("*" | "/") PrimExpr };
>
> PrimExpr =
> LiteralInteger |
> ("+" | "-") PrimExpr |
> "(" Expr ")";
>
> If anyone is happy to take the challenge I'm happy to develop and post
> a C++ solution that can be compared to some relational solution. It
> would also be interesting to see solutions in other languages.
>
> I suggest that the comparison be based primarily on simplicity,
> expressiveness and clarity, and not on performance given the lack of a
> mature language and compiler for an RM based approach. Also the
> relational solution is free to introduce its own language constructs,
> perhaps making use of FP,LP or even some OO given that RA is not
> Turing complete. In other words a hybrid solution is allowable.

This is an excellent challenge. However my response might be something of a letdown. My ideal relational/complete language includes tagged unions and pattern matching a la SML. These are desirable for a number of reasons, and in fact they simplify some things even in a purely relational approach, such as mutually exclusing choices. (There was a recent thread in which we discussed an example from Darwen of an employee table with salaried, unsalaried, and unknown salary employees which I felt was best handled by a tagged union.)

Once you have tagged unions and pattern matching, you have a complete solution to the above parsing problem, and for once join doesn't offer you much. Unless maybe you want to parse a whole set of expressions at once. :-)

So my answer to this challenge reduces to the canonical SML parsing solution.

Marshall Received on Tue Feb 06 2007 - 19:39:58 CET