Simple rules engine pattern

Does anyone have a link to a good simple Rules Engine pattern that can be implemented in javascript? I am interested in doing this for the SheetWorker, since the pathfinder sheet has several places to allow players to enter their own macros (no die rolls, just calculations for abilities such as n uses per y levels etc) I have built rules engines in the distant past (at least 10 years ago), and hooked up other rules engines to other products. I am not sure if it's worth it in this case, but I'm thinking it may be a fun exercise as long as it ends up not too slow. The search/replace attributes is easy enough, which I detailed  here , I am trying to determine a good method / pattern for parsing the grammar.  I am thinking: first replace all [[ and ]] with ( and ) so it's more of a simple math equation, Then for each () group, treat that as a node related to each other by the operand. I guess that means the operands are the  internal nodes. And the arguments would be the leaf nodes. say we have (A + B * C)/2 travelling left to right method I'm thinking of would be: for each set of () use recursion to go down a level just to make it easier instead of loops. each time we have to save the current parent operand of this iteration/recursion, plus the last leaf node read (last argument/number). Hit ( so save it (implementation: call same method with string between ( ) ?) A + B : simple 3 node: create a + node, with A and B as leaf.  if A + B + C: if next operand is same then set C.parent = b.parent. if A + B - C if next operand is different but same precedence, keep order (it probably matters, simplest to just keep order), so set: +.parent = -, C.parent = -.  if A + B * C if next operand is higher precedence, replace B node with that operand: *.parent = B.parent, B.parent=*, C.parent=* Hit closing ) so go back up to highest node of () which would be the +. (i.e. return + in  1st and 3rd example, - in 2nd example) () / 2 : simple 3 node again +.parent=/ 2.parent=/ other operands like floor, abs, would have only one child node.  the 4 arithmetic operands could have n child nodes. kl1 kh1 also have n child nodes.

You're basically describing a lexer. There exist programs to  generate  lexers, although I don't know of any that generate JavaScript, so if you used one you'd have to translate some other language to JS. Of course, you could also sift through the JS source linked from the VTT to find the lexer/parser used by Roll20. IIRC, the source is lightly obfuscated, though.

There's a parser that's compatible with Roll20's roll expressions in the Extended Expressions script.  It's a little heavier than you need (the whole point of the script is to add new functionality to roll expressions), but it's a starting point. Essentially, you maintain two stacks: one of operators and one of operands.  When you encounter a lower- (or equal-) precedence operator, you pop your way up the stack (evaluating as you go) until you come to a higher-precedence operator, then go back to pushing. For example, consider the expression "1 + 2 * 3 + 4 * 5".  You start off with "1", which is a number, so you push it as an operand.  Then you get a "+", which is an operator, so you push it as such.  Then "2" goes onto the operand stack.  Then you get a "*", which is a higher-precedence operator than the top of the operator stack ("+"), so you push it.  Then "3" goes onto the operand stack.  Now the interesting bit happens: the "+" has lower precedence than the "*" on the operator stack, so you pop the top two operands and the top operator ("2", "3", "*"), evaluate (2*3=6), and push the result back onto the operand stack (so now the operand stack is [1,6] and the operator stack is "+").  The "+" we just got is the same precedence as the "+" on the operator stack, so we keep collapsing (evaluating 1+6=7, giving us an operand stack of [7] and an empty operator stack), then push the "+" operator and continue.  The next few steps bring the operand stack to [7,4,5] and the operator stack to [+,*].  When we hit the end, we do one final round of collapsing (pop the "4" and "5" operands and the "*" operator, push the result back onto the operands stack, then pop the "7" and "20" operands and the "+" operator to get the final result of 27).  Then, if everything went right, we have one item in our operand stack and nothing in the operator stack; return the one operand.  If that isn't the case, then something went wrong; report a syntax error. There's a little more to it (as you've noted above, and will see in Extended Expressions) when your tokens can be more than just operators and operands (and when you can have unary operators), but conceptually it's not significantly harder than the bit explained above.

That makes me feel better I was on a similar track with two data structures. I was using trees but stacks make more sense: <a href="http://jsfiddle.net/yxg7p8qz/22/" rel="nofollow">http://jsfiddle.net/yxg7p8qz/22/</a> but I will definitely check out extended expressions.

Building the AST is useful if you have unknowns (e.g. ExtendedExpressions does that for rolls it hasn't submitted yet), but it's easier both on CPU and memory to just process as you go if everything is known at parse-time (which it should be in the context of SheetWorkers).

I adapted ExtendedExpressions here: <a href="https://github.com/plutosdad/SheetWorkerParsing" rel="nofollow">https://github.com/plutosdad/SheetWorkerParsing</a> Let me know if I handled attribution to you incorrectly and you want me to do something differently. I guess I should add some in the actual code so if someone downloads it they know who wrote the code and where to find updates. I had to make some minor changes because neither inline nor roll worked in the context of a sheetworker, but those were of course mainly in the "handle" function. But there were about 2 other places in binary ops where it checked x and y for null, which for some reason was failing every time, so i removed those. I&nbsp;found one bug, i think, in operation where you have a | instead of || , which I only found because I was trying to handle decimals. I don't know if it's a bug or was deliberate, but i needed decimals for my purposes: &nbsp; &nbsp; &nbsp; &nbsp; function flattenAST(t) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var retval; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch (t.type) { &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case "number": &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case "rollspec": &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; retval = t.value || 0; //this was | 0, which was truncating values &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;