brownplt/pyret-lang — pull request #133 by blerner (2013-12-17 00:46:58+00:00)
Title: Parsers!

I'm now pretty confident that I have a working parser to give you. To use:

1. Run `node bnf-parser.js`. This will compile the BNF grammar into a parser, then parse (a variant of) the Pyret `grammar.rkt` file (at a hard-coded location for now, until we figure out where everything needs to be), and generate `grammar.js` from it.
2. Run `node grammar.js`. This will compile the Pyret grammar, and generate `pyret-parser.js`.
3. Run `node parse-pyret ` to use the parser generated above to parse a Pyret file and print out a s-exp representation of the parse tree.

In general, once `pyret-parser.js` is built, steps 1 and 2 don't need to happen again. For now, it uses node.js, so I could run it from the command line, and one test file uses log4js so I could redirect console logging. Neither of these are hard dependencies, and once constructed, the parser itself is pure JS and can be run with no dependencies.

The parser constructs a simple tree, where each node has a `label`, a `pos`ition, and an array of `kids` that are in turn nodes, or else are simply `Token`s (that also have `pos`ition information). The parser engine can also check whether the grammar is cyclic (that is, allows some derivation of the form `A => ... => A`, and therefore admits infinitely many parse trees for the nonterminal `A`), and can check whether a given input file has resulted in multiple ambiguous parsings (and if so, how many).

The parse algorithm used is the RNGLR algorithm, by Scott & Johnstone (TOPLAS, July 2006). The code isn't very commented/documented yet, but that can be added later...