Parsing a mathematical expression with missing multiplication signs
Based on this question , I now wanted to write a parser implementation.
// 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 should modify this method to allow expressions like 3(a+b)
... And also if this approach and function is the correct way to archive this.
source to share
This is just a case changing your (unsettled) grammar:
Summand = Factor | Summand "*" Factor | Summand "/" Factor ;
to
Summand = Factor | Summand Factor | Summand "/" Factor ;
and modifying the hand-written recursive descent parser.
So, you need to change "Summand" so that it doesn't check for the explicit multiplication operator, but continues to check for the division operator.
Thus, the code will 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 is missing is a signal from each subparameter that indicates that the subparameter could not find what was requested to parse. (You need to implement the idea of "Factor_failed".) This is different from what was found that what was suggested for parsing was, but is not valid syntax. I suggest you change each return type to "bool", return "true" if the subparser succeeds, "false" if it can't find evidence that it should parse, and throw an exception if it hits halfway through the syntax analysis and fails.
See an organized way of creating recursive descent parsers that implements these ideas.
source to share