Hacker News Reader

Comment by iovrthoughtthis | Hacker News Reader

How have you totally missed GLL and GLR parsing?!

One of the most interesting parser libraries I've encountered uses GLL. It's a clojure library called Instaparse [1]. The author had a nice presentation on it [2]. I'm not sure how well it works in practice though. Another great article on the subject [3].

[1] https://github.com/Engelberg/instaparse

[2] https://www.youtube.com/watch?v=b2AUW6psVcE

[3] https://epsil.github.io/gll/

Who uses them? I know someone who wrote a GLR parser generator, but I've never seen the algorithm used in production.

I've heard of one C++ front end that uses it -- Elkhound -- but the only context I've heard of Elkhound is in GLR parsing! As far as I can tell Clang is now the state of the art. (i.e. Clang probably does everything Elkhound does, but better and faster.)

I have looked at least 30+ parsers for programming languages. I see:

    - hand-written recursive descent (with operator precedence for expressions)
    - yacc (Ruby, R, awk, etc.)
    - ANTLR
    - Bespoke parser generators
      - Python's pgen.c - LL(1) with some tricks
      - sqlite's Lemon - similar to Yacc except you push tokens

That's about it. I've never encountered notable usages of Earley or GLL or GLR parsing.

I don't know if it really counts, but I used RNGLR for the programming language I've been working on, and have been planning on replacing it with a GLL version in a bit. RNGLR was fairly complicated, and I did find the paper a bit hard to read, which might have limited its spread somewhat. When messing with the syntax for my language, it was nice to only have to worry about if my grammar was ambiguous rather than weather it would fit into LL, LR or LALR, and made it easy to change syntax very quickly without changing any actual code.

They do:

http://semanticdesigns.com/Products/DMS/DMSToolkit.html

With all that, what do we need another parsing tech for if it's programming related? ;) GLR was also used for NLP. The Elkhound approach mixes (IIRC!) GLR and LALR to get benefits of both with it easily handling one of hardest languages out there.

A little weird to leave off the list one of best techniques around.

Also, silentbicycle countered with it and some other on top of that here:

https://lobste.rs/s/pkfdah/parsing_timeline#c_suirwn

FWIW, Bison (which I'd expect most people are using rather than the original yacc, though I can't be sure) does support GLR parsing.

I haven't seen GLR used in production either, but my experience with projects I've been involved in is that this is sometimes just due to inertia. Taking full advantage of GLR's support for ambiguity requires reworking both your grammar and your early stages of semantic analysis, and even if people agree that the result might be nicer, nobody has the time or motivation to do all that work.

I've used GLR to parse C files in isolation - no lexer hack needed. More generally, at least historically, a lot of wizzy parsing tech has been closely held by companies selling their ability to deal with enterprise legacy code.

Tangentially related, the author of this timeline has developed an Earley parsing framework called Marpa. http://savage.net.au/Marpa.html .

It's used in other projects (eg, https://github.com/jddurand/MarpaX-Languages-C-AST ) but the only ones I found which look production ready, in a cursory search, also involved the author.

And it wasn't until now that I got to that section of the timeline.

Thanks, this is what I'm getting at. A lot of parsing techniques seem to fall into the category of "only people who care about parsing use them."

That's not to say they will never jump the chasm. I'm just a bit conservative in my design choices and I look for algorithms that have been "battle-tested".

As a minor commentary, back around 2000 I used Aycock's SPARK parser for Python, which was based on the Earley algorithm. I first learned about the Earley algorithm from Aycock's presentation at the Python conference IPC7. (His use of docstrings to annotate the grammar went on to influence Beazley's PLY parser, which is LALR(1))

Aycock's work with SPARK was one of the influences of Kegler's Marpa. I was surprised to see Aycock mentioned on this timeline as it was the only name were I could say "I met him".

Thus, I can say that for my work, I used the Earley algorithm. However, I don't think it was essential for the parsing I needed, only that it was available.

Ah that's interesting. I recognize SPARK because it used to be part of the Python distribution, used to parse the DSL that describes Python's AST:

https://eli.thegreenplace.net/2014/06/04/using-asdl-to-descr...

In other words it was DSL used to implement a DSL used to implement Python -- how meta! But that post describes replacing it with a simple recursive descent parser in Python.

I used ASDL itself (not SPARK) extensively in my shell:

http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL

But still I would say that counts as a production usage of Earley parsing! Interesting. I don't know of any others.

(On the other hand, the fact that it was replaced with a few hundred lines of Python code means it probably wasn't needed in the first place.)

The Spoofax Language Workbench http://www.metaborg.org/en/latest/ uses scannerless generalized LR parsing. When language processor development effort is more important than raw parsing speed (e.g. for external domain specific languages), Spoofax's grammar, abstract syntax tree, and semantics tools are exactly the right thing.

I'm no expert, but my (very crude) understanding is that much of modern natural language parsing frameworks (e.g., Google's SyntaxNet) can be viewed as variations of GLR where we slap a probability onto each possible transition.

Not exactly what you're after, but I've been using Might's "Parsing With Derivatives", which is a general parsing algorithm, for my toy language I'm working on. Links are in my root-level comment above. (I'm on mobile or else I'd just provide the links for you here directly.)

Reply on news.ycombinator.com