7 ms·

How have you totally missed GLL and GLR parsing?! http://dotat.at/tmp/gll.pdf http://dotat.at/tmp/gll.pdf

chubot 9y ago
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.
- miloignis 9y ago
  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.
- nickpsecurity 9y ago
  They do: http://semanticdesigns.com/Products/DMS/DMSToolkit.html 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 https://lobste.rs/s/pkfdah/parsing_timeline#c_suirwn
- housel 9y ago
  The Spoofax Language Workbench http://www.metaborg.org/en/latest/ 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.
- swift 9y ago
  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.
  - mncharity 9y ago
    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.
- eesmith 9y ago
  Tangentially related, the author of this timeline has developed an Earley parsing framework called Marpa. http://savage.net.au/Marpa.html http://savage.net.au/Marpa.html . It's used in other projects (eg, https://github.com/jddurand/MarpaX-Languages-C-AST 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.
  - eesmith 9y ago
    And it wasn't until now that I got to that section of the timeline.
  - chubot 9y ago
    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".
    - eesmith 9y ago
      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.
      - chubot 9y ago
        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-describe-asts-in-compilers 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 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.)
- yongjik 9y ago
  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.
- DonaldPShimoda 9y ago
  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.)
undecidabot 9y ago
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 https://github.com/Engelberg/instaparse [2] https://www.youtube.com/watch?v=b2AUW6psVcE https://www.youtube.com/watch?v=b2AUW6psVcE [3] https://epsil.github.io/gll/ 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.

miloignis 9y ago
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.
nickpsecurity 9y ago
They do: http://semanticdesigns.com/Products/DMS/DMSToolkit.html 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 https://lobste.rs/s/pkfdah/parsing_timeline#c_suirwn
housel 9y ago
The Spoofax Language Workbench http://www.metaborg.org/en/latest/ 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.
swift 9y ago
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.
- mncharity 9y ago
  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.
eesmith 9y ago
Tangentially related, the author of this timeline has developed an Earley parsing framework called Marpa. http://savage.net.au/Marpa.html http://savage.net.au/Marpa.html . It's used in other projects (eg, https://github.com/jddurand/MarpaX-Languages-C-AST 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.
- eesmith 9y ago
  And it wasn't until now that I got to that section of the timeline.
- chubot 9y ago
  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".
  - eesmith 9y ago
    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.
    - chubot 9y ago
      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-describe-asts-in-compilers 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 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.)
yongjik 9y ago
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.
DonaldPShimoda 9y ago
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.)

undecidabot 9y ago

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 https://github.com/Engelberg/instaparse [2] https://www.youtube.com/watch?v=b2AUW6psVcE https://www.youtube.com/watch?v=b2AUW6psVcE [3] https://epsil.github.io/gll/ https://epsil.github.io/gll/