javascript - Prevent extreme slowdown on PEG.js - Stack Overflow

admin管理员组

文章数量:1322533

The bulk of PEG.js (or Peggy) examples don't support much beyond a basic math formula. I've written up this arithmetic logic to provide full math parsing support with a foundation for adding custom functions.

Of course in production the console.log() statements would not be in there, but it is used to investigate how many time the evaluations functions are executed.

It seems with each layer in the order of operations there is a doubling of the amount of code executions.

My questions is-- how can this performance problem be avoided? I'm new to PEG and there might be an advanced feature that would prevent it from taking such a complex attack at it.

The below code can be put into .html Then here's some example functions to notice:

5*(3+3) This 7 character function creates over 500 console.log statements Probably a good first clue this parsing is not optimal. How a 500 step process could be used to parse 7 characters I don't understand.

It's rough enough that PEG.js found 500 things to do, but the real issue is that it executes the callback part (the {} part that has the console.log) every time. Every time. Note it is the same language element, and it's getting passed a "9" and last time it returned 9. Is there a trick so PEG.js can just remember that? This current code is trivial, but more complex functions run significant code and the developer doesn't expect it to be executed 64 times when the grammar for it shows up only once in the formula.

1.1 / ( 2 * ( (9 * 9) + (9 * 9) + (9 * 9) ) ) or 1.1 / (( 2 * ( 9 * 9 + 9 * 9 + 9 * 9 ) ) ) Either of these work ok (might as well leave the browser console closed, the number of logs is wild) Note that they do parse quickly.

1.1 / (( 2 * ( (9 * 9) + (9 * 9) + (9 * 9) ) ) ) This is where the cliff shows up. Just one more layer of complexity than the above two but this one will fully lock up the browser for a fair amount of time.

{
  const operations = {
        "√": (power, value) => Math.pow(value, 1 / power),
        "^": (base, exponent) => base ** exponent,
        "*": (multiplicand, multiplier) => multiplicand * multiplier,
        "/": (dividend, divisor) => dividend / divisor,
        "+": (addend1, addend2) => addend1 + addend2,
        "-": (minuend, subtrahend) => minuend||0 - subtrahend,
        "<": (a, b) => a < b,
        ">": (a, b) => a > b,
        "<=": (a, b) => a <= b,
        ">=": (a, b) => a >= b,
        "=": (a, b) => a == b,
        "!=": (a, b) => a != b
    };
}

// Define our end result should be something ReadyToReturn
Start = _ value:ReadyToReturn _ { return value; }

// * means zero or more so even empty strings count as whitespace
_ "whitespace" = [ \t\n\r]*

NumericValue
  = scientific:(_ "-"? [0-9]+ ("." [0-9]+)? [eE] [+-]? [0-9]+) { console.log('scientific'); return text(); }
  / double:(_ $("-"? [0-9]+ "." [0-9]* / "-"? "." [0-9]+)) { console.log('double'); return Number(text()); }
  / integer:(_ "-"? [0-9]+) { console.log('integer'); return parseInt(text(), 10); }

QuoteText = "\"" chars:([^\\"] / "\\" .)*  "\"" { return chars.join(""); }

PlainText = [a-zA-Z0-9 ]+ { return text().trim(); }

SimpleValue = NumericValue / QuoteText / PlainText

// After functions and columns are handled, we are left with simple numbers and ready to do math
ReadyToCalculate
  = negate:[-]? result:Function {
      if (!negate) {
        return result;
      }
      return isNumber(result) ? 0 - result : "-" + result;
  }
  / SimpleValue

// Functions need to be processed in the order they appear in the formula so finding arguments works correctly
Function = firstFunction:(
  Parentheses
  / RoundDown
  / RoundUp
) {
  return firstFunction;
}

Parentheses = "(" _ expr:ReadyToReturn _ ")" {
  console.log('( )');
  return expr;
}

RoundDown = "ROUNDDOWN(" _ value:ReadyToReturn places:(_ "," _ ReadyToReturn)? _ ")" {
  console.log('ROUNDDOWN');
  const digitNum = (places && places[2]) || 0;
  const base = 10 ** digitNum
  if (value < 0) {
    return Math.ceil(value * base) / base;
  }
  return Math.floor(value * base) / base;
}

RoundUp = "ROUNDUP(" _ value:ReadyToReturn _ places:("," _ ReadyToReturn _)? ")" {
  console.log('ROUNDUP');
  const digitNum = (places && places[2]) || 0;
  const base = 10 ** digitNum
  if (value < 0) {
    return Math.floor(value * base) / base;
  }
  return Math.ceil(value * base) / base;
}

////////////////////////////////////////////////////////
// This is the order of operations part.
// Each ReadyTo* definition expects the previous ReadyTo* which means that higher level has completed.
////////////////////////////////////////////////////////

// When handling roots, the two definitions are processed in order.
//  If it can consume a number to the left, it will
//  Then it will process √ characters without needing a number to the left
//  Finally, if no root work needs to be done, a ReadyToCalculate can simploy pass through
ReadyToExponent
  = head:ReadyToCalculate _ tail:(_ "√" _ ReadyToCalculate)+ {
      console.log('_√_');
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), head);
    }
  / negate:[-]? tail:(_ "√" _ ReadyToCalculate)+ {
      console.log('√_');
      if (negate) {
        return 0 - tail.reduce((result, element) => operations[element[1]](result, element[3]), 2);
      }
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), 2);
    }
  / ReadyToCalculate

ReadyToMultiply
  = head:ReadyToExponent tail:(_ "^" _ ReadyToExponent)+ {
      console.log('Exponent');
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), head);
    }
  / ReadyToExponent

ReadyToAdd
  = head:ReadyToMultiply tail:(_ ("*" / "/") _ ReadyToMultiply)+ {
      console.log('Multiply');
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), head);
    }
  / ReadyToMultiply

ReadyToCompare
  = head:ReadyToAdd tail:(_ ("+" / "-") _ ReadyToAdd)+ {
      console.log('Add');
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), head);
    }
  / ReadyToAdd

ReadyToReturn
  = head:ReadyToCompare tail:(_ ("<=" / "<" / ">=" / ">" / "!=" / "=") _ ReadyToCompare)+ {
      console.log('Compare');
      return tail.reduce((result, element) => operations[element[1]](result, element[3]), head);
    }
  / ReadyToCompare

本文标签： javascriptPrevent extreme slowdown on PEGjsStack Overflow