Parsing a mathematical expression with missing multiplication signs

Question

Coming from this question, I now wanted to write an implementation of the parser.

// Handles * and / 
private static void Summand(Scanner scanner, ref TermNode currentTree, ref Token currentToken)
{
    Factor(scanner, ref currentTree, ref currentToken);

    while (currentToken is OperatorToken && _multiplicationOperators.Contains(((OperatorToken)currentToken).OperatorChar)) // So long as the token is * or /
    {
        TermNode node = new TermNode(currentTree, null, currentToken);
        currentTree = null;
        scanner.MoveNext();
        currentToken = scanner.Current;
        Factor(scanner, ref currentTree, ref currentToken); // Handles ^
        node.RightChild = currentTree;
        currentTree = node;
    }
}

// I think this one might be wrong...
private static void Factor(Scanner scanner, ref TermNode currentTree, ref Token currentToken)
{
    Exponent(scanner, ref currentTree, ref currentToken);

    while (currentToken is OperatorToken && ((OperatorToken)currentToken).OperatorChar == '^') // So long as the token is ^
    {
        TermNode node = new TermNode(currentTree, null, currentToken);
        currentTree = null;
        scanner.MoveNext();
        currentToken = scanner.Current;
        Exponent(scanner, ref currentTree, ref currentToken);
        node.RightChild = currentTree;
        currentTree = node;
    }
}

private static void Exponent(Scanner scanner, ref TermNode currentTree, ref Token currentToken)
{
    if (currentToken is BracketToken)
    {
        BracketToken bracketToken = (BracketToken)currentToken;
        if (bracketToken.IsOpening)
        {
            scanner.MoveNext();
            currentToken = scanner.Current;
            Term(scanner, ref currentTree, ref currentToken);
            if (currentToken is BracketToken && !((BracketToken)currentToken).IsOpening)
            {
                scanner.MoveNext();
                currentToken = scanner.Current;
            }
            else
                throw new ParseException("Unbalanced brackets!");
        }
    }
    else
    {
        node = new TermNode(null, null, currentToken);

        if (currentToken is OperatorToken)
        {
            currentTree = null;
            scanner.MoveNext();
            currentToken = scanner.Current;
            Exponent(scanner, ref currentTree, ref currentToken, false);
            node.RightChild = currentTree;
            currentTree = node;
        }
        else if (currentToken is VariableToken || currentToken is ConstantToken)
        {
            currentTree = node;
            scanner.MoveNext();
            currentToken = scanner.Current;
        }
        else if (currentToken is FunctionToken)
        {
            currentTree = null;
            scanner.MoveNext();
            currentToken = scanner.Current;
            Exponent(scanner, ref currentTree, ref currentToken, false);
            node.RightChild = currentTree;
            currentTree = node;
        }
    }

}

Now I was wondering how I would have to change this method in order to allow expressions such as 3(a+b)... And also whether this approach and the function are the correct way to archieve this.

Answer 1

This is just a case modifying your (unstated) grammar from:

Summand = Factor | Summand "*" Factor | Summand "/" Factor ;

to

Summand = Factor | Summand Factor | Summand "/" Factor ; 

and modifying the hand written recursive descent parrser according.

So you need to modify "Summand" so it doesn't check for an explicit multiplication operator, but continues to check for a division operator.

So the code would look something like this:

private static void Summand(Scanner scanner, ref TermNode currentTree, ref Token currentToken)
{
   Factor(scanner, ref currentTree, ref currentToken);
   while (true) // repeat for each implicit multiply or explicit divide
   {
     if (currentToken is OperatorToken && ((OperatorToken)currentToken).OperatorChar == '/')
     { // handle divide
       TermNode node = new TermNode(currentTree, null, currentToken);
       currentTree = null;
       scanner.MoveNext();
       currentToken = scanner.Current;
       Factor(scanner, ref currentTree, ref currentToken);
       node.RightChild = currentTree;
       currentTree = node;
     }
     else { // handle possible multiplication
            TermNode multiplicand = node ;
            Factor(scanner, ref currentTree, ref currentToken)
            if (Factor_failed) return; // no implicit product
            currentTree = new TermNode(multiplicand, currentTree,  maketoken("*"));              

          }
   } //while
} // Summand

What your parser lacks is a signal from each sub-parser that indicates that the subparser could not find what it was requested to parse. (You need to implement the idea "Factor_failed".) This is different than it found evidence that what it was requested to parse was there, but is not valid syntax. I suggest you change each return type to "bool", return "true" if the subparser succeed, "false" if it cannot find evidence of what it is supposed to parse, and throws an exception if it gets halfway through parsing and fails.

See an organized way to build recursive descent parsers that implements these ideas.