解析缺少乘法符号的数学表达式 [英] Parsing a mathematical expression with missing multiplication signs

问题描述

来自此问题，我现在想编写一个解析器的实现.

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

}

现在，我想知道如何更改此方法以允许诸如3(a+b)的表达式...以及此方法和函数是否是正确的归档方法.

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.

推荐答案

这只是从以下位置修改(未说明的)语法的一种情况:

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

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

到

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

，然后根据需要修改手写递归下降解析器.

and modifying the hand written recursive descent parrser according.

因此，您需要修改"Summand"，以便它不检查显式乘法运算符，而是继续检查除法运算符.

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

解析器所缺少的是来自每个子解析器的信号，该信号指示该子解析器找不到请求解析的内容. (您需要实现"Factor_failed"的想法.)这不同于发现证据表明请求解析的内容在那里，但语法无效.我建议您将每个返回类型更改为"bool"，如果子解析器成功，则返回"true"，如果无法找到应该解析的内容的证据，则返回"false"，如果解析中途失败，则抛出异常.

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.

请参阅 查看全文