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.
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.
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.
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.
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 ).
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.
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.
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.
The author would be wise to look at clojure.spec, a project which has leveraged parsing with derivatives to revolutionize dynamic language data validation.
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.
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.
"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."
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.
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].
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.
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 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.
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.
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.
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:
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.)
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.
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:
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.
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.
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.
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.
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.
> 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.
> PEG’s linear memory requirement in the length of the input
What kind of PEG are you talking about? At it's core, PEG is syntax sugar over recursive descent, and has the same memory requirements. Memoization, maybe?
That said, I wouldn't use PEG for anything else than LL(1). Add a second level with precedence climbing, and you're set for a pretty big class of languages.
I’m talking about the Packrat algorithm which, as far as I know, is the only practically used PEG algorithm. The memory requirement comes from the fact that the algorithm handles partial match failures without having to recompute intermediate steps. By comparison, a bog-standard recursive descent parser without memoisation has exponential worst-case runtime [1].
Last time I checked Packrat had nothing to do with memoization. Packrat parsing is the same as precedence climbing, very similar to the shunting yard algorithm, except it leverages the call stack to simplify the code.
And last time I checked, PEG was syntax sugar above recursive descent, just like parser combinators. I implemented¹ the damn thing, so I think I know what I'm talking about. Somewhat. Memoization is just a way to go beyond LL(1), and handle left recursive grammars, it's not not mandatory.
The original Packrat parser explicitly defines it as using memoisation:
> Packrat parsing provides the simplicity, elegance, and generality of the backtracking model, but eliminates the risk of super-linear parse time, by saving all intermediate parsing results as they are computed and ensuring that no result is evaluated more than once.[1]
And just to get a potential misunderstanding out of the way: I’m not claiming that PEGs are formally distinct from recursive descent: According to my understanding (but unlike you I’ve never implemented the packrat algorithm itself … though I’ve written plenty of recursive descent parsers and some PEG-based parsers) there’s a 1:1 correspondence between nonterminals in PEG, and a function in the recursive descent parser. The difference is that one is a formal grammar for describing parsers, while the other is the actual parser implementation.
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.
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 .. :)
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.
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.
Yes, as I said above, politics (re American policy) may have some role, but mostly, he has argued forcefully against a whole range of approaches to studying language. And many people (most prominently those in the Barbara Partee/Montague tradition) don't like that.
Oh, and at last look he was not just the most cited linguist. He was the most cited living human being.
(And FWIW, I came to linguistics from philosophy via formal semantics; I once held negative opinions of Chomsky myself. It took time to see that he was right.)
I wouldn't say that I ever came to the view that his anti-functionalist views were right. In other fields of science, biology, for example, it's taken as given that one can and should reason from function to form and vice versa. I got my PhD and left to program computers, in large part because I'd soured on the politics within the field. I was interested in semantics myself.
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.
"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
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.
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.
"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.
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.
> 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.
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.
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.
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.
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.
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.
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.
> 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.
* 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.