Ohm Polynomial Differentiator

Illustration of using Ohm to parse polynomials and generating derivatives with semantic actions written in CoffeeScript

by Ray Toal

HTML

<script src="https://unpkg.com/[email protected]/dist/ohm.js"></script>
<link rel="stylesheet" href="https://code.jquery.com/qunit/qunit-git.css">
<script src="https://code.jquery.com/qunit/qunit-git.js"></script>
<script type="text/ohm-js">
Polynomial {
  Poly  = Poly "+" Term       -- plus
        | Poly "-" Term       -- minus
        | "-" Term            -- negate
        | Term
  Term  = Coeff "x" "^" Exp   -- coeff_var_exp
        | Coeff "x"           -- coeff_var
        | Coeff               -- coeff
        | "x" "^" Exp         -- var_exp
        | "x"                 -- var
  Coeff = digit+
  Exp   = "-"? digit+
}
</script>
<div id="qunit"></div>
<div id="qunit-fixture"></div>

CoffeeScript

g = ohm.grammarFromScriptElement()

semantics = g.createSemantics().addOperation('diff', {
  Poly_plus: (p, op, t) -> p.diff() + "+" + t.diff(),
  Poly_minus: (p, op, t) -> p.diff() + "-" + t.diff(),
  Poly_negate: (op, t) -> "-" + t.diff(),
  Term_coeff_var_exp: (c, x, _, e) -> (e.val()*c.val()) + "x^" + (e.val()-1),
  Term_coeff_var: (c, x) -> c.val(),
  Term_coeff: (c) -> "0",
  Term_var_exp: (x, _, e) -> e.val() + "x^" + (e.val()-1),
  Term_var: (x) -> "1",
}).addOperation('val', {
  Coeff: (num) -> @sourceString,
  Exp: (sign, num) -> @sourceString,
})

diff = (poly) -> 
  match = g.match poly
  throw match.message if not match.succeeded()
  semantics(match).diff().replace(/--/g,'+').replace(/\+-/g,'-')
      
QUnit.test 'Parser detects malformed polynomials', (assert) ->
  assert.throws () -> diff('2y')
  assert.throws () -> diff('blah')
  assert.throws () -> diff('2x*6')
    
QUnit.test 'Single term polynomials differentiate correctly', (assert) ->
  assert.equal diff('4'), '0'
  assert.equal diff('2238'), '0'
  assert.equal diff('x'), '1'
  assert.equal diff('4x'), '4'
  assert.equal diff('x ^ 5'), '5x^4'
  assert.equal diff('2x ^ -4'), '-8x^-5'

QUnit.test 'Polynomials with term operators differentiate correctly', (assert) ->
  assert.equal diff('-4'), '-0'
  assert.equal diff('-2238'), '-0'
  assert.equal diff('-x'), '-1'
  assert.equal diff('-x ^ 5'), '-5x^4'
  assert.equal diff('-x ^ -5'), '+5x^-6'
  assert.equal diff('2x ^ -4 + 7x  ^2'), '-8x^-5+14x^1'
  assert.equal diff('2x ^ -4 - 7x  ^20'), '-8x^-5-140x^19'
  assert.equal diff('2x ^ -4 + 7x  ^-2'), '-8x^-5-14x^-3'