Queensu Requirements Grammar Parser

grammer.jison

%lex

%%

\s+                       /* skip whitespace */
"."|","|";"|":"           /* skip punctuation */

[Rr][Ee][Cc][Oo][Mm][Mm][Ee][Nn][Dd]
|[Rr][Ee][Cc][Oo][Mm][Mm][Ee][Nn][Dd][Aa][Tt][Ii][Oo][Nn][Ss]?
                          return 'RECOMMEND';

[Pp][Rr][Ee][Rr][Ee][Qq][Uu][Ii][Ss][Ii][Tt][Ee][Ss]?
                          return 'PREREQUISITE';

[Cc][Oo][Rr][Ee][Qq][Uu][Ii][Ss][Ii][Tt][Ee][Ss]?
                          return 'COREQUISITE';

[Oo][Rr]                  return 'OR';
[Aa][Nn][Dd]              return 'AND';

"("                       return '(';
")"                       return ')';

[a-zA-Z]+" "?[pP]?[0-9]+  return 'COURSE';

<<EOF>>                   return 'EOF';

.                         /* Ignore everything else */

/lex

%token RECOMMEND PREREQUISITE COREQUISITE '(' ')' COURSE

%left "OR"
%left "AND"

%start full

%%

full
  : reqsetlist EOF {
    // The document is just a requirements set list
    $$ = $1;
    global.parsed = $$;
    console.log($$);
  }
  ;

reqsetlist
  : {
    // No requirements or anything like that
    $$ = [];
  }
  | reqset {
    if ($1.courses.items.length === 0) {
      /* Don't pass empty reqsets through */
      $$ = [];
    } else {
      $$ = [$1];
    }
  }
  | reqsetlist reqset {
    /* Add an item to the requirement set list */
    if ($2.courses.items.length === 0) {
      /* Don't pass empty reqsets through */
      $$ = $1;
    } else {
      $$ = $1.slice(0);
      $$.push($2);
    }
  }
  ;

/* A set of requirements/recommendations/corequisites */
reqset
  : RECOMMEND courselist {
    $$ = {
      type: 'recommend',
      courses: $2
    };
  }
  | COREQUISITE courselist {
    $$ = {
      type: 'corequisite',
      courses: $2
    };
  }
  | PREREQUISITE courselist {
    $$ = {
      type: 'prerequisite',
      courses: $2
    };
  }
  | courselist {
    $$ = {
      type: 'prerequisite',
      courses: $1
    }
  }
  ;

courselist
  : COURSE {
    $$ = {
      type: "and",
      items: [$1]
    };
    console.log($1);
  }
  | courselist AND courselist {
    /* And two items together */
    $$ = courselistAnd($1, $3);
  }
  | courselist courselist {
    /* Connect the two courses together with an AND by default */
    $$ = courselistAnd($1, $2);
  }
  | courselist OR courselist {
    /* Or two items together */
    $$ = courselistOr($1, $3);
  }
  | "(" courselist ")" {
    /* Make sure that the stuff inside is evaluated first */
    $$ = $2;
  }
  /* To deal with floating ANDs and ORs */
  | OR {
    $$ = {type: "and", items: []};
  }
  | AND {
    $$ = {type: "and", items: []};
  }
  ;

%%

test.js

var fs = require('fs');

var Parser = require('jison').Parser;

var parser = new Parser(fs.readFileSync('grammar.jison', 'utf8'));

// At some point I should add more strings to test
// I am too lazy to fetch them right now
var strings = [
  "Must be registered in a BSCE or UENG program.",
  "APSC 131 OR CHEM 120",
  "APSC 293 Cor req",
  "Recommendation    BIOL 201 and BIOL 202. Prerequisite    A minimum grade of C- in BIOL 205.",
  "Prerequisite    BIOL 308. Prior to registering in the course, students must complete the application process, be placed in a module and complete the field work.",
  "Prerequisites    BIOL 201 and BIOL 202 and (a minimum grade of C- in BIOL 206) and (BIOL 243 or PSYC 202 or STAT 269)."
];

// Set some helper functions in the global scope
global.courselistAnd = function courselistAnd(a, b) {
  if (a.type === "and" && b.type === "and") {
    // Grow the and list
    return {
      type: "and",
      items: a.items.concat(b.items)
    };
  } else if (a.type === "and" && b.type === "or") {
    // Add the or item as an item in the and list
    return {
      type: "and",
      items: a.items.concat([b])
    };
  } else if (a.type === "or" && b.type === "and") {
    // Add the or item as an item in the and list
    return {
      type: "and",
      items: b.items.concat([a])
    };
  } else {
    // Items on both sides are ORs, we want both to be true
    return {
      type: "and",
      items: [a, b]
    };
  }
};

global.courselistOr = function courselistOr(a, b) {
  if (a.type === "and" && b.type === "and") {
    // Check if one or the other is of length 1
    // If it is, we can simplify
    if (a.items.length === 1)
      a = a.items[0];
    if (b.items.length === 1)
      b = b.items[0];

    return {
      type: "or",
      items: [a, b]
    };
  } else if (a.type === "and" && b.type === "or") {
    // Add the AND as a value to the OR
    if (a.items.length === 1)
      a = a.items[0];

    return {
      type: "or",
      items: b.items.concat([a])
    };
  } else if (a.type === "or" && b.type === "and") {
    // Add the AND as a value to the OR
    if (b.items.length === 1)
      b = b.items[0];

    return {
      type: "or",
      items: a.items.concat([b])
    };
  } else {
    // Items on both sides are ORs, lets just link them together
    return {
      type: "or",
      items: a.items.concat(b.items)
    };
  }
};

// Loop through each of the strings, parsing them
strings.forEach(function (string) {
  console.log(string);
  console.log(parser.parse(string));
  console.log(Array(80).join("*"));
});

use

npm install jison
node test.js

Things that need to be added to the syntax:

1. Equivalencies
2. Exclusions/One Way Exclusions (I can probably treat them the same way)

These should be relatively trivial to add. Is there anything else that I need to add?