A parser generator using the Grammar Flow Graph

Recently, a new way to represent context-free grammars (CFG) has been put forward. The representation uses a directed graph called the Grammar Flow Graph (GFG). The GFG provides a framework to parse all context-free languages (CFL) based on Earley´s algorithm that is easier to understand than the original Earley´s presentation. In addition, the GFG connects two seemingly distant concepts for regular language parsing and parsing of CFLs. It shows that simulating all the moves through a non-deterministic finite-state automaton (NFA) can be generalized to moving along all appropriate GFG paths. This paper introduces a GFG parser generator whose functionalities are equivalent to popular parser generators like Yacc or Bison. However, it works on all CFGs-ambiguous or unambiguous. Our parser generator takes a grammar file that represents strings in CFL as an input and outputs a parser program to parse those strings. We evaluate it against two other parser generators, one based on the original Earley´s representation and the other based on the Cocke-Younger-Kasami (CYK) algorithm. The result indicates that the performance of our parser generator is on a par with that based on the original Earley´s scheme and superior to the CYK´s parser generator. The code for our parser generator can be downloaded from the following link: https://bitbucket.org/kramatk/earleyparser.