Skip to content

Instantly share code, notes, and snippets.

@andreasf

andreasf/DependencyInterpreter.java

Created March 15, 2012 15:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save andreasf/2044864 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save andreasf/2044864 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
DependencyInterpreter.java
package models.form;
import java.util.*;
/**
* <p>An interpreter for a simple language to model question dependencies.</p>
* <code>
* EXPR ::= QUESTION COMP_OP ANSWER | "(" EXPR ")" | EXPR BOOL_OP EXPR
* COMP_OP ::= "==" | "!="
* BOOL_OP ::= "&" | "|"
* QUESTION ::= QPART | QPART NUMBER | NUMBER QPART | QPART QPART
* QPART ::= LETTER | "_"
* NUMBER :: numbers from "0" to "9"
* LETTER :: letters from "A" to "Z" and from "a" to "z"
*
* QUESTION and ANSWER must not include whitespace.
* BOOL_OPs are left-associative.
* </code>
*
* <p>Examples: <ul>
* <li>q1 == 0</li>
* <li>(Question_1 == 0 | Question_1 == 1) & Question_2 != 2</li>
* </ul></p>
*
* Usage: <code>DependencyInterpreter.interpret(questionMap, showIf);</code>
*
* @author afleig
*/
public class DependencyInterpreter
{
// token types
private static final int BOOL_OP = 0;
private static final int CL_BRACKET = 1;
private static final int OP_BRACKET = 2;
private static final int COMP_OP = 3;
private static final int VAR_Q = 4;
private static final int VAR_A = 5;
// syntax checking automaton
private static final int[][] DFA;
private static final int STATE_START = 0;
private static final int STATE_1 = 1;
private static final int STATE_2 = 2;
private static final int STATE_FINAL = 3;
private static final int STATE_INVALID = -1;
static {
// configure the syntax checking automaton
DFA = new int[4][6];
for (int i=0; i<DFA.length; i++) {
for (int j=0; j<DFA[i].length; j++) {
DFA[i][j] = STATE_INVALID;
}
}
DFA[STATE_START][OP_BRACKET] = STATE_START;
DFA[STATE_START][VAR_Q] = STATE_1;
DFA[STATE_1][COMP_OP] = STATE_2;
DFA[STATE_2][VAR_A] = STATE_FINAL;
DFA[STATE_FINAL][CL_BRACKET] = STATE_FINAL;
DFA[STATE_FINAL][BOOL_OP] = STATE_START;
}
/**
* A generic node in the abstract syntax tree
*/
private static class AstNode
{
AstNode[] nodes;
protected int nodeNumber;
Strategy strategy;
public AstNode()
{
nodes = new AstNode[2];
nodeNumber = -1;
}
public void attachNode(AstNode node)
{
nodeNumber++;
nodes[nodeNumber] = node;
}
public boolean eval(Map<String, Question> questionMap)
{
return strategy.eval(this, questionMap);
}
public boolean hasNextNode()
{
return nodeNumber < nodes.length-1;
}
}
/**
* An AST node type for variables
*/
private static class VarNode extends AstNode
{
private String value;
public VarNode(String value)
{
this.value = value;
}
}
/**
* Processing context, used in buildAst
*/
private static class AstContext
{
AstNode current = new AstNode();
Deque<AstNode> stack = new ArrayDeque<AstNode>();
}
/*
* Evaluation strategies for AST nodes
*/
private interface Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap);
}
private static class Equal implements Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap)
{
String q = ((VarNode)node.nodes[0]).value;
int a = Integer.parseInt(((VarNode)node.nodes[1]).value);
return a == questionMap.get(q).getAnswer();
}
}
private static class NotEqual implements Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap)
{
return !(new Equal().eval(node, questionMap));
}
}
private static class And implements Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap)
{
return node.nodes[0].eval(questionMap) &&
node.nodes[1].eval(questionMap);
}
}
private static class Or implements Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap)
{
return node.nodes[0].eval(questionMap) ||
node.nodes[1].eval(questionMap);
}
}
private static class Bracket implements Strategy
{
public boolean eval(AstNode node, Map<String, Question> questionMap)
{
return node.nodes[0].eval(questionMap);
}
}
/*
* Exceptions
*/
public static class InterpreterError extends Exception {
public InterpreterError(String message) {
super(message);
}
}
public static class SyntaxError extends InterpreterError {
public SyntaxError(String message) {
super(message);
}
}
public static class InvalidTokenError extends InterpreterError {
public InvalidTokenError(String message) {
super(message);
}
}
/**
* Interprets <code>showIf</code> and returns a result. Questions variables
* used in <code>showIf</code> must be present in <code>questionMap</code>.
* @param questionMap assignment of question variables to Questions
* @param showIf question dependency code
* @throws InterpreterError if showIf contains invalid tokens or syntax
* errors
* @return true, if all dependencies are met, false otherwise
*/
public static boolean interpret(Map<String, Question> questionMap,
String showIf) throws InterpreterError
{
List<String> tokens = tokenize(showIf);
List<Integer> types = new LinkedList<Integer>();
checkTokens(tokens, types, questionMap);
checkSyntax(types);
AstNode ast = buildAst(tokens, types);
return ast.eval(questionMap);
}
/**
* Tokenizes the given String to a list of Strings and replaces operators
* @param showIf Question dependency code
* @return List of tokens
*/
private static List<String> tokenize(final String showIf)
{
List<String> tokens = new LinkedList<String>();
int lastOffset = 0;
for (int i=0; i<showIf.length(); i++) {
switch (showIf.charAt(i)) {
case ' ':
case '(':
case ')':
case '&':
case '|':
// end last token
if (i - lastOffset > 0) {
String tok = showIf.substring(lastOffset, i);
// replace "==" => "=" and "!=" => "~"
if (tok.equals("==")) {
tokens.add("=");
} else {
if (tok.equals("!=")) {
tokens.add("~");
} else {
tokens.add(tok);
}
}
}
lastOffset = i+1;
// add new token
if (showIf.charAt(i) != ' ')
tokens.add(""+showIf.charAt(i));
break;
}
}
if (lastOffset < showIf.length()) {
tokens.add(showIf.substring(lastOffset, showIf.length()));
}
return tokens;
}
/**
* Checks all tokens in <code>tokens</code> if they are valid.
* Question variables MUST use A-Z, a-z, the underscore and CAN
* use numbers additionally (but not exclusively). Answer variables must
* use 0-9. If a question variable name is not found in
* <code>questionMap</code>, an error is returned.
* The method also fills the <code>types</code> list with the types of all
* tokens.
* @param tokens List of tokens
* @param types List of types -- this is an output parameter!
* @param questionMap Map of question ids -> questions
* @throws InvalidTokenError If invalid tokens or unknown question ids are
* found
* @return true, if all tokens are valid.
*/
private static boolean checkTokens(List<String> tokens, List<Integer>
types, Map<String, Question> questionMap) throws InvalidTokenError
{
for (String tok : tokens) {
int type = tokenType(tok);
types.add(type);
switch (type) {
case -1:
throw new InvalidTokenError(
"Invalid operator or variable name in question " +
"dependencies: "+tok);
case VAR_Q:
if (!questionMap.containsKey(tok)) {
throw new InvalidTokenError(
"Unknown question id in dependencies: " +
""+tok);
}
break;
}
}
return true;
}
/**
* Returns the type of a token: OPERATOR, CL_BRACKET, OP_BRACKET,
* VAR_Q or VAR_A.
* For invalid tokens, -1 is returned.
*
* @param token token to analyze
* @return type of the token or -1
*/
private static int tokenType(String token)
{
if (token.length() != 1)
return isQuestionOrAnswer(token);
switch (token.charAt(0)) {
case '&':
case '|':
return BOOL_OP;
case '~':
case '=':
return COMP_OP;
case '(':
return OP_BRACKET;
case ')':
return CL_BRACKET;
}
return isQuestionOrAnswer(token);
}
/**
* Returns <code>VAR_Q</code>, if <code>token</code> contains letters,
* numbers and underscores, <code>VAR_A</code> if <code>token</code> only
* contains numbers, and <code>-1</code> otherwise.
* @param token token to analyze
* @return VAR_Q, VAR_A or -1
*/
private static int isQuestionOrAnswer(final String token)
{
boolean answer = true;
for (int i=0; i<token.length(); i++) {
char chr = token.charAt(i);
if ((chr > 64 && chr < 91) || // A-Z
(chr > 96 && chr < 123) || // a-z
chr == 95) { // underscore
answer = false;
continue;
}
if (chr > 47 && chr < 58) { // 0-9
// answer doesn't change here
} else
return -1;
}
if (answer)
return VAR_A;
return VAR_Q;
}
/**
* Checks the syntax of <code>types</code> using an automaton.
* @param types List of token types
* @throws SyntaxError on bracketing and other syntax errors.
* @return True, if the syntax is correct.
*/
private static boolean checkSyntax(List<Integer> types) throws SyntaxError
{
int brackets = 0;
int state = STATE_START;
for (int type : types) {
// brackets
switch (type) {
case CL_BRACKET:
brackets--;
if (brackets < 0) {
throw new SyntaxError("Bracketing error in question " +
"dependency");
}
break;
case OP_BRACKET:
brackets++;
}
// syntax
state = DFA[state][type];
if (state == STATE_INVALID) {
throw new SyntaxError("Syntax error in question dependency");
}
}
if (brackets != 0) {
throw new SyntaxError("Bracketing error in question dependency");
}
if (state != STATE_FINAL) {
throw new SyntaxError("Syntax error in question dependency");
}
return true;
}
/**
* Builds an abstract syntax tree from the given list of tokens.
* @param tokens List of tokens
* @param types List of token types, in the same order as
* <code>tokens</code>
* @return The root node of the AST
*/
private static AstNode buildAst(List<String> tokens, List<Integer> types)
{
AstContext ctx = new AstContext();
Iterator<Integer> ti = types.iterator();
for (String tok : tokens) {
int type = ti.next();
switch (type) {
case OP_BRACKET:
handleBracket(ctx);
break;
case CL_BRACKET:
// jump to the parent node
ctx.current = ctx.stack.pop();
break;
case VAR_A:
case VAR_Q:
ctx.current.attachNode(new VarNode(tok));
break;
case COMP_OP:
ctx.current.strategy = (tok.charAt(0) == '=') ?
new Equal() : new NotEqual();
break;
case BOOL_OP:
handleBool(ctx, tok);
break;
}
}
try {
return ctx.stack.getFirst();
} catch (NoSuchElementException e) {
return ctx.current;
}
}
/**
* Handles opening brackets: inserts a new child node and continues
* from there.
* @param ctx The processing context
*/
private static void handleBracket(AstContext ctx)
{
// insert and jump to a new child node
AstNode newnode = new AstNode();
ctx.current.attachNode(newnode);
ctx.current.strategy = new Bracket();
ctx.stack.push(ctx.current);
ctx.current = newnode;
}
/**
* Handle boolean operators: inserts a new child node at *some point* in
* the tree, sets the strategy of the parent node, adjusts the stack and
* continues from the new node.
* @param ctx Processing context
* @param tok Token of the boolean operator
*/
private static void handleBool(AstContext ctx, String tok)
{
Strategy st = (tok.charAt(0) == '&') ? new And() : new Or();
// after a BOOL_OP, a new node is always inserted for the
// clause after the OP. the parent for this new node must
// be determined first.
AstNode newnode = new AstNode();
AstNode theparent;
if (ctx.current.hasNextNode()) {
// the current node still has space for newnode.
// this means we just processed a closing bracket.
theparent = ctx.current;
} else {
// we travel up the AST and either find space or insert
// a new root
AstNode uptheast;
AstNode oldroot = null;
do {
uptheast = ctx.stack.peek();
if (uptheast != null)
oldroot = ctx.stack.pop();
} while (uptheast != null && !uptheast.hasNextNode());
if (uptheast == null) {
// we are at the top of the ast and have to insert
// a new root
theparent = new AstNode();
theparent.attachNode(oldroot);
} else {
// we are somewhere in the middle of the ast and
// there is space for another node. this space
// exists because of an unclosed bracket. since
// we don't want to mess with brackets, we insert
// theparent as the new left child of this
// bracketing node.
theparent = new AstNode();
theparent.attachNode(uptheast.nodes[0]);
uptheast.nodes[0] = theparent;
ctx.stack.push(uptheast);
}
}
// finally, set the strategy and attach newnode
theparent.strategy = st;
theparent.attachNode(newnode);
ctx.stack.push(theparent);
ctx.current = newnode;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment