10 ms·

Parsing: a timeline

326 points by janvdberg 9y ago

ahazred8ta 9y ago
Impressive. Half the breakthroughs involve Chomsky.
- bla2 9y ago
  Probably because the author of this article studied Chomsky a lot and others less.
- sp332 9y ago
  The advisor for my CS degree, a Romanian woman for whom English was a fourth language, pointed out that one of our textbooks had several chapters on Chomsky's generative grammars but never mentioned his name. She said (and I agree) this was most likely due to his politics. I don't doubt that his other views influence how much credit he is or isn't given.
- carapace 9y ago
  Chomsky's Transformational Grammar is part of the origin story of Neuro-Linguistic Programming.
  - sp332 9y ago
    NLP in this context refers to Natural Language Processing. Neuro-lingustic programming is a very different thing. https://en.wikipedia.org/wiki/Neuro-linguistic_programming https://en.wikipedia.org/wiki/Neuro-linguistic_programming
    - carapace 9y ago
      Yes, I know, I'm familiar with both "NLP"'s. My point is I think it's a fascinating and historically important fact that Neuro-lingustic programming grew directly out of Chomsky-informed analysis of the communications between therapists and their clients. If you read "Structure of Magic, Vol. I" it's basically using Transformational Grammar to detect missing information in the surface structure of clients' statements in a therapeutic context. ----- I've got to say that that wikipedia article is one of the very few that I have encountered that badly misrepresents its subject. I have direct experience of NLP. I would describe it as the operating system of the human mind. I don't really know what to make of the idea that it "has been discredited as a pseudoscience by experts" except that they must not have been very good experts.
      - sp332 9y ago
        Oh, crazy. Ok, thanks.
      - klmr 9y ago
        > I don't really know what to make of the idea that it "has been discredited as a pseudoscience by experts" The Wikipedia article actually does a fairly good job of listing the evidence for this claim (further down). In particular, they show polls of the lack of acceptance by experts within the field of psychology. So the best you could say is that it’s a fringe theory. Furthermore, several claims of the original creators very directly contradict established biological facts (treating physiological ailments such as near-sightedness or the common cold). This obviously casts suspicion on the rest of the theory.
- jules 9y ago
  Not really, only the definition of context free grammar.
  - jeffmcmahan 9y ago
    "Not really, only the basis of the entire business."
    - jules 9y ago
      It's a good contribution but don't exaggerate it. Just because you defined something doesn't mean it's impressive. Peano rigorously defined natural numbers but Wiles' proof of Fermat's last theorem is a tad more impressive. The parsing contribution of figures like Knuth is orders of magnitude more impressive. I see that above you state "Noam is on the short list of the most intellectually impactful human beings of the period since Descartes". This is just not the case. The religion built around Chomsky is a bit crazy. Chomsky contributed to linguistics and it was an interesting theory but it turned out he was mostly wrong, but fortunately his work is applicable to parsing computer languages. That's it. He certainly doesn't belong on a list that Einstein "maybe" belongs to.
      - jeffmcmahan 9y ago
        "Chomsky contributed to linguistics and it was an interesting theory but it turned out he was mostly wrong..." You've made a very strong claim about linguistic theory while knowing very little about it. The vast majority of those working on phonology do so within the mold set by Chomsky & Morris Halle in 1970, and there are roughly zero syntacticians doing serious work on natural language syntax outside the Chomskyan tradition (whether in GB or Minimalism). "The religion built around Chomsky is a bit crazy." You're hardly in a position to judge, with no more than a passing acquaintance with psych 101 summaries of his work. "Just because you defined something doesn't mean it's impressive." The Chomsky hierarchy was not "defined" in the deflationary sense that you're pushing. Chomsky discovered that generative mechanisms partake of a special set of related properties relating the range of their output to specific constraints on the formalisms that can exactly describe their grammars. It so happens that this discovery made possible much that happened in CS during the 60s and into the 70s. I'll leave aside your bizarre comments as to the unimpressiveness of Peano arithmetic.
- jeffmcmahan 9y ago
  Noam is on the short list of the most intellectually impactful human beings of the period since Descartes: Newton, Darwin, Smith, maybe Ricardo, Marx, maybe Frege or Russell, Einstein, Turing, Keynes, Chomsky, and a scant few more. His politics may motivate people to disregard him, but mostly he's just come to the devastating conclusion (for solid reasons) that people working on language outside the Chomskyan tradition are not doing science; semantics, linguistic anthropology, and some areas of psychology are just wind. People who do such work will not understand his criticism because their academic standing depends on their not understanding it. There is thus a supply of motivated PhDs ready to dismiss and de-emphasize his contributions. Some of the same applies to philosophers who work on language.
  - skybrian 9y ago
    Although oddly, Chomsky seems more important for computer languages than natural languages? The most successful machine translation systems don't use Chomsky's grammars. But their compiler's parser probably does. More: http://norvig.com/chomsky.html http://norvig.com/chomsky.html
    - jeffmcmahan 9y ago
      As the article you linked says of Chomsky's view (correctly), "Statistical language models have had engineering success, but that is irrelevant to science." Chomsky wants to know how your brain does things, and not how best to make a computer do something to approximate that. He reiterated to me and a few others in 2009, during a seminar, that right from the start he always said that the only way to do machine translation is brute force statistics -- but back in the 50s he took the funding for translation research, and then just did whatever he wanted with it.
  - Froyoh 9y ago
    And Knuth!
    - jeffmcmahan 9y ago
      Haha, yes, perhaps. "I found the mathematical approach to grammar immediately appealing---so much so, in fact, that I must admit to taking a copy of Noam Chomsky's Syntactic Structures along with me on my honeymoon in 1961." - Knuth
- vlmlee 9y ago
  I was listening to some lecture and they were talking about there being really only two modes of thought - through pictures and/or through words. Imagine being the one to break down one whole class of thought into a formal discipline.
chrisaycock 9y ago
I like ANTLR 4's innovations, which are missing from the article. This paper introduces the ALL(*) parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down LL(k) parsers with the power of a GLR- like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets ALL(*) handle any non-left-recursive context-free grammar. https://dl.acm.org/citation.cfm?id=2660202 https://dl.acm.org/citation.cfm?id=2660202
- drfuchs 9y ago
  Non-paywalled: http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf
iovrthoughtthis 9y ago
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
finnh 9y ago
My professor-of-sanskrit friend chimes in: The Germans were deep into Pannini in the 1800s, and the Russians were as well. So it's possible the first point overstates the degree of ignorance of Pannini, at least on Markov's part =)
- Isamu 9y ago
  Thanks for this pointer. https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini "Pāṇini's work became known in 19th-century Europe, where it influenced modern linguistics initially through Franz Bopp, who mainly looked at Pāṇini. Subsequently, a wider body of work influenced Sanskrit scholars such as Ferdinand de Saussure, Leonard Bloomfield, and Roman Jakobson."
danharaj 9y ago
Misses the subplot of Lambek's categorial grammar and the way it frames parsing as proof search. Pretty cool idea, perhaps underexplored.
- haskellandchill 9y ago
  I have some older books and heavy papers on the subject. Any recent lightweight treatments you can link to? Thanks.
  - danharaj 9y ago
    This paper is fresh in my mind since I recently read it. I liked it: https://www.eecs.harvard.edu/shieber/Biblio/Papers/infer.pdf https://www.eecs.harvard.edu/shieber/Biblio/Papers/infer.pdf We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine can interpret such deduction systems so as to implement the corresponding parser. The method generalizes easily to parsers for augmented phrase structure formalisms, such as definite-clause grammars and other logic grammar formalisms, and has been used for rapid prototyping of parsing algorithms for a variety of formalisms including variants of tree-adjoining grammars, categorial grammars, and lexicalized context-free grammars.
    - DonbunEf7 9y ago
      I knew Earley parsing before I read this paper. Now I know things about logic and theorem proving. Cool paper, would read again.
Al-Khwarizmi 9y ago
The first entry seemed to imply that the post would be about (or at least include) natural language parsing, but it only focuses on the formal language parsing used in compilers.
- catpolice 9y ago
  This is because the two subjects were largely indistinguishable until fairly recently. Most of the theory for language parsing came from efforts to describe natural languages in terms of formal grammars, and until ALGOL, most programming languages didn't have especially complex grammars. So until recently, the study of formal languages was a linguistics thing - it's since become much more popular in the CS world.
  - Al-Khwarizmi 9y ago
    Certainly they share a common root, but "largely indistinguishable until fairly recently" is quite an overstatement. They have had distinct goals and methods for at least 50 years, and for the last 20 years the overlap has been minimal. CKY is from the 60s. Inside-outside from the 70s. Mild context sensitivity, tree adjoining grammars and other similar formalisms from the 70s-80s. Chart parsers that actually work for natural language in real life scenarios from the 90s (Collins, Charniak, Eisner). All that is seminal work in natural language parsing and mostly useless for compilers, just like LR is mostly useless for natural language.
    - catpolice 9y ago
      Sorry, I'm from a philosophy background so I think of anything published in the last ~100 years as "fairly recent" ;) All I meant was that that many ideas and methods developed originally for linguistics were taken up and expanded upon in programming language research, so that they had a great deal of overlap until about half way through the timeline in the link.
      - jcranmer 9y ago
        Programming languages didn't exist in any meaningful sense until the 1950s, and the theoretical framework didn't really exist until the 1960s. There's very little cross-pollination between compiler and natural language theory, both before and after the time. Strip out the notion of the CFG (a one-way development), and there's not really any overlap.
ulrikrasmussen 9y ago
Also, for a very comprehensive survey on parsing techniques, I can recommend "Parsing Techniques" by Grune and Jacobs: https://dickgrune.com/Books/PTAPG_2nd_Edition/ https://dickgrune.com/Books/PTAPG_2nd_Edition/
DonaldPShimoda 9y ago
This was a good article! It's (reasonably) missing one of my favorite parsing algorithms, though, which is Might's "Parsing with Derivatives" [0, 1]. It's not very efficient compared to some other algorithms, but I think it is very elegant conceptually. [0] Blog post: http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/ [1] Paper: http://matt.might.net/papers/might2011derivatives.pdf http://matt.might.net/papers/might2011derivatives.pdf [2] Improvements: https://michaeldadams.org/papers/derivatives2/derivatives2.pdf https://michaeldadams.org/papers/derivatives2/derivatives2.p...
- fithisux 9y ago
  The author, according to my understanding, says that parsing with derivatives does not improve the state of the art either in terms of complexity or in terms of elegance. My personal opinion is that Matt Might uses a different avenue to derive the state of the art and even though the original algorithm can be trapped to exponential complexity, the improved analysis and amendments in the 2012 paper save the situation. I think it is quite an achievement to fight against so many experts who believed that the flaws could not be worked around and re-derive the state of art complexity. At least in the field of pure mathematics this has a very big value.
  - cwzwarich 9y ago
    Did any experts actually say that the flaw couldn't be worked around? I thought the argument was just that working around the flaw gives you known algorithms.
  - DonaldPShimoda 9y ago
    You bring up good points! I think the efficiency in real-world applications is still not as good as alternative solutions, but what I really like about PWD is that it's a general parsing algorithm that's incredibly simple to understand (if you have a working knowledge of regular languages). The implementation can be a little more tricky (e.g. if you've never written a fix-point before[0]), but the actual concepts just seem so simple. PWD was actually one of the first parsing algorithms I learned about (odd, I know), and even without much prior knowledge of the field of parsing I was able to grasp the gist of it in a single sitting. [0] You can also just skip over establishing a fix-point if you guarantee that your language is not left-recursive.
Froyoh 9y ago
Don Knuth is a genius
kummappp 9y ago
The PEG comments seems to be a bit bitter and I would like to hear the story behind the frustration.
- majewsky 9y ago
  The article says that PEG handles non-deterministic grammars by becoming non-deterministic itself. I don't know about PEG, but if that's true, it sure sounds like a recipe for disaster.
  - jeffreykegler 9y ago
    Thanks for reading my article. I don't say that, though the distinction is tricky. PEG is relentlessly deterministic, but that does not mean that the user can determine, in practice, what choice PEG will make. It's the difference between my being able to tell you that Jimmy Hoffa is definitely in a specific place, and my being able to tell you where that place is.
    - lucio 9y ago
      Are you saying that the user "can not" determine? Who's the user? the source code writer?
      - jeffreykegler 9y ago
        The author of the PEG script cannot in general know what language it actually describes -- it's just too hard. For more, see https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2015/03/peg.html https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi.... It has references, which you can follow up on. You're safe if the grammar is LL(1) -- what you sees is what you get. After that it gets mysterious fast.
        lucio 9y ago
        The language definition is pre-existent to the PEG parser you can write for it. PEG has a lot of advantages as a tool, and its a nice experience to write by hand. You do not author a PEG script, you author a language definition first. You're saying that if the lang definition is lost, then is hard to recover it from the PEG script or the parser code. Yes, but it is not a normal situation.
majewsky 9y ago
Somewhat related: Marpa is a fantastic piece of software. I used it once for implementing a custom query language for a DCIM I was working on. If I'd still be using Perl, I'm sure I would've put it to good use again.
- eesmith 9y ago
  The Marpa FAQ at http://savage.net.au/Perl-modules/html/marpa.faq/faq.html#q131 http://savage.net.au/Perl-modules/html/marpa.faq/faq.html#q1... asks "Are there C/Lua/Python/etc bindings for libmarpa?" and answers that there are "Various language bindings for libmarpa" at https://github.com/rns/libmarpa-bindings https://github.com/rns/libmarpa-bindings .
  - mncharity 9y ago
    > there are "Various language bindings for libmarpa" The C libmarpa is regrettably only the core of the larger parser[1], written in Perl. And at least as of several years ago, it had not been used elsewhere. Though it looks like there was some unmerged ruby activity in 2016. [1] https://metacpan.org/source/JKEGL/Marpa-R2-4.000000/lib/Marpa https://metacpan.org/source/JKEGL/Marpa-R2-4.000000/lib/Marp...
deleted 9y ago
[deleted]
haberman 9y ago
The author has assembled an interesting timeline. It leaves a lot out (this is inevitable; the theoretical research around parsing is unbelievably vast). But ultimately the goal of the article appears to be placing their project Marpa in its historical context. Marpa is one of many attempts to "solve" the problem of parsing. Other notable attempts are PEG (Parsing Expression Grammars), the ALL(*) algorithm from ANTLR (http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf) and GLR. I wrote an article about what makes this such a difficult problem: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...
xiaq 9y ago
I get the quest for more elegant and powerful parsing techniques, but it seems that some very interesting real-world problems - mostly arising in code editors - don't get enough academic love: * Fast re-parsing when part of the input changes; * Parsing of incomplete input, and enumerating possible ways to continue the input. These can be very useful for code editors, for syntax highlighting and code completion. Some editors work around this by using a more restricted lexical syntax and avoiding to build a complete parse tree (Vim); newer editors - JetBrain and VS Code AFAIK - do have some pretty good techniques, but they don't seem to get a lot of academic treatise.
- danharaj 9y ago
  You might like this page: http://okmij.org/ftp/continuations/differentiating-parsers.html http://okmij.org/ftp/continuations/differentiating-parsers.h...
- catpolice 9y ago
  Fast re-parsing is tricky. I'm building a JS IDE for a simple language, and it needs to only re-parse the part of the syntax tree that an edit affects (and only update the minimal number of affected DOM nodes). Writing the (recursive descent) lexer/parser by hand was easy. Being able to stream text diffs to the lexer/parser and have it rebuild only the appropriate part of the AST took... a bit of work. Writing unit tests might kill me.
  - xiaq 9y ago
    I cannot find the link now, but I remember reading a recent article saying that what VSCode does is basically storing some context information for each line. When input changes, the line is reparsed, and then the context provides enough information on how to modify the parse tree.
    - catpolice 9y ago
      Yeah, that's pretty similar to what I ended up doing - it comes pretty natural with recursive descent to just store enough of the parser state on relevant nodes that you can restart it at natural breaks. For my application, I end up having to make expensive async queries about the expressions the user writes. In order to minimize server load/make things responsive/avoid invalidating perfectly good caches, this means that I have to know exactly what to keep and what to throw out with each edit, which means that I never want to replace any node in the AST with an identical one that was needlessly re-parsed if I can help it. So my lexer does a lot of work trying not to throw out parts of lines that the user hasn't touched, and the parser can figure out what changes are relevant to invalidate my caches. Oddly the restartable lexer has turned out to be the most frustrating part - selectively diffing parts of two doubly linked lists and snipping them together in the way I ended up having to is one of those things that isn't conceptually very difficult but has the potential for unusually subtle bugs.
systemBuilder 9y ago
Missing important details concerning why LLVM is taking over the world.

Parsing: a timeline

326 points by janvdberg 9y ago

ahazred8ta 9y ago

Impressive. Half the breakthroughs involve Chomsky.

bla2 9y ago
Probably because the author of this article studied Chomsky a lot and others less.
sp332 9y ago
The advisor for my CS degree, a Romanian woman for whom English was a fourth language, pointed out that one of our textbooks had several chapters on Chomsky's generative grammars but never mentioned his name. She said (and I agree) this was most likely due to his politics. I don't doubt that his other views influence how much credit he is or isn't given.
carapace 9y ago
Chomsky's Transformational Grammar is part of the origin story of Neuro-Linguistic Programming.
- sp332 9y ago
  NLP in this context refers to Natural Language Processing. Neuro-lingustic programming is a very different thing. https://en.wikipedia.org/wiki/Neuro-linguistic_programming https://en.wikipedia.org/wiki/Neuro-linguistic_programming
  - carapace 9y ago
    Yes, I know, I'm familiar with both "NLP"'s. My point is I think it's a fascinating and historically important fact that Neuro-lingustic programming grew directly out of Chomsky-informed analysis of the communications between therapists and their clients. If you read "Structure of Magic, Vol. I" it's basically using Transformational Grammar to detect missing information in the surface structure of clients' statements in a therapeutic context. ----- I've got to say that that wikipedia article is one of the very few that I have encountered that badly misrepresents its subject. I have direct experience of NLP. I would describe it as the operating system of the human mind. I don't really know what to make of the idea that it "has been discredited as a pseudoscience by experts" except that they must not have been very good experts.
    - sp332 9y ago
      Oh, crazy. Ok, thanks.
    - klmr 9y ago
      > I don't really know what to make of the idea that it "has been discredited as a pseudoscience by experts" The Wikipedia article actually does a fairly good job of listing the evidence for this claim (further down). In particular, they show polls of the lack of acceptance by experts within the field of psychology. So the best you could say is that it’s a fringe theory. Furthermore, several claims of the original creators very directly contradict established biological facts (treating physiological ailments such as near-sightedness or the common cold). This obviously casts suspicion on the rest of the theory.
jules 9y ago
Not really, only the definition of context free grammar.
- jeffmcmahan 9y ago
  "Not really, only the basis of the entire business."
  - jules 9y ago
    It's a good contribution but don't exaggerate it. Just because you defined something doesn't mean it's impressive. Peano rigorously defined natural numbers but Wiles' proof of Fermat's last theorem is a tad more impressive. The parsing contribution of figures like Knuth is orders of magnitude more impressive. I see that above you state "Noam is on the short list of the most intellectually impactful human beings of the period since Descartes". This is just not the case. The religion built around Chomsky is a bit crazy. Chomsky contributed to linguistics and it was an interesting theory but it turned out he was mostly wrong, but fortunately his work is applicable to parsing computer languages. That's it. He certainly doesn't belong on a list that Einstein "maybe" belongs to.
    - jeffmcmahan 9y ago
      "Chomsky contributed to linguistics and it was an interesting theory but it turned out he was mostly wrong..." You've made a very strong claim about linguistic theory while knowing very little about it. The vast majority of those working on phonology do so within the mold set by Chomsky & Morris Halle in 1970, and there are roughly zero syntacticians doing serious work on natural language syntax outside the Chomskyan tradition (whether in GB or Minimalism). "The religion built around Chomsky is a bit crazy." You're hardly in a position to judge, with no more than a passing acquaintance with psych 101 summaries of his work. "Just because you defined something doesn't mean it's impressive." The Chomsky hierarchy was not "defined" in the deflationary sense that you're pushing. Chomsky discovered that generative mechanisms partake of a special set of related properties relating the range of their output to specific constraints on the formalisms that can exactly describe their grammars. It so happens that this discovery made possible much that happened in CS during the 60s and into the 70s. I'll leave aside your bizarre comments as to the unimpressiveness of Peano arithmetic.
jeffmcmahan 9y ago
Noam is on the short list of the most intellectually impactful human beings of the period since Descartes: Newton, Darwin, Smith, maybe Ricardo, Marx, maybe Frege or Russell, Einstein, Turing, Keynes, Chomsky, and a scant few more. His politics may motivate people to disregard him, but mostly he's just come to the devastating conclusion (for solid reasons) that people working on language outside the Chomskyan tradition are not doing science; semantics, linguistic anthropology, and some areas of psychology are just wind. People who do such work will not understand his criticism because their academic standing depends on their not understanding it. There is thus a supply of motivated PhDs ready to dismiss and de-emphasize his contributions. Some of the same applies to philosophers who work on language.
- skybrian 9y ago
  Although oddly, Chomsky seems more important for computer languages than natural languages? The most successful machine translation systems don't use Chomsky's grammars. But their compiler's parser probably does. More: http://norvig.com/chomsky.html http://norvig.com/chomsky.html
  - jeffmcmahan 9y ago
    As the article you linked says of Chomsky's view (correctly), "Statistical language models have had engineering success, but that is irrelevant to science." Chomsky wants to know how your brain does things, and not how best to make a computer do something to approximate that. He reiterated to me and a few others in 2009, during a seminar, that right from the start he always said that the only way to do machine translation is brute force statistics -- but back in the 50s he took the funding for translation research, and then just did whatever he wanted with it.
- Froyoh 9y ago
  And Knuth!
  - jeffmcmahan 9y ago
    Haha, yes, perhaps. "I found the mathematical approach to grammar immediately appealing---so much so, in fact, that I must admit to taking a copy of Noam Chomsky's Syntactic Structures along with me on my honeymoon in 1961." - Knuth
vlmlee 9y ago
I was listening to some lecture and they were talking about there being really only two modes of thought - through pictures and/or through words. Imagine being the one to break down one whole class of thought into a formal discipline.

chrisaycock 9y ago

I like ANTLR 4's innovations, which are missing from the article. This paper introduces the ALL(*) parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down LL(k) parsers with the power of a GLR- like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets ALL(*) handle any non-left-recursive context-free grammar. https://dl.acm.org/citation.cfm?id=2660202 https://dl.acm.org/citation.cfm?id=2660202

drfuchs 9y ago
Non-paywalled: http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf

iovrthoughtthis 9y ago

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

finnh 9y ago

My professor-of-sanskrit friend chimes in: The Germans were deep into Pannini in the 1800s, and the Russians were as well. So it's possible the first point overstates the degree of ignorance of Pannini, at least on Markov's part =)

Isamu 9y ago
Thanks for this pointer. https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini "Pāṇini's work became known in 19th-century Europe, where it influenced modern linguistics initially through Franz Bopp, who mainly looked at Pāṇini. Subsequently, a wider body of work influenced Sanskrit scholars such as Ferdinand de Saussure, Leonard Bloomfield, and Roman Jakobson."

danharaj 9y ago

Misses the subplot of Lambek's categorial grammar and the way it frames parsing as proof search. Pretty cool idea, perhaps underexplored.

haskellandchill 9y ago
I have some older books and heavy papers on the subject. Any recent lightweight treatments you can link to? Thanks.
- danharaj 9y ago
  This paper is fresh in my mind since I recently read it. I liked it: https://www.eecs.harvard.edu/shieber/Biblio/Papers/infer.pdf https://www.eecs.harvard.edu/shieber/Biblio/Papers/infer.pdf We present a system for generating parsers based directly on the metaphor of parsing as deduction. Parsing algorithms can be represented directly as deduction systems, and a single deduction engine can interpret such deduction systems so as to implement the corresponding parser. The method generalizes easily to parsers for augmented phrase structure formalisms, such as definite-clause grammars and other logic grammar formalisms, and has been used for rapid prototyping of parsing algorithms for a variety of formalisms including variants of tree-adjoining grammars, categorial grammars, and lexicalized context-free grammars.
  - DonbunEf7 9y ago
    I knew Earley parsing before I read this paper. Now I know things about logic and theorem proving. Cool paper, would read again.

Al-Khwarizmi 9y ago

The first entry seemed to imply that the post would be about (or at least include) natural language parsing, but it only focuses on the formal language parsing used in compilers.

catpolice 9y ago
This is because the two subjects were largely indistinguishable until fairly recently. Most of the theory for language parsing came from efforts to describe natural languages in terms of formal grammars, and until ALGOL, most programming languages didn't have especially complex grammars. So until recently, the study of formal languages was a linguistics thing - it's since become much more popular in the CS world.
- Al-Khwarizmi 9y ago
  Certainly they share a common root, but "largely indistinguishable until fairly recently" is quite an overstatement. They have had distinct goals and methods for at least 50 years, and for the last 20 years the overlap has been minimal. CKY is from the 60s. Inside-outside from the 70s. Mild context sensitivity, tree adjoining grammars and other similar formalisms from the 70s-80s. Chart parsers that actually work for natural language in real life scenarios from the 90s (Collins, Charniak, Eisner). All that is seminal work in natural language parsing and mostly useless for compilers, just like LR is mostly useless for natural language.
  - catpolice 9y ago
    Sorry, I'm from a philosophy background so I think of anything published in the last ~100 years as "fairly recent" ;) All I meant was that that many ideas and methods developed originally for linguistics were taken up and expanded upon in programming language research, so that they had a great deal of overlap until about half way through the timeline in the link.
    - jcranmer 9y ago
      Programming languages didn't exist in any meaningful sense until the 1950s, and the theoretical framework didn't really exist until the 1960s. There's very little cross-pollination between compiler and natural language theory, both before and after the time. Strip out the notion of the CFG (a one-way development), and there's not really any overlap.

ulrikrasmussen 9y ago

Also, for a very comprehensive survey on parsing techniques, I can recommend "Parsing Techniques" by Grune and Jacobs: https://dickgrune.com/Books/PTAPG_2nd_Edition/ https://dickgrune.com/Books/PTAPG_2nd_Edition/

DonaldPShimoda 9y ago

This was a good article! It's (reasonably) missing one of my favorite parsing algorithms, though, which is Might's "Parsing with Derivatives" [0, 1]. It's not very efficient compared to some other algorithms, but I think it is very elegant conceptually. [0] Blog post: http://matt.might.net/articles/parsing-with-derivatives/ http://matt.might.net/articles/parsing-with-derivatives/ [1] Paper: http://matt.might.net/papers/might2011derivatives.pdf http://matt.might.net/papers/might2011derivatives.pdf [2] Improvements: https://michaeldadams.org/papers/derivatives2/derivatives2.pdf https://michaeldadams.org/papers/derivatives2/derivatives2.p...

fithisux 9y ago
The author, according to my understanding, says that parsing with derivatives does not improve the state of the art either in terms of complexity or in terms of elegance. My personal opinion is that Matt Might uses a different avenue to derive the state of the art and even though the original algorithm can be trapped to exponential complexity, the improved analysis and amendments in the 2012 paper save the situation. I think it is quite an achievement to fight against so many experts who believed that the flaws could not be worked around and re-derive the state of art complexity. At least in the field of pure mathematics this has a very big value.
- cwzwarich 9y ago
  Did any experts actually say that the flaw couldn't be worked around? I thought the argument was just that working around the flaw gives you known algorithms.
- DonaldPShimoda 9y ago
  You bring up good points! I think the efficiency in real-world applications is still not as good as alternative solutions, but what I really like about PWD is that it's a general parsing algorithm that's incredibly simple to understand (if you have a working knowledge of regular languages). The implementation can be a little more tricky (e.g. if you've never written a fix-point before[0]), but the actual concepts just seem so simple. PWD was actually one of the first parsing algorithms I learned about (odd, I know), and even without much prior knowledge of the field of parsing I was able to grasp the gist of it in a single sitting. [0] You can also just skip over establishing a fix-point if you guarantee that your language is not left-recursive.

Froyoh 9y ago

Don Knuth is a genius

kummappp 9y ago

The PEG comments seems to be a bit bitter and I would like to hear the story behind the frustration.

majewsky 9y ago
The article says that PEG handles non-deterministic grammars by becoming non-deterministic itself. I don't know about PEG, but if that's true, it sure sounds like a recipe for disaster.
- jeffreykegler 9y ago
  Thanks for reading my article. I don't say that, though the distinction is tricky. PEG is relentlessly deterministic, but that does not mean that the user can determine, in practice, what choice PEG will make. It's the difference between my being able to tell you that Jimmy Hoffa is definitely in a specific place, and my being able to tell you where that place is.
  - lucio 9y ago
    Are you saying that the user "can not" determine? Who's the user? the source code writer?
    - jeffreykegler 9y ago
      The author of the PEG script cannot in general know what language it actually describes -- it's just too hard. For more, see https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2015/03/peg.html https://jeffreykegler.github.io/Ocean-of-Awareness-blog/indi.... It has references, which you can follow up on. You're safe if the grammar is LL(1) -- what you sees is what you get. After that it gets mysterious fast.
      - lucio 9y ago
        The language definition is pre-existent to the PEG parser you can write for it. PEG has a lot of advantages as a tool, and its a nice experience to write by hand. You do not author a PEG script, you author a language definition first. You're saying that if the lang definition is lost, then is hard to recover it from the PEG script or the parser code. Yes, but it is not a normal situation.

majewsky 9y ago

Somewhat related: Marpa is a fantastic piece of software. I used it once for implementing a custom query language for a DCIM I was working on. If I'd still be using Perl, I'm sure I would've put it to good use again.

eesmith 9y ago
The Marpa FAQ at http://savage.net.au/Perl-modules/html/marpa.faq/faq.html#q131 http://savage.net.au/Perl-modules/html/marpa.faq/faq.html#q1... asks "Are there C/Lua/Python/etc bindings for libmarpa?" and answers that there are "Various language bindings for libmarpa" at https://github.com/rns/libmarpa-bindings https://github.com/rns/libmarpa-bindings .
- mncharity 9y ago
  > there are "Various language bindings for libmarpa" The C libmarpa is regrettably only the core of the larger parser[1], written in Perl. And at least as of several years ago, it had not been used elsewhere. Though it looks like there was some unmerged ruby activity in 2016. [1] https://metacpan.org/source/JKEGL/Marpa-R2-4.000000/lib/Marpa https://metacpan.org/source/JKEGL/Marpa-R2-4.000000/lib/Marp...

deleted 9y ago

[deleted]

haberman 9y ago

The author has assembled an interesting timeline. It leaves a lot out (this is inevitable; the theoretical research around parsing is unbelievably vast). But ultimately the goal of the article appears to be placing their project Marpa in its historical context. Marpa is one of many attempts to "solve" the problem of parsing. Other notable attempts are PEG (Parsing Expression Grammars), the ALL(*) algorithm from ANTLR (http://www.antlr.org/papers/allstar-techreport.pdf http://www.antlr.org/papers/allstar-techreport.pdf) and GLR. I wrote an article about what makes this such a difficult problem: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...

xiaq 9y ago

I get the quest for more elegant and powerful parsing techniques, but it seems that some very interesting real-world problems - mostly arising in code editors - don't get enough academic love: * Fast re-parsing when part of the input changes; * Parsing of incomplete input, and enumerating possible ways to continue the input. These can be very useful for code editors, for syntax highlighting and code completion. Some editors work around this by using a more restricted lexical syntax and avoiding to build a complete parse tree (Vim); newer editors - JetBrain and VS Code AFAIK - do have some pretty good techniques, but they don't seem to get a lot of academic treatise.

danharaj 9y ago
You might like this page: http://okmij.org/ftp/continuations/differentiating-parsers.html http://okmij.org/ftp/continuations/differentiating-parsers.h...
catpolice 9y ago
Fast re-parsing is tricky. I'm building a JS IDE for a simple language, and it needs to only re-parse the part of the syntax tree that an edit affects (and only update the minimal number of affected DOM nodes). Writing the (recursive descent) lexer/parser by hand was easy. Being able to stream text diffs to the lexer/parser and have it rebuild only the appropriate part of the AST took... a bit of work. Writing unit tests might kill me.
- xiaq 9y ago
  I cannot find the link now, but I remember reading a recent article saying that what VSCode does is basically storing some context information for each line. When input changes, the line is reparsed, and then the context provides enough information on how to modify the parse tree.
  - catpolice 9y ago
    Yeah, that's pretty similar to what I ended up doing - it comes pretty natural with recursive descent to just store enough of the parser state on relevant nodes that you can restart it at natural breaks. For my application, I end up having to make expensive async queries about the expressions the user writes. In order to minimize server load/make things responsive/avoid invalidating perfectly good caches, this means that I have to know exactly what to keep and what to throw out with each edit, which means that I never want to replace any node in the AST with an identical one that was needlessly re-parsed if I can help it. So my lexer does a lot of work trying not to throw out parts of lines that the user hasn't touched, and the parser can figure out what changes are relevant to invalidate my caches. Oddly the restartable lexer has turned out to be the most frustrating part - selectively diffing parts of two doubly linked lists and snipping them together in the way I ended up having to is one of those things that isn't conceptually very difficult but has the potential for unusually subtle bugs.

systemBuilder 9y ago

Missing important details concerning why LLVM is taking over the world.