noahlt/truthtable.html

## truthtable.html
<html>

<!--

Copyright (c) 2013 Noah Tye <noah@tyes.us>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

-->

<head>
  <title>Truth Table</title>
<style type="text/css">
body {
  font-family: Helvetica, Sans-serif;
  color: #333;
  margin: 2em;
}

/* Form */

form {
  margin: 2em 0 1em;
  display: block;
  height: 1.6em;
}

input {
  border: 1px solid #adadad;
  padding: 4px 8px;
  font-size: 16px;
  margin: 0;
  display: block;
  float: left;
  width: 16em;
}

button {
  border: 1px solid #5cb85c;
  background-color: #5cb85c;
  color: #fafafa;
  font-size: 14px;
  padding: 5px;
  margin: 0;
  margin-left: 6px;
  display: block;
  float: left;
  font-family: Helvetica;
}

button:hover {
  background-color: #6cc86c;
}

button:active {
  background-color: #4cae4c;
  border: 1px solid #449d44;
}

.active { background-color: #efefef; }

/* Intro text */

p { width: 600px; }

a:link, a:visited {
  color: #33c;
  text-decoration: none;
}
a:hover {
  border-bottom: 1px solid #55e;
}

/* Table */

table { border-collapse: collapse; }

td {
  text-align: center;
  border: 1px solid #cdcdcd;
  padding: .25em .75em;
}
</style>
</head>

<body>
<h1>Truth Table Generator</h1>

  <p>Type a Boolean expression and click <small>GO</small> to generate a truth
  table.</p>

  <p>For example, you could review <a class="example-link" href="#A_&amp;_B">conjunction</a> and <a class="example-link" href="#A_|_B">disjunction</a>, prove <a class="example-link" href="#!(A_&amp;_B)__=__(!A_|_!B)">one of de Morgan's laws</a>, or  show that conjunction and disjunction are <a class="example-link" href="#(A_=_B)__=__(A_&amp;_B_=_A_|_B)">equivalent only when the operands are equal</a>.

  <form>
    <input id="exp" autofocus="autofocus" autocomplete="off"></input>
    <button>GO</button>
  </form>

</body>

<script>

//// Configuration variables //////////////////////////////////////////////////

// characters which will be recognized as variable names
var varNames = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

// representations for true and false during evaluation & presentation
var T = 'T', F = 'F';

//// JS utils /////////////////////////////////////////////////////////////////

function repeatStr(s, n) {
  return new Array(n + 1).join(s);
}

function contains(arraylike, x) {
  return arraylike.indexOf(x) >= 0;
}

/*
 * Call f on every element in arraylike & return an array with the results.
 */
function map(arraylike, f) {
  var r = Array(arraylike.length);
  for (var i = 0; i < arraylike.length; i++) {
    r[i] = f(arraylike[i]);
  }
  return r;
}

/*
 * Call f on every element in `arraylike` & discard the results.
 */
function each(arraylike, f) {
  for (var i = 0; i < arraylike.length; i++) {
    f(arraylike[i]);
  }
}

/*
 * Like `each`, but goes in reverse, in decreasing index order. One useful
 * property of going in reverse is that it allows `f` to remove the current
 * element from `arraylike` without messing up the traversal index.
 */
function reverseEach(arraylike, f) {
  for (var i = arraylike.length - 1; i >= 0; i--) {
    f(arraylike[i]);
  }
}

// Imitating Ruby.
String.prototype.gsub = function(search, replace) {
  return this.replace(RegExp(search, 'g'), replace);
}

/*
 * Copied from http://stackoverflow.com/a/7616484
 */
String.prototype.hashCode = function() {
    var hash = 0, i, char;
    if (this.length == 0) return hash;
    for (i = 0, l = this.length; i < l; i++) {
        char  = this.charCodeAt(i);
        hash  = ((hash<<5)-hash)+char;
        hash |= 0; // Convert to 32bit integer
    }
    return hash;
};

//// DOM helpers //////////////////////////////////////////////////////////////

function makeElt(selector, textContent) {
  var sel = selector.split('.');
  var elt = document.createElement(sel[0]);
  if (sel.length > 1) elt.className = sel.slice(1).join(' ');
  if (typeof textContent !== 'undefined') elt.textContent = textContent;
  return elt;
}

function removeElt(elt) {
  elt.parentElement.removeChild(elt);
}

function nbsp(s) { return s.gsub(' ', '&nbsp;'); }

/*
 * After calling trace on the name of a function, every following time the
 * named function is called it will first print its name and the arguments
 * with which it was invoked.
 */
function trace(fname) {
  var originalFunction = window[fname];
  if (typeof originalFunction !== 'function') {
    console.error('argument to trace must be a valid function name');
    return;
  }
  window[fname] = function() {
    console.log('trace:', fname, arguments);
    return originalFunction.apply(window, arguments);
  }
  console.log('now tracing', fname);
}

//// Parser & Eval ////////////////////////////////////////////////////////////

/*
 * varNode and opNode: constructors for nodes to be added to the AST
 */

function varNode(varName, src) {
  return {
    name: varName,
    nodeType: 'var',
    src: (typeof src !== 'undefined') ? src : varName,
    left: null,
    right: null
  }
}

function opNode(opName, left, right, src) {
  var node = {
    name: opName,
    nodeType: 'op',
    src: src
  }
  node.left = (typeof left !== 'undefined') ? left : null;
  node.right = (typeof right !== 'undefined') ? right : null;
  return node;
}

/*
 * Replaces parenthesized expressions with XXX's. Used by parseExpr to ignore
 * any operators inside parentheses.
 *
 * redactParens('abc(def)ghi') -> 'abc(XXX)ghi'
 * redactParens('abc(def(ghi)jkl)mno') -> 'abc(XXXXXXXXXXX)mno'
 */
function redactParens(expString) {
  var parens = [];
  var opener, closer;
  for (var i = 0; i < expString.length; i++) {
    if (expString[i] == '(') {
      parens.push(i)
    } else if (expString[i] == ')') {
      closer = i;
      opener = parens.pop();
      if (typeof opener === 'undefined') console.log('warning: extra closing paren', expString);
      expString = expString.slice(0, opener+1) + repeatStr('X', closer-opener-1) + expString.slice(closer);
    }
  }
  while (parens.length > 0) console.log('warning: extra opening paren at', parens.pop());
  return expString;
}

/*
 * Remove surrounding whitespace and parentheses:
 *
 *   stripExpr('(abc)') -> 'abc'
 *   stripExpr('abc') -> 'abc'
 *   stripExpr('  abc ') -> 'abc'
 *   stripExpr(' (abc) ') -> 'abc'
 *   stripExpr(' ( abc ) ') -> 'abc'
 *
 */
function stripExpr(expString) {
  var parens = [];
  var opener, closer;
  stripped = expString.trim();
  for (var i = 0; i < stripped.length; i++) {
    if (stripped[i] == '(') {
      parens.push(i);
    } else if (stripped[i] == ')') {
      closer = i;
      opener = parens.pop();
      if (opener == 0 && closer == stripped.length-1) stripped = stripped.slice(1, -1);
    }
  }
  stripped = stripped.trim();
  // This function is kind of janky and should be replaced by two functions f
  // and g, where f removes outside whitespace and the outermost parentheses
  // and g finds the fixed point of f on the input string.
  var startStripped = expString.indexOf(stripped);
  return [startStripped, startStripped + stripped.length];
}

function findFirst(searchString) {
  var pos, searchItems = Array.prototype.slice.call(arguments, 1);
  for (var i=0; i<searchItems.length; i++) {
    if ((pos = searchString.indexOf(searchItems[i])) >= 0) return pos;
  }
  return -1;
}

function parseExpr(expString) {
  var operatorPosition,
      strippedIndices = stripExpr(expString),
      strippedStart = strippedIndices[0],
      strippedEnd = strippedIndices[1],
      stripped = expString.slice(strippedStart, strippedEnd),
      redacted = redactParens(stripped),
      srcAnnotation = {
        original: expString,
        leftJunk: expString.slice(0, strippedStart),
        rightJunk: expString.slice(strippedEnd),
        opWithWhitespace: expString // default value for varnodes; gets overridden for operators
      };
  if (stripped.length == 0)
    return null;
  if (stripped.length == 1 && contains(varNames, stripped))
    return varNode(stripped, srcAnnotation);
  if ((operatorPosition = findFirst(redacted, '=', '&', '|', '!', '~')) >= 0) {
    // Empty for-loops to find the boundaries of the whitespace surrounding
    // the operator, saved to operatorLeft and operatorRight.
    for (var operatorLeft = operatorPosition;
         operatorPosition == operatorLeft || (operatorLeft >= 0 && redacted[operatorLeft] == ' ');
         operatorLeft--) { }

    for (var operatorRight = operatorPosition;
         operatorPosition == operatorRight || (operatorRight < redacted.length && redacted[operatorRight] == ' ');
         operatorRight++) { }

    srcAnnotation.opWithWhitespace = stripped.slice(operatorLeft+1, operatorRight);

    return opNode(stripped[operatorPosition],
                  parseExpr(stripped.slice(0, operatorLeft+1)),
                  parseExpr(stripped.slice(operatorRight)),
                  srcAnnotation);
  }
}

function evalTree(tree, values) {
  // Doing nothing when tree == null allows us to indiscriminately eval both
  // tree.left and tree.right without null-checking them first.
  if (tree == null) return;

  evalTree(tree.left, values);
  evalTree(tree.right, values);

  if (tree.nodeType == 'var') {
    tree.value = values[tree.name];
  } else if (tree.nodeType == 'op' && (tree.name == '~' || tree.name == '!')) {
    tree.value = (tree.right.value == T) ? F : T;
  } else if (tree.nodeType == 'op' && tree.name == '&') {
    tree.value = (tree.left.value == T && tree.right.value == T) ? T : F;
  } else if (tree.nodeType == 'op' && tree.name == '|') {
    tree.value = (tree.left.value == F && tree.right.value == F) ? F : T;
  } else if (tree.nodeType == 'op' && tree.name == '=') {
    tree.value = ( (tree.left.value == T && tree.right.value == T) ||
                   (tree.left.value == F && tree.right.value == F) ) ? T : F;
  } else {
    tree.value = 'eval error: looks like our tree was not a var, ~, |, or &';
  }
  return tree;
}

//// UI ///////////////////////////////////////////////////////////////////////

function scanVars(expString) {
  var vars = [];
  each(varNames, function(char) {
    if (contains(expString, char)) vars.push(char);
  });
  return vars;
}

function generateCombinations(vars) {
  if (vars.length == 0) {
    return [];
  } else if (vars.length == 1) {
    return [[T], [F]];
  } else {
    var otherVars = generateCombinations(vars.slice(1)),
        trueBranch =  otherVars.map(function (combination) { return [T].concat(combination) }),
        falseBranch = otherVars.map(function (combination) { return [F].concat(combination) });
    return trueBranch.concat(falseBranch);
  }
}

function combinationToScope(combination, vars) {
  if (vars.length != combination.length) {
    console.error("combination/vars size mismatch; can't produce scope");
    return {};
  }
  r = {};
  for (var i = 0; i < combination.length; i++) {
    r[vars[i]] = combination[i];
  }
  return r;
}

/*
 * Runs f(x) on every node x in a depth-first traversal of tree, returning
 * an array of the return values.
 */
function traverse(tree, f) {
  if (tree == null) return;
  var result = [];
  if (tree.left  != null) result = result.concat(traverse(tree.left, f));
  if (tree.right != null) result = result.concat(traverse(tree.right, f));
  result.push(f(tree));
  return result;
}

/*
 * Like traverse, but only calls f if it hasn't seen a node with the same
 * name before.
 */
function traverseUnique(tree, f) {
  var alreadyTraversedNodeNames = [];
  return traverse(tree, function (node) {
    if (!contains(alreadyTraversedNodeNames, node.src.original)) {
      alreadyTraversedNodeNames.push(node.src.original);
      return f(node);
    }
  });
}

function annotateSrc(node) {
  if (node == null) return '';
  var className = 'expr-' + (node.src.original.hashCode());
  return '<span class="'+className+'">' + nbsp(node.src.leftJunk) +
    annotateSrc(node.left) + nbsp(node.src.opWithWhitespace) + annotateSrc(node.right) +
    nbsp(node.src.rightJunk) + '</span>';
}

function activate (elt) { elt.classList.add('active'); }
function deactivate (elt) { elt.classList.remove('active'); }

function linkActiveHover (parentElt, hoverClass, colClass) {
  each(parentElt.getElementsByClassName(hoverClass), function (elt) {
    elt.addEventListener('mouseover', function (evt) {
      evt.stopPropagation();
      activate(elt)
      each(parentElt.getElementsByClassName(colClass), activate);
      each(parentElt.getElementsByClassName(hoverClass), activate);
    }, false); // false to use event bubbling rather than event capture

    elt.addEventListener('mouseout', function (evt) {
      evt.stopPropagation()
      deactivate(elt);
      each(parentElt.getElementsByClassName(colClass), deactivate);
      each(parentElt.getElementsByClassName(hoverClass), deactivate);
    }, false); // false to use event bubbling rather than event capture
  });
}

function renderTable(exp) {
  each(document.getElementsByTagName('table'), function (elt) { removeElt(elt); });
  var vars = scanVars(exp),
      tableElt = makeElt('table'),
      tree = parseExpr(exp);

  var labelRow = makeElt('tr');
  traverseUnique(tree, function (node) {
    var colLabel = document.createElement('td');
    colLabel.innerHTML = annotateSrc(node);
    colLabel.className = 'col-' + node.src.original.hashCode();
    labelRow.appendChild(colLabel);
  });
  tableElt.appendChild(labelRow);

  traverseUnique(tree, function (node) {
    var hash = node.src.original.hashCode();
    linkActiveHover(tableElt, 'expr-'+hash, 'col-'+hash);
  });

  generateCombinations(vars).forEach(function (combination) {
    var valueRow = makeElt('tr');
    // note that we parse the expression fresh each time, because evalTree is
    // dumb and mutates the tree.
    myTree = evalTree(parseExpr(exp), combinationToScope(combination, vars));
    traverseUnique(myTree, function (nodeWithValue) {
      var selector = 'td.col-'+nodeWithValue.src.original.hashCode();
      valueRow.appendChild(makeElt(selector, nodeWithValue.value));
    });

    tableElt.appendChild(valueRow);
  });

  document.body.appendChild(tableElt);
}

function renderFromInput(evt) {
  evt.preventDefault();
  var expr = document.getElementById('exp').value;
  renderTable(expr);
  window.location.hash = expr.gsub(' ', '_');
}

document.getElementById('exp').onkeypress = function (evt) {
  if (evt.keyCode == 13) {
    renderFromInput(evt);
    evt.target.blur();
  }
}

document.getElementsByTagName('button')[0].onclick = renderFromInput;

// Hash changing code /////////////////////////////////////////////////////////

function renderFromHash() {
  var hash, expr;
  if ((hash = window.location.hash.slice(1)) != '') {
    expr = hash.gsub('_', ' ');
    document.getElementById('exp').value = expr;
    renderTable(expr);
  }
}

window.onhashchange = renderFromHash;

renderFromHash(); // in case there was hash data in the inbound link


/*

Some example parse trees (originally, sketches to help me figure out how parseExp should behave)

A ->
{
  value: 'A'
  nodeType: 'var'
}

~A ->
{
  value: '~'
  nodeType: 'op'
  left: {
    value: 'A'
    nodeType: 'var'
  }
  right: null
}

A&B
{
  value: '&'
  nodeType: 'op'
  left: {
    value: 'A'
    nodeType: 'var'
  }
  right: {
    value: 'B'
    nodeType: 'var'
  }
}

*/
</script>

</html>
	<html>

	<!--

	Copyright (c) 2013 Noah Tye <noah@tyes.us>

	Permission is hereby granted, free of charge, to any person obtaining a copy
	of this software and associated documentation files (the "Software"), to deal
	in the Software without restriction, including without limitation the rights
	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	copies of the Software, and to permit persons to whom the Software is
	furnished to do so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in
	all copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	THE SOFTWARE.

	-->

	<head>
	<title>Truth Table</title>
	<style type="text/css">
	body {
	font-family: Helvetica, Sans-serif;
	color: #333;
	margin: 2em;
	}

	/* Form */

	form {
	margin: 2em 0 1em;
	display: block;
	height: 1.6em;
	}

	input {
	border: 1px solid #adadad;
	padding: 4px 8px;
	font-size: 16px;
	margin: 0;
	display: block;
	float: left;
	width: 16em;
	}

	button {
	border: 1px solid #5cb85c;
	background-color: #5cb85c;
	color: #fafafa;
	font-size: 14px;
	padding: 5px;
	margin: 0;
	margin-left: 6px;
	display: block;
	float: left;
	font-family: Helvetica;
	}

	button:hover {
	background-color: #6cc86c;
	}

	button:active {
	background-color: #4cae4c;
	border: 1px solid #449d44;
	}

	.active { background-color: #efefef; }

	/* Intro text */

	p { width: 600px; }

	a:link, a:visited {
	color: #33c;
	text-decoration: none;
	}
	a:hover {
	border-bottom: 1px solid #55e;
	}

	/* Table */

	table { border-collapse: collapse; }

	td {
	text-align: center;
	border: 1px solid #cdcdcd;
	padding: .25em .75em;
	}
	</style>
	</head>

	<body>
	<h1>Truth Table Generator</h1>

	<p>Type a Boolean expression and click <small>GO</small> to generate a truth
	table.</p>

	<p>For example, you could review <a class="example-link" href="#A_&_B">conjunction</a> and <a class="example-link" href="#A_\|_B">disjunction</a>, prove <a class="example-link" href="#!(A_&_B)__=__(!A_\|_!B)">one of de Morgan's laws</a>, or show that conjunction and disjunction are <a class="example-link" href="#(A_=_B)__=__(A_&_B_=_A_\|_B)">equivalent only when the operands are equal</a>.

	<form>
	<input id="exp" autofocus="autofocus" autocomplete="off"></input>
	<button>GO</button>
	</form>

	</body>

	<script>

	//// Configuration variables //////////////////////////////////////////////////

	// characters which will be recognized as variable names
	var varNames = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

	// representations for true and false during evaluation & presentation
	var T = 'T', F = 'F';

	//// JS utils /////////////////////////////////////////////////////////////////

	function repeatStr(s, n) {
	return new Array(n + 1).join(s);
	}

	function contains(arraylike, x) {
	return arraylike.indexOf(x) >= 0;
	}

	/*
	* Call f on every element in arraylike & return an array with the results.
	*/
	function map(arraylike, f) {
	var r = Array(arraylike.length);
	for (var i = 0; i < arraylike.length; i++) {
	r[i] = f(arraylike[i]);
	}
	return r;
	}

	/*
	* Call f on every element in `arraylike` & discard the results.
	*/
	function each(arraylike, f) {
	for (var i = 0; i < arraylike.length; i++) {
	f(arraylike[i]);
	}
	}

	/*
	* Like `each`, but goes in reverse, in decreasing index order. One useful
	* property of going in reverse is that it allows `f` to remove the current
	* element from `arraylike` without messing up the traversal index.
	*/
	function reverseEach(arraylike, f) {
	for (var i = arraylike.length - 1; i >= 0; i--) {
	f(arraylike[i]);
	}
	}

	// Imitating Ruby.
	String.prototype.gsub = function(search, replace) {
	return this.replace(RegExp(search, 'g'), replace);
	}

	/*
	* Copied from http://stackoverflow.com/a/7616484
	*/
	String.prototype.hashCode = function() {
	var hash = 0, i, char;
	if (this.length == 0) return hash;
	for (i = 0, l = this.length; i < l; i++) {
	char = this.charCodeAt(i);
	hash = ((hash<<5)-hash)+char;
	hash \|= 0; // Convert to 32bit integer
	}
	return hash;
	};

	//// DOM helpers //////////////////////////////////////////////////////////////

	function makeElt(selector, textContent) {
	var sel = selector.split('.');
	var elt = document.createElement(sel[0]);
	if (sel.length > 1) elt.className = sel.slice(1).join(' ');
	if (typeof textContent !== 'undefined') elt.textContent = textContent;
	return elt;
	}

	function removeElt(elt) {
	elt.parentElement.removeChild(elt);
	}

	function nbsp(s) { return s.gsub(' ', ' '); }

	/*
	* After calling trace on the name of a function, every following time the
	* named function is called it will first print its name and the arguments
	* with which it was invoked.
	*/
	function trace(fname) {
	var originalFunction = window[fname];
	if (typeof originalFunction !== 'function') {
	console.error('argument to trace must be a valid function name');
	return;
	}
	window[fname] = function() {
	console.log('trace:', fname, arguments);
	return originalFunction.apply(window, arguments);
	}
	console.log('now tracing', fname);
	}

	//// Parser & Eval ////////////////////////////////////////////////////////////

	/*
	* varNode and opNode: constructors for nodes to be added to the AST
	*/

	function varNode(varName, src) {
	return {
	name: varName,
	nodeType: 'var',
	src: (typeof src !== 'undefined') ? src : varName,
	left: null,
	right: null
	}
	}

	function opNode(opName, left, right, src) {
	var node = {
	name: opName,
	nodeType: 'op',
	src: src
	}
	node.left = (typeof left !== 'undefined') ? left : null;
	node.right = (typeof right !== 'undefined') ? right : null;
	return node;
	}

	/*
	* Replaces parenthesized expressions with XXX's. Used by parseExpr to ignore
	* any operators inside parentheses.
	*
	* redactParens('abc(def)ghi') -> 'abc(XXX)ghi'
	* redactParens('abc(def(ghi)jkl)mno') -> 'abc(XXXXXXXXXXX)mno'
	*/
	function redactParens(expString) {
	var parens = [];
	var opener, closer;
	for (var i = 0; i < expString.length; i++) {
	if (expString[i] == '(') {
	parens.push(i)
	} else if (expString[i] == ')') {
	closer = i;
	opener = parens.pop();
	if (typeof opener === 'undefined') console.log('warning: extra closing paren', expString);
	expString = expString.slice(0, opener+1) + repeatStr('X', closer-opener-1) + expString.slice(closer);
	}
	}
	while (parens.length > 0) console.log('warning: extra opening paren at', parens.pop());
	return expString;
	}

	/*
	* Remove surrounding whitespace and parentheses:
	*
	* stripExpr('(abc)') -> 'abc'
	* stripExpr('abc') -> 'abc'
	* stripExpr(' abc ') -> 'abc'
	* stripExpr(' (abc) ') -> 'abc'
	* stripExpr(' ( abc ) ') -> 'abc'
	*
	*/
	function stripExpr(expString) {
	var parens = [];
	var opener, closer;
	stripped = expString.trim();
	for (var i = 0; i < stripped.length; i++) {
	if (stripped[i] == '(') {
	parens.push(i);
	} else if (stripped[i] == ')') {
	closer = i;
	opener = parens.pop();
	if (opener == 0 && closer == stripped.length-1) stripped = stripped.slice(1, -1);
	}
	}
	stripped = stripped.trim();
	// This function is kind of janky and should be replaced by two functions f
	// and g, where f removes outside whitespace and the outermost parentheses
	// and g finds the fixed point of f on the input string.
	var startStripped = expString.indexOf(stripped);
	return [startStripped, startStripped + stripped.length];
	}

	function findFirst(searchString) {
	var pos, searchItems = Array.prototype.slice.call(arguments, 1);
	for (var i=0; i<searchItems.length; i++) {
	if ((pos = searchString.indexOf(searchItems[i])) >= 0) return pos;
	}
	return -1;
	}

	function parseExpr(expString) {
	var operatorPosition,
	strippedIndices = stripExpr(expString),
	strippedStart = strippedIndices[0],
	strippedEnd = strippedIndices[1],
	stripped = expString.slice(strippedStart, strippedEnd),
	redacted = redactParens(stripped),
	srcAnnotation = {
	original: expString,
	leftJunk: expString.slice(0, strippedStart),
	rightJunk: expString.slice(strippedEnd),
	opWithWhitespace: expString // default value for varnodes; gets overridden for operators
	};
	if (stripped.length == 0)
	return null;
	if (stripped.length == 1 && contains(varNames, stripped))
	return varNode(stripped, srcAnnotation);
	if ((operatorPosition = findFirst(redacted, '=', '&', '\|', '!', '~')) >= 0) {
	// Empty for-loops to find the boundaries of the whitespace surrounding
	// the operator, saved to operatorLeft and operatorRight.
	for (var operatorLeft = operatorPosition;
	operatorPosition == operatorLeft \|\| (operatorLeft >= 0 && redacted[operatorLeft] == ' ');
	operatorLeft--) { }

	for (var operatorRight = operatorPosition;
	operatorPosition == operatorRight \|\| (operatorRight < redacted.length && redacted[operatorRight] == ' ');
	operatorRight++) { }

	srcAnnotation.opWithWhitespace = stripped.slice(operatorLeft+1, operatorRight);

	return opNode(stripped[operatorPosition],
	parseExpr(stripped.slice(0, operatorLeft+1)),
	parseExpr(stripped.slice(operatorRight)),
	srcAnnotation);
	}
	}

	function evalTree(tree, values) {
	// Doing nothing when tree == null allows us to indiscriminately eval both
	// tree.left and tree.right without null-checking them first.
	if (tree == null) return;

	evalTree(tree.left, values);
	evalTree(tree.right, values);

	if (tree.nodeType == 'var') {
	tree.value = values[tree.name];
	} else if (tree.nodeType == 'op' && (tree.name == '~' \|\| tree.name == '!')) {
	tree.value = (tree.right.value == T) ? F : T;
	} else if (tree.nodeType == 'op' && tree.name == '&') {
	tree.value = (tree.left.value == T && tree.right.value == T) ? T : F;
	} else if (tree.nodeType == 'op' && tree.name == '\|') {
	tree.value = (tree.left.value == F && tree.right.value == F) ? F : T;
	} else if (tree.nodeType == 'op' && tree.name == '=') {
	tree.value = ( (tree.left.value == T && tree.right.value == T) \|\|
	(tree.left.value == F && tree.right.value == F) ) ? T : F;
	} else {
	tree.value = 'eval error: looks like our tree was not a var, ~, \|, or &';
	}
	return tree;
	}

	//// UI ///////////////////////////////////////////////////////////////////////

	function scanVars(expString) {
	var vars = [];
	each(varNames, function(char) {
	if (contains(expString, char)) vars.push(char);
	});
	return vars;
	}

	function generateCombinations(vars) {
	if (vars.length == 0) {
	return [];
	} else if (vars.length == 1) {
	return [[T], [F]];
	} else {
	var otherVars = generateCombinations(vars.slice(1)),
	trueBranch = otherVars.map(function (combination) { return [T].concat(combination) }),
	falseBranch = otherVars.map(function (combination) { return [F].concat(combination) });
	return trueBranch.concat(falseBranch);
	}
	}

	function combinationToScope(combination, vars) {
	if (vars.length != combination.length) {
	console.error("combination/vars size mismatch; can't produce scope");
	return {};
	}
	r = {};
	for (var i = 0; i < combination.length; i++) {
	r[vars[i]] = combination[i];
	}
	return r;
	}

	/*
	* Runs f(x) on every node x in a depth-first traversal of tree, returning
	* an array of the return values.
	*/
	function traverse(tree, f) {
	if (tree == null) return;
	var result = [];
	if (tree.left != null) result = result.concat(traverse(tree.left, f));
	if (tree.right != null) result = result.concat(traverse(tree.right, f));
	result.push(f(tree));
	return result;
	}

	/*
	* Like traverse, but only calls f if it hasn't seen a node with the same
	* name before.
	*/
	function traverseUnique(tree, f) {
	var alreadyTraversedNodeNames = [];
	return traverse(tree, function (node) {
	if (!contains(alreadyTraversedNodeNames, node.src.original)) {
	alreadyTraversedNodeNames.push(node.src.original);
	return f(node);
	}
	});
	}

	function annotateSrc(node) {
	if (node == null) return '';
	var className = 'expr-' + (node.src.original.hashCode());
	return '<span class="'+className+'">' + nbsp(node.src.leftJunk) +
	annotateSrc(node.left) + nbsp(node.src.opWithWhitespace) + annotateSrc(node.right) +
	nbsp(node.src.rightJunk) + '</span>';
	}

	function activate (elt) { elt.classList.add('active'); }
	function deactivate (elt) { elt.classList.remove('active'); }

	function linkActiveHover (parentElt, hoverClass, colClass) {
	each(parentElt.getElementsByClassName(hoverClass), function (elt) {
	elt.addEventListener('mouseover', function (evt) {
	evt.stopPropagation();
	activate(elt)
	each(parentElt.getElementsByClassName(colClass), activate);
	each(parentElt.getElementsByClassName(hoverClass), activate);
	}, false); // false to use event bubbling rather than event capture

	elt.addEventListener('mouseout', function (evt) {
	evt.stopPropagation()
	deactivate(elt);
	each(parentElt.getElementsByClassName(colClass), deactivate);
	each(parentElt.getElementsByClassName(hoverClass), deactivate);
	}, false); // false to use event bubbling rather than event capture
	});
	}

	function renderTable(exp) {
	each(document.getElementsByTagName('table'), function (elt) { removeElt(elt); });
	var vars = scanVars(exp),
	tableElt = makeElt('table'),
	tree = parseExpr(exp);

	var labelRow = makeElt('tr');
	traverseUnique(tree, function (node) {
	var colLabel = document.createElement('td');
	colLabel.innerHTML = annotateSrc(node);
	colLabel.className = 'col-' + node.src.original.hashCode();
	labelRow.appendChild(colLabel);
	});
	tableElt.appendChild(labelRow);

	traverseUnique(tree, function (node) {
	var hash = node.src.original.hashCode();
	linkActiveHover(tableElt, 'expr-'+hash, 'col-'+hash);
	});

	generateCombinations(vars).forEach(function (combination) {
	var valueRow = makeElt('tr');
	// note that we parse the expression fresh each time, because evalTree is
	// dumb and mutates the tree.
	myTree = evalTree(parseExpr(exp), combinationToScope(combination, vars));
	traverseUnique(myTree, function (nodeWithValue) {
	var selector = 'td.col-'+nodeWithValue.src.original.hashCode();
	valueRow.appendChild(makeElt(selector, nodeWithValue.value));
	});

	tableElt.appendChild(valueRow);
	});

	document.body.appendChild(tableElt);
	}

	function renderFromInput(evt) {
	evt.preventDefault();
	var expr = document.getElementById('exp').value;
	renderTable(expr);
	window.location.hash = expr.gsub(' ', '_');
	}

	document.getElementById('exp').onkeypress = function (evt) {
	if (evt.keyCode == 13) {
	renderFromInput(evt);
	evt.target.blur();
	}
	}

	document.getElementsByTagName('button')[0].onclick = renderFromInput;

	// Hash changing code /////////////////////////////////////////////////////////

	function renderFromHash() {
	var hash, expr;
	if ((hash = window.location.hash.slice(1)) != '') {
	expr = hash.gsub('_', ' ');
	document.getElementById('exp').value = expr;
	renderTable(expr);
	}
	}

	window.onhashchange = renderFromHash;

	renderFromHash(); // in case there was hash data in the inbound link


	/*

	Some example parse trees (originally, sketches to help me figure out how parseExp should behave)

	A ->
	{
	value: 'A'
	nodeType: 'var'
	}

	~A ->
	{
	value: '~'
	nodeType: 'op'
	left: {
	value: 'A'
	nodeType: 'var'
	}
	right: null
	}

	A&B
	{
	value: '&'
	nodeType: 'op'
	left: {
	value: 'A'
	nodeType: 'var'
	}
	right: {
	value: 'B'
	nodeType: 'var'
	}
	}

	*/
	</script>

	</html>