Right associative operator in a mathematical expression parser

Question

Finally, coming from this question, the problem remains, that this subparser...

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;
    }
}

...does not handle the exponential operator ("^") correctly. This is due to the fact that it is right associative. The code above handles it as if it was left associative.

For example: The text e^x^2 is interpreted as (e^x)^2. However, the correct "interpretation" would be e^(x^2).

I have already tried something like this:

if (/* The current token is ^ */)
{
    TermNode node = new TermNode(tree, null, currentToken);
    tree = null;
    scanner.MoveNext();
    currentToken = scanner.Current;
    Exponent(ref tree);
    node.RightChild = tree;
    tree = node;
}
while (/* The current token is ^  */)
{
    TermNode detachedExponent = tree.RightChild;
    TermNode oldTree = tree;
    Token token = currentToken;
    tree.RightChild = null;
    tree = null;
    scanner.MoveNext();
    currentToken = scanner.Current;
    Exponent(ref tree);
    oldTree.RightChild = new TermNode(distachedExponent, tree, token);
    tree = oldTree;
}

Which only works for two sequential "^"-expressions. Not something like e^x^y^z (which would be e^(x^(y^z)) and not e^((x^y)^z) like the parser claims... What am I missing?

I assume "how can I make this parser handle right-associative operators like ^ correctly?". — Jerry Federspiel, Jul 27 '15 at 15:53
This is easy. *First* write the BNF you wish to accept. Then code the recursive descent parser the way I suggested. if the operator is right-associative, the grammar will specify that way, and your parser will work accordingly. I showed you how in your previous question; I leave it to your carry it out. — Ira Baxter, Jul 27 '15 at 18:35

score 1 · Accepted Answer · answered Jul 27 '15 at 17:38

When you have a^b, and you see ^c, you inject it into the RHS of the top-level ^, creating a^(b^c), and leave yourself with the resulting full expression. When you then see ^d, you again inject it into the RHS of the top-level ^, creating a^((b^c)^d). You shouldn't be injecting it into the RHS of the top-level ^, but into the right/inner-most ^ expression. To achieve that, simply keep track of that expression in a separate variable. Then, instead of modifying the top level expression's RightChild property, modify the child's.

Right associative operator in a mathematical expression parser

1 Answers1