Parsing: a timeline

https://jeffreykegler.github.io/personal/timeline_v3

by janvdberg • 8 years ago

326 85 8 years ago

jeffreykegler.github.io

ahazred8ta• 8 years ago

Impressive. Half the breakthroughs involve Chomsky.

bla2• 8 years ago

Probably because the author of this article studied Chomsky a lot and others less.

sp3323• 8 years 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.

carapace2• 8 years ago

Chomsky's Transformational Grammar is part of the origin story of Neuro-Linguistic Programming.

sp3323• 8 years 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

jules2• 8 years ago

Not really, only the definition of context free grammar.

jeffmcmahan6• 8 years ago

"Not really, only the basis of the entire business."

jeffmcmahan6• 8 years 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.

Froyoh2• 8 years ago

And Knuth!

skybrian• 8 years 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

DFHippie2• 8 years ago

Within linguistics there's plenty of politics associated with Chomsky but it's mostly politics within the field, it has nothing to do with politics writ large. He is cited more than any other linguist I expect. I haven't paid attention in about 15 years now, but back in the day there were plenty of linguists who liked his politics plenty but were sore that lines of inquiry they found fruitful -- reasoning about how linguistic form relates to function in particular -- had been banished from the influential journals and conferences by Chomsky and his acolytes. Semantics is plenty formal, by the way. Lambda calculus and other formalisms get lots of print.

iovrthoughtthis• 8 years ago

How have you totally missed GLL and GLR parsing?!

http://dotat.at/tmp/gll.pdf

chubot4• 8 years 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• 8 years 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• 8 years ago

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

swift2• 8 years 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.

eesmith4• 8 years ago

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.

housel• 8 years ago

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.

yongjik• 8 years 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.

DonaldPShimoda3• 8 years 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• 8 years 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

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

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

finnh• 8 years 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• 8 years ago

Thanks for this pointer.

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."

danharaj3• 8 years ago

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

haskellandchill• 8 years ago

I have some older books and heavy papers on the subject. Any recent lightweight treatments you can link to? Thanks.

danharaj3• 8 years 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

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.

chrisaycock• 8 years 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

drfuchs• 8 years ago

Non-paywalled: http://www.antlr.org/papers/allstar-techreport.pdf

Al-Khwarizmi2• 8 years 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.

catpolice4• 8 years 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-Khwarizmi2• 8 years 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.

ulrikrasmussen• 8 years 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/

DonaldPShimoda3• 8 years 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/

[1] Paper: http://matt.might.net/papers/might2011derivatives.pdf

[2] Improvements: https://michaeldadams.org/papers/derivatives2/derivatives2.p...

fithisux• 8 years 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• 8 years 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.

DonaldPShimoda3• 8 years 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.

bgorman• 8 years ago

The author would be wise to look at clojure.spec, a project which has leveraged parsing with derivatives to revolutionize dynamic language data validation.

Froyoh2• 8 years ago

Don Knuth is a genius

kummappp2• 8 years ago

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

majewsky2• 8 years 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.

swift2• 8 years ago

PEG uses ordered choice instead of alternation; all PEGs are thus deterministic. The article's description of PEG is so off-base that it makes me question the entire article.

kummappp2• 8 years ago

How about not making the grammar non deterministic in the first place? I think that 'attractive new syntax' -comment means that there is no usable ports for Marpa. I guess I could try to help with that .. :)

jeffreykegler2• 8 years 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.

klmr4• 8 years ago

The article says that PEG handles non-deterministic grammars by becoming non-deterministic itself.

Wait, where? As noted here, PEGs are certainly deterministic, so I just double-checked the article: it doesn’t claim that PEGs are non-deterministic. In fact, it says that “PEG [is] always linear”, and (way before that), “all non-deterministic parsers can run in worse than quasi-linear time”. So the article indirectly states that PEGs are, in fact, deterministic.

PEG’s problem isn’t non-determinism; it’s PEG’s linear memory requirement in the length of the input (rather than the parse tree depth), as well as the fact that it fails to parse some nondeterministic (but unambiguous) grammars.

jcranmer2• 8 years ago

The PEG aficionados basically believe that PEG is the magical solution to parsing problems: the grammar is by definition deterministic, so that's totally the solution to everything.

The problem is that the problem isn't so much that there can be two parse trees, it's that, as a language author, one needs to be aware of when two parse trees could come up. Precedence and dangling-else are well-known problems where declaring one path to be canonical is obviously the right answer, but most vexing parse is an example where the fact that an ambiguity existed in the first place is the problem, and declaring one to be the "right" way merely makes everyone complain about how it doesn't make sense.

When it comes to dealing with ambiguous grammars, PEG states that there's only one way to read a grammar, so you don't necessarily know that you're obscuring an ambiguity, unlike if you try to build an LR parser.

mncharity3• 8 years ago

PEG aficionados basically believe that PEG is the magical solution to parsing problems

Which can make for fun conversations...

PEG aficionado: [magical solution]

person2: [grammar limitations]

PEG aficionado: Yes, PEGs don't support legacy languages. [emphasis theirs]

person3: By legacy, you mean most all existing programming languages?

PEG aficionado: Yes. [straight face]

majewsky2• 8 years 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.

eesmith4• 8 years ago

The Marpa FAQ at 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 .

mncharity3• 8 years 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/Marp...

haberman• 8 years 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) 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...

xiaq3• 8 years 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.

danharaj3• 8 years ago

You might like this page: http://okmij.org/ftp/continuations/differentiating-parsers.h...

catpolice4• 8 years 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.

xiaq3• 8 years 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.

blake8086• 8 years ago

You will probably be interested in this explanation of how xi-editor does it: https://google.github.io/xi-editor/docs/rope_science_11.html

chubot4• 8 years ago

This feels like it's fairly far removed from practice, but this talk addresses reparsing in an algebraic fashion:

Monoidal Parsing - Ed Kmett

https://www.youtube.com/watch?v=Txf7swrcLYs

nly• 8 years ago

I feel you are right. Most AOT parsing jobs (compiled languages etc.) are well-solved by straightforward, 'inefficient' recursive descent.

Untrusted inputs with complex grammars or realtime parsing like the IDE use-case are vastly more interesting.

Promarged• 8 years ago

I think these issues were directly tackled on by Roslyn team, that wanted something more than just compiler black box (text goes in, machine code goes out). There are some interesting videos on Channel9 about Roslyn internals (sorry no access now ).

systemBuilder• 8 years ago

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

Parsing: a timeline

Related Stories