GLL Parser Combinator or Generator in/for C or C++ [closed]

Question

Is there any existing implementation of the GLL algorithm, either in the form of parser combinators (preferred) or as a parser generator for C or C++?

My requirements are that the output is a shared packed parse forest (SPPF) which I can later disambiguate using semantic and/or contextual rules. There are other parsing algorithms such as GLR which are able to cope with general context-free grammars, however, all GLR parser generators I could find either return the first successful parse tree or fail if any ambiguity remains at the end.

Posen

I understand Bison has a GLR switch, but I don't know what its properties are. I'm suprised that those tools you could find objected if there were any remaining ambiguities (we use GLR parsers and keep these precisely to do semantic analysis as you suggest). If they do, there must be a moment in time in which they have the entire tree ambiguities and all; you should be able to step in an take the tree at that moment. – Protestantism

According to the Bison homepage, its GLR parser is exponential in time (i.e. it isn't implemented correctly, as a GLR parser with the correct data structures is O(n³) – Posen

Have you considered an Earley parser as an alternative to a GLL parser? Marpa is an Earley parser for Perl that is implemented via a C library. – Heterosis

Have you seen sourceforge.net/projects/cocom (docs at cocom.sourceforge.net/ammunition++-13.html ) – Towle

Have you checked github.com/djspiewak/gll-combinators ? – Machinate

@Machinate Scala is not c++ – Posen

Answer 1

What if you try out GLL Combinators? Although it uses Scala, you may write "thin" wrappers for it by means of the JNI.

GLL Combinators is a framework designed to implement the GLL parsing algorithm (Scott and Johnstone, LDTA 2009) in a functional manner. More specifically, the framework makes use of atomic parser combinators to compose grammars which are then evaluated using the GLL algorithm. The framework provides a syntax for this task which is almost identical to that of the parser combinator framework built into Scala. For example, we can render the classic "parentheses grammar" using GLL combinators:

lazy val expr: Parser[Any] = (
    "(" ~ expr ~ ")"
  | ""
)

As the type annotation implies, expr will reference an instance of type Parser[Any]. That is, an atomic parser which consumes some input and returns a value of type Any. We can invoke this parser against a String input in the following way:

expr("((()))")

This will return a value of type Stream[Result[Any]]. The Result[A] ADT is defined as one of the following (for some type A):

• Success[A] -- Represents a successful parse and contains the resulting value.
• Failure -- Represents a failed parse and contains the relevant error message as well as the remainder of the parse stream (the characters which were not consumed).

If any result is successful (i.e. an instance of Success[A]), then no failures will be returned. Thus, the Stream returned will be completely homogeneous, containing either Success or Failure, but not both. A Stream is returned rather than a single value to allow for ambiguity in the grammar (see below).

It's worth mentioning that GLL is a form of recursive-descent parsing. It has all of the advantages of conventional recursive-descent, including an intuitive control flow, arbitrary positioning of semantic actions and superior error messages. In fact, it is the fact that GLL is recursive-descent which allows it to be implemented using atomic combinators. Other algorithms which share the same capabilities as GLL (such as GLR, Earley Parsing, etc) are fundamentally incompatible with the combinator model due to their highly-unintuitive control flow. In GLL parsing, the control flow follows that of the grammar, as it does in traditional parser combinators or any other form of recursive-descent.

Statistician

I very much doubt there is any reasonable mapping for the combinators themselves via JNI. – Posen

@Joe: Not for the combinators themselves, no. That's simply non-sense. I was thinking that you could create some kind of wrapper in Scheme that makes the calls easier for C/C++ code,. and call those functions throught JNI – Statistician