[2015 day 19] Part 2 [spoilers!]

• parseback

  1 196 10.0 Scala

  A Scala implementation of parsing with derivatives

Next with some research I read Parsing With Derivatives, with an implementation in scala. Unfortunately, this still appears to have exponential runtime; my initial test target string of ~20 characters took an hour to complete.

• gll-combinators

  1 298 0.0 Scala

  A parser combinator library based on the GLL algorithm

Next, I tried a general GLL parser. This, however, required more memory than my 16GB macbook could provide. A 256G AWS cloud instance proved insufficient, as did a 1TB cloud instance. No good.

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• java-probabilistic-earley-parser

  1 34 0.0 Java

  🎲 Efficient Java implementation of the probabilistic Earley algorithm to parse Stochastic Context Free Grammars (SCFGs)

Finally, I looked for java libraries for Earley parsers, and found this one. Constructing the grammar was straightforward, and I had the advantage of being able to "weight" each production rule with a 1-epsilon probability, meaning it would selectively produce the shortest possible parse derivation first.

Suggest a related project