BASIC solutions: expressions

Previously, I showed the beginnings of a GW-BASIC expression parser. As of now, the parser is essentially feature complete! I fixed the unary minus bug and went on to implement all the remaining features — mainly relational, logical, and functional operators.

Now having more Sprache experience (and a better understanding of precedence climbing), most of the work was straightforward. I hit one notable snag along the way when I attempted to support logical AND/OR for mixed type expressions, e.g. X$="str" AND A=1. The grammar I had come up with at that point was too restrictive since it considered string and numeric expressions separately. To get around the parse error, I was forced to relax the grammar. While there might be a way in Sprache to achieve what I was trying to do, a simple solution escaped me. So technically the expression parser as-is accepts several actually invalid expressions (e.g. "1" AND 0). In any case, I am not worried much about it as this type of semantic analysis is typically handled after parsing anyway.

There is still one problem remaining which I have marked with several skipped tests. In an earlier change I disallowed the use of reserved words as identifiers; e.g. a variable named LEFT$ cannot be used since it conflicts with the LEFT$ function. Something about the way this is implemented seems to cause a more restrictive condition where no prefix of a reserved word can be used as an identifier; e.g. the expression LEFT+1 should be allowed since a numeric variable named LEFT is allowed by GW-BASIC. I have chosen to ignore this problem for the time being.

As an added bonus, I decided to implement the visitor pattern for dealing with the parts of the expression. Traversing a symbolic expression is quite literally a textbook example of the visitor pattern, so it turned out to be a pretty natural fit. It is also a way to allow extensibility of a sort without directly exposing the class hierarchy or the internals of each expression type. The first and only use case right now is a visitor for string formatting of the expression (which replaced the original ToString() overrides). However, I plan to use it later when I get around to implementing the C# code translation part of this project.

For completeness, here is a demonstration of the GW-BASIC equivalent of the quadratic formula, parsed and written back out as a string, with some spacing to help show the structure:

string input = "(-B+SQR(B^2-4*A*C))/(2*A)";
string output = BasicExpression.FromString(input).ToString();
string expected =
"Div(" +
    "Add(" +
        "Neg(NumV(B)), " +
        "Sqrt(" + 
            "Sub(" +
                "Pow(NumV(B), NumL(2)), " +
                "Mult(Mult(NumL(4), NumV(A)), NumV(C))" +
            ")" +
        ")" +
    "), " +
    "Mult(NumL(2), NumV(A))" +
")";
bool eq = output == expected; // true

See for yourself by checking out the ExpressionSample code on GitHub. Come back soon for more GW-BASIC adventures!