ocfgc - a parser generator for ordered CFG (with GLR/Tomita's parsing)

ocfgc - a parser generator for ordered CFG (with GLR/Tomita's parsing)

[Stephen Tse]

We would like to announce our project written in OCaml: "ocfgc" - a
parser generator for ordered context free grammars (OCFG) based on GLR
(Generalized LR) parsing, also known as Tomita's parsing.

GLR parsing allows syntax specification in the full context-free
grammar, eliminating shift or reduce conflicts in LR/LALR parsing.
High efficiency is achieved using a graph-structured parse stack.

Ordered CFG (see our paper below) specifies the datatype tags together
with associativity and precedence per production rule, making it
possibly to generate abstract syntax trees from a concise specification of
concrete syntax.

We have applied the parser generator for Java 5; the parser can parse
any JDK 1.5 files under 0.5 second.

Features:
- concise specification (e.g. http://www.cis.upenn.edu/~stse/javac/java.g)
- automatic error diagnosis with line numbers and grammar information
- automatic construction of abstract-syntax trees
- generates maps, iterators, pretty-printers
- on-the-fly disambiguation filters

Currently ocfgc is bundled with our fjavac (Functional Java Compiler)
project, which can be obtained at:

 http://www.cis.upenn.edu/~stse/javac/

Basic type checking and bytecode compilation of the compiler are
implemented, but supports for generics and type inference are still
underway.

Our following paper "Concise Concrete Syntax" explains the idea of
ordered CFG, which can also be applied to LR/LALR parsing:

 http://www.cis.upenn.edu/~stse/javac/ocfg.pdf


Cheers,
Stephen